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

A metaheuristic for the vehicle-routeing problem with soft time windows

Author

Listed:
  • W-C Chiang

    (Operations Management, University of Tulsa)

  • R A Russell

    (Operations Management, University of Tulsa)

Abstract

This paper develops a metaheuristic for the vehicle-routeing and scheduling problem with soft time window constraints. A tabu search solution method is developed, which utilizes a mixed neighbourhood structure and an advanced recovery procedure to generate high-quality solutions. Computational results on test problems from the literature are reported. The metaheuristic achieves solutions that compare favourably with previously reported results.

Suggested Citation

  • W-C Chiang & R A Russell, 2004. "A metaheuristic for the vehicle-routeing problem with soft time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(12), pages 1298-1310, December.
    • Handle: RePEc:pal:jorsoc:v:55:y:2004:i:12:d:10.1057_palgrave.jors.2601791
    DOI: 10.1057/palgrave.jors.2601791
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2601791
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2601791?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. Wen-Chyuan Chiang & Robert A. Russell, 1997. "A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 9(4), pages 417-430, November.
    2. S. Lin & B. W. Kernighan, 1973. "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," Operations Research, INFORMS, vol. 21(2), pages 498-516, April.
    3. Chiang, Wen-Chyuan & Russell, Robert A., 2004. "Integrating purchasing and routing in a propane gas supply chain," European Journal of Operational Research, Elsevier, vol. 154(3), pages 710-729, May.
    4. Éric Taillard & Philippe Badeau & Michel Gendreau & François Guertin & Jean-Yves Potvin, 1997. "A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows," Transportation Science, INFORMS, vol. 31(2), pages 170-186, May.
    5. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    6. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    7. Robert A. Russell, 1977. "Technical Note—An Effective Heuristic for the M -Tour Traveling Salesman Problem with Some Side Conditions," Operations Research, INFORMS, vol. 25(3), pages 517-524, June.
    8. Yiannis A. Koskosidis & Warren B. Powell & Marius M. Solomon, 1992. "An Optimization-Based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints," Transportation Science, INFORMS, vol. 26(2), pages 69-85, May.
    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. Sébastien Mouthuy & Florence Massen & Yves Deville & Pascal Van Hentenryck, 2015. "A Multistage Very Large-Scale Neighborhood Search for the Vehicle Routing Problem with Soft Time Windows," Transportation Science, INFORMS, vol. 49(2), pages 223-238, May.
    2. Andres Figliozzi, Miguel, 2012. "The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(3), pages 616-636.
    3. Daniel Schubert & André Scholz & Gerhard Wäscher, 2017. "Integrated Order Picking and Vehicle Routing with Due Dates," FEMM Working Papers 170007, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    4. 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.
    5. Md. Anisul Islam & Yuvraj Gajpal, 2021. "Optimization of Conventional and Green Vehicles Composition under Carbon Emission Cap," Sustainability, MDPI, vol. 13(12), pages 1-20, June.
    6. Daniel Schubert & André Scholz & Gerhard Wäscher, 2018. "Integrated order picking and vehicle routing with due dates," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 1109-1139, October.
    7. Matteo Salani & Maria Battarra, 2018. "The opportunity cost of time window violations," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(4), pages 343-361, December.
    8. Z Fu & R Eglese & L Y O Li, 2008. "A unified tabu search algorithm for vehicle routing problems with soft time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(5), pages 663-673, May.
    9. R A Russell & T L Urban, 2008. "Vehicle routing with soft time windows and Erlang travel times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(9), pages 1220-1228, September.
    10. Junlong Zhang & William Lam & Bi Chen, 2013. "A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service," Networks and Spatial Economics, Springer, vol. 13(4), pages 471-496, December.
    11. Jbili, S. & Chelbi, A. & Radhoui, M. & Kessentini, M., 2018. "Integrated strategy of Vehicle Routing and Maintenance," Reliability Engineering and System Safety, Elsevier, vol. 170(C), pages 202-214.
    12. Kuhn, Heinrich & Schubert, Daniel & Holzapfel, Andreas, 2021. "Integrated order batching and vehicle routing operations in grocery retail – A General Adaptive Large Neighborhood Search algorithm," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1003-1021.
    13. Hideki Hashimoto & Mutsunori Yagiura & Shinji Imahori & Toshihide Ibaraki, 2013. "Recent progress of local search in handling the time window constraints of the vehicle routing problem," Annals of Operations Research, Springer, vol. 204(1), pages 171-187, April.
    14. Lei Chen & Haiyan Ma & Yi Wang & Feng Li, 2022. "Vehicle Routing Problem for the Simultaneous Pickup and Delivery of Lithium Batteries of Small Power Vehicles under Charging and Swapping Mode," Sustainability, MDPI, vol. 14(16), pages 1-23, August.

    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. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    2. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    3. Homberger, Jorg & Gehring, Hermann, 2005. "A two-phase hybrid metaheuristic for the vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 162(1), pages 220-238, April.
    4. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    5. R A Russell & T L Urban, 2008. "Vehicle routing with soft time windows and Erlang travel times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(9), pages 1220-1228, September.
    6. Hideki Hashimoto & Mutsunori Yagiura & Shinji Imahori & Toshihide Ibaraki, 2013. "Recent progress of local search in handling the time window constraints of the vehicle routing problem," Annals of Operations Research, Springer, vol. 204(1), pages 171-187, April.
    7. Olli Bräysy, 2003. "A Reactive Variable Neighborhood Search for the Vehicle-Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 15(4), pages 347-368, November.
    8. T. Ibaraki & S. Imahori & M. Kubo & T. Masuda & T. Uno & M. Yagiura, 2005. "Effective Local Search Algorithms for Routing and Scheduling Problems with General Time-Window Constraints," Transportation Science, INFORMS, vol. 39(2), pages 206-232, May.
    9. Sébastien Mouthuy & Florence Massen & Yves Deville & Pascal Van Hentenryck, 2015. "A Multistage Very Large-Scale Neighborhood Search for the Vehicle Routing Problem with Soft Time Windows," Transportation Science, INFORMS, vol. 49(2), pages 223-238, May.
    10. Chiang, Wen-Chyuan & Russell, Robert & Xu, Xiaojing & Zepeda, David, 2009. "A simulation/metaheuristic approach to newspaper production and distribution supply chain problems," International Journal of Production Economics, Elsevier, vol. 121(2), pages 752-767, October.
    11. Calvete, Herminia I. & Gale, Carmen & Oliveros, Maria-Jose & Sanchez-Valverde, Belen, 2007. "A goal programming approach to vehicle routing problems with soft time windows," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1720-1733, March.
    12. Liu, Fuh-Hwa Franklin & Shen, Sheng-Yuan, 1999. "A route-neighborhood-based metaheuristic for vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 118(3), pages 485-504, November.
    13. 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.
    14. Sana Jawarneh & Salwani Abdullah, 2015. "Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows," PLOS ONE, Public Library of Science, vol. 10(7), pages 1-23, July.
    15. Müller, Juliane, 2010. "Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 202(1), pages 223-231, April.
    16. Z Fu & R Eglese & L Y O Li, 2008. "A unified tabu search algorithm for vehicle routing problems with soft time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(5), pages 663-673, May.
    17. Okitonyumbe Y.F., Joseph & Ulungu, Berthold E.-L. & Kapiamba Nt., Joel, 2015. "Cobweb Heuristic for solving Multi-Objective Vehicle Routing Problem," MPRA Paper 66121, University Library of Munich, Germany.
    18. Russell Bent & Pascal Van Hentenryck, 2004. "A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 38(4), pages 515-530, November.
    19. 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.
    20. K H Kim & M J Lee, 2007. "Scheduling trucks in local depots for door-to-door delivery services," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(9), pages 1195-1202, September.

    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:55:y:2004:i:12:d:10.1057_palgrave.jors.2601791. 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.