Highlights Differences between the pickup and delivery scenarios are discussed in detail. The practical constraints imposed by the pickup operations are presented. Pickup capacitated vehicle routing problem with three-dimensional loading constraints (3L-PCVRP) is introduced. A model of 3L-PCVRP, which can be easily converted to a model of 3L-CVRP, is proposed. Improved algorithms, including an improved tree search algorithm (TRSA) and an improved greedy heuristic algorithm (GHA), are developed to investigate the loading feasibility of the routes. The algorithms demonstrate an overall improvement in efficiency and effectiveness. An improved branch-and-price-based algorithm is developed to solve 3L-PCVRP. A label-correcting-based algorithm (LCA) is developed for efficient route generation. By employing a two-stage method to call the improved TRSA and the improved GHA at different frequencies, the efficiency and effectiveness of the LCA are enhanced.

    Abstract 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 3L-PCVRP 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 two-stage 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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:
    Chi, Jushang (author) / He, Shiwei (author)


    Publication date :

    2023-06-10




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English