基于禁忌搜索算法求解带软时间窗的定位-路线问题

建立了描述带软时间窗的定位-路线问题(LRPSTW)的混合整数规划模型,给出了求解该问题的基于禁忌搜索算法的两阶段启发式算法:第一阶段采用禁忌搜索算法确定配送中心的位置和客户群的分配,设计的swap*-opt*邻域操作算子能够有效地搜索邻域解空间;第二阶段则采用禁忌搜索算法对选中的配送中心进行路线优化,并通过设定需要重新分配的客户数量的最大阈值来提高路线优化的效率。通过实例验算,将该算法和其他算法进行了比较,证明了该算法的可行性和有效性。

Tabu Search Algorithm for Location-Routing with Soft Time Windows

Location-routing is an important branch of route optimization in integrated logistics system.In view of LRPSTW complexity,a mixed-integer optimization model and a two-phase heruistic algorithm based on tabu search algorithm are proposed.In the first phase of the proposed algorithm,the tabu search algorithm is performed to determine the location of depots and the allocation of customers to the depots.And the swap*-opt* operater design can effectively search neighbourhood space of the solution.In the second phase,the routings for the selected depots are optimized by tabu search algorithm.By setting the maximal threshhold value of the reassigned customers in this phase,it can improve the routings optimization efficiency.The algorithm performance is compared with other algorithms by experiments.The proposed algorithm for location-routing problem with soft time windows is feasible and efficient.