IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v56y2005i8d10.1057_palgrave.jors.2601916.html
   My bibliography  Save this article

A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem

Author

Listed:
  • İ K Altınel

    (Boǧaziçi University, Bebek)

  • T Öncan

    (Galatasaray University, Ortaköy)

Abstract

In this work we are concerned with the Clarke–Wright savings method for the classical capacitated vehicle routing problem. This is an NP-hard problem and numerous heuristic solution methods have been proposed. They can be classified as the classical ones and metaheuristics. Recent developments have shown that classical heuristics do not compare with the best metaheuristic implementations. However, some of them are very fast and simple to implement. This explains the popularity of the Clarke–Wright savings method in practice and the motivation behind its enhancements. We follow this line of research and propose a new enhancement which differs from the previous ones in its saving criterion: Customer demands are considered in addition to distances. Based on the extensive computational experiments we can say that the new method is not only very fast but also very accurate.

Suggested Citation

  • İ K Altınel & T Öncan, 2005. "A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(8), pages 954-961, August.
    • Handle: RePEc:pal:jorsoc:v:56:y:2005:i:8:d:10.1057_palgrave.jors.2601916
    DOI: 10.1057/palgrave.jors.2601916
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2601916
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2601916?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. Vigo, Daniele, 1996. "A heuristic algorithm for the asymmetric capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 89(1), pages 108-126, February.
    2. Wade, A. C. & Salhi, S., 2002. "An investigation into a new class of vehicle routing problem with backhauls," Omega, Elsevier, vol. 30(6), pages 479-487, December.
    3. S Salhi & G Nagy, 1999. "A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(10), pages 1034-1042, October.
    4. Paessens, H., 1988. "The savings algorithm for the vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 34(3), pages 336-344, March.
    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. M. Kritikos & G. Ioannou, 2017. "A greedy heuristic for the capacitated minimum spanning tree problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(10), pages 1223-1235, October.
    2. Chang, Ximing & Wu, Jianjun & Sun, Huijun & Correia, Gonçalo Homem de Almeida & Chen, Jianhua, 2021. "Relocating operational and damaged bikes in free-floating systems: A data-driven modeling framework for level of service enhancement," Transportation Research Part A: Policy and Practice, Elsevier, vol. 153(C), pages 235-260.
    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. Yuan Zhang & Yu Yuan & Kejing Lu, 2020. "RETRACTED ARTICLE: E-commerce information system data analytics by advanced ACO for asymmetric capacitated vehicle delivery routing," Information Systems and e-Business Management, Springer, vol. 18(4), pages 911-929, December.
    5. Emre Tokgöz & Samir Alwazzi & Theodore Trafalis, 2015. "A heuristic algorithm to solve the single-facility location routing problem on Riemannian surfaces," Computational Management Science, Springer, vol. 12(3), pages 397-415, July.

    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. Maria João Santos & Pedro Amorim & Alexandra Marques & Ana Carvalho & Ana Póvoa, 2020. "The vehicle routing problem with backhauls towards a sustainability perspective: a review," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 358-401, July.
    2. C. Y. Lam, 2021. "Optimizing logistics routings in a network perspective of supply and demand nodes," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 29(1), pages 357-377, March.
    3. Wade, A. C. & Salhi, S., 2002. "An investigation into a new class of vehicle routing problem with backhauls," Omega, Elsevier, vol. 30(6), pages 479-487, December.
    4. S Mitra, 2008. "A parallel clustering technique for the vehicle routing problem with split deliveries and pickups," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(11), pages 1532-1546, November.
    5. Ropke, Stefan & Pisinger, David, 2006. "A unified heuristic for a large class of Vehicle Routing Problems with Backhauls," European Journal of Operational Research, Elsevier, vol. 171(3), pages 750-775, June.
    6. Ganesh, K. & Narendran, T.T., 2007. "CLOVES: A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up," European Journal of Operational Research, Elsevier, vol. 178(3), pages 699-717, May.
    7. Zachariadis, Emmanouil E. & Tarantilis, Christos D. & Kiranoudis, Chris T., 2010. "An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries," European Journal of Operational Research, Elsevier, vol. 202(2), pages 401-411, April.
    8. N Wassan, 2007. "Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1630-1641, December.
    9. Ann Melissa Campbell & Martin Savelsbergh, 2004. "Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems," Transportation Science, INFORMS, vol. 38(3), pages 369-378, August.
    10. Lei, Jieyu & Che, Ada & Van Woensel, Tom, 2024. "Collection-disassembly-delivery problem of disassembly centers in a reverse logistics network," European Journal of Operational Research, Elsevier, vol. 313(2), pages 478-493.
    11. Lucas Agussurja & Shih-Fen Cheng & Hoong Chuin Lau, 2019. "A State Aggregation Approach for Stochastic Multiperiod Last-Mile Ride-Sharing Problems," Service Science, INFORMS, vol. 53(1), pages 148-166, February.
    12. Niaz A. Wassan & A. Hameed Wassan & Gábor Nagy, 2008. "A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries," Journal of Combinatorial Optimization, Springer, vol. 15(4), pages 368-386, May.
    13. Arvind U. Raghunathan & David Bergman & John N. Hooker & Thiago Serra & Shingo Kobori, 2024. "Seamless Multimodal Transportation Scheduling," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 336-358, March.
    14. YazgI Tütüncü, G. & Carreto, Carlos A.C. & Baker, Barrie M., 2009. "A visual interactive approach to classical and mixed vehicle routing problems with backhauls," Omega, Elsevier, vol. 37(1), pages 138-154, February.
    15. Yang, Senyan & Ning, Lianju & Shang, Pan & (Carol) Tong, Lu, 2020. "Augmented Lagrangian relaxation approach for logistics vehicle routing problem with mixed backhauls and time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 135(C).
    16. Haughton, Michael A., 1998. "The performance of route modification and demand stabilization strategies in stochastic vehicle routing," Transportation Research Part B: Methodological, Elsevier, vol. 32(8), pages 551-566, November.
    17. Tarantilis, C. D. & Diakoulaki, D. & Kiranoudis, C. T., 2004. "Combination of geographical information system and efficient routing algorithms for real life distribution operations," European Journal of Operational Research, Elsevier, vol. 152(2), pages 437-453, January.
    18. Loske, Dominic & Klumpp, Matthias, 2021. "Human-AI collaboration in route planning: An empirical efficiency-based analysis in retail logistics," International Journal of Production Economics, Elsevier, vol. 241(C).
    19. Arild Hoff & Arne Løkketangen, 2006. "Creating lasso-solutions for the traveling salesman problem with pickup and delivery by Tabu search," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 14(2), pages 125-140, June.
    20. J-F Chen & T-H Wu, 2006. "Vehicle routing problem with simultaneous deliveries and pickups," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(5), pages 579-587, May.

    More about this item

    Keywords

    heuristics; vehicle routing problem;

    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:pal:jorsoc:v:56:y:2005:i:8:d:10.1057_palgrave.jors.2601916. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    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.