Please use this identifier to cite or link to this item:
Title: Heuristic methods for vehicle routing problem with time windows
Authors: Tan, K.C. 
Lee, L.H. 
Zhu, Q.L. 
Ou, K.
Keywords: Combinatorial optimisation
Genetic algorithm
Simulated annealing
Tabu search
Time windows
Vehicle routing problem
Issue Date: 2001
Citation: Tan, K.C., Lee, L.H., Zhu, Q.L., Ou, K. (2001). Heuristic methods for vehicle routing problem with time windows. Artificial Intelligence in Engineering 15 (3) : 281-295. ScholarBank@NUS Repository.
Abstract: This paper documents our investigation into various heuristic methods to solve the vehicle routing problem with time windows (VRPTW) to near optimal solutions. The objective of the VRPTW is to serve a number of customers within predefined time windows at minimum cost (in terms of distance travelled), without violating the capacity and total trip time constraints for each vehicle. Combinatorial optimisation problems of this kind are non-polynomial-hard (NP-hard) and are best solved by heuristics. The heuristics we are exploring here are mainly third-generation artificial intelligent (AI) algorithms, namely simulated annealing (SA), Tabu search (TS) and genetic algorithm (GA). Based on the original SA theory proposed by Kirkpatrick and the work by Thangiah, we update the cooling scheme and develop a fast and efficient SA heuristic. One of the variants of Glover's TS, strict Tabu, is evaluated and first used for VRPTW, with the help of both recency and frequency measures. Our GA implementation, unlike Thangiah's genetic sectoring heuristic, uses intuitive integer string representation and incorporates several new crossover operations and other advanced techniques such as hybrid hill-climbing and adaptive mutation scheme. We applied each of the heuristics developed to Solomon's 56 VRPTW 100-customer instances, and yielded 18 solutions better than or equivalent to the best solution ever published for these problems. This paper is also among the first to document the implementation of all the three advanced AI methods for VRPTW, together with their comprehensive results. © 2001 Elsevier Science Ltd. All rights reserved.
Source Title: Artificial Intelligence in Engineering
ISSN: 09541810
DOI: 10.1016/S0954-1810(01)00005-X
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Jan 16, 2019


checked on Jan 16, 2019

Page view(s)

checked on Dec 29, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.