IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v39y1991i3p456-469.html
   My bibliography  Save this article

Parallel Savings Based Heuristics for the Delivery Problem

Author

Listed:
  • Kemal Altinkemer

    (Purdue University, West Lafayette, Indiana)

  • Bezalel Gavish

    (Vanderbilt University, Nashville, Tennessee)

Abstract

The delivery problem consists of finding a set of routes for a fleet of capacitated vehicles to satisfy the cargo delivery requirements of customers. The vehicles are located in a central depot, and have to fulfill the delivery requirements in a sequence that minimizes total delivery costs. Each vehicle tour starts and terminates at the central depot, and each node is supplied by exactly one vehicle. All vehicles have the same cargo carrying capacity. The paper presents parallel savings algorithms (PSAs) for generating feasible solutions to this problem. The new algorithms combine the savings approach, with matching based procedures. In computational tests the heuristic produces better solutions than the best known solutions for six problems out of a standard set of 14 difficult test problems. Augmented Lagrangian based lower bounding procedures are developed, and used to evaluate the quality of the solutions generated by PSAs. The lower bounds generated by the augmented Lagrangian are the tightest bounds known for delivery problems. The performance of the PSAs is also compared to tour partitioning based heuristics which have better worst case error bounds. The average quality of solutions generated by PSAs is shown to be significantly superior on large sets of test problems.

Suggested Citation

  • Kemal Altinkemer & Bezalel Gavish, 1991. "Parallel Savings Based Heuristics for the Delivery Problem," Operations Research, INFORMS, vol. 39(3), pages 456-469, June.
    • Handle: RePEc:inm:oropre:v:39:y:1991:i:3:p:456-469
    DOI: 10.1287/opre.39.3.456
    as

    Download full text from publisher

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

    Citations

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


    Cited by:

    1. Holmberg, Kaj & Ronnqvist, Mikael & Yuan, Di, 1999. "An exact algorithm for the capacitated facility location problems with single sourcing," European Journal of Operational Research, Elsevier, vol. 113(3), pages 544-559, March.
    2. Kazaz, Burak & Altinkemer, Kemal, 2003. "Optimization of multi-feeder (depot) printed circuit board manufacturing with error guarantees," European Journal of Operational Research, Elsevier, vol. 150(2), pages 370-394, October.
    3. Merve Cengiz Toklu, 2023. "A fuzzy multi-criteria approach based on Clarke and Wright savings algorithm for vehicle routing problem in humanitarian aid distribution," Journal of Intelligent Manufacturing, Springer, vol. 34(5), pages 2241-2261, June.
    4. Ido Orenstein & Tal Raviv & Elad Sadan, 2019. "Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 683-711, December.
    5. Ronnqvist, Mikael & Tragantalerngsak, Suda & Holt, John, 1999. "A repeated matching heuristic for the single-source capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 116(1), pages 51-68, July.
    6. Gouveia, Luis, 1995. "A result on projection for the vehicle routing ptoblem," European Journal of Operational Research, Elsevier, vol. 85(3), pages 610-624, September.
    7. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    8. Eveborn, Patrik & Flisberg, Patrik & Ronnqvist, Mikael, 2006. "Laps Care--an operational system for staff planning of home care," European Journal of Operational Research, Elsevier, vol. 171(3), pages 962-976, June.
    9. Altinkemer, Kemal & Kazaz, Burak & Koksalan, Murat & Moskowitz, Herbert, 2000. "Optimization of printed circuit board manufacturing: Integrated modeling and algorithms," European Journal of Operational Research, Elsevier, vol. 124(2), pages 409-421, July.
    10. Pearn, W. L. & Chung, S. H. & Chen, A. Y. & Yang, M. H., 2004. "A case study on the multistage IC final testing scheduling problem with reentry," International Journal of Production Economics, Elsevier, vol. 88(3), pages 257-267, April.
    11. Gilbert Laporte, 2007. "What you should know about the vehicle routing problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(8), pages 811-819, December.
    12. Y Gajpal & P Abad, 2010. "Saving-based algorithms for vehicle routing problem with simultaneous pickup and delivery," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(10), pages 1498-1509, October.
    13. W L Pearn & S H Chung & M H Yang & Y H Chen, 2004. "Algorithms for the wafer probing scheduling problem with sequence-dependent set-up time and due date restrictions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(11), pages 1194-1207, November.
    14. Poot, A. & Kant, G. & Wagelmans, A.P.M., 1999. "A savings based method for real-life vehicle routing problems," Econometric Institute Research Papers EI 9938/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    15. Yao, Yu & Zhu, Xiaoning & Dong, Hongyu & Wu, Shengnan & Wu, Hailong & Carol Tong, Lu & Zhou, Xuesong, 2019. "ADMM-based problem decomposition scheme for vehicle routing problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 156-174.

    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:oropre:v:39:y:1991:i:3:p:456-469. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.