Search

Disasters such as earthquake or tsunami can easily take the lives of thousands of people and millions worth of property in a fleeting moment. A successful emergency evacuation plan is critical in response to disasters. In this paper, we seek to investigate the multi-source, multi-destination evacuation problem. First, we construct a mixed integer linear programming model. Second, based on K shortest paths and user equilibrium, we propose a novel algorithm (hereafter KPUE), whose complexity is polynomial in the numbers of nodes and evacuees. Finally, we demonstrate the effectiveness of algorithm KPUE by a real evacuation network in Shanghai, China. The numerical examples show that the average computation time of the proposed algorithm is 95% less than that of IBM ILOG CPLEX solver and the optimality gap is no more than 5%.

In several multiobjective decision problems Pairwise Comparison Matrices (PCM) are applied to evaluate the decision variants. The problem that arises very often is the inconsistency of a given PCM. In such a situation it is important to approximate the PCM with a consistent one. One of the approaches is to minimize the distance between the matrices, most often the Euclidean distance. In the paper we consider the problem of minimizing the maximum distance. After applying the logarithmic transformation we are able to formulate the obtained subproblem as a Shortest Path Problem and solve it more efficiently. We analyze the structure of the set of optimal solutions and prove some of its properties. This allows us to provide an iterative algorithm that results in a unique, Pareto-efficient solution.

Network routing problems are often modeled with the assumption that the network structure is deterministic, though they are often subject to uncertainty in many real-life scenarios. In this paper, we study the traveling salesman and the shortest path problems with uncertain topologies modeled by arc failures. We present the formulations that incorporate chance constraints to ensure reliability of the selected route considering all arc failure scenarios. Due to the computational complexity and large scales of these stochastic network optimization problems, we consider two cutting plane methods and a Benders decomposition algorithm to respectively solve them. We also consider to solve the reformulations of the problems obtained by taking the logarithm transformation of the chance constraints. Numerical experiments are performed to obtain results for comparisons among these proposed methods.

We consider the one-warehouse multi-retailer problem (OWMR) and perform both theoretical and computational studies of different formulations for the problem. Several formulations that were not yet directly applied to the OWMR are considered, namely an echelon stock formulation strengthened with valid inequalities, a two-level lot-sizing based formulation strengthened with valid inequalities, a multicommodity formulation and a dynamic programming based formulation. These are also compared with a strengthened echelon stock formulation and the previously best performing formulations available in the literature, a transportation and a shortest path formulations, which were studied in a previous work (Solyali and Sural in Ann Oper Res 196(1):517–541, 2012). The formulations were ordered according to the provided linear relaxation bounds, assuming there is no available stock at the beginning of the planning horizon. Experimental results using a commercial MIP solver indicate that a partial version of the two-level lot-sizing based formulation strengthened with valid inequalities and the multicommodity formulation outperform the others, especially as the sizes of the instances become larger. Besides, these two new best performing formulations allow the solver to prove optimality of instances for which not even the linear relaxation could be solved using the previously best performing formulations.

Given a graph G(N,A) with a cost (or benefit) and a delay on each arc, the constrained routing problem (CRP) aims to find a minimum-cost or a maximum-benefit path from a given source to a given destination node, subject to an end-to-end delay constraint. The problem (with a single constraint) is NP-hard, and has been studied by many researchers who found fully polynomial approximation schemes (FPAS) for this problem. The current paper focuses on a generalized CRP version, CRP with hop-wise constraints (CRPH). In the generalized version, instead of one constraint there are up to n−1 special-type constraints, where n is the number of nodes. An FPAS based on interval partitioning is proposed for both the minimization and the maximization versions of CRPH. For G(N,A) with n nodes and m arcs, the complexity of the algorithm is O(mn 2/e).

A minimum cost shortest-path tree is a tree that connects the source with every node of the network by a shortest path such that the sum of the cost (as a proxy for length) of all arcs is minimum.

