Abstract
The VRPTW is a well-known and complex combinatorial problem which has considerable attention in recent years. Combinatorial optimization problems of this kind are NP-hard and are best solved to near optimum by heuristics. Here, we propose a two-stage optimization strategy for VRPTW. Firstly, for constructing a good initial solution, we use the stochastic PFIH, guaranteeing the diversity of the initial solution. And then a hybrid system based on the combination of SA and LNS is proposed to optimize the initial solution. Secondly, tune time windows for the customers using a regression iterative strategy which is put forward to and figure out the optimum time for each vehicle departing. It can make the total waiting time zero. The test of this work is executed over the type C101 in Solomon’s VRPTW instances. It is proved by the experiment that our algorithm can solve VRPTW efficiently and quickly.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alvarenga, G.B., Mateus, G.R.: Hierarchical Tournament Selection Genetic Algorithm for the vehicle Routing Problem with Time Windows. In: HIS 2004, Fourth International Conference, pp. 410–415 (2004)
Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 35(2), 254–265 (1987)
Oliveira, H.C.B., Vasconcelos, G.C., Alvarenga, G.B.: Reducing traveled distance in the vehicle routing problem with time windows using a multi-start simulated annealing. In: IJCNN 2006, pp. 3013–3020, July 16-21 (2006)
Alvarenga, G.B., Mateus, G.R.: A two-phase genetic and set partitioning approach for the vehicle routing problem with time windows. In: Proc. 4th International Conference on Hybrid Intelligent Systems, pp. 428–433 (2004)
Lim, A., Zhang, X.: A two-stage heuristic for the vehicle routing problem with time windows and a limited number of vehicles. In: Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS 2005), p. 82c (2007)
Shaw, P.: Using constraint Programming and local search methods to solve vehicle routing problems. In: Proceeding of the 4th International Conference on Principle and practice of Constrant Programming, pp. 417–431 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jiang, D., Jiang, W., Huang, Z. (2008). A Hybrid Algorithm for Vehicle Routing Problem with Time Windows. In: Kang, L., Cai, Z., Yan, X., Liu, Y. (eds) Advances in Computation and Intelligence. ISICA 2008. Lecture Notes in Computer Science, vol 5370. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92137-0_22
Download citation
DOI: https://doi.org/10.1007/978-3-540-92137-0_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92136-3
Online ISBN: 978-3-540-92137-0
eBook Packages: Computer ScienceComputer Science (R0)