【作者】 李青； 刘兆健； 薛军； 孙光圻；

【Author】 Li Qing, Liu Zhaojian, Xue Jim, Sun Guangqi(School of Transportation and Logistics, Dalian Maritime University, Dalian 116026)

【机构】 大连海事大学交通工程与物流学院；

【摘要】 定位——运输路线安排问题(Location-Routing Problem--LRP)是物流系统规划和设计中涉及到的一类复杂的组合优化问题,是NP-hard问题,只能用启发式(heuristic)或超启发式(metaheuristic)算法求解。根据对LRP问题的分析和所建立的数学模型,提出了一种用于求解该类问题的metaheuristic算法:禁忌搜索——蚁群混合算法。该算法在禁忌搜索算法的框架中嵌入蚁群算法,用禁忌搜索的方式搜索配送中心的定位方案,对于给定的定位方案通过蚁群算法求出优化的运输路线,运输路线安排优化的结果用于指导禁忌搜索的进一步搜索。禁忌搜索——蚁群混合算法在求解LRP问题的过程中整体考虑了定位和运输路线优化两方面的决策,能够充分搜索问题的解空间,有效地避免陷入“局部最优”。仿真实验证明了所提出算法的有效性。更多还原

【Abstract】 Location - Routing Problem (LRP) is complex combinatorial optimization problem in designing logistic systems. The proper methods to solve LRP are heuristics or metaheuristics because of its NP -hard feature. A hybrid algorithm combined tabu search algorithm with Ant Colony Optimization (ACO) was proposed based on the analysis of LRP and its mathematic model. The hybrid algorithm searched the candidate distribution centers and their customers using tabu search. Then ACO embodied in tabu search framework was performed to search the optimal routes for the given set of distribution centers and their customers. The results obtained by ACO were also used to guide the further search of tabu search. The hybrid algorithm considered the decisions of location and the decision of routing as a whole. The proposed algorithm can search the solution space sufficiently and the "local optimal" can be avoided effectively. Computer simulation shows that the algorithm is effective.更多还原