Application of Genetic Algorithms to Solve the Multidepot Vehicle Routing Problem.pdf
文本预览下载声明
IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, VOL. 7, NO. 2, APRIL 2010 383
Application of Genetic Algorithms to Solve the
Multidepot Vehicle Routing Problem
H. C. W. Lau, T. M. Chan, W. T. Tsui, and W. K. Pang
Abstract—This paper deals with the optimization of vehicle routing
problem in which multiple depots, multiple customers, and multiple
products are considered. Since the total traveling time is not always
restrictive as a time window constraint, the objective regarded in this
paper comprises not only the cost due to the total traveling distance, but
also the cost due to the total traveling time. We propose to use a stochastic
search technique called fuzzy logic guided genetic algorithms (FLGA) to
solve the problem. The role of fuzzy logic is to dynamically adjust the
crossover rate and mutation rate after ten consecutive generations. In
order to demonstrate the effectiveness of FLGA, a number of benchmark
problems are used to examine its search performance. Also, several search
methods, branch and bound, standard GA (i.e., without the guide of fuzzy
logic), simulated annealing, and tabu search, are adopted to compare
with FLGA in randomly generated data sets. Simulation results show that
FLGA outperforms other search methods in all of three various scenarios.
Note to Practitioners—The multidepot vehicle routing problem is one of
the common optimization problems in the logistics area. In a real-world
environment, drivers choose the shortest route to reach a destination since
they assume that it should take the shortest time to travel the shortest route.
However, if some events such as traffic congestions, accidents happen in the
shortest route, the traveling time spent on this route can be greater than
that on the longer route. Thus, this paper considers not only the cost due
to the total traveling distance, but also the cost due to the total traveling
time, as two objectives. We propose a stochastic search technique called
FLGA to solve the problem.
显示全部