Pick-Up and Delivery Problem for Sequentially Consolidated Urban Transportation with Mixed and Multi-Pupropse Vehicle Fleet

Different urban transportation flows (e.g., passenger journeys, freight distribution, and waste management) are conventionally separately handled by corresponding single-purpose vehicles (SVs). The multi-purpose vehicle (MV) is a novel vehicle concept that can enable the sequential sharing of different transportation flows by changing the so-called modules, thus theoretically improving the efficiency of urban transportation through the utilization of higher vehicles. In this study, a variant of the pick-up and delivery problem with time windows is established to describe the sequential sharing problem considering both MVs and SVs with features of multiple depots, partial recharging strategies, and fleet sizing. MVs can change their load modules to carry all item types that can also be carried by SVs. To solve the routing problem, an adaptive large neighborhood search (ALNS) algorithm is developed with new problem-specific heuristics. The proposed ALNS is tested on 15 small-size cases and evaluated using a commercial MIP solver. Results show that the proposed algorithm is time-efficient and able to generate robust and high-quality solutions. We investigate the performance of the ALNS algorithm by analyzing convergence and selection probabilities of the heuristic solution that destroy and repair operators. On 15 large-size instances, we compare results for pure SV, pure MV, and mixed fleets, showing that the introduction of MVs can allow smaller fleet sizes while approximately keeping the same total travel distance as for pure SVs.

Automated summary

This study introduces a variant of the pick-up and delivery problem with features like multiple depots, partial recharging strategies, and fleet sizing, considering both multi-purpose vehicles (MV) and single-purpose vehicles (SV). By developing an adaptive large neighborhood search (ALNS) algorithm with problem-specific heuristics, the efficiency of urban transportation is improved, as shown by time-efficient and robust high-quality solutions in testing. The study compares results for pure SV, pure MV, and mixed fleets, demonstrating that the introduction of MVs can lead to smaller fleet sizes while maintaining similar total travel distances as pure SVs.