Fairness and Efficiency in Emerging Vehicle Routing Problems

• Applicant: Dr. Martin Aleksandrov
• Subject Area: Traffic and Transport Systems, Intelligent and Automated Traffic
• Term: since 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 497791398

Let us consider two practical applications of vehicle routing problems (VRPs). As a first application, consider sharing subsidized vehicles (SSVs). In times of COVID- 19, SSVs could help us increase social distancing compared to public transport vehicles. Additionally, an increase in their use could lead to a decrease in the use of commuting private cars and, therefore, their associated CO2 emissions. Also, they could help us decrease the commuting workload in the public transport network. As a second application, consider sharing autonomous vehicles (SAVs). SAVs could make our roads safer because they are likely to prevent deliberate human violations of regulations. Further, they could encourage the mobility of people with impairments or without licenses. Even more, they could potentially remove the responsibility of drivers, expenditures for ownership, and costs for maintenance. In this project, we receive motivation from such applications and propose novel research for emerging VRPs.In particular, the project aims at developing novel fairness and efficiency algorithmics for (shared and/or autonomous) VRPs. For this purpose, it has four main goals: (1) to design new models for VRPs that suit real-world scenarios in our congested cities more appropriately, (2) to give new mechanisms for fairness (e.g. minimising maximum user waiting time) and efficiency (e.g. maximising minimum vehicle sharing rate), (3) to analyse theoretically such mechanisms with various tools for computation, fairness and efficiency, and (4) to evaluate empirically the mechanisms on various VRP benchmarks. For the project, we will adapt to our model common concepts from matching theory (e.g. stability), social choice theory (e.g. price of fairness), computability theory (e.g. Karp-reducibility), economics (e.g. Pareto-optimality), game theory (e.g. Nash equilibria), and behavioral theory (e.g. price of anarchy). From this perspective, the project will pave an interdisciplinary avenue for novel analyses of emerging VRPs by integrating concepts from these theories.

• DFG Programme: Research Grants
• International Connection: Australia, France, Portugal
• Co-Investigators: Professorin Dr. Sabine Ammon; Professor Dr.-Ing. Christoph Benzmüller; Professorin Dr. Natalia Kliewer
• Cooperation Partners: Professor Pedro Barahona; Professor Dr. Phil Kilby; Professor Dr. Jerome Lang