求解两级定位—路径问题的粒子群算法

计算机应用 ›› 2013, Vol. 33 ›› Issue (08): 2261-2264.

求解两级定位—路径问题的粒子群算法

陈久梅¹,²,龚英¹,²

1. 电子商务及供应链系统重庆市重点实验室(重庆工商大学)，重庆 400067
2. 重庆工商大学商务策划学院，重庆 400067;

收稿日期:2013-02-24 修回日期:2013-04-15 出版日期:2013-08-01 发布日期:2013-09-11
通讯作者: 陈久梅
作者简介:陈久梅(1976-)，女，重庆人，副教授，博士，主要研究方向：物流系统优化、智能算法;
龚英(1968-)，女，重庆人，教授，主要研究方向：逆向物流。
基金资助:
国家自然科学基金资助项目

Particle swarm optimization for two-echelon location-routing problem

CHEN Jiumei¹,²,GONG Ying¹,²

1. Chongqing Key Laboratory of Electronic Commerce & Supply Chain System (Chongqing Technology and Business University), Chongqing 400067,China
2. School of Business Planning, Chongqing Technology and Business University, Chongqing 400067, China

Received:2013-02-24 Revised:2013-04-15 Online:2013-09-11 Published:2013-08-01
Contact: CHEN Jiumei

摘要/Abstract

摘要： 为求解配送网络中的两级定位—路径问题，提出一种在粒子更新过程中融入路径重连启发式搜索策略的粒子群算法。其中，根据两级定位—路径问题中解的属性，提出以中转站、路径、边为对象的三个路径重连搜索模块；同时基于搜索模块的不同组合，提出四种路径重连策略。应用不同规模算例测试结果表明，该粒子群算法能有效求解两级定位—路径问题，且路径重连策略一的求解效率较高，策略二求解的稳定性较好，策略三求解时各方面均无突出表现，策略四求解时解的质量较高。

关键词: 两级定位—路径问题, 粒子群算法, 路径重连, 配送

Abstract: In order to solve two-echelon location-routing problem of distribution network, particle swarm optimization with path relinking integrated into particle update process was proposed. Three path relinking search modules with regarding transfer station, path and edge as the object were put forward according to the attributes of the solution of two-echelon location-routing problem. At the same time, on the basis of the different combinations of these search modules, four kinds of path relinking strategy were put forward. The test results on different scale examples show that the particle swarm optimization can solve two-echelon location-routing problem effectively, the first path relinking strategy has higher efficiency. The second one has higher stability, the third one has no obvious performance in every aspect, and the fourth one has higher quality solution. Key words: two-echelon location - routing problem; particle swarm optimization; path relinking; distribution

Key words: Two-Echelon Location-Routing Problem (2E-LRP), Particle Swarm Optimization (PSO), path relinking, distribution

中图分类号:

TP18

陈久梅龚英. 求解两级定位—路径问题的粒子群算法[J]. 计算机应用, 2013, 33(08): 2261-2264.

CHEN Jiumei GONG Ying. Particle swarm optimization for two-echelon location-routing problem[J]. Journal of Computer Applications, 2013, 33(08): 2261-2264.

参考文献

［1］NAGY G, SALHI S. Location-routing: Issues, models and methods［J］.European Journal of Operational Research, 2007,177(2):649-672.

［2］LIN C K Y, CHOW C K，CHEN A. A location routing-loading problem for bill delivery services ［J］. Computers & Industrial Engineering, 2002,5(25):43.

［3］AMBROSINOA D, SCIOMACHENA A, SCUTELLAB M G. A heuristic based on multi-exchange techniques for a regional fleet assignment location-routing problem ［J］. Computers & Operations Research,2009,36(2):442-460.

［4］CONTARDO C, HEMMELMAYR V, CRAINIC T G. Lower and upper bounds for the two-echelon capacitated location-routing problem ［R］. Montreal: CIRRELT,2011.

［5］STERLE C. Location-routing models and methods for freight distribution and infomobility in city logistics ［D］. Napoli: Università degli Studi di Napoli “Federico II”,2009.

［6］BOCCIA M,CRAINIC T G, SFORZA A, et al. A metaheuristic for a two echelon location-routing problem ［J］. Experimental Algorithms, 2010, 6049:288-301.

［7］CRAINIC T G，SFORZA A，STERLE C. Tabu search heuristic for a two-echelon location-routing problem ［R］. Montreal: CIRRELT,2011.