We consider the one-warehouse multi-retailer problem where a warehouse replenishes multiple retailers with deterministic dynamic demands over a horizon. The problem is to determine when and how much to order to the warehouse and retailers such that the total system-wide costs are minimized. We propose a new (combined transportation and shortest path based) integer programming reformulation for the problem in addition to the echelon stock and transportation based formulations in the literature. We analyze the strength of the LP relaxations of three formulations and show that the new formulation is stronger than others. We also show that the new and transportation based formulations are equivalent for the joint replenishment problem, where the warehouse is a crossdocking facility. We extend all formulations to the case with initial inventory at the warehouse and reveal the relation among their LP relaxations. We present our computational experiments with all formulations over a set of randomly generated test instances.

In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogota’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine.

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nl) respectively, where n is the number of vertices of the grid and l is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.

International audience; This paper is devoted to the search of robust solutions in finite graphs when costs depend on scenarios. We first point out similarities between robust optimization and multiobjective optimization. Then, we present axiomatic requirements for preference compatibility with the intuitive idea of robustness in a multiple scenarios decision context. This leads us to propose the Lorenz dominance rule as a basis for robustness analysis. Then, after presenting complexity results about the determination of Lorenz optima, we show how the search can be embedded in algorithms designed to enumerate k best solutions. Then, we apply it in order to enumerate Lorenz optimal spanning trees and paths. We investigate possible refinements of Lorenz dominance and we propose an axiomatic justification of OWA operators in this context. Finally, the results of numerical experiments on randomly generated graphs are provided. They show the numerical efficiency of the suggested approach.

Modern communication networks often use Internet Protocol routing and the intra- domain protocol OSPF (Open Shortest Path First). The routers in such a network calculate the shortest path to each destination and send the traffic on these paths, using load balancing. The issue of survivability, i.e. the question of how much traffic the network will be able to accommodate if components fail, is increasingly important. We consider the problem of designing a survivable IP network, which also requires determining the routing of the traffic. This is done by choosing the weights used for the shortest path calculations.

Computing shortest paths with two or more conflicting optimization criteria is a fundamental problem in transportation and logistics. We study the problem of finding all Pareto-optimal solutions for the multi-criteria single-source shortest-path problem with nonnegative edge lengths. The standard approaches are generalizations of label-setting (Dijkstra) and label-correcting algorithms, in which the distance labels are multi-dimensional and more than one distance label is maintained for each node. The crucial parameter for the run time and space consumption is the total number of Pareto optima. In general, this value can be exponentially large in the input size. However, in various practical applications one can observe that the input data has certain characteristics, which may lead to a much smaller number—small enough to make the problem efficiently tractable from a practical viewpoint. For typical characteristics which occur in various applications we study in this paper whether we can bound the size of the Pareto set to a polynomial size or not. These characteristics are also evaluated (1) on a concrete application scenario (computing the set of best train connections in view of travel time, fare, and number of train changes) and (2) on a simplified randomized model. It will turn out that the number of Pareto optima on each visited node is restricted by a small constant in our concrete application, and that the size of the Pareto set is much smaller than our worst case bounds in the randomized model.

This paper determines the optimal location of K connections in the plane, where a connection links pairs of existing facilities. Both uncapacitated and capacitated versions of the problem are considered. Discretization results for general polyhedral gauges and other properties are established. Two heuristic algorithms are developed for each case using the concept of a shortest path flow set coupled with a sequential location and allocation approach. Computational results show that the algorithms are efficient and accurate.

Constraint programming based column generation is a hybrid optimization framework recently proposed (Junker et al., 1999) that uses constraint programming to solve column generation subproblems. In the past, this framework has been used to solve scheduling problems where the associated graph is naturally acyclic and has done so very efficiently. This paper attempts to solve problems whose graph is cyclic by nature, such as routing problems, by solving the elementary shortest path problem with constraint programming. We also introduce new redundant constraints which can be useful in the general framework. The experimental results are comparable to those of the similar method in the literature (Desrochers, Desrosiers, and Solomon, 1992) but the proposed method yields a much more flexible approach.

