A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows |
| |
Authors: | K C Tan Y H Chew L H Lee |
| |
Institution: | (1) Department of Electrical and Computer Engineering, National University of Singapore, 4 Engineering Drive 3, Singapore, 117576;(2) Department of Industrial and Systems Engineering, National University of Singapore, 10 Kent Ridge Crescent, Singapore, 119260 |
| |
Abstract: | Vehicle routing problem with time windows (VRPTW) involves the routing of a set of vehicles with limited capacity from a central
depot to a set of geographically dispersed customers with known demands and predefined time windows. The problem is solved
by optimizing routes for the vehicles so as to meet all given constraints as well as to minimize the objectives of traveling
distance and number of vehicles. This paper proposes a hybrid multiobjective evolutionary algorithm (HMOEA) that incorporates
various heuristics for local exploitation in the evolutionary search and the concept of Pareto's optimality for solving multiobjective
optimization in VRPTW. The proposed HMOEA is featured with specialized genetic operators and variable-length chromosome representation
to accommodate the sequence-oriented optimization in VRPTW. Unlike existing VRPTW approaches that often aggregate multiple
criteria and constraints into a compromise function, the proposed HMOEA optimizes all routing constraints and objectives simultaneously,
which improves the routing solutions in many aspects, such as lower routing cost, wider scattering area and better convergence
trace. The HMOEA is applied to solve the benchmark Solomon's 56 VRPTW 100-customer instances, which yields 20 routing solutions
better than or competitive as compared to the best solutions published in literature. |
| |
Keywords: | vehicle routing problems evolutionary algorithms multiobjective optimization |
本文献已被 SpringerLink 等数据库收录! |
|