期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 266, 期 2, 页码 487-497出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2017.10.017
关键词
Cutting; Branch and cut; Polyhedral combinatorics; Two-echelon vehicle routing
资金
- National Natural Science Foundation of China [71501091, 71571077, 71571094]
- Huazhong University of Science and Technology [5001300001]
- Guangdong Natural Science Funds for Distinguished Young Scholar [2015A030306007]
- NRF Singapore [NRF-RSS2016-004]
- Singapore MOE-AcRF-Tier 1 [R-266-000-096-133, R-266-000-096-731]
In this paper, we present a branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints (2E-CVRPGC), which is a new problem deriving from the classical two-echelon capacitated vehicle routing problem (2E-CVRP) by considering grouping constraints in the second echelon. Customers in the 2E-CVRPGC are divided into several disjoint groups, and the grouping constraints ensure that customers from the same group are served by vehicles from the same satellite. We formulate the problem as a mixed 0-1 linear program and propose five families of valid inequalities to strengthen the model. Based on the model and the inequalities, we implement a branch-and-cut algorithm to solve the problem. The proposed branch-and-cut algorithm was evaluated on two classes of randomly generated instances. The computational results show that the five families of valid inequalities can substantially improve the lower bounds yielded by the LP relaxation of the model, and the branch-and-cut algorithm can solve more instances to optimality than CPLEX. We also conduct additional experiments to analyze the impacts of the grouping constraints on the problem, and illustrate the differences between the 2E-CVRPGC and the 2E-CVRP. (C) 2017 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据