A branch and cut algorithm for the VRP with satellite facilities

Jonathan F. Bard, Liu Huang, Moshe Dror, Patrick Jaillet

Research output: Contribution to journalArticlepeer-review

67 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)821-834
Number of pages14
JournalIIE Transactions (Institute of Industrial Engineers)
Issue number9
StatePublished - Sep 1998

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering


Dive into the research topics of 'A branch and cut algorithm for the VRP with satellite facilities'. Together they form a unique fingerprint.

Cite this