A branch and cut algorithm for the VRP with satellite facilities
- 1 September 1998
- journal article
- research article
- Published by Taylor & Francis in IIE Transactions
- Vol. 30 (9) , 821-834
Abstract
An important aspect of the vehicle routing problem (VRP) that has been largely overlooked is the use of satellite facilities to replenish vehicles during a route. When possible, satellite replenishment allows the drivers to continue making deliveries until the close of their shift without necessarily returning to the central depot. This situation arises primarily in the distribution of fuels and certain retail items. When demand is random, optimizing customer routes a priori may result in significant additional costs for a particular realization of demand. Satellite facilities are one way of safeguarding against unexpected demand. This paper presents a branch and cut methodology for solving the VRP with satellite facilities subject to capacity and route time constraints. We begin with a mixed-integer linear programming formulation and then describe a series of valid inequalities that can be used to cut off solutions to the linear programming relaxation. Several separation heuristics are then outlined that are used to generate the cuts. Embedded in the methodology is a VRP heuristic for finding good feasible solutions at each stage of the computations. Results are presented for a set of problems derived from our experience with a leading propane distributor.Keywords
This publication has 14 references indexed in Scilit:
- A Polyhedral Approach to the Asymmetric Traveling Salesman ProblemManagement Science, 1997
- The vehicle routing problem: An overview of exact and approximate algorithmsEuropean Journal of Operational Research, 1992
- A New Optimization Algorithm for the Vehicle Routing Problem with Time WindowsOperations Research, 1992
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman ProblemsSIAM Review, 1991
- An exact algorithm for the asymmetrical capacitated vehicle routing problemNetworks, 1986
- A computational comparison of algorithms for the inventory routing problemAnnals of Operations Research, 1985
- Optimal Routing under Capacity and Distance RestrictionsOperations Research, 1985
- Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxationsMathematical Programming, 1981
- A generalized assignment heuristic for vehicle routingNetworks, 1981
- Networks and vehicle routing for municipal waste collectionNetworks, 1974