A MapReduce based hybrid genetic algorithm using island approach for solving time dependent vehicle routing problem

摘要

The vehicle routing problem (VRP) is a well-known combinatorial optimization problem, seeking to service a number of customers with a fleet of vehicles. It is an important problem in field of distribution, transportation and logistics. But the traditional VRP doesn''t consider the traffic condition of the road network. In this paper we provide a mapreduce based hybrid genetic solution using island approach for solving large scale vehicle routing problems in dynamic network with fluctuant link travel time. We used a hybrid approach for generating a mélange of both random and locally optimized population using routing construction algorithms (NNC, Savings and Random). Island model is used for parallelization of genetic algorithm as it has been informally argued that having multiple subpopulations helps to preserve genetic diversity, since each island can potentially follow a different search trajectory through the search space. Various local search methods such as 2-opt have been applied for improving the routes. Our algorithm design and implementation of TDVRPTW is deployed on Hadoop, an open source implementation of MapReduce. Computation results of test problems on a distributed platform showed a tremendous improvement, both in terms of computation time and efficiency.