IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v300y2022i1p221-236.html
   My bibliography  Save this article

Pickup and delivery problems with autonomous vehicles on rings

Author

Listed:
  • Trotta, Manuel
  • Archetti, Claudia
  • Feillet, Dominique
  • Quilliot, Alain

Abstract

In this paper we introduce a new class of Pickup and Delivery problems on circles (or rings). These problems arise in the field of public transportation systems where autonomous (i.e. driverless) vehicles travel on circular networks. We consider a set of stations arranged in a circle and a set of transportation requests. Each request asks for the transportation of a certain quantity from a pickup station to a delivery station. A fleet of capacitated vehicles is available at the depot. In the first part of the paper we propose a classification scheme for these problems. In the second part, we address the variants in which the vehicles are allowed to move in a single direction of the circle (either clockwise or counterclockwise) and the objective is to minimize the number of tours on the ring while serving all the requests. We provide a complexity analysis for this class of problems. We develop polynomial time algorithms for the variants that are polynomially solvable and proofs of NP-hardness for the variants that are NP-hard. In addition, for the latter, we provide mathematical formulations and perform computational tests that show the effectiveness of these formulations. Finally, we compare optimal solutions with those obtained using a straightforward greedy algorithm.

Suggested Citation

  • Trotta, Manuel & Archetti, Claudia & Feillet, Dominique & Quilliot, Alain, 2022. "Pickup and delivery problems with autonomous vehicles on rings," European Journal of Operational Research, Elsevier, vol. 300(1), pages 221-236.
    • Handle: RePEc:eee:ejores:v:300:y:2022:i:1:p:221-236
    DOI: 10.1016/j.ejor.2021.07.050
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721006603
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.07.050?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Fabio Antonialli, 2019. "International benchmark on experimentations with Autonomous Shuttles for Collective Transport," Post-Print hal-02489797, HAL.
    2. Flavia Bonomo & Guillermo Durán & Javier Marenco, 2009. "Exploring the complexity boundary between coloring and list-coloring," Annals of Operations Research, Springer, vol. 169(1), pages 3-16, July.
    3. Berbeglia, Gerardo & Cordeau, Jean-François & Laporte, Gilbert, 2010. "Dynamic pickup and delivery problems," European Journal of Operational Research, Elsevier, vol. 202(1), pages 8-15, April.
    4. Fabio Antonialli, 2019. "International benchmark on experimentations with autonomous shuttle for collective transport," Post-Print halshs-02487530, HAL.
    5. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Rejoinder on: Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 45-47, July.
    6. Ho, Sin C. & Szeto, W.Y. & Kuo, Yong-Hong & Leung, Janny M.Y. & Petering, Matthew & Tou, Terence W.H., 2018. "A survey of dial-a-ride problems: Literature review and recent developments," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 395-421.
    7. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 1-31, July.
    8. Jean-François Cordeau & Gilbert Laporte, 2007. "The dial-a-ride problem: models and algorithms," Annals of Operations Research, Springer, vol. 153(1), pages 29-46, September.
    9. Yves Molenbruch & Kris Braekers & An Caris, 2017. "Typology and literature review for dial-a-ride problems," Annals of Operations Research, Springer, vol. 259(1), pages 295-325, December.
    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. Sharif Azadeh, Sh. & Atasoy, Bilge & Ben-Akiva, Moshe E. & Bierlaire, M. & Maknoon, M.Y., 2022. "Choice-driven dial-a-ride problem for demand responsive mobility service," Transportation Research Part B: Methodological, Elsevier, vol. 161(C), pages 128-149.
    2. Behrend, Moritz & Meisel, Frank & Fagerholt, Kjetil & Andersson, Henrik, 2019. "An exact solution method for the capacitated item-sharing and crowdshipping problem," European Journal of Operational Research, Elsevier, vol. 279(2), pages 589-604.
    3. Capelle, Thomas & Cortés, Cristián E. & Gendreau, Michel & Rey, Pablo A. & Rousseau, Louis-Martin, 2019. "A column generation approach for location-routing problems with pickup and delivery," European Journal of Operational Research, Elsevier, vol. 272(1), pages 121-131.
    4. Regnier-Coudert, Olivier & McCall, John & Ayodele, Mayowa & Anderson, Steven, 2016. "Truck and trailer scheduling in a real world, dynamic and heterogeneous context," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 389-408.
    5. Agatz, Niels & Erera, Alan & Savelsbergh, Martin & Wang, Xing, 2012. "Optimization for dynamic ride-sharing: A review," European Journal of Operational Research, Elsevier, vol. 223(2), pages 295-303.
    6. Ritzinger, Ulrike & Puchinger, Jakob & Rudloff, Christian & Hartl, Richard F., 2022. "Comparison of anticipatory algorithms for a dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 301(2), pages 591-608.
    7. Lahyani, Rahma & Khemakhem, Mahdi & Semet, Frédéric, 2015. "Rich vehicle routing problems: From a taxonomy to a definition," European Journal of Operational Research, Elsevier, vol. 241(1), pages 1-14.
    8. Kishore Bhoopalam, A. & Agatz, N.A.H. & Zuidwijk, R.A., 2017. "Planning of Truck Platoons: a Literature Review and Directions for Future Research," ERIM Report Series Research in Management ERS-2017-010-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    9. Tafreshian, Amirmahdi & Abdolmaleki, Mojtaba & Masoud, Neda & Wang, Huizhu, 2021. "Proactive shuttle dispatching in large-scale dynamic dial-a-ride systems," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 227-259.
    10. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    11. MELIS, Lissa & SÖRENSEN, Kenneth, 2021. "The real-time on-demand bus routing problem: What is the cost of dynamic requests?," Working Papers 2021003, University of Antwerp, Faculty of Business and Economics.
    12. Mohammad Torkjazi & Nathan Huynh, 2019. "Effectiveness of Dynamic Insertion Scheduling Strategy for Demand-Responsive Paratransit Vehicles Using Agent-Based Simulation," Sustainability, MDPI, vol. 11(19), pages 1-12, September.
    13. Lian, Ying & Lucas, Flavien & Sörensen, Kenneth, 2024. "Prepositioning can improve the performance of a dynamic stochastic on-demand public bus system," European Journal of Operational Research, Elsevier, vol. 312(1), pages 338-356.
    14. John Lees-Miller, 2016. "Minimising average passenger waiting time in personal rapid transit systems," Annals of Operations Research, Springer, vol. 236(2), pages 405-424, January.
    15. Sophie N. Parragh & Jorge Pinho de Sousa & Bernardo Almada-Lobo, 2015. "The Dial-a-Ride Problem with Split Requests and Profits," Transportation Science, INFORMS, vol. 49(2), pages 311-334, May.
    16. Gupta, Diwakar & Chen, Hao-Wei & Miller, Lisa A. & Surya, Fajarrani, 2010. "Improving the efficiency of demand-responsive paratransit services," Transportation Research Part A: Policy and Practice, Elsevier, vol. 44(4), pages 201-217, May.
    17. Qiu, Xiaoqiu & Feuerriegel, Stefan & Neumann, Dirk, 2017. "Making the most of fleets: A profit-maximizing multi-vehicle pickup and delivery selection problem," European Journal of Operational Research, Elsevier, vol. 259(1), pages 155-168.
    18. Zhu, Lin & Sheu, Jiuh-Biing, 2018. "Failure-specific cooperative recourse strategy for simultaneous pickup and delivery problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 271(3), pages 896-912.
    19. Mina Roohnavazfar & Seyed Hamid Reza Pasandideh, 2022. "Decomposition algorithm for the multi-trip single vehicle routing problem with AND-type precedence constraints," Operational Research, Springer, vol. 22(4), pages 4253-4285, September.
    20. Arslan, A.M. & Agatz, N.A.H. & Kroon, L.G. & Zuidwijk, R.A., 2016. "Crowdsourced Delivery: A Dynamic Pickup and Delivery Problem with Ad-hoc Drivers," ERIM Report Series Research in Management ERS-2016-003-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.

    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:eee:ejores:v:300:y:2022:i:1:p:221-236. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.