Multiagent approaches for the allocation of routes to a fleet of autonomous taxis

Multiagent approaches for the allocation of routes to a fleet of autonomous taxis

Gauthier Picard Flavien Balbo Olivier Boissier  

Univ Lyon, MINES Saint-Étienne, CNRS, Laboratoire Hubert Curien UMR 5516 Saint-Étienne, France

Corresponding Author Email: 
{gauthier.picard,flavien.balbo,olivier.boissier}@emse.fr
Page: 
223-247
|
DOI: 
https://doi.org/10.3166/RIA.32.223-247
Received: 
|
Accepted: 
|
Published: 
30 April 2018
| Citation

OPEN ACCESS

Abstract: 

This work is interested in decentrally solving a taxi allocation problem over a fleet of autonomous taxis. Classically, to solve this problem, requests are centralized into a portal where a dispatcher allocates requests to taxis (ideally, in an optimal manner). This requires taxis have continuous access to the portal. However, getting access to such global communication infrastructureis very expensive for taxi companies. The idea here is to use new affordable vehicle-to-vehicle communication technologies to coordinate taxis without global communication infrastructure. Our approach is presented and empirically evaluated via simulations. We have developed different scenarios with different communication infrastructure and coordination mechanisms, and we analyze, their resulting quality of service, user welfare, gain and robustness to message loss.  

Keywords: 

resource allocation, autonomous taxis, DCOP

1. Introduction
2. Problème d’allocation de taxi (TSAP)
3. Modèle multiagent
4. Évaluations
5. Travaux liés
6. Conclusions
Remerciements
  References

Alshamsi A., Abdallah S., Rahwan I. (2009). Multiagent self-organization for a taxi dispatch system. In 8th international conference on autonomous agents and multiagent systems, p. 21–28. 

Cerquides J., Farinelli A., Meseguer P., Ramchurn S. D. (2014). A tutorial on optimization for multi-agent systems. The Computer Journal, vol. 57, no 6, p. 799–824. http://dx.doi.org/10.1093/comjnl/bxt146 

Egan M., Jakob M. (2016). Market mechanism design for profitable on-demand transport services. Transportation Research Part B: Methodological, vol. 89, p. 178–195. 

Glaschenko A., Ivaschenko A., Rzevski G., Skobelev P. (2009). Multi-agent real time scheduling system for taxi companies. In 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), Budapest, Hungary, p. 29–36. Consulté sur https:// pdfs.semanticscholar.org/dc25/22cfba5bd99e107c93feb4d75d593327a753.pdf 

Grau J. M. S., Romeu M. A. E. (2015). Agent based modelling for simulating taxi services. Procedia Computer Science, vol. 52, p. 902–907. 

Horn M. E. (2002). Fleet scheduling and dispatching for demand-responsive passenger services. Transportation Research Part C: Emerging Technologies, vol. 10, no 1, p. 35–63. 

Jin X., Jie L. (2012). A study of multi-agent based model for urban intelligent transport systems. International Journal of Advancements in Computing Technology, vol. 4, no 6, p. 126–134. 

Maciejewski M., Nagel K. (2013). The influence of multi-agent cooperation on the efficiency of taxi dispatching. In International conference on parallel processing and applied mathematics, p. 751–760. 

Pujol-Gonzalez M., Cerquides J., Farinelli A., Meseguer P., Rodriguez-Aguilar J. A. (2015). Efficient inter-team task allocation in robocup rescue. In Proceedings of the 2015 international conference on autonomous agents and multiagent systems, p. 413–421. Richland, SC, International Foundation for Autonomous Agents and Multiagent Systems. Consulté sur http://dl.acm.org/citation.cfm?id=2772879.2772933 

Pujol-Gonzalez M., Cerquides J., Meseguer P., Rodríguez-Aguilar J. A., Tambe M. (2013). Engineering the decentralized coordination of uavs with limited communication range. In 15th conference of the spanish association for artificial intelligence, caepia 2013, p. 199– 208. Springer. Consulté sur http://dx.doi.org/10.1007/978-3-642-40643-0_21 

Santani D., Balan R. K., Woodard C. J. (2008). Spatio-temporal efficiency in a taxi dispatch system. In 6th international conference on mobile systems, applications, and services, mobisys. 

Seow K. T., Dang N. H., Lee D.-H. (2010). A collaborative multiagent taxi-dispatch system. IEEE Transactions on Automation Science and Engineering, vol. 7, no 3, p. 607–616. 

Shen W., Lopes C. (2015). Managing autonomous mobility on demand systems for better passenger experience. In International conference on principles and practice of multi-agent systems, p. 20–35. 

Zargayouna M., Balbo F., Ndiaye K. (2016). Generic model for resource allocation in transportation. application to urban parking management. Transportation Research Part C: Emerging Technologies, vol. 71, p. 538–554.