一类集散货物路线问题的禁忌搜索算法设计

A Tabu Search Algorithm for Vehicle Routing Problem with Simultaneous Deliveries and Pickups

针对该类同时集散货物路线问题(VRPSDP)的特点,文章将配送中心车辆的固定费用和可变费用之和作为目标函数.然后,提出了一种SFC-TS算法:先应用分形理论中的空间填充曲线法(SpacefillingCurves,SFC)求解初始解,再用禁忌搜索法(Tabu Search Algorithm,TS)对初始解进行改进优化.最后,应用算例验证了SFC-TS算法的有效性,结果表明SFC-TS算法在求解小规模问题(20个点)时其性能总体优于已有的同类问题的算法.

The vehicle routing problems with backhauls presume that the delivery and pickup of goods take place at different customer locations. In many practical situations, however, the same customer may require both delivery and pickup of goods simultaneously. According to its features, in this paper, object function is the sum of the fixed and variable expenses consumed by vehicles. Then a SFC-TS Algorithm is proposed： firstly, the initial solution is obtained by means of spacefilling curves in the fractal theory, and then it is impoved by the tabu search algorithm. In the end, computational examples are taken to demonstrate the efficiency of the SFC-TS Algorithm. The results show that the proposed method in the paper can obtain the optimal solutions to the small-sized problems in a much shorter time compared with other algorithms.