Abstract
We consider classical vehicle routing problems with customer costs, vehicle feasibilities, driver profits, and driver responsiveness. We motivate a new template for these new problems, which first returns some feasible matching between drivers and customers and then some feasible plan for routing the vehicles through their matched locations. Thus, by using this template, we show that bounded equitability for drivers and Pareto optimality for customers can always be achieved in isolation but not always in combination. Finally, we give fixed-parameter tractable routing algorithms for fleet equitability and fleet efficiency.
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
References
Aleksandrov, M.: Jealousy-freeness and other common properties in fair division of mixed manna. CoRR abs/2004.11469 (2020). https://arxiv.org/abs/2004.11469
Aleksandrov, M.D.: Fleet fairness and fleet efficiency in capacitated pickup and delivery problems. In: Proceedings of the 32nd IEEE Intelligent Vehicles Symposium (IV21), Nagoya, Japan, 11–17 July 2021, pp. 1156–1161. IEEE Xplore, July 2021. https://doi.org/10.1109/IV48863.2021.9576002
Aleksandrov, M.D.: Minimising fleet times in multi-depot pickup and dropoff problems. In: Marreiros, G., Melo, F.S., Lau, N., Lopes Cardoso, H., Reis, L.P. (eds.) EPIA 2021. LNCS (LNAI), vol. 12981, pp. 199–210. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-86230-5_16
Aleksandrov, M.D.: Fairness for drivers with additive profits in emerging vehicle routing problems. Technical report, AAAI Press, March 2022. https://martofena.github.io/fevrps/publications/2022aaai-symp.pdf
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, April 2018. https://ojs.aaai.org/index.php/AAAI/article/view/11298
Brams, S.J., Taylor, A.D.: Fair Division - From Cake-Cutting to Dispute Resolution. Cambridge University Press, Cambridge (1996). https://doi.org/10.1017/CBO9780511598975
Camerer, C.F.: Behavioral Game Theory Experiment in Strategic Interaction, vol. 32. Princeton University Press, Princeton (2003). https://press.princeton.edu/books/hardcover/9780691090399/behavioral-game-theory
Dubins, L.E., Spanier, E.H.: How to cut a cake fairly. Am. Math. Mon. 68(1), 1–17 (1961). https://doi.org/10.2307/2311357
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979). https://dl.acm.org/doi/10.5555/574848
Lesmana, N.S., Zhang, X., Bei, X.: Balancing efficiency and fairness in on-demand ridesourcing, vol. 32, pp. 5309–5319. Curran Associates Inc., Red Hook, December 2019. https://proceedings.neurips.cc/paper/2019/file/3070e6addcd702cb58de5d7897bfdae1-Paper.pdf
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
Llorca, D.F., Gutierrez, E.G.: Trustworthy autonomous vehicles. Technical report, KJ-NA-30942-EN-N (online), EUR 30942 EN, Publications Office of the European Union, Luxembourg, ISBN 978-92-76-46055-8, Luxembourg, December 2021. https://doi.org/10.2760/120385. JRC127051
Männel, D., Bortfeldt, A.: Solving the pickup and delivery problem with three-dimensional loading constraints and reloading ban. Eur. J. Oper. Res. 264(1), 119–137 (2018). https://doi.org/10.1016/j.ejor.2017.05.034
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
Rheingans-Yoo, D., Kominers, S.D., Ma, H., Parkes, D.C.: Ridesharing with driver location preferences. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-2019, pp. 557–564. International Joint Conferences on Artificial Intelligence Organization, July 2019. https://dl.acm.org/doi/abs/10.5555/3367032.3367112
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, August 2013. https://doi.org/10.5555/2540128.2540544
Acknowledgements
Martin Aleksandrov was supported by the DFG Individual Research Grant on “Fairness and Efficiency in Emerging Vehicle Routing Problems” (497791398).
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. (2022). Driver Equitability and Customer Optimality in Intelligent Vehicle Applications. In: Marreiros, G., Martins, B., Paiva, A., Ribeiro, B., Sardinha, A. (eds) Progress in Artificial Intelligence. EPIA 2022. Lecture Notes in Computer Science(), vol 13566. Springer, Cham. https://doi.org/10.1007/978-3-031-16474-3_26
Download citation
DOI: https://doi.org/10.1007/978-3-031-16474-3_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-16473-6
Online ISBN: 978-3-031-16474-3
eBook Packages: Computer ScienceComputer Science (R0)