Path inequalities for the vehicle routing problem with time windows
Abstract
In this paper we introduce a new formulation of the vehicle routing problem with time windows (VRPTW) involving only binary variables. The new formulation is based on the formulation of the asymmetric traveling salesman problem with time windows by Ascheuer et al. (Networks 36 (2000) 69–79) and has the advantage of avoiding additional variables and linking constraints. In the new formulation, time windows are modeled using path inequalities that eliminate time and capacity infeasible paths. We present a new class of strengthened path inequalities based on the polyhedral results obtained by Mak (Ph.D. Thesis, 2001) for a variant of the TSP. We study the VRPTW polytope and determine its dimension. We show that the lifted path inequalities are facet defining under certain assumptions. We also introduce precedence constraints in the context of the VRPTW. Computational experiments are performed with a branch and cut algorithm on the Solomon test problems with wide time windows. Based on results on 25‐node problems, the outcome is promising compared to leading algorithms in the literature. In particular, we report a solution to a previously unsolved 50‐node Solomon test problem R208. The conclusion is therefore that a polyhedral approach to the VRPTW is a viable alternative to the path formulation of Desrochers et al. (Oper Res 40 (1992), 342–354). © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 273–293 2007Keywords
This publication has 16 references indexed in Scilit:
- Lagrangian duality applied to the vehicle routing problem with time windowsComputers & Operations Research, 2006
- A Branch-and-Cut Procedure for the Vehicle Routing Problem with Time WindowsTransportation Science, 2002
- Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cutMathematical Programming, 2001
- A polyhedral study of the asymmetric traveling salesman problem with time windowsNetworks, 2000
- A GRASP for the Vehicle Routing Problem with Time WindowsINFORMS Journal on Computing, 1995
- The precedence-constrained asymmetric traveling salesman polytopeMathematical Programming, 1995
- Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraintsOperations Research Letters, 1991
- Local search in routing problems with time windowsAnnals of Operations Research, 1985
- Integer programming formulations of vehicle routing problemsEuropean Journal of Operational Research, 1985
- Integer Programming Formulation of Traveling Salesman ProblemsJournal of the ACM, 1960