Chinese Journal of Computers   Full Text
Title	A Hybrid Heuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pickup
Authors	CHEN Ping HUANG Hou-Kuan DONG Xing-Ye
Address	(School of Computer Science and Information Technology, Beijing Jiaotong University, Beijing 100044)
Year	2008
Issue	No.4(565—573)
Abstract &   Background	Abstract A hybrid heuristic algorithm ACS_VND is proposed and applied to solving the vehicle routing problem with simultaneous delivery and pickup, which combines two metaheuristics, i.e., Ant Colony System and Variable Neighborhood Descent. Several weakly feasible solutions are built by an insertion based ACS solution construction method, which are then transformed into strongly feasible ones, the best of which is taken as the initial solution of the VND procedure. During the VND procedure, three different neighborhood structures, i.e., insertion, swap and 2-opt are successively used. Computational results on the 55 benchmark problems with the size ranging from 22 to 199, show that the proposed hybrid heuristic algorithm can find the best known solution for 52 problems in a short time; furthermore, the best known solutions for 44 problems are updated, which indicates that the proposed ACS_VND outperforms other algorithms in literatures. keywords vehicle routing problem with simultaneous delivery and pickup; hybrid metaheuristics; ant colony system; variable neighborhood descent; combinatorial optimization; NP-hard background Distribution of goods is of paramount importance in the logistics and supply chain management. Since the transportation cost occupies a great proportion in the total logistics cost, dispatching and routing the vehicles in a rational way may considerably cut off the cost of the logistics companies. Furthermore, the energy consumption may be also reduced, which is good for the environmental protection. In this paper, a variant of vehicle routing problem, i.e., vehicle routing problem with simultaneous delivery and pickup is discussed. It has a strong background in the reverse logistics and has attracted researchers’ interests recently. The vehicle routing problem is NP-hard, heuristic and metaheuristic methods, which can find quite good solutions in a very short time, are practical for solving this problem. Recently, it has become evident that the concentration on a sole metaheuristic is rather restrictive. Thus the hybrid heuristic methods, which are to combine a metaheuristic with other optimization techniques, can behave more efficiently and flexibly when dealing with real-world and large-scale problems. In this paper, a new hybrid heuristic algorithm is proposed, which can find 52 best known solutions and update 44 best known solutions out of 55 benchmark problems. This work is supported by the National Basic Research Program(973 Program) of China under grant No.2006CB705500.