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. |
Vehicle routing problem
|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. https://doi.org/10.1016/S0954-1810(01)00005-X|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Oct 10, 2018
WEB OF SCIENCETM
checked on Oct 10, 2018
checked on Jul 27, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.