An Exact Algorithm for Passenger Pickup and Delivery Problem with Modular Vehicles

Abstract

<p>Modular vehicles (MVs) possess the flexibility to decouple and couple modular units en route to form platoons,offering advantages in energy efficiency and cost efficiency. Routing a homogeneous fleet of MVs for the pickupand delivery problem (PDP) for passengers, while considering the decoupling and coupling operations betweenMVs, presents a significant challenge. This is because the resource consumption of a MV on an arc is not onlylinearly related to the distance but also depends on the number of vehicles that choose to pass through the arc(i.e., the platoon size). To address the modular vehicle routing problem (MVRP) for PDP with passenger servicetime windows, we first formulate an arc-flow model to represent MV movement. We acknowledge thatpassenger demand appears over time, thus, a rolling horizon framework is introduced to accommodate thedynamic nature of passenger demands. To solve the static MVRP for each horizon, we propose a novel exactmethod based on a branch-price-and-cut algorithm. Unlike existing branch-price-and-cut algorithms fortraditional vehicle routing problems, the pricing subproblem of the MVRP cannot be solved with an exact routecost for each MV individually, as the arc cost is variable and may be affected by the pricing subproblems ofother MVs. Therefore, we design a new labeling algorithm with tailored dominance rules for the unique pricingsubproblems. We anticipate that the new exact algorithm will be capable of solving the MVRP for small-to-medium-sized datasets within an acceptable computation time for each horizon.<br></p>