TY - JOUR
T1 - Vehicle routing with split deliveries
AU - Dror, Moshe
AU - Laporte, Gilbert
AU - Trudeau, Pierre
N1 - Funding Information:
The authors are grateful to the Canadian Natural Sciences and Engineering Research Council for its financial support (grants OGP 0036429a nd OGP 0039682). Thanks are also due to Martin Desrochers and to the referees for their helpful suggestions.
PY - 1994/5/20
Y1 - 1994/5/20
N2 - This paper considers a relaxation of the classical vehicle routing problem (VRP), in which split deliveries are allowed. As the classical VRP, this problem is NP-hard, but nonetheless it seems more difficult to solve exactly. It is first formulated as an integer linear program. Several new classes of valid constraints are derived, and a hierarchy between these is established. A constraint relaxation branch and bound algorithm for the problem is then described. Computational results indicate that by using an appropriate combination of constraints, the gap between the lower and upper bounds at the root of the search tree can be reduced considerably. These results also confirm the quality of a previously published heuristic for this problem.
AB - This paper considers a relaxation of the classical vehicle routing problem (VRP), in which split deliveries are allowed. As the classical VRP, this problem is NP-hard, but nonetheless it seems more difficult to solve exactly. It is first formulated as an integer linear program. Several new classes of valid constraints are derived, and a hierarchy between these is established. A constraint relaxation branch and bound algorithm for the problem is then described. Computational results indicate that by using an appropriate combination of constraints, the gap between the lower and upper bounds at the root of the search tree can be reduced considerably. These results also confirm the quality of a previously published heuristic for this problem.
KW - Connectivity constraints
KW - Fractional cycle elimination constraints
KW - Split delivery vehicle routing problem
KW - Subtour elimination constraints
KW - k-split cycles
UR - http://www.scopus.com/inward/record.url?scp=0000855841&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0000855841&partnerID=8YFLogxK
U2 - 10.1016/0166-218X(92)00172-I
DO - 10.1016/0166-218X(92)00172-I
M3 - Article
AN - SCOPUS:0000855841
SN - 0166-218X
VL - 50
SP - 239
EP - 254
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 3
ER -