Theoretical Paper
Journal of the Operational Research Society (2008) 59, 663–673. doi:10.1057/palgrave.jors.2602371 Published online 7 February 2007
A unified tabu search algorithm for vehicle routing problems with soft time windows
Z Fu1, R Eglese2 and L Y O Li3
- 1Central South University, Changsha, P.R. China
- 2Lancaster University Management School, Lancaster, UK
- 3The Hong Kong Polytechnic University, Hong Kong, P.R. China
Correspondence: Z Fu, School of Traffic and Transportation Engineering, Central South University at Railway Campus, Changsha, Hunan 410075, P.R. China. E-mail: zhfu@mail.csu.edu.cn
Received June 2005; Accepted October 2006; Published online 7 February 2007.
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.
Keywords:
distribution, vehicle routing, soft time windows, heuristics, tabu search
