Optimization method to integrate driver consistency and route balancing in a heterogeneous multi-period dial-a-ride problem

Abstract

The classic Dial-A-Ride Problem (DARP) is commonly encountered in door-to-door transportation services catering to elderly or disabled individuals (Cordeau and Laporte (2003)). In the DARP, the goal is to plan a set of routes and associated schedules for a fleet of vehicles in order to fulfill outbound and inbound requests from patients while adhering to various constraints. The objective function of the DARP can vary depending on the specific application, encompassing economic and service-level considerations. The DARP has been extensively studied in the research community for several decades; some notable recent comprehensive surveys on the topic can be found in Ho et al. (2018) and Molenbruch et al. (2017b). The primary objective of the Dial-A-Ride Problem (DARP) is to fulfill the transportation requirements of patients while ensuring their comfort and satisfaction. However, it is equally important to consider the well-being of the drivers who provide these services. To date, no research has focused on investigating the satisfaction of both patients and drivers within the context of the DARP. Specifically, only a few studies have explored the preference of patients to be served by a consistent set of drivers over multiple time periods, known as driver consistency (Braekers and Kovacs (2016)). Additionally, the concept of route balancing, which ensures an equitable distribution of workload among drivers, has not been extensively studied in the existing literature, except in the context of Vehicle Routing Problems (VRPs) (Matl et al. (2018)). This thesis is dedicated to the development and implementation of a Simulated Annealing (SA) algorithm specifically tailored for the Multi-Period Dial-A-Ride Problem (MP-DARP). The primary focus is on minimizing the number of distinct drivers encountered by each patient. As a secondary objective, the algorithm aims to achieve a balanced distribution of workload among drivers. The main goal of this research is to demonstrate the feasibility of simultaneously optimizing patient satisfaction and ensuring fairness among drivers within a unified problem formulation for the MPDARP. The dataset used in this study was initially created by Braekers and Kovacs (2016) and serves as the foundation for the testing and evaluation of the algorithm. The results obtained from this study shed light on the potential advantages of integrating both patient satisfaction and driver fairness in transportation systems. These findings contribute to improving the overall quality of service in the context of DARPs. While further research is needed to explore the potential limitations of the proposed system, this pioneering work reveals new avenues for investigation in the field of DARPs.