Dynamic vehicle routing using genetic algorithms |
| |
Authors: | Franklin T Hanshar Beatrice M Ombuki-Berman |
| |
Affiliation: | (1) Department of Computer Science, Brock University, St. Catharines, ON, Canada, L2S 3A1 |
| |
Abstract: | Many difficult combinatorial optimization problems have been modeled as static problems. However, in practice, many problems
are dynamic and changing, while some decisions have to be made before all the design data are known. For example, in the Dynamic
Vehicle Routing Problem (DVRP), new customer orders appear over time, and new routes must be reconfigured while executing
the current solution. Montemanni et al. 1] considered a DVRP as an extension to the standard vehicle routing problem (VRP)
by decomposing a DVRP as a sequence of static VRPs, and then solving them with an ant colony system (ACS) algorithm.
This paper presents a genetic algorithm (GA) methodology for providing solutions for the DVRP model employed in 1]. The effectiveness
of the proposed GA is evaluated using a set of benchmarks found in the literature. Compared with a tabu search approach implemented
herein and the aforementioned ACS, the proposed GA methodology performs better in minimizing travel costs.
Franklin T. Hanshar is currently a M.Sc. student in the Department of Computing and Information Science at the University of Guelph, Ontario,
Canada. He received a B.Sc. degree in Computer Science from Brock University in 2005. His research interests include uncertain
reasoning, optimization and evolutionary computation.
Beatrice Ombuki-Berman is currently an Associate Professor in the Department of Computer Science at Brock University, Ontario, Canada. She obtained
a PhD and ME in Information Engineering from University of The Ryukyus, Okinawa, Japan in 2001 and 1998, respectively. She
received a B.Sc. in Mathematics and Computer Science from Jomo Kenyatta University, Nairobi, Kenya. Her primary research interest
is evolutionary computation and applied optimization. Other research interests include neural networks, machine learning and
ant colony optimization. |
| |
Keywords: | Dynamic vehicle routing Genetic algorithms Tabu search |
本文献已被 SpringerLink 等数据库收录! |
|