Abstract: Capacitated vehicle routing problem(CVRP)is animportant combinatorial optimization problem. However, it is quite difficult toachieve an optimal solution with the traditional optimization methods owing to the high computational complexity. A tabusearch was developed to solve the problem. The paper designs a tabu searchalgorithm for a kind of CVRP with soft time windows based on natural numbercoding, studies the influence of parameters on search effect andachieves very good results in the instance. The resultsobtained show that the proposed algorithm is a feasible and effective methodfor this kind of problem．
Key words: tabu search algorithm, CVRP, soft time window, non-full load
1 Introduction
Physical distribution CVRP isa well-known combinatorial optimization problem and is also a focal problem ofdistribution management.Many differentapproaches have been developed to attempt to solve the CVRP. In general, theapproaches are divided into two classes: exact algorithm(Christofides,N., Mignozzi,A., and Toth,P.,1981)and heuristic algorithm. Since the vehiclerouting problem (VRP) is an NP-hard problem(Laporte,G..,1992),as Toth and Vigo(Toth,P., and Vigo,D.,2002)reported, no exact algorithm can consistently solve CRVP-instances withmore than 50 customers; thus, the heuristic approaches such as genetic algorithm(GA),neuralnetwork(NN),simulated annealing(SA) algorithm are considered as a reasonablechoice in finding solutions for large-scale instances.
The Tabu Search(TS)proposed and formalized by Glover(Glover,F.,1989;Glover,F.,1990)is a meta-heuristic algorithm that isused to get optimal or near-optimal solution of combinational optimizationproblems. This algorithm is based on localsearch to find a member in a certain finite set of feasible solutions, and canavoid going back the former local optimum statesby a tabu table. In this paper, a TSalgorithm based on natural number codingis introduced.
The rest of this paper is organized as follow: Section2introduces the problem description. Section3gives a tabu search algorithm. Section4shows a sample. Finally, we concludethe paper with a summary in Section 5.