Pickup capacitated vehicle routing problem with three-dimensional loading constraints: Model and algorithms

作     者：Chi, Jushang He, Shiwei 

作者机构：Beijing Jiaotong Univ Key Lab Transport Ind Big Data Applicat Technol Co Beijing Peoples R China 

出 版 物：《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》 (运输研究E部分：后勤学与运输评论)

年 卷 期：2023年第176卷第1期

核心收录：

学科分类：0201[经济学-理论经济学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0814[工学-土木工程] 0823[工学-交通运输工程] 

基　　金：Fundamental Research Funds for the Central Universities (Science and technology leading talent team project) National Natural Science Foundation of China [K2022X015] Research Project of China Railway Corporation 2022JBQY006 

主　　题：Three-dimensional loading Routing Pickup operation Loading algorithm Branch-and-price algorithm 

摘      要：This study addresses the pickup capacitated vehicle routing problem with three-dimensional loading constraints (3L-PCVRP), which combined the container loading problem (CLP) and the capacitated vehicle routing problem (CVRP). A mixed-integer linear programming model for 3LPCVRP is designed with the objective of minimizing the total transportation cost. The basic constraints of CLP and CVRP as well as the practical constraints imposed by the pickup operations are incorporated in 3L-PCVRP. An improved branch-and-price-based (B & P) algorithm is proposed to solve 3L-PCVRP. The 3L-PCVRP model is decomposed into the restricted master problem (RMP) for selecting routes and the subproblem (SP) for generating routes that satisfy the loading and routing constraints. A label-correcting-based algorithm (LCA) is presented to solve the SP, which employs a two-stage method and two enhanced loading algorithms to ensure the loading feasibility of the routes. The two loading algorithms (tree search and greedy heuristic algorithms) are improved by a new evaluation function and an improved space-merging method. The twostage method is designed to call the two loading algorithms at different frequencies to investigate the route feasibility accurately and efficiently. Numerical experiments are designed to test the performance of the proposed algorithms. The efficiency and effectiveness of the improved loading algorithms are demonstrated in hundreds randomly generated instances. For small-scale 3L-PCVRP instances, the B & P algorithm can generate solutions that are not worse than those of the solver within 0.14% of the solver s running time. The efficiency and effectiveness of the improved B & P algorithm are also validated in large-scale benchmark instances.