A branch and cut algorithm for the VRP with satellite facilities
作者:
JONATHANF. BARD,
LIU HUANG,
MOSHE DROR,
PATRICK JAILLET,
期刊:
IIE Transactions
(Taylor Available online 1998)
卷期:
Volume 30,
issue 9
页码: 821-834
ISSN:0740-817X
年代: 1998
DOI:10.1080/07408179808966528
出版商: Taylor & Francis Group
数据来源: Taylor
摘要:
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.
点击下载:
PDF (1703KB)
返 回