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

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

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

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 LRP,a two-phase 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.