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

An Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem

Author

Listed:
  • Quan Lu

    (Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089-0193)

  • Maged Dessouky

    (Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089-0193)

Abstract

We consider the multiple vehicle pickup and delivery problem (MVPDP) with the objective of minimizing the total travel cost and the fixed vehicle cost. Most of the optimization-based approaches for solving the MVPDP are developed for a restrictive hard time window or tight capacity environment that depend significantly on the reduction of the feasible solution space. We develop an alternative optimization solution approach for the MVPDP that does not require these constraints to be tight. The problem is formulated as a 0–1 integer-programming problem. A branch-and-cut algorithm is developed to optimally solve the problem. Four classes of valid inequalities for the MVPDP are proposed. By using the proposed solution approach, we were able to optimally solve problem instances of up to 5 vehicles and 17 customers on problems without clusters and up to 5 vehicles and 25 customers on problems with clusters within a stopping criterion of three CPU hours on a SUN Fire 4800 server.

Suggested Citation

  • Quan Lu & Maged Dessouky, 2004. "An Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 38(4), pages 503-514, November.
    • Handle: RePEc:inm:ortrsc:v:38:y:2004:i:4:p:503-514
    DOI: 10.1287/trsc.1030.0040
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1030.0040
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1030.0040?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. Harilaos N. Psaraftis, 1980. "A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem," Transportation Science, INFORMS, vol. 14(2), pages 130-154, May.
    2. Dumas, Yvan & Desrosiers, Jacques & Soumis, Francois, 1991. "The pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 54(1), pages 7-22, September.
    3. Kalantari, Bahman & Hill, Arthur V. & Arora, Sant R., 1985. "An algorithm for the traveling salesman problem with pickup and delivery customers," European Journal of Operational Research, Elsevier, vol. 22(3), pages 377-386, December.
    4. Irina Ioachim & Jacques Desrosiers & Yvan Dumas & Marius M. Solomon & Daniel Villeneuve, 1995. "A Request Clustering Algorithm for Door-to-Door Handicapped Transportation," Transportation Science, INFORMS, vol. 29(1), pages 63-78, February.
    5. Martin Savelsbergh & Marc Sol, 1998. "Drive: Dynamic Routing of Independent Vehicles," Operations Research, INFORMS, vol. 46(4), pages 474-490, August.
    6. Harilaos N. Psaraftis, 1983. "An Exact Algorithm for the Single Vehicle Many-to-Many Dial-A-Ride Problem with Time Windows," Transportation Science, INFORMS, vol. 17(3), pages 351-357, August.
    7. Gilbert Laporte & Yves Nobert & Martin Desrochers, 1985. "Optimal Routing under Capacity and Distance Restrictions," Operations Research, INFORMS, vol. 33(5), pages 1050-1073, October.
    8. Matteo Fischetti & Paolo Toth, 1989. "An Additive Bounding Procedure for Combinatorial Optimization Problems," Operations Research, INFORMS, vol. 37(2), pages 319-328, April.
    9. Paolo Toth & Daniele Vigo, 1997. "Heuristic Algorithms for the Handicapped Persons Transportation Problem," Transportation Science, INFORMS, vol. 31(1), pages 60-71, February.
    10. M. W. P. Savelsbergh & M. Sol, 1995. "The General Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 29(1), pages 17-29, 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. Diana, Marco & Dessouky, Maged M., 2004. "A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(6), pages 539-557, July.
    2. Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2006. "A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1117-1139, October.
    3. Mahmoudi, Monirehalsadat & Zhou, Xuesong, 2016. "Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations," Transportation Research Part B: Methodological, Elsevier, vol. 89(C), pages 19-42.
    4. Liu, Mengyang & Luo, Zhixing & Lim, Andrew, 2015. "A branch-and-cut algorithm for a realistic dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 267-288.
    5. Quadrifoglio, Luca & Dessouky, Maged M. & Ordonez, Fernando, 2008. "Mobility allowance shuttle transit (MAST) services: MIP formulation and strengthening with logic constraints," European Journal of Operational Research, Elsevier, vol. 185(2), pages 481-494, March.
    6. Hou, Liwen & Li, Dong & Zhang, Dali, 2018. "Ride-matching and routing optimisation: Models and a large neighbourhood search heuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 143-162.
    7. Dessouky, Maged M. & Aldaihani, Majid & Shah, Rutvij, 2002. "Evaluating the Impact of ITS on Personalized Public Transit," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt7fb4h2dg, Institute of Transportation Studies, UC Berkeley.
    8. Cortés, Cristián E. & Matamala, Martín & Contardo, Claudio, 2010. "The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method," European Journal of Operational Research, Elsevier, vol. 200(3), pages 711-724, February.
    9. Jean-François Cordeau, 2006. "A Branch-and-Cut Algorithm for the Dial-a-Ride Problem," Operations Research, INFORMS, vol. 54(3), pages 573-586, June.
    10. Luo, Ying & Schonfeld, Paul, 2007. "A rejected-reinsertion heuristic for the static Dial-A-Ride Problem," Transportation Research Part B: Methodological, Elsevier, vol. 41(7), pages 736-755, August.
    11. Zhixing Luo & Mengyang Liu & Andrew Lim, 2019. "A Two-Phase Branch-and-Price-and-Cut for a Dial-a-Ride Problem in Patient Transportation," Service Science, INFORMS, vol. 53(1), pages 113-130, February.
    12. Cordeau, Jean-François & Laporte, Gilbert, 2003. "A tabu search heuristic for the static multi-vehicle dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 37(6), pages 579-594, July.
    13. Mahmoudi, Monirehalsadat & Chen, Junhua & Shi, Tie & Zhang, Yongxiang & Zhou, Xuesong, 2019. "A cumulative service state representation for the pickup and delivery problem with transfers," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 351-380.
    14. Roberto Baldacci & Vittorio Maniezzo & Aristide Mingozzi, 2004. "An Exact Method for the Car Pooling Problem Based on Lagrangean Column Generation," Operations Research, INFORMS, vol. 52(3), pages 422-439, June.
    15. Grunert, Tore & Sebastian, Hans-Jurgen, 2000. "Planning models for long-haul operations of postal and express shipment companies," European Journal of Operational Research, Elsevier, vol. 122(2), pages 289-309, April.
    16. 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.
    17. Lauri Häme & Harri Hakula, 2015. "A Maximum Cluster Algorithm for Checking the Feasibility of Dial-A-Ride Instances," Transportation Science, INFORMS, vol. 49(2), pages 295-310, May.
    18. Liu, Ran & Xie, Xiaolan & Augusto, Vincent & Rodriguez, Carlos, 2013. "Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care," European Journal of Operational Research, Elsevier, vol. 230(3), pages 475-486.
    19. Kai Gutenschwager & Christian Niklaus & Stefan Voß, 2004. "Dispatching of an Electric Monorail System: Applying Metaheuristics to an Online Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 38(4), pages 434-446, November.
    20. 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.

    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:38:y:2004:i:4:p:503-514. 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.