Research on New Tabu Search Algorithm for Min-Max Vehicle Routing Problem - Advanced Research on Computer Education, Simulation and Modeling - page 79

Research on New Tabu Search Algorithm for Min-Max
Vehicle Routing Problem
Chunyu Ren
School of Information science and technology, Heilongjiang University,
15080 Harbin, China
[e-mail]
Abstract. In order to satisfy with the individual and various demand of cus-
tomer, the present study is focused on the Min-Max Vehicle Routing Problem.
According to the characteristics of model, new tabu search algorithm is used to
get the optimization solution. It applies newly improved insertion method to
construct initial solution, to improve the feasibility of the solution; centers the
longest route to design dual layered random operation to construct its neighbor-
hood, to realize the strategy of optimizing between and within the route, to
boost the efficiency and quality of the searching. Applies auto adaptive tabu
length to control the searching capability dynamically; At last, it uses simulated
experiments to prove the effectiveness and feasibility of this algorithm, and
provides clues for massively solving practical problems.
Keywords: MMVRP, new tabu search algorithm, improved insertion method,
dual layered random operation, auto adaptive tabu length.
1 Introduction
In the recent years, with the development of the modern logistics, vehicle routing prob-
lem has received widespread attention. Optimizing the problem can increase economic
efficiency of logistics distribution. When it comes to solve massive complicated prob-
lems, the intelligent algorithm has wider application. Yuvraj applied large-scale ant
colony algorithm to solve VRPB [1]. Ai designed a particle swarm optimization algo-
rithm based on multiple social structures to solve pickup-delivery problem [2].
In practice, there exists a type of problems, whose aim is not to demand the short-
est distance of the whole route, but to demand the shortest distance of the longest sub
route throughout the whole route, for which is called Min-Max Vehicle Routing Prob-
lem, MMVRP. Michael firstly solved the minimum boundary value of the objective
function in MMVRP, and then used tabu search algorithm to get the solution [3].
Sema studied the school commuting bus MMVRP, and used the tabu search algorithm
of the Cross and Or-opt Exchange Algorithm [4]. Arkin divided the n number of
routes created by MMVRP into n number of sub regions of solving TSP problem and
applied approximate algorithm to get the solution [5].
Considering the complexity of MMVRP, the essay proposed to apply new tabu
search algorithm.