Skip to main content
SpringerLink
Log in

A unified tabu search algorithm for vehicle routing problems with soft time windows

  • Theoretical Paper
  • Published:
Journal of the Operational Research Society

Abstract

The different ways of allowing time window violations lead to different types of the vehicle routing problems with soft time windows (VRPSTW). In this paper, different types of VRPSTW are analysed. A unified penalty function and a unified tabu search algorithm for the main types of VRPSTW are presented, with which different types of VRPSTW can be solved by simply changing the values of corresponding parameters in the penalty function. Computational results on benchmark problems are provided and compared with other methods in the literature. Some best known solutions for the benchmark problems in the literature have been improved with the proposed algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1

Similar content being viewed by others

References

  • Balakrishnan N (1993). Simple heuristic for the vehicle routing problem with soft time windows. J Opl Res Soc 44: 279–287.

    Article  Google Scholar 

  • Brandão J (2004). A tabu search algorithm for the open vehicle routing problem. Eur J Opl Res 157: 552–564.

    Article  Google Scholar 

  • Chiang W-C and Russell RA (2004). A metaheuristic for the vehicle-routing problem with soft time windows. J Opl Res Soc 55: 1298–1310.

    Article  Google Scholar 

  • Cordeau J-F, Laporte G and Mercier A (2001). A unified tabu search heuristic for vehicle routing problems with time windows. J Opl Res Soc 52: 928–936.

    Article  Google Scholar 

  • Cordeau J-F, Desaulniers G, Desrosiers J, Solomon MM and Soumis F (2002). VRP with time windows. In: Toth P and Vigo D (eds). The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. SIAM: Philadelphia PA, pp. 157–194.

    Google Scholar 

  • Duhamel C, Potvin JY and Rousseau JM (1997). A tabu search heuristic for the vehicle routing problem with backhauls and time windows. Transport Sci 31: 49–59.

    Article  Google Scholar 

  • Fagerholt K (2001). Ship scheduling with soft time windows: An optimisation based approach. Eur J Opl Res 131: 559–571.

    Article  Google Scholar 

  • Fu Z, Eglese R and Li LYO (2005). A new tabu search heuristic for the open vehicle routing problem. J Opl Res Soc 56: 267–274.

    Article  Google Scholar 

  • Fu Z, Eglese R and Li LYO (2006). Corrigendum: A new tabu search heuristic for the open vehicle routing problem. J Opl Res Soc 57: 1018–1018.

    Article  Google Scholar 

  • Gambardella LM, Taillard E and Agazzi G (1999). MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In: Corne D, Dorigo M and Glover F (eds). New Ideas in Optimization. McGraw-Hill: London, pp. 63–76.

    Google Scholar 

  • Gendreau M, Hertz A and Laporte G (1994). A tabu search heuristic for the vehicle routing problem. Mngt Sci 40: 1276–1290.

    Article  Google Scholar 

  • Glover F and Laguna M (1997). Tabu Search. Kluwer Academic Publishers: Norwell, MA.

    Book  Google Scholar 

  • Homberger J and Gehring H (1999). Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR 37: 297–318.

    Google Scholar 

  • Koskosidis YA, Powell WB and Solomon MM (1992). An optimization-based heuristic for vehicle routing and scheduling with soft time windows constraints. Transport Sci 26: 69–85.

    Article  Google Scholar 

  • Osman IH (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann Opns Res 41: 421–451.

    Article  Google Scholar 

  • Pureza VM and França PM (1991). Vehicle routing problems via tabu search metaheuristic. Technical Report CRT-347, Centre for Research on Transportation, Montreal, Canada.

  • Rochat Y and Taillard ED (1995). Probabilistic diversification and intensification in local search for vehicle routing. J Heuristics 1: 147–167.

    Article  Google Scholar 

  • Rousseau LM, Gendreau M and Pesant G (2002). Using constraint-based operators to solve the vehicle routing problem with time windows. J Heuristics 1: 43–58.

    Article  Google Scholar 

  • Schrimpf G, Schneider J, Stamm-Wilbrandt H and Dueck G (2000). Record breaking optimization results using the ruin and recreate principle. J Comput Phys 159: 139–171.

    Article  Google Scholar 

  • Shaw P (1998). Using constraint programming and local search methods to solve vehicle routing problems. In: Maher M and Puget J-F (eds). Principles and Practice of Constraint Programming-CP98, Lecture Notes in Computer Science. Springer-Verlag: New York, pp. 417–431.

    Chapter  Google Scholar 

  • Solomon MM (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Opns Res 35: 254–265.

    Article  Google Scholar 

  • Taillard E, Badeau P, Gendreau M, Guertin F and Potvin JY (1997). A tabu search heuristic for the vehicle routing problem with soft time windows. Transport Sci 31: 170–186.

    Article  Google Scholar 

  • Van Breedam A (2001). Comparing descent heuristics and metaheuristics for the vehicle routing problem. Comput Opns Res 28: 289–315.

    Article  Google Scholar 

Download references

Acknowledgements

We are grateful to the anonymous referees for their useful comments and suggestions that helped us to improve the presentation of this paper. This research was supported by the National Natural Science Foundation of China (NSFC, 70071003, 70671108).

Author information

Authors and Affiliations

  1. Central South University, Changsha, P.R., China

    Z Fu

  2. Lancaster University Management School, Lancaster, UK

    R Eglese

  3. The Hong Kong Polytechnic University, Hong Kong, P.R., China

    L Y O Li

Authors
  1. Z Fu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R Eglese
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. L Y O Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Z Fu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fu, Z., Eglese, R. & Li, L. A unified tabu search algorithm for vehicle routing problems with soft time windows. J Oper Res Soc 59, 663–673 (2008). https://doi.org/10.1057/palgrave.jors.2602371

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/palgrave.jors.2602371

Keywords

Search

Navigation