期刊
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL
卷 162, 期 -, 页码 261-291出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.trb.2022.06.003
关键词
Two-echelon vehicle routing; Grouping constraints; Simultaneous pickup and delivery; Valid inequalities; Branch-and-cut-and-price
类别
资金
- National Natural Science Foundation of China [71971090, 71821001, 7210010522]
- Research Grants Council of the Hong Kong Special Administrative Region, China [15210620]
This paper investigates a new variant of the two-echelon capacitated vehicle routing problem (2E-VRP) called the two-echelon capacitated vehicle routing problem with grouping constraints and simultaneous pickup and delivery (2E-VRPGS). A tailored branch-and-cut-and-price algorithm is developed to solve this problem and two related variants. Extensive numerical experiments show the efficacy of the algorithm and its competitiveness with existing algorithms.
This paper investigates the two-echelon capacitated vehicle routing problem with grouping constraints and simultaneous pickup and delivery (2E-VRPGS), which is a new variant of the classical two-echelon capacitated vehicle routing problem (2E-VRP). In the 2E-VRPGS, customers from the same administrative region are served by vehicles from the same satellite so as to ensure service consistency, with pickup and delivery being performed simultaneously in the second echelon. To solve this problem to optimality, we formulate it as a path-based model and develop a tailored branch-and-cut-and-price algorithm, which can also exactly solve two closely related variants of 2E-VRPGS in the literature: the 2E-VRP with grouping constraints (2EVRPG), and the 2E-VRP with simultaneous pickup and delivery (2E-VRPS). In particular, a novel dominance rule in the labeling algorithm, together with several customized valid inequalities, has been put forward to effectively accelerate the solution method by exploiting the problem characteristics. To evaluate the efficacy of the proposed algorithm on the problems 2E-VRPG, 2E-VRPS, and 2E-VRPGS, extensive numerical experiments have been conducted on three types of benchmark instances. Computational results on the 2E-VRPGS show that our dominance rule can significantly reduce the number of generated labels and all families of valid inequalities have a great impact on strengthening the path-based model. The algorithm is found to be highly competitive when compared with the existing exact algorithm for the 2E-VRPG and some new findings and managerial insights are derived from sensitivity analysis.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据