A Hybrid Genetic Algorithm for the Vehicle-Routing Problem with Controlling Lethal Gene

Sangheon Han ； Yoshio Tabata

《Asia Pacific Management Review》 7卷3期 (2002/09) Pp. 405-425

並列摘要

One of the main obstacles in applying genetic algorithms (GAs) to complex problems has been the high computational cost due to their slow convergence rate. We encounter such a difficulty when we attempt to use the classical GA for vehicle routing problem (VRP). In the Vehicle routing Problem, a set of customers is served by a fleet of vehicles of limited capacity, initially located at a central depot. The object is to find tours for the vehicles, such that each customer is served, the total load on any vehicle is no more than the vehicle capacity, and the total distance traveled is as small as possible. To alleviate this difficulty, we develop a hybrid approach that combines GA with another heuristic algorithm such as Sweep Algorithm to solve VRP. Overall, computational results show that our hybrid approach is an effective and robust optimization technique.

並列關鍵字

Hybrid-Genetic Algorithm ； Vehicle Routing Problem ； Sweep Algorithm

參考文獻

Back, T., Fogel, D. B., Michalewicz, Z.(1996).Handbook of Evolutionary Computation.New York:University of Oxford Press.

Christofides, N.(1985).The Traveling Salesman Problem.John Wiley ＆ Sons.

Conru, A. B.(1994).Proceedings of the First IEEE Conference on Evolutionary Computing.Orlando, FL:

Cordeau, J. F., Gendreau, M., Laporte, G.(1995).A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems.Montreal:Center for Research on Transportation.

Dantzig, G. B., Ramser, J. H.(1959).The Truck Dispatching Problem.Management Science.6(1)