Branch and price algorithm for the stop number minimization problem
TL;DR
This work modeled the SNMP as a Pickup and Delivery Problem on an expanded graph with an ordered structure and solved it via a branch-and-price algorithm, using a labeling algorithm with two distinct dominance rules.
Abstract
The Stop Number Minimization Problem (SNMP), inspired by an autonomous vehicle service from France, arises when a homogeneous fleet of autonomous vehicles transports cargo and personnel across a circuit of stations. The objective is to satisfy all client requests while minimizing the total number of pickup/dropoff stops made by the vehicles, without violating their maximum capacity. We modeled the SNMP as a Pickup and Delivery Problem on an expanded graph with an ordered structure and solved it via a branch-and-price algorithm. The pricing problem was solved using a labeling algorithm with two distinct dominance rules. Additionally, three types of path elimination were introduced in the pricing algorithm. When branching, two strategies were implemented: SOS and Ryan-Foster. We tested our approach in a setting where each vehicle may perform up to 4 laps on the circuit. Computational experiments indicate that this approach solves instances of equivalent size to those tested in previous works in less time. Furthermore, our approach solved instances with up to 80 requests in the single-lap setting, contrasting previous works that solved instances with up to 50 requests.