［8］JIN L, ZHU Y L, SHEN H,et al. A hybrid genetic algorithm for two-layer location-routing problem ［C］// Proceedings of 2010 4th International Conference on New Trends in Information Science and Service Science. Piscataway: IEEE, 2010: 642-645.

［9］王绍仁,马祖军.震害紧急响应阶段应急物流系统中的LRP［J］.系统工程理论与实践, 2011,31(8):1497-1507.

［10］NGUYEN V P, PRINS C, PRODHON C. Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking ［J］. European Journal of Operational Research,2012,216(1): 113-126.

［11］NGUYEN V P, PRINS C, PRODHON C. A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem ［J］. Engineering Applications of Artificial Intelligence,2012,25(1): 56-71.

［12］KENNEDY J，EBERHART R. Particle swarm optimization ［C］// Proceedings of 1995 International Conference on Neural Networks. Washington, DC: IEEE Computer Society, 1995：1942-1948.

［13］KHARE A, RANGNEKAR S. A review of particle swarm optimization and its applications in Solar Photovoltaic system ［J］. Applied Soft Computing,2012, 13(5): 2997-3006.

［14］RESENDE M G C, RIBEIRO C C, GLOVER F, et al. Scatter search and path-relinking: fundamentals, advances, and applications ［M］// Handbook of Metaheuristics: International Series in Operations Research & Management Science Volume 146. Berlin: Springer-Verlag, 2010: 87-107.

［15］胡大伟.设施定位和车辆路线问题模型及其启发式算法研究［D］.西安:长安大学,2008:129-133.

[1]	郑李萍, 王建强, 张玉召, 董祚帆. 多时空配送任务驱动的无人车队车辆数优化方法[J]. 计算机应用, 2021, 41(5): 1406-1411.
[2]	郝芃斐, 池瑞, 屈志坚, 涂宏斌, 池学鑫, 张地友. 求解铁路物流配送中心选址问题的改进灰狼优化算法[J]. 计算机应用, 2021, 41(10): 2905-2911.
[3]	杨晓华, 郭健全. 模糊环境下多周期多决策生鲜闭环物流网络[J]. 计算机应用, 2019, 39(7): 2168-2174.
[4]	武旭晨, 朴春慧, 蒋学红. 基于GPU并行计算的电动出租车新建充电站选址模型[J]. 计算机应用, 2019, 39(10): 3071-3078.
[5]	王庆荣, 王瑞峰. 基于改进粒子群算法的配电网重构策略[J]. 计算机应用, 2018, 38(9): 2720-2724.
[6]	曹琦, 曹阳. 应急物资配送车辆调度模型与优化综述[J]. 计算机应用, 2018, 38(8): 2416-2422.
[7]	石建力, 张锦. 行驶时间随机的分批配送车辆路径问题模型与算法[J]. 计算机应用, 2018, 38(2): 573-581.
[8]	邱晗光, 周愉峰. 基于嵌套Logit选择模型的城市配送自提柜选址路径问题[J]. 计算机应用, 2018, 38(2): 582-588.
[9]	熊瑞琦, 马昌喜. 多配送中心危险货物配送路径鲁棒优化[J]. 计算机应用, 2017, 37(5): 1485-1490.
[10]	谢红侠, 马晓伟, 陈晓晓, 邢强. 基于多种群的改进粒子群算法多模态优化[J]. 计算机应用, 2016, 36(9): 2516-2520.
[11]	韩雪, 程奇峰, 赵婷婷, 张利民. 基于粒子滤波重采样与变异操作的改进粒子群算法[J]. 计算机应用, 2016, 36(4): 1008-1014.
[12]	何莉, 刘晓东, 李松阳, 张倩. 多核环境下并行粒子群算法[J]. 计算机应用, 2015, 35(9): 2482-2485.
[13]	闫华, 高黎, 刘国勇, 王红旗. 基于多时间窗的油料保障模型[J]. 计算机应用, 2015, 35(7): 2096-2100.
[14]	尚俊娜, 刘春菊, 岳克强, 李林. 基于改进双系统协同进化算法的无线传感器网络节点定位[J]. 计算机应用, 2015, 35(6): 1514-1518.
[15]	于泉, 孙顺远, 徐保国, 陈淑娟. 基于改进粒子群算法的无线传感器网络节点定位[J]. 计算机应用, 2015, 35(6): 1519-1522.