Scheduling of staff is an important area, both from an academic and industrial point of view. There has been a lot of attention to develop new and efficient methods and models. In this paper, we consider the problem that given a work-force demand, a set of working rules and regulations find schedules for staff members with individual skills and preferences. The planning horizon is typically one week to several months. The problem both constructs tasks and simultaneously allocates them to staff members. The purpose of this paper is not to develop new theoretical results. Instead it deals with novel applications of known approaches to real-world practice. We describe a general scheduling software called SCHEDULER that includes a number of important features. The model is based on a elastic set-partitioning model and as solution method we use a branch-and-price algorithm. As branching strategy we make use of constraint branching and the column generator is a nested constrained shortest path formulation. An important feature is that only legal schedules are generated and used within the model. The system also allows for task changes within shifts, a general description of legal restrictions, preferences and allowable times. The system is in use at a number of companies and we report on the usage at some companies. We also give some numerical results to illustrate the behavior of some important features.

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines. The aim of the article is to develop a Lagrangian heuristic to obtain good solutions to this problem and good lower bounds to certify the quality of solutions. Based on a strong reformulation of the problem as a shortest path problem, the Lagrangian relaxation is applied to the demand constraints (flow constraint) and the relaxed problem is decomposed per period and per machine. The subgradient optimization method is used to update the Lagrangian multipliers. A primal heuristic, based on transfers of production, is designed to generate feasible solutions (upper bounds). Computational results using data from the literature are presented and show that our method is efficient, produces lower bounds of good quality and competitive upper bounds, when compared with the bounds produced by another method from the literature and by high-performance MIP software.

We consider the n‐city traveling salesman problem (TSP), symmetric or asymmetric,with the following attributes. In one case, a positive integer k and an ordering (1,..., n) ofthe cities is given, and an optimal tour is sought subject to the condition that for any pairi, j ∈ (1..., n), if j ≥ i + k, then i precedes j in the tour. In another case, position i in the tourhas to be assigned to some city within k positions from i in the above ordering. This case isclosely related to the TSP with time windows. In a third case, an optimal tour visiting m outof n cities is sought subject to constraints of the above two types. This is a special case ofthe Prize Collecting TSP (PCTSP). In any of the three cases, k may be replaced by city‐specificintegers k(i), i = 1,..., n. These problems arise in practice. For each class, we reducethe problem to that of finding a shortest source‐sink path in a layered network with a numberof arcs linear in n and exponential in the parameter k (which is independent of the problemsize). Besides providing linear time algorithms for the solution of these problems, the reductionto a shortest path problem also provides a compact linear programming formulation.Finally, for TSPs or PCTSPs that do not have the required attributes, these algorithms canbe used as heuristics that find in linear time a local optimum over an exponential‐sizeneighborhood.

The growing interest in computer graphics and Geographical Information Systems has made it necessary to develop efficient data structures and algorithmic procedures for handling graphical information in real-time. In this paper, we consider the problem of storage and manipulation of large-scale networks which can undergo dynamic changes. Two complementary data structures are presented: a topological and a topographical representa-tion. The objective is to support both graph-theoretic and geometric operations efficiently. A topological representation facilitates the implementation of graph-theoretic optimization algorithms such as the shortest path and spanning tree problems. In this context, a new dynamic forward star structure is developed and contrasted with the classic (static) forward star representation of sparse graphs. Algorithmic procedures and complexity analysis for network editing operations of this structure are provided. A topographical representation is necessary for geometric operations such as nearest neighbour location and range retrieval. Algorithms for performing editing and geometric operations on the BD-tree are presented. Finally, the practical efficiency of the data structures is investigated by computational experiments on large-scale road networks.

In physical VLSI design, network design (wiring) is the most time-consuming phase. For solving global wiring problems, we propose to first compute from the layout geometry a graph that preserves all shortest paths between pairs of relevant points, and then to operate on that graph for computing shortest paths, Steiner minimal tree approximations, or the like. For a set of points and a set of simple orthogonal polygons as obstacles in the plane, withn input points (polygon corner or other) altogether, we show how a shortest paths preserving graph of sizeO(n logn) can be computed in timeO(n logn) in the worst case, with spaceO(n). We illustrate the merits of this approach with a simple example: If the length of a longest edge in the graph is bounded by a polynomial inn, an assumption that is clearly fulfilled for graphs derived from VLSI layout geometries, then a shortest path can be computed in timeO(n logn log logn) in the worst case; this result improves on the known best one ofO(n(logn)3/2).

