IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v46y2012i3p359-373.html
   My bibliography  Save this article

Feasibility of the Pickup and Delivery Problem with Fixed Partial Routes: A Complexity Analysis

Author

Listed:
  • Gerardo Berbeglia

    (Melbourne Business School, Carlton, 3053, Australia)

  • Gilles Pesant

    (Département de génie informatique et génie logiciel, École Polytechnique de Montréal, Montréal H3T 2A7, Canada)

  • Louis-Martin Rousseau

    (Département de mathématiques et de génie industriel, École Polytechnique de Montréal, Montréal H3T 2A7, Canada)

Abstract

In the pickup and delivery problem (PDP) a fleet of vehicles must serve customers' requests, which consist of transporting objects from their origins to their destinations. We introduce the PDP with fixed partial routes (PDP-FPR), in which some partial routes are given, and the problem consists in obtaining a solution (a set of routes) that includes those partial routes. We have analyzed the complexity of determining whether or not a feasible solution exists for this problem as well as for some relaxations of it. Checking the feasibility of the PDP-FPR and some of its relaxations is shown to be NP-complete, whereas for other relaxations, the problem was proved to be polynomial-time solvable.

Suggested Citation

  • Gerardo Berbeglia & Gilles Pesant & Louis-Martin Rousseau, 2012. "Feasibility of the Pickup and Delivery Problem with Fixed Partial Routes: A Complexity Analysis," Transportation Science, INFORMS, vol. 46(3), pages 359-373, August.
    • Handle: RePEc:inm:ortrsc:v:46:y:2012:i:3:p:359-373
    DOI: 10.1287/trsc.1110.0394
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1110.0394
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1110.0394?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
    ---><---

    References listed on IDEAS

    as
    1. Gianpaolo Ghiani & Gilbert Laporte & Frédéric Semet, 2006. "The Black and White Traveling Salesman Problem," Operations Research, INFORMS, vol. 54(2), pages 366-378, April.
    2. Mosheiov, Gur, 1994. "The Travelling Salesman Problem with pick-up and delivery," European Journal of Operational Research, Elsevier, vol. 79(2), pages 299-310, December.
    3. Carlo Meloni & Dario Pacciarelli & Marco Pranzo, 2004. "A Rollout Metaheuristic for Job Shop Scheduling Problems," Annals of Operations Research, Springer, vol. 131(1), pages 215-235, October.
    4. 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.
    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. Gerardo Berbeglia & Gilles Pesant & Louis-Martin Rousseau, 2011. "Checking the Feasibility of Dial-a-Ride Instances Using Constraint Programming," Transportation Science, INFORMS, vol. 45(3), pages 399-412, August.
    7. Mascis, Alessandro & Pacciarelli, Dario, 2002. "Job-shop scheduling with blocking and no-wait constraints," European Journal of Operational Research, Elsevier, vol. 143(3), pages 498-517, December.
    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.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Gilbert Laporte, 2016. "Scheduling issues in vehicle routing," Annals of Operations Research, Springer, vol. 236(2), pages 463-474, January.
    2. 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.
    3. Gilbert Laporte, 2016. "Scheduling issues in vehicle routing," Annals of Operations Research, Springer, vol. 236(2), pages 463-474, January.
    4. Wang, Yong & Peng, Shouguo & Zhou, Xuesong & Mahmoudi, Monirehalsadat & Zhen, Lu, 2020. "Green logistics location-routing problem with eco-packages," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).

    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. Roel G. van Anholt & Leandro C. Coelho & Gilbert Laporte & Iris F. A. Vis, 2016. "An Inventory-Routing Problem with Pickups and Deliveries Arising in the Replenishment of Automated Teller Machines," Transportation Science, INFORMS, vol. 50(3), pages 1077-1091, August.
    2. Hernández-Pérez, Hipólito & Salazar-González, Juan-José, 2009. "The multi-commodity one-to-one pickup-and-delivery traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 196(3), pages 987-995, August.
    3. 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.
    4. Salazar-González, Juan-José & Santos-Hernández, Beatriz, 2015. "The split-demand one-commodity pickup-and-delivery travelling salesman problem," Transportation Research Part B: Methodological, Elsevier, vol. 75(C), pages 58-73.
    5. 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.
    6. 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.
    7. 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.
    8. Hoff, Arild & Gribkovskaia, Irina & Laporte, Gilbert & Løkketangen, Arne, 2009. "Lasso solution strategies for the vehicle routing problem with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 192(3), pages 755-766, February.
    9. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    10. 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.
    11. Gábor Nagy & Niaz A. Wassan & M. Grazia Speranza & Claudia Archetti, 2015. "The Vehicle Routing Problem with Divisible Deliveries and Pickups," Transportation Science, INFORMS, vol. 49(2), pages 271-294, May.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. T-S Chang & Y-F Liao, 2011. "Routing strategies for integrating forward distribution and reverse collection," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(6), pages 971-981, June.
    18. Agustín Montero & Juan José Miranda-Bront & Isabel Méndez-Díaz, 2017. "An ILP-based local search procedure for the VRP with pickups and deliveries," Annals of Operations Research, Springer, vol. 259(1), pages 327-350, December.
    19. Yanik, Seda & Bozkaya, Burcin & deKervenoael, Ronan, 2014. "A new VRPPD model and a hybrid heuristic solution approach for e-tailing," European Journal of Operational Research, Elsevier, vol. 236(3), pages 879-890.
    20. Lu, Chung-Cheng & Diabat, Ali & Li, Yi-Ting & Yang, Yu-Min, 2022. "Combined passenger and parcel transportation using a mixed fleet of electric and gasoline vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).

    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:inm:ortrsc:v:46:y:2012:i:3:p:359-373. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.