The Shortest Path Problem with Time Windows and Linear Waiting Costs

Desaulniers, Guy; Villeneuve, Daniel
August 2000
Transportation Science;Aug2000, Vol. 34 Issue 3, p312
Academic Journal
This paper considers the shortest path problem with waiting costs (SPWC) as an extension to the shortest path problem with time windows. The problem consists of finding the minimum cost path in a network, where cost and time are two independent quantities associated with a path. Path feasibility is constrained by time windows at each node and a linear cost penalty is imposed for each unit of time spent waiting along the path. Starting from a known, nonlinear, integer programming formulation, we propose two alternative formulations for which algorithms already exist. First, we indicate how to transform the SPWC into a shortest path problem with time windows and linear node costs. Second, we prove that the SPWC can also be formulated as a two-resource generalized shortest path problem with resource constraints. Computational results used to compare these alternative formulations are presented.


Related Articles

  • Parallel branch-and-branch algorithms: Survey and synthesis. Gendron, Bernard; Crainic, Teodor Gabriel // Operations Research;Nov/Dec94, Vol. 42 Issue 6, p1042 

    We present a detailed and up-to-date survey of the literature on parallel branch-and-bound algorithms. We synthesize previous work in this area and propose a new classification of parallel branch-and-bound algorithms. This classification is used to analyze the methods proposed in the literature....

  • MINIMUM SPILLAGE SEQUENCING. Tovey, Craig A.; Weiss, Gideon; Wilson, James R. // Management Science;Mar88, Vol. 34 Issue 3, p306 

    The minimum spillage sequencing problem, which arises in real-time satellite signal data processing requires a set of numbers to be arranged so as to minimize the "overflow" of the partial sums above an upper bound. We subject several heuristics to worst-case analysis, average-case analysis, and...

  • Concave Programming Applied to a Special Class of 0-1 Integer Programs. Glover, Fred; Klingman, K. // Operations Research;Jan/Feb73, Vol. 21 Issue 1, p135 

    This paper connects some of the recent developments in concave and integer programming. In particular, it points out parallels between the work of HOANG TUI and R. D. YOUNG. From these methods, a finite algorithm for solving a special class of 0–1 integer programs is developed. Our...

  • ASYMPTOMATIC METHODS IN THE PROBABILISTIC ANALYSES OF SEQUENCING AND PACKING HEURISTICS. Coffman Jr., E.G.; Lueker, G.S.; Kan, A.H.G. Rinnooy // Management Science;Mar88, Vol. 34 Issue 3, p266 

    Recently there has been considerable interest in the average-case performance of heuristics. This paper pursues that interest, where it concerns sequencing and packing problems. In particular, we survey the methods that have been used to obtain formal probabilistic analyses of heuristics for...

  • HEURISTICS BASED ON SPACEFILLING CURVES FOR COMBINATORIAL PROBLEMS IN EUCLIDEAN SPACE. Bartholdi III, John J.; Platzman, Loren K. // Management Science;Mar88, Vol. 34 Issue 3, p291 

    We describe a family of heuristics to solve combinatorial problems such as routing and partitioning. These heuristics exploit geometry but ignore specific distance measures. Consequently they are simple and fast, but nonetheless fairly accurate, and so seem well-suited to operational problems...

  • ON THE UNLIMITED NUMBER OF FACES IN INTEGER HULLS OF LINEAR PROGRAMS WITH A SINGLE CONSTRAINT. Rubin, David S. // Operations Research;Fall70 Supplenment 2, Vol. 18 Issue 5, p940 

    The convex hull of the feasible integer points to a given integer program is a convex polytope I. The feasible set obtained by relaxing the integrality requirements is another convex polytope L. Cutting-plane algorithms essentially try to remove part of L--I. Hence the more complicated the...

  • Enumerative Cuts: I. Burdet, Claude-Alain // Operations Research;Jan/Feb73, Vol. 21 Issue 1, p61 

    This paper presents new types of cutting-plane algorithms for integer-constrained optimization problems. The underlying idea of the method of enumerative cuts is to make use of an enumeration procedure in order to construct cutting planes that can be made arbitrarily deep. In recent...

  • Equivalent Mixed Integer Programming Problems. Bradley, Gordon H. // Operations Research;Jan/Feb73, Vol. 21 Issue 1, p323 

    Every mixed integer programming problem is shown to be equivalent to an infinite number of other mixed integer programming problems. The optimal solution to any problem in a class determines the optimal solution to every other problem in the class. Canonical problems existing in every...

  • A TWO STAGE SOLUTION PROCEDURE FOR THE LOCK BOX LOCATION PROBLEM. Fielitz, Bruce D.; White, Daniel L. // Management Science;Aug1981, Vol. 27 Issue 8, p881 

    New lock box solution techniques have recently been suggested by Stone and Nauss-Markland. This paper briefly discusses these new methodologies and shows how the algorithms can be combined into a third solution procedure which exploits the computational efficiency of the Stone heuristic and...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics