TY - JOUR

T1 - Multistars, partial multistars and the capacitated vehicle routing problem

AU - Lysgaard, J

AU - Eglese, R W

AU - Letchford, A N

PY - 2002

Y1 - 2002

N2 - In an unpublished paper, Araque, Hall and Magnanti considered polyhedra associated with the Capacitated Vehicle Routing Problem (CVRP) in the special case of unit demands. Among the valid and facet-inducing inequalities presented in that paper were the so-called multistar and partial multistar inequalities, each of which came in several versions. Some related inequalities for the case of general demands have appeared subsequently and the result is a rather bewildering array of apparently different classes of inequalities. The main goal of the present paper is to present two relatively simple procedures that can be used to show the validity of all known (and some new) multistar and partial multistar inequalities, in both the unit and general demand cases. The procedures provide a unifying explanation of the inequalities and, perhaps more importantly, ideas that can be exploited in a cutting plane algorithm for the CVRP. Computational results show that the new inequalities can be useful as cutting planes for certain CVRP instances.

AB - In an unpublished paper, Araque, Hall and Magnanti considered polyhedra associated with the Capacitated Vehicle Routing Problem (CVRP) in the special case of unit demands. Among the valid and facet-inducing inequalities presented in that paper were the so-called multistar and partial multistar inequalities, each of which came in several versions. Some related inequalities for the case of general demands have appeared subsequently and the result is a rather bewildering array of apparently different classes of inequalities. The main goal of the present paper is to present two relatively simple procedures that can be used to show the validity of all known (and some new) multistar and partial multistar inequalities, in both the unit and general demand cases. The procedures provide a unifying explanation of the inequalities and, perhaps more importantly, ideas that can be exploited in a cutting plane algorithm for the CVRP. Computational results show that the new inequalities can be useful as cutting planes for certain CVRP instances.

KW - vehicle routing

KW - valid inequalities

KW - cutting planes

U2 - 10.1007/s10107-002-0336-8

DO - 10.1007/s10107-002-0336-8

M3 - Journal article

VL - 94

SP - 21

EP - 40

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1

ER -