A multi-period dial-a-ride problem with driver consistency

Abstract

Dial-a-ride services are transportation services offered to individual persons requesting transportation between specific origin and destination locations. These services arise in the context of demand responsive transportation and they differ from taxi services by the fact that users may be grouped together in a vehicle. Dial-A-Ride Problems (DARP) are concerned with the design of efficient vehicle routes for performing such dial-a-ride services, using a fleet of vehicles with limited capacity. In the past, these problems have mainly been studied as routing problems with a planning horizon of a single day. However, in many applications of dial-a-ride services, such as the transportation of elderly and disabled people, users may repeatedly have the same transportation requests over a longer period of time. Additionally, these regular users appreciate always being serviced by the same (subset of) driver(s). Service providers may hence improve their service quality by considering driver consistency over a longer planning horizon. This work therefore extends the standard single-day dial-a-ride problem to a general multi-period dial-a-ride problem with driver consistency. A mathematical formulation for the problem is proposed. Small problem instances are solved to optimality using an adapted version of an existing branch-and-cut algorithm. To solve larger instances, a meta-heuristic solution approach is proposed. Preliminary computational results will be discussed.