Fleet management for autonomous vehicles: Online PDP under special constraints
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 3, pp. 1007-1031.

The VIPAFLEET project consists in developing models and algorithms for managing a fleet of Individual Public Autonomous Vehicles (VIPA). Hereby, we consider a fleet of cars distributed at specified stations in an industrial area to supply internal transportation, where the cars can be used in different modes of circulation (tram mode, elevator mode, taxi mode). One goal is to develop and implement suitable algorithms for each mode in order to satisfy all the requests under an economic point of view by minimizing the total tour length. The innovative idea and challenge of the project is to develop and install a dynamic fleet management system that allows the operator to switch between the different modes within the different periods of the day according to the dynamic transportation demands of the users. We model the underlying online transportation system and propose a corresponding fleet management framework, to handle modes, demands and commands. We consider two modes of circulation, tram and elevator mode, propose for each mode appropriate online algorithms and evaluate their performance, both in terms of competitive analysis and practical behavior.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2018042
Classification : 90C27, 05C21
Mots-clés : Fleet management, Online transportation problem, autonomous vehicles, competitive analysis
Bsaybes, Sahar 1 ; Quilliot, Alain 1 ; Wagler, Annegret K. 1

1 
@article{RO_2019__53_3_1007_0,
     author = {Bsaybes, Sahar and Quilliot, Alain and Wagler, Annegret K.},
     title = {Fleet management for autonomous vehicles: {Online} {PDP} under special constraints},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1007--1031},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {3},
     year = {2019},
     doi = {10.1051/ro/2018042},
     zbl = {1423.90211},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2018042/}
}
TY  - JOUR
AU  - Bsaybes, Sahar
AU  - Quilliot, Alain
AU  - Wagler, Annegret K.
TI  - Fleet management for autonomous vehicles: Online PDP under special constraints
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 1007
EP  - 1031
VL  - 53
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2018042/
DO  - 10.1051/ro/2018042
LA  - en
ID  - RO_2019__53_3_1007_0
ER  - 
%0 Journal Article
%A Bsaybes, Sahar
%A Quilliot, Alain
%A Wagler, Annegret K.
%T Fleet management for autonomous vehicles: Online PDP under special constraints
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 1007-1031
%V 53
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2018042/
%R 10.1051/ro/2018042
%G en
%F RO_2019__53_3_1007_0
Bsaybes, Sahar; Quilliot, Alain; Wagler, Annegret K. Fleet management for autonomous vehicles: Online PDP under special constraints. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 3, pp. 1007-1031. doi : 10.1051/ro/2018042. http://www.numdam.org/articles/10.1051/ro/2018042/

R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network flows: theory, algorithms, and applications. In: Prentice-Hall, Englewood Cliffs, New Jersey, USA Arrow, KJ (1963). Social Choice and Individual Values, Wiley, New York. Gibbard, A.(1973). Manipulation of Voting Schemes: A general result, Econometrica. 41 (1993) 587–602. | Zbl

N. Ascheuer, S.O. Krumke and J. Rambau, Online dial-a-ride problems: minimizing the completion time. In: STACS 2000. Springer (2000) 639–650. | Zbl

G. Berbeglia, J.-F. Cordeau and G. Laporte, Dynamic pickup and delivery problems. Eur. J. Oper. Res. 202 (2010) 8–15. | Zbl

M. Blom, S.O. Krumke, W.E. De Paepe and L. Stougie, The online TSP against fair adversaries. INFORMS J. Comput. 13 (2001) 138–148. | Zbl

A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (2005). | Zbl

J.-F. Cordeau and G. Laporte, The dial-a-ride problem: models and algorithms. Ann. Oper. Res. 153 (2007) 29–46. | Zbl

S. Deleplanque and A. Quilliot, Transfers in the on-demand transportation: the DARPT Dial-a-Ride Problem with transfers allowed. Multi. Int. Scheduling Conf. Theory Appl. (MISTA) 2013 (2013) 185–205.

Easymile, available at: http://www.easymile.com (2015).

A. Fabri and P. Recht, Online dial-a-ride problem with time windows: an exact algorithm using status vectors. In: Operations Research Proceedings 2006. Springer (2007), 445–450. | Zbl

N. Labadi, C. Prins and M. Reghioui, A memetic algorithm for the vehicle routing problem with time windows. RAIRO: OR 42 (2008) 415–431. | Zbl

Ligier group, available at: http://www.ligier.fr (2015).

S. Olariu, An optimal greedy heuristic to color interval graphs. Info. Process. Lett. 37 (1991) 21–25. | Zbl

E. Royer, J. Bom, M. Dhome, B. Thuilot, M. Lhuillier and F. Marmoiton, Outdoor autonomous navigation using monocular vision, In: 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2005 (IROS 2005). IEEE (2005) 1253–1258.

E. Royer, F. Marmoiton, S. Alizon, D. Ramadasan, M. Slade, A. Nizard, M. Dhome, B. Thuilot and F. Bonjean, Retour d’expérience aprés plus de 1000 km en navette sans conducteur guidée par vision. RFIA2016 (2016).

E.L. Solano-Charris, C. Prins and A. Cynthia Santos, Solving the bi-objective robust vehicle routing problem with uncertain costs and demands. RAIRO: OR 50 (2016) 689–714. | Zbl

É.D. Taillard, A heuristic column generation method for the heterogeneous fleet vrp. RAIRO: OR 33 (1999) 1–14. | Zbl

Viaméca, available at: http://www.viameca.fr (2015).

Z. Yan, Simulator for vipafleet management, Master thesis, ISIMA Institut Supérieur d’Informatique de Modélisation et de leurs Applications, Clermont Ferrand, France (2016).

Cité par Sources :