定位-车辆路径问题的两阶段混合启发式算法

A Two-Phase Hybrid Heuristic Algorithm for Location-Routing Problem

定位-车辆路径问题(LRP)集成了设施定位分配和车辆路径决策,属于NP-hard难题.为有效求解实际大规模的具有设施容量约束和车辆容量约束的LRP问题,设计了基于禁忌搜索及双种群蚁群算法的两阶段混合启发式算法.算法第1阶段采用禁忌搜索算法确定设施定位及客户分配,算法第2阶段采用双种群蚁群算法优化车辆路径,蚁群间的通信与协调通过信息素共享来实现.通过仿真试验并与其他启发式算法进行对比,结果表明,该算法是可行和有效的.

The location-routing problem （LRP）, which combines the facility location allocation and vehicle routing decisions, is an NP-hard problem. In order to solve practical large scale capacitated I,RP, a twophase hybrid heuristic algorithm based on taboo search and double population ant colony search approach was proposed. In the first phase of the proposed algorithm, a taboo search is performed on the location variables to determine the location of facilities and the allocation of customer to the facilities. In the second phase, in order to obtain a good routing for the given configuration, a double population ant colony algorithm is run on the routing variables through communication and collaboration between ant colonies. To compare the proposed algorithm with other heuristic algorithms, a series of computational experiments are done on randomly generated test problems. The simulation results demonstrate that the above approach is feasible and efficient.