A Modified Tabu Search Algorithm to Solve Vehicle Routing Problem

Qinhong Fu ； Kang Zhou ； Huaqing Qi ； Falin Jiang

《電腦學刊》 29卷3期 (2018/06) Pp. 197-209

https://doi.org/10.3966/199115992018062903019

摘要

A modified tabu search algorithm (TS) is designed to enhance the efficiency of TS, the relevant data structures are redesigned; in order to solve the precision of TS, the algorithm flow is adjusted under the premise of retaining the essence of TS, besides, and the modified algorithm uses three neighborhood functions to generate candidate solutions sorted to better the precision and efficiency of VRP. Comparing the efficiency with the classical TS, the computation time of the modified algorithm is obviously shortened. Mean-while, Solomon instance of different scales are tested, the result shows that the optimum solution obtained by the modified algorithm is better than the classical TS, the search time is also greatly shorten and the deviation rate is further reduced. Furthermore, comparing the experiment result with Artificial Bee Colony algorithm (ABC), the modified algorithm that can find the optimum solution is better than ABC, in addition, com-pared with the ACO algorithm, the result is not much better than the ACO algorithm, but the computing time is nearly half of the reduction, which explains TS to solve vehicle routing problem has a certain advantage and proves the effectiveness and efficiency of the modified algorithm.

關鍵字

algorithm efficiency ； data structure ； tabu search ； VRP