Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows

Ropke, Stefan; Cordeau, Jean-François
August 2009
Transportation Science;Aug2009, Vol. 43 Issue 3, p267
Academic Journal
In the pickup and delivery problem with time windows vehicle routes must be designed to satisfy a set of transportation requests, each involving a pickup and delivery location, under capacity, time window, and precedence constraints. This paper introduces a new branch-and-cut-and-price algorithm in which lower bounds are computed by solving through column generation the linear programming relaxation of a set partitioning formulation. Two pricing subproblems are considered in the column generation algorithm: an elementary and nonelementary shortest path problem. Valid inequalities are added dynamically to strengthen the relaxations. Some of the previously proposed inequalities for the pickup and delivery problem with time windows are also shown to be implied by the set partitioning formulation. Computational experiments indicate that the proposed algorithm outperforms a recent branch-and-cut algorithm.


Related Articles

  • Augmented Reality Internet Labs versus its Traditional and Virtual Equivalence. Odeh, Salaheddin; Abu Shanab, Shatha; Anabtawi, Mahasen // International Journal of Emerging Technologies in Learning;2015, Vol. 10 Issue 3, p4 

    Engineering is an applied science; it makes science come alive through experiments and labs. Students can only gain practical knowledge that goes beyond mere scientific theory in the educational labs. This can be done using three different types of educational labs: Augmented reality labs,...

  • A Dual-Bounded Algorithm for the p-Median Problem. Galv�o, Roberto O. // Operations Research;Sep/Oct80, Vol. 28 Issue 5, p1112 

    The p-median problem consists of locating p facilities on a network, so that the sum of shortest distances from each of the nodes of the network to its nearest facility is minimized. A dual bound, based on the dual of the LP relaxation of the integer programming formulation of the problem, is...

  • A Branch and Bound Algorithm to Minimize Total Weighted Tardiness on a Single Processor. Babu, Pascal; Peridy, Laurent; Pinson, Eric // Annals of Operations Research;Jul2004, Vol. 129 Issue 1-4, p33 

    In this paper, we consider the problem of minimizing the total weighted tardiness of a set of jobs processed on a single processor. First, a lower bound based on a Lagrangian decomposition is presented. The particularity of this decomposition, based on a 0–1 time indexed formulation, is...

  • Sufficient Optimality Criterion for Linearly Constrained, Separable Concave Minimization Problems. Illés, T.; Nagy, Á B. // Journal of Optimization Theory & Applications;Jun2005, Vol. 125 Issue 3, p559 

    A sufficient optimality criterion for linearly-constrained concave minimization problems is given in this paper. Our optimally criterion is based on the sensitivity analysis of the relaxed linear programming Problem. The main result is similar to that of Phillips and Rosen (Ref. 1); however, our...

  • A NEW BRANCH-AND-BOUND ALGORITHM FOR THE FIXED-CHARGE TRANSPORTATION PROBLEM. Kennington, Jeff; Unger, Ed // Management Science;Jun76, Vol. 22 Issue 10, p1116 

    A new branch-and-bound procedure specialized for the fixed-charge transportation problem has been developed. The technique strongly exploits the underlying transportation structure. The relaxed problem assumes this form and simple penalties are easily constructed from the optimal solution of...

  • Multi-Way Distance Join Queries in Spatial Databases. Corral, Antonio; Manolopoulos, Yannis; Theodoridis, Yannis; Vassilakopoulos, Michael // GeoInformatica;Dec2004, Vol. 8 Issue 4, p373 

    Let a tuple of n objects obeying a query graph (QG) be called the n-tuple. The �D_distance-value� of this n-tuple is the value of a linear function of distances of the n objects that make up this n-tuple, according to the edges of the QG. This paper addresses the problem of finding the...

  • Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine. Vickson, R. G. // Operations Research;Sep/Oct80, Vol. 28 Issue 5, p1155 

    This paper treats the problem of minimizing the total weighted flow cost plus job-processing cost in a single machine sequencing problem for jobs having processing costs which are linear functions of processing times. The optimal job sequence and processing times are obtainable from the solution...

  • MINIMIZING THE SUM OF THE JOB COMPLETION TIMES IN THE TWO-MACHINE FLOW SHOP BY LAGRANGIAN RELAXATION. van de Velde, S. L. // Annals of Operations Research;1990, Vol. 26 Issue 1-4, p257 

    A branch-and-bound algorithm is presented for the two-machine flow shop problem with the objective of minimizing the sum of the job completion times. Lower bounds and precedence constraints result from a Lagrangian relaxation of this problem. The Lagrangian subproblem turns out to be a linear...

  • Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methods. Fernández, José; Tóth, Boglárka // Computational Optimization & Applications;Apr2009, Vol. 42 Issue 3, p393 

    Obtaining a complete description of the efficient set of multiobjective optimization problems can be of invaluable help to the decision-maker when the objectives conflict and a solution has to be chosen. In this paper we present an interval branch-and-bound algorithm which aims at obtaining a...

  • BRANCH-AND-BOUND AS A HIGHER-ORDER FUNCTION. Mckeown, G. P.; Rayward-Smith, V. J.; Turpin, H. J. // Annals of Operations Research;1991, Vol. 33 Issue 1-4, p379 

    The branch-and-bound paradigm is presented as a higher-order function and illustrated by instantiations, providing two well-known branch-and-bound algorithms for the Steiner tree problem in graphs and one for the travelling salesman problem. We discuss the advantages of such a specification 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