Skip to main content
SpringerLink
Log in

Fleet management for autonomous vehicles using flows in time-expanded networks

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

VIPAFLEET is a framework to manage a fleet of Individual public autonomous vehicles (VIPA). 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). We treat in this paper the pickup and delivery problem related to the taxi mode by means of flows in time-expanded networks. This enables us to compute optimal offline solutions, to propose strategies for the online situation, and to evaluate their performance in comparison with the optimal offline solution.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

Notes

  1. Note that a request \(r_j\) with \(z_j > Cap\) can be replaced by \(\lceil \frac{z_j}{Cap} \rceil \) many requests \(r_j'\) respecting the constraint \(z_j' \le Cap\).

  2. Note that a tour may be empty, i.e., \(\varGamma ^i = (v_0 , 0), (v_0 , T)\), when VIPA i is not used but stays in the depot.

References

  • Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, Upper Saddle River, New Jersey. ISBN 0-13-617549-X

  • Ascheuer N, Krumke SO, Rambau J (1998) The online transportation problem: competitive scheduling of elevators. ZIB

  • Ascheuer N, Krumke SO, Rambau J (2000) Online dial-a-ride problems: minimizing the completion time. In: STACS 2000. Springer, pp 639–650

  • Ausiello G, Feuerstein E, Leonardi S, Stougie L, Talamo M (1995) Competitive algorithms for the on-line traveling salesman. In: Workshop on algorithms and data structures. Springer, pp 206–217

  • Ausiello G, Feuerstein E, Leonardi S, Stougie L, Talamo M (2001) Algorithms for the on-line travelling salesman 1. Algorithmica 29(4):560–581

    Article  Google Scholar 

  • Berbeglia G, Cordeau JF, Laporte G (2010) Dynamic pickup and delivery problems. Eur J Oper Res 202(1):8–15

    Article  Google Scholar 

  • Boland N, Hewitt M, Marshall L, Savelsbergh M (2017) The continuous-time service network design problem. Oper Res 65:1303–1321

    Article  Google Scholar 

  • Borodin A, El-Yaniv R (2005) Online computation and competitive analysis. Cambridge University Press, Cambridge

    Google Scholar 

  • Bsaybes S (2017) Modèles et algorithmes de gestion de flottes de véhicules vipa. Ph.D. thesis, Université Clermont Auvergne

  • Bsaybes S, Quilliot A, Wagler AK (2017) Fleet management for autonomous vehicles using flows in time-expanded networks. Electron Notes Discrete Math (Special Issue of LAGOS 2017) 62:255–260

    Article  Google Scholar 

  • Bsaybes S, Quilliot A, Wagler AK (2018a) Fleet management for autonomous vehicles: online PDP under special constraints. RAIRO Oper Res. https://doi.org/10.1051/ro/2018042

    Google Scholar 

  • Bsaybes S, Quilliot A, Wagler AK (2018b) Fleet management for autonomous vehicles using multicommodity coupled flows in time-expanded networks. In: D’Angelo G (ed) 17th International symposium on experimental algorithms (SEA 2018), Leibniz international proceedings in informatics (LIPIcs). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, vol 103, pp 25:1–25:14. https://doi.org/10.4230/LIPIcs.SEA.2018.25

  • Cordeau JF, Laporte G (2007) The dial-a-ride problem: models and algorithms. Ann Oper Res 153(1):29–46

    Article  Google Scholar 

  • Deleplanque S, Quilliot A (2013) Transfers in the on-demand transportation: the DARPT Dial-a-Ride Problem with transfers allowed. In: Multidisciplinary international scheduling conference: theory and applications (MISTA), pp 185–205

  • Dragomir AG, Nicola D, Soriano A, Gansterer M (2018) Multidepot pickup and delivery problems in multiple regions: a typology and integrated model. Int Trans Oper Res 25(2):569–5971

    Article  Google Scholar 

  • Eglese RB, Zambirinis S (2018) Disruption management in vehicle routing and scheduling for road freight transport: a review. TOP 26:1

    Article  Google Scholar 

  • Fabri A, Recht P (2007) Online dial-a-ride problem with time windows: an exact algorithm using status vectors. In: Operations research proceedings 2006. Springer, pp 445–450

  • Ford LR Jr, Fulkerson DR (1958) Constructing maximal dynamic flows from static flows. Oper Res 6(3):419–433

    Article  Google Scholar 

  • Groß M, Skutella M (2011) Generalized maximum flows over time. In: International workshop on approximation and online algorithms. Springer, pp 247–260

  • Grötschel M, Krumke SO, Rambau J (2013) Online optimization of large scale systems. Springer, New York

    Google Scholar 

  • http://www.viameca.fr: Viaméca (2015) http://www.viameca.fr/

  • Kliewer N, Mellouli T, Suhl L (2006) A time-space network based exact optimization model for multi-depot bus scheduling. Eur J Oper Res 175(3):1616–1627

    Article  Google Scholar 

  • Koch R, Nasrabadi E, Skutella M (2011) Continuous and discrete flows over time. Math Methods Oper Res 73(3):301

    Article  Google Scholar 

  • Lenstra JK, Kan A (1981) Complexity of vehicle routing and scheduling problems. Networks 11(2):221–227

    Article  Google Scholar 

  • Lucas K, Roosen P (2010) Emergence, analysis and evolution of structures: concepts and strategies across disciplines. Springer, Berlin

    Book  Google Scholar 

  • Munari P, Morabito RVP (2018) A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen. TOP 26:437

    Article  Google Scholar 

  • Royer E, Bom J, Dhome M, Thuilot B, Lhuillier M, Marmoiton F (2005) Outdoor autonomous navigation using monocular vision. In: Intelligent robots and systems (IROS 2005). IEEE, pp 1253–1258

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

  • Yang J, Jaillet P, Mahmassani H (2004) Real-time multivehicle truckload pickup and delivery problems. Transp Sci 38(2):135–148

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Université Grenoble Alpes, Grenoble INP, G-SCOP, Grenoble, France

    Sahar Bsaybes

  2. Université Clermont Auvergne (LIMOS UMR CNRS 6158), Clermont-Ferrand, France

    Alain Quilliot & Annegret K. Wagler

Authors
  1. Sahar Bsaybes
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alain Quilliot
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Annegret K. Wagler
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Annegret K. Wagler.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work was founded by the French National Research Agency, the European Commission (Feder funds) and the Région Auvergne in the framework of the excellence cluster LabEx IMobS3.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bsaybes, S., Quilliot, A. & Wagler, A.K. Fleet management for autonomous vehicles using flows in time-expanded networks. TOP 27, 288–311 (2019). https://doi.org/10.1007/s11750-019-00506-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-019-00506-4

Keywords

Search

Navigation