Dynamic programming formulations of optimization problems often call for the computation of shortest paths in networks derived from recurrence relations. These derived networks tend to be very large, but they are also very regular and lend themselves to the computation of nontrivial lower bounds on path lengths. In this tutorial paper, we describe unidirectional and bidirectional search procedures that make use of bounding information in computing shortest paths. When applied to many optimization problems, these shortest path algorithms capture the advantages of both dynamic programming and branch-and-bound.

We propose an algorithm to compute the optimum departure time and path for a commuter in a congested network. Constant costs for use of arcs, cost functions of travel time depending on exogenous congestion and schedule delay are taken into account. A best path for a given departure time is computed with a previous algorithm for the generalized shortest path problem. The globally optimal departure time and an optimal path are determined by adapting Piyavskii's algorithm to the case of one-sided Lipschitz functions.

The multi-item capacitated lot-sizing problem consists of determining the magnitude and the timing of some operations of durable results for several items in a finite number of processing periods so as to satisfy a known demand in each period. We show that the problem is strongly NP-hard. To explain why one of the most popular among exact and approximate solution methods uses a Lagrangian relaxation of the capacity constraints, we compare this approach with every alternate relaxation of the classical formulation of the problem, to show that it is the most precise in a rigorous sense. The linear relaxation of a shortest path formulation of the same problem has the same value, and one of its Lagrangian relaxations is even more accurate. It is comforting to note that well-known relaxation algorithms based on the traditional formulation can be directly used to solve the shortest path formulation efficiently, and can be further enhanced by new algorithms for the uncapacitated lot-sizing problem. An extensive computational comparison between linear programming, column generation and subgradient optimization exhibits this efficiency, with a surprisingly good performance of column generation. We pinpoint the importance of the data characteristics for an empirical classification of problem difficulty and show that most real-world problems are easier to solve than their randomly generated counterparts because of the presence of initial inventories and their large number of items.

The quasi-assignment problem can be used to solve the bus scheduling problem, the tourist guide problem, and the minimum number of chains in a partially ordered set. A successive shortest path algorithm for the assignment problem is extended to the quasiassignment problem. The algorithm is a variation of the primal-dual algorithm, and its computational complexity isO(n3).

In this paper, we examine the problems of finding thek-shortest paths, thek-shortest paths without repeated nodes, and the shortest path with a single side constraint between an origin and destination pair. Distances are assumed to be non-negative, but networks may be either directed or undirected. Two versions of algorithms for all these problems are compared. The computational results show that, in each case, the advantage of the adaptive version (as measured by total number of permanent labels) grows with the problem size.

This paper develops a polynomial-time algorithm that reconstructs a shortest path between two vertices using only the all pairs shortest path distance matrix. For graphs with positive edge weights, the algorithm requiresO(⦹V|log|V|) time. When the graph contains both positive and negative, but not zero, edge weights, and all cycles have positive length, the algorithm runs inO(|V|2) time. The remarkable feature about the algorithm is that it does not require explicit information about edges in the original graph.

A broad class of problems involving the optimal control of robot arms can be formulated as dynamic programming problems whose structure is particularly attractive for parallel processing. For certain simple cost functions the dynamic programming formulation reduces to determining the shortest path through a network. This algorithm has been implemented on a Floating Point Systems' T-20 hypercube computer. An analysis of the performance of the algorithm provides several important insights into the interplay between problem size and the number of processors in a parallel computer. The results also underscore the potential for parallel computers in real-time control applications.

Theshortest path problem is considered from a computational point of view. Eight algorithms which solve theshortest path tree problem on directed graphs are presented, together with the results of wide-ranging experimentation designed to compare their relative performances on different graph topologies. The focus of this paper is on the implementation of the different data structures used in the algorithms. A "Pidgin Pascal" description of the algorithms is given, containing enough details to allow for almost direct implementation in any programming language. In addition, Fortran codes of the algorithms and of the graph generators used in the experimentation are provided on the diskette.

This paper concerns the problem of locating a central facility on a connected networkN. The network,N, could be representative of a transport system, while the central facility takes the form of a connected subgraph ofN. The problem is to locate a central facility of minimum length so that each of several demand points onN is covered by the central facility: a demand point atv i inN is covered by the central facility if the shortest path distance betweenv i and the closest point in the central facility does not exceed a parameterr i . This location problem is NP-hard, but for certain special cases, efficient solution methods are available.