A Two-phase Hybrid Metaheuristic For Vehicle Routing Problem With Time Windows And Applications

Based on characters of tobacco distribution problem, the subject of this paper isvehicle routing problem with time windows (VRPTW), in order to lower enterprises’logistics cost, increase their profits and lift their core competence.This paper designs a two-phase hybrid metaheuristic for the VRPTW. The primaryobjective of the VRPTW is to minimize the number of vehicles and the secondaryobjective is to minimize the total travel distance. The aim of the first phase is tominimize the number of vehicles by means of variable neighborhood search algorithm,whereas in the second phase the total travel distance is minimized using a tabu searchalgorithm based on the first phase.Variable neighborhood search algorithm contains four processes, initial solutionconstruction, neighborhood changing, local search, and optimal solution updation. Theconstruction of the initial solution adopts the modified Solomon insertion algorithm andthe changing of the neighborhood uses several operators, such as exchange,2-opt,crossexchange, etc. Then the neighborhood solution is submitted to the local searchusing relocate and ejection chain operators. The optimal solution is updated accordingto the three criterions: minimize the number of vehicles, minimize the number ofcustomers of the shortest route, and minimize the total travel distance. The priorities ofthe three criterions drop gradually. The algorithm exits when several runs have beencomputed and the optimal solution has not been updated, that is to say, the algorithmhas reached the maximum iterations set by this paper.The tabu search phase comprises some elements, such as initial solution, candidatesolutions, tabu list, aspiration criterion, convergence criterion and so on. The initialsolution obtains from the first phase-variable neighborhood search, then it adoptsexchange,2-opt, relocate operators to generate candidate solutions. In this paper, tabuobject of the tabu list is the value of total travel distance. The optimal solution isupdated according to the two criterions: minimize the number of vehicles, and minimizethe total travel distance. The tabu search algorithm exits when several runs have beencomputed and the optimal solution has not been updated, that is to say, the algorithmhas reached the maximum iterations set by this paper. In order to gain results efficiently, a one-way linked list is raised to store solutionsand it greatly lessens the computing time compared with the one-dimension andtwo-dimension array. This paper tests multiple groups of parameters used in thetwo-phase hybrid metaheuristic and in the end confirms the values of these parameters.Then the two-phase hybrid metaheuristic is subjected to a comparative test on the basisof356problems proposed by Solomon, Gehring and Homberger with sizes varyingfrom100to1000customers, grouped by Solomon, G02, G04, G06, G08, G10. Themetaheuristic implements several runs to every problem and best result is extracted andcompared to the current best solution published on the internet. Experimental resultsshow that the two-phase hybrid metaheuristic has computed new best solutions to everygroup, and has gained103new results. The metaheuristic has outstanding performanceto group Solomon and G02problems, such as82.14%,58.33%of the problems in thegroup Solomon and G02have gained new best solutions. And the metaheuristic haspreferably performance to group G04and performs well to group G06, G08, G10to acertain extent.The two-phase hybrid metaheuristic is also embedded to TransRouter distributionoptimization system. Routes have been planned for Chongqing Hero Company andZhengzhou Tobacco Company using the two-phase hybrid metaheuristic.