An event-based model for the electric autonomous dial-a-ride problem
Sprache des Vortragstitels:
Englisch
Original Tagungtitel:
International Conference on Operations Research (OR) 2023
Sprache des Tagungstitel:
Englisch
Original Kurzfassung:
Motivated by rising transportation related problems such as urban traffic congestion and pollution, we discuss the electric autonomous dial-a-ride problem (e-ADARP).
The e-ADARP determines minimum-cost vehicle routes and assigns user requests with specified pick-up and drop-off locations to the vehicles. It is assumed that an electric and
autonomous vehicle fleet is used for the ride-sharing services. The additional battery capacity and omitted maximum route duration constraints make the e-ADARP even more challenging to solve than the
standard dial-a-ride problem (DARP). The weighted sum objective minimizing routing costs and total excess user ride times further complicates the problem. We develop a mixed integer linear programming
model for the e-ADARP based on an event-based graph. The event nodes consist of tuples representing feasible user allocations to a vehicle as well as the current location of the vehicle. Arcs are only introduced
between a pair of event nodes if the corresponding sequence of events is feasible. Our model is based on a recently proposed event-based formulation for the standard DARP from the literature. By using an event-based
graph representation instead of a geographical one, capacity, pairing, and precedence constraints are implicitly applied. To strengthen the model, infeasible path constraints based on the maximum user ride time are
adapted and added to the event-based model. We show that the benchmark instances are solved optimally within similar computation times as current, more sophisticated exact solution methods. Even for larger instances
with up to 8 vehicles and 96 user requests, feasible solutions are obtained. With the additional valid inequalities, the model is able to yield improved feasible solutions for several instances