IDEAS home Printed from https://ideas.repec.org/p/aeg/report/2012-08.html

An adaptive Cooperative Receding Horizon controller for the multivehicle routing problem

Author

Listed:
  • Giorgia Chini

    (Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza")

  • Maria Guido Oddi

    (Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza")

  • Antonio Pietrabissa

    (Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza")

Abstract

The objective of the Vehicle Routing Problem (VRP), in the meaning of this paper, is to find the best path for a vehicle, or the best paths for a fleet of vehicles, with the aim of visiting a set of targets. Possible applications of the vehicle routing problem include surveillance, exploration, logistic,transportation, relief systems, etc. A lot of research has been carried out so far, but the VRP remains a complex and computationally expensive combinatorial problem, leading to the difficulty to actually solve the problem on-line. This paper presents a technique based on the Cooperative Receding Horizon (CRH) approach proposed in [Li06], in which a sequence of optimization problems are computed over a planning horizon and the decisions are applied only over a shorter action horizon, in order to rapidly adapt to possible configuration changes (e.g., new targets appearance). Moreover, the proposed algorithm is able to dynamically adapt to the time-variable configuration of both vehicles and targets as well as to handle the discovery of unknown targets. Several proof of concept simulations show the enhancements of the proposed technique in comparison to the one in [Li06].

Suggested Citation

  • Giorgia Chini & Maria Guido Oddi & Antonio Pietrabissa, 2012. "An adaptive Cooperative Receding Horizon controller for the multivehicle routing problem," DIAG Technical Reports 2012-08, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    • Handle: RePEc:aeg:report:2012-08
    as

    Download full text from publisher

    File URL: http://www.dis.uniroma1.it/~bibdis/RePEc/aeg/report/2012-08.pdf
    File Function: Revised version, 2012
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Gilbert Laporte & François Louveaux & Hélène Mercure, 1992. "The Vehicle Routing Problem with Stochastic Travel Times," Transportation Science, INFORMS, vol. 26(3), pages 161-170, August.
    2. Michel Gendreau & François Guertin & Jean-Yves Potvin & Éric Taillard, 1999. "Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching," Transportation Science, INFORMS, vol. 33(4), pages 381-390, November.
    3. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    4. Moshe Dror & Gilbert Laporte & Pierre Trudeau, 1989. "Vehicle Routing with Stochastic Demands: Properties and Solution Frameworks," Transportation Science, INFORMS, vol. 23(3), pages 166-176, August.
    5. Zhi-Long Chen & Hang Xu, 2006. "Dynamic Column Generation for Dynamic Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 40(1), pages 74-88, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    2. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    3. Dennis Adelhütte & Kristin Braun & Frauke Liers & Sebastian Tschuppik, 2025. "Minimizing delays of patient transports with incomplete information: A modeling approach based on the vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 47(2), pages 565-604, June.
    4. Laporte, Gilbert, 2024. "Fifty years of operational research: 1972–2022," European Journal of Operational Research, Elsevier, vol. 319(2), pages 347-360.
    5. Sheng Liu & Zhixing Luo, 2023. "On-Demand Delivery from Stores: Dynamic Dispatching and Routing with Random Demand," Manufacturing & Service Operations Management, INFORMS, vol. 25(2), pages 595-612, March.
    6. Novoa, Clara & Storer, Robert, 2009. "An approximate dynamic programming approach for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 196(2), pages 509-515, July.
    7. Zhenzhen Zhang & Yu Zhang & Roberto Baldacci, 2024. "Generalized Riskiness Index in Vehicle Routing Under Uncertain Travel Times: Formulations, Properties, and Exact Solution Framework," Transportation Science, INFORMS, vol. 58(4), pages 761-780, July.
    8. Jinil Han & Chungmok Lee & Sungsoo Park, 2014. "A Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times," Transportation Science, INFORMS, vol. 48(3), pages 373-390, August.
    9. Shubhechyya Ghosal & Wolfram Wiesemann, 2020. "The Distributionally Robust Chance-Constrained Vehicle Routing Problem," Operations Research, INFORMS, vol. 68(3), pages 716-732, May.
    10. Prasanna Balaprakash & Mauro Birattari & Thomas Stützle & Marco Dorigo, 2015. "Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers," Computational Optimization and Applications, Springer, vol. 61(2), pages 463-487, June.
    11. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    12. Chen, Lijian & Chiang, Wen-Chyuan & Russell, Robert & Chen, Jun & Sun, Dengfeng, 2018. "The probabilistic vehicle routing problem with service guarantees," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 111(C), pages 149-164.
    13. Hossein Hashemi Doulabi & Gilles Pesant & Louis-Martin Rousseau, 2020. "Vehicle Routing Problems with Synchronized Visits and Stochastic Travel and Service Times: Applications in Healthcare," Transportation Science, INFORMS, vol. 54(4), pages 1053-1072, July.
    14. Karels, Vincent C.G. & Rei, Walter & Veelenturf, Lucas P. & Van Woensel, Tom, 2024. "A vehicle routing problem with multiple service agreements," European Journal of Operational Research, Elsevier, vol. 313(1), pages 129-145.
    15. Marlin W. Ulmer & Leonard Heilig & Stefan Voß, 2017. "On the Value and Challenge of Real-Time Information in Dynamic Dispatching of Service Vehicles," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 59(3), pages 161-171, June.
    16. Abdelkader Sbihi & Richard W. Eglese, 2007. "The Relationship between Vehicle Routing & Scheduling and Green Logistics - A Literature Survey," Working Papers hal-00644133, HAL.
    17. Benjamin Lev, 2009. "Book Reviews," Interfaces, INFORMS, vol. 39(4), pages 375-379, August.
    18. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2006. "Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 40(2), pages 211-225, May.
    19. Schyns, M., 2015. "An ant colony system for responsive dynamic vehicle routing," European Journal of Operational Research, Elsevier, vol. 245(3), pages 704-718.
    20. Salavati-Khoshghalb, Majid & Gendreau, Michel & Jabali, Ola & Rei, Walter, 2019. "An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy," European Journal of Operational Research, Elsevier, vol. 273(1), pages 175-189.

    More about this item

    Keywords

    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:aeg:report:2012-08. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Antonietta Angelica Zucconi The email address of this maintainer does not seem to be valid anymore. Please ask Antonietta Angelica Zucconi to update the entry or send us the correct address (email available below). General contact details of provider: https://edirc.repec.org/data/dirosit.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.