Abstract
We look at the dial-a-ride problem through the lens of mechanism design, where the goal is to design mechanisms, toward natural objectives, in strategic settings, where customers act rationally. For this problem, we consider customer preferences for detour times and waiting times of services, as well as mechanisms for minimising the detour times, waiting times, and detour plus waiting times of customers on vehicles. We characterise mechanisms that are economically efficient and game-theoretically truthful. With detour-time preferences, we show that there are mechanisms that are both efficient and truthful in all instances. With waiting-time preferences, we show that there are mechanisms that are efficient but not truthful in some instances.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Change history
22 January 2023
In the originally published version of chapter 48, Table 1 and the equation on page 696 contained errors. This has been corrected.
References
Afrati, F., Cosmadakis, S., Papadimitriou, C.H., Papageorgiou, G., Papakostantinou, N.: The complexity of the travelling repairman problem. RAIRO Theor. Inform. Appl. Inform. Théorique et Appl. 20(1), 79–87 (1986). http://www.numdam.org/item/ITA_1986__20_1_79_0/
Aleksandrov, M.D.: Fleet fairness and fleet efficiency in capacitated pickup and delivery problems. In: Proceedings of the 32nd IEEE Intelligent Vehicles Symposium (IV21), 11–17. Nagoya, Japan, pp. 1156–1161. IEEE Xplore (2021). https://doi.org/10.1109/IV48863.2021.9576002
Araque G, J.R., Kudva, G., Morin, T.L., Pekny, J.F.: A branch-and-cut algorithm for vehicle routing problems. Ann. Oper. Res. 50(1), 37–59 (1994). https://doi.org/10.1007/BF02085634
Bei, X., Zhang, S.: Algorithms for trip-vehicle assignment in ride-sharing. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32, no. 1 (2018). https://ojs.aaai.org/index.php/AAAI/article/view/11298
Cordeau, J.F., Laporte, G.: The dial-a-ride problem (DARP): models and algorithms. Ann. Oper. Res. 153, 29–46 (2007). https://doi.org/10.1007/s10479-007-0170-8
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6, 80–91 (1959). https://doi.org/10.1287/mnsc.6.1.80
Gschwind, T., Drexl, M.: Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem. Transp. Sci. 53, 480–491 (2019). https://doi.org/10.1287/trsc.2018.0837
Li, B., Krushinsky, D., Reijers, H.A., Woensel, T.V.: The share-a-ride problem: people and parcels sharing taxis. Eur. J. Oper. Res. 238(1), 31–40 (2014). https://doi.org/10.1016/j.ejor.2014.03.003
Liu, M., Brynjolfsson, E., Dowlatabadi, J.: Do digital platforms reduce moral hazard? The case of uber and taxis. Manage. Sci. 67(8), 4665–4685 (2021). https://doi.org/10.1287/mnsc.2020.3721
Matl, P., Hartl, R.F., Vidal, T.: Workload equity in vehicle routing problems: a survey and analysis. Transp Sci. 52(2), 239–260 (2018). https://doi.org/10.1287/trsc.2017.0744
Nucamendi, S., Cardona-Valdes, Y., Angel-Bello Acosta, F.: Minimizing customers’ waiting time in a vehicle routing problem with unit demands. J. Comput. Syst. Sci. Int. 54(6), 866–881 (2015). https://doi.org/10.1134/S1064230715040024
Paquette, J., Bellavance, F., Cordeau, J.F., Laporte, G.: Measuring quality of service in dial-a-ride operations: the case of a Canadian city. Transportation 39(3), 539–564 (2012). https://doi.org/10.1007/s11116-011-9375-4
Pareto, V.: Cours d’économie politique. Œuvres complètes publiées sous la direction de giovanni busino. tomes 1 et 2 en un volume (1897). https://doi.org/10.3917/droz.paret.1964.01, 9782600040143
Santos, D.O., Xavier, E.C.: Dynamic taxi and ridesharing: a framework and heuristics for the optimization problem. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence IJCAI 2013, pp. 2885–2891. AAAI Press (2013). https://dl.acm.org/doi/10.5555/2540128.2540544
Vidal, T., Laporte, G., Matl, P.: A concise guide to existing and emerging vehicle routing problem variants. Eur. J. Oper. Res. 286(2), 401–416 (2020). https://doi.org/10.1016/j.ejor.2019.10.010
Zhang, M.: Mechanism design in facility location games. In: Proceedings of the 20th International AAMAS Conference, pp. 1850–1852. AAMAS 2021, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC (2021). https://dl.acm.org/doi/10.5555/3463952.3464262
Acknowledgements
Martin Aleksandrov was supported by the DFG Individual Research Grant on “Fairness and Efficiency in Emerging Vehicle Routing Problems” (497791398). Martin Aleksandrov thanks Prof. Christoph Benzmüller for their brief feedback on the motivation. We thank the reviewers for their valuable and constructive comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Aleksandrov, M., Kilby, P. (2022). Efficiency and Truthfulness in Dial-a-Ride Problems with Customers Location Preferences. In: Aziz, H., Corrêa, D., French, T. (eds) AI 2022: Advances in Artificial Intelligence. AI 2022. Lecture Notes in Computer Science(), vol 13728. Springer, Cham. https://doi.org/10.1007/978-3-031-22695-3_48
Download citation
DOI: https://doi.org/10.1007/978-3-031-22695-3_48
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22694-6
Online ISBN: 978-3-031-22695-3
eBook Packages: Computer ScienceComputer Science (R0)