混合启发式算法求解多配送人员车辆路径问题

Hybrid Heuristic Algorithm for the Vehicle Routing Problem with Multiple Deliverymen

为解决带时间窗和多配送人员的车辆路径问题,本文采用混合启发式算法对其进行求解。该算法主要由整数规划重组、局部搜索算法和模拟退火算法三部分组成。在算法中,整数规划重组有效提高了解的质量,局部搜索算法和模拟退火算法保证了算法搜索的深入性和广泛性。通过与CPLEX和禁忌搜索算法进行对比,证实了混合启发式算法实用价值更高,求解效果更好。

To solve the vehicle routing problem with time windows and multiple deliverymen,we adopt a hybrid heuristic algorithm,which is characterized by the hybridization of the integer programming recombination,the local search(LS)algorithm and the simulated annealing(SA)algorithm.In the proposed algorithm,the integer programming recombination is capable of providing better solutions for further improvement,and LS and SA make a good balance between exploration and exploitation.Computational results indicate the proposed algorithm is more effective than CPLEX and the tabu search algorithm.