TY - JOUR
T1 - Two-echelon capacitated vehicle routing problem with grouping constraints and simultaneous pickup and delivery
AU - Li, Jiliu
AU - Xu, Min
AU - Sun, Peng
N1 - Funding Information:
The work described in this paper was supported by a grant from National Natural Science Foundation of China (No. 71901189 ) and a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. PolyU 15210620 ). This research was also partially supported by National Natural Science Foundation of China (Grant nos. 71971090 , 71821001 , 7210010522 ). The authors would like to thank the anonymous reviewers and associate editor for their helpful suggestions and very thorough review of the paper. The authors also thank Tian Liu for providing the instances and the corresponding details used in Liu et al. (2018) .
Publisher Copyright:
© 2022 Elsevier Ltd
PY - 2022/8
Y1 - 2022/8
N2 - 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 (2E-VRPG), 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.
AB - 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 (2E-VRPG), 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.
KW - Branch-and-cut-and-price
KW - Grouping constraints
KW - Simultaneous pickup and delivery
KW - Two-echelon vehicle routing
KW - Valid inequalities
UR - http://www.scopus.com/inward/record.url?scp=85132938366&partnerID=8YFLogxK
U2 - 10.1016/j.trb.2022.06.003
DO - 10.1016/j.trb.2022.06.003
M3 - Journal article
AN - SCOPUS:85132938366
SN - 0191-2615
VL - 162
SP - 261
EP - 291
JO - Transportation Research Part B: Methodological
JF - Transportation Research Part B: Methodological
ER -