An event-based model for the electric autonomous dial-a-ride problem

Description

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

Period	31 Aug 2023
Event title	International Conference on Operations Research (OR) 2023
Event type	Conference
Location	GermanyShow on map