Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows
Top Cited Papers
- 1 August 2009
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 43 (3), 267-286
- https://doi.org/10.1287/trsc.1090.0272
Abstract
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.Keywords
This publication has 31 references indexed in Scilit:
- Tabu Search, Partial Elementarity, and Generalized k-Path Inequalities for the Vehicle Routing Problem with Time WindowsTransportation Science, 2008
- An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cutsMathematical Programming, 2007
- A Branch-and-Cut Algorithm for the Dial-a-Ride ProblemOperations Research, 2006
- A Branch-and-Price Approach to the Vehicle Routing Problem with Simultaneous Distribution and CollectionTransportation Science, 2006
- Accelerated label setting algorithms for the elementary resource constrained shortest path problemOperations Research Letters, 2006
- Branch-and-Price: Column Generation for Solving Huge Integer ProgramsOperations Research, 1998
- A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling ProblemsPublished by Springer Science and Business Media LLC ,1998
- The precedence-constrained asymmetric traveling salesman polytopeMathematical Programming, 1995
- A New Optimization Algorithm for the Vehicle Routing Problem with Time WindowsOperations Research, 1992
- A Dynamic Programming Solution of the Large-Scale Single-Vehicle Dial-A-Ride Problem with Time WindowsAmerican Journal of Mathematical and Management Sciences, 1986