Location algorithm of mobile warehouse in express demand region with high strength
Article Text (Baidu Translation)
-
摘要: 研究了高强度快递需求区域移动仓库选址问题的特点, 以移动仓库总建设规模最小为目标函数, 以区域需求量和仓库服务能力为约束条件, 提出了基于多粒度集合覆盖问题的相遇蚁群算法。将需求点虚拟成粒子, 利用K-means算法对粒子聚类, 在划分好的粒子群里得到移动仓库备选点, 分别应用传统的蚁群算法和相遇蚁群算法进行实例验证。计算结果表明: 运用传统的蚁群算法, 运算时间为12.714 4s, 最优解个数为13, 最差解个数为15, 平均解个数为13, 解的正确率为79%;运用相遇蚁群算法, 运算时间为3.806 4s, 最优解个数为12, 最差解个数为13, 平均解个数为12, 解的正确率为98%, 移动仓库选址方案的建设数量为12, 有10个备选移动仓库是多余的。Abstract: The characteristic of location problem for mobile warehouse in express demand region with high strength was studied. The minimum total construction scale of mobile warehouse was taken as objective function, the region demand and service ability of mobile warehouse were taken as constraint conditions, and the meeting ant colony optimization(MACO) based on the set-covering problem of multiple granularities was put out. The demand points were regard as virtual particles, and K-means algorithm was used to cluster the particles. The preparation points of mobile warehouse were got from the divided particles, and the example verification was carried out by using traditional ACO and MACO respectively. Calculation result indicates that while traditional ACO is used, the computing time is 12.714 4 s, the optimal solution number is 13, the most poor solution number is 15, the average solution number is 13, and the correct rate of solution is 79%. While the proposed MACO is used, the computing time is 3.806 4 s, the optimal solution number is 12, the most poor solution number is 13, the average solution number is 12, the correct rate of solution is 98%, the construction number of location scheme for mobile warehouse is 12, and 10 preparation mobile warehouses are unnecessary.
-
表 1 粒子坐标与需求量
Table 1. Coordinates and demands of particles
粒子 1 2 3 4 5 6 7 8 9 坐标/m (22, 15) (34, 10) (46, 18) (46, 20) (28, 25) (42, 30) (46, 35) (50, 40) (44, 43) 需求量/(万单·月-1) 0.5 0.7 1.0 0.3 0.6 1.2 0.5 0.4 0.8 粒子 10 11 12 13 14 15 16 17 18 坐标/m (30, 37) (32, 50) (38.57) (18, 53) (14, 60) (26, 65) (45, 68) (30, 73) (23, 76) 需求量/(万单·月-1) 1.2 2.0 0.7 0.4 1.5 0.8 0.3 2.5 0.5 
下载: 导出CSV
表 2 移动仓库服务状况
Table 2. Service status of mobile warehouses
移动仓库 坐标/m 服务能力/(万单·月-1) 服务粒子 1 (36, 20) 3.2 1, 2, 3, 4, 5 2 (38, 37) 4.5 6, 7, 8, 9, 10 3 (20, 65) 3.0 13, 14, 15, 18, 19 4 (23, 53) 5.0 11, 13, 14, 15 5 (33, 61) 7.2 11, 12, 15, 16, 17, 18 6 (39, 71) 4.0 12, 16, 17, 20 7 (51, 80) 5.5 12, 20, 21, 22, 24 8 (41, 90) 4.6 20, 22, 23, 25, 26 9 (26, 98) 8.0 23, 25, 26, 27, 28, 29, 30 10 (15, 105) 3.4 28, 29, 30 11 (68, 16) 6.0 31, 32, 33, 34, 35 12 (76, 21) 7.1 32, 33, 34, 36, 38, 39 13 (82, 29) 9.3 33, 34, 36, 37, 38, 39, 40, 41 14 (88, 50) 6.9 40, 41, 42, 44, 45, 47 15 (80, 45) 6.5 38, 39, 41, 42, 44, 48 16 (95, 55) 3.4 43, 45, 46 17 (91, 62) 7.4 42, 43, 44, 45, 46, 47, 54 18 (94, 90) 4.1 55, 56, 57 19 (87, 78) 5.5 47, 53, 54, 56, 58 20 (80, 90) 6.0 52, 53, 57, 58, 59, 60 21 (79, 65) 7.8 44, 47, 48, 49, 50, 52, 53 22 (73, 80) 8.0 48, 49, 50, 51, 52, 59, 61
下载: 导出CSV
表 3 两种算法比较
Table 3. Comparison of two algorithms
算法 ACO MACO 最优解 13 12 最差解 15 13 平均解 13 12 正确率/% 79 98 运算时间/s 12.714 4 3.806 4
下载: 导出CSV
表 4 移动仓库选址方案
Table 4. Location schemes of mobile warehouses
移动仓库 1 2 3 5 7 9 坐标/m (36, 20) (38, 37) (20, 65) (33, 61) (51, 80) (26, 98) 服务能力/(万单·月-1) 3.2 4.5 3.0 7.2 5.5 8.0 服务粒子 1, 2, 3, 4, 5 6, 7, 8, 9, 10 13, 14, 15, 18, 19 11, 12, 15, 16, 17, 18 12, 20, 21, 22, 24 23, 25, 26, 27, 28, 29, 30 移动仓库 11 13 17 18 20 22 坐标/m (68, 16) (82, 29) (91, 62) (94, 90) (80, 90) (73, 80) 服务能力/(万单·月-1) 6.0 9.3 7.4 4.1 6.0 8.0 服务粒子 31, 32, 33, 34, 35 33, 34, 36, 37, 38, 39, 40, 41 42, 43, 44, 45, 46, 47, 54 55, 56, 57 52, 53, 57, 58, 59, 60 48, 49, 50, 51, 52, 59, 61
下载: 导出CSV
-
[1] 谷淑娟, 高学东, 刘燕驰, 等. 基于多尺度网格模型的物流配送中心选址候选集构建方法[J]. 控制与决策, 2011, 26(8): 1141-1146. https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201108007.htmGU Shu-juan, GAO Xue-dong, LIU Yan-chi, et al. Candi-date set construction method in distribution center location based on multi-scale gridding model[J]. Control and Deci-sion, 2011, 26(8): 1141-1146. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201108007.htm [2] 周爱莲, 李旭宏, 毛海军. 企业物流中心稳健性选址模型[J]. 交通运输工程学报, 2010, 10(1): 60-65. doi: 10.3969/j.issn.1671-1637.2010.01.011ZHOU Ai-lian, LI Xu-hong, MAO Hai-jun. Robusth loca-tion model of enterprise logistics center[J]. Journal of Traffic and Transportation Engineering, 2010, 10(1): 60-65. (in Chinese). doi: 10.3969/j.issn.1671-1637.2010.01.011 [3] 秦进, 史峰. 物流设施选址问题的双层模拟退火算法[J]. 系统工程, 2007, 25(2): 36-40. https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT200702007.htmQIN Jin, SHI Feng. Bi-level simulated annealing algorithm for facility location[J]. Systems Engineering, 2007, 25(2): 36-40. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT200702007.htm [4] 秦固. 基于蚁群优化的多物流配送中心选址算法[J]. 系统工程理论与实践, 2006, 26(4): 120-124. doi: 10.3321/j.issn:1000-6788.2006.04.020QIN Gu. Logistics distribution center allocation based on ant colony optimization[J]. Systems Engineering—Theory and Practice, 2006, 26(4): 120-124. (in Chinese). doi: 10.3321/j.issn:1000-6788.2006.04.020 [5] KUO M S. Optimal location selection for an international dis-tribution center by using a new hybrid method[J]. Expert Systems with Applications, 2011, 38(6): 7208-7221. doi: 10.1016/j.eswa.2010.12.002 [6] BATANOVIC V, PETROVIC D, PETROVIC R. Fuzzy logic based algorithms for maximum covering location problems[J]. Information Sciences, 2009, 179(1/2): 120-129. [7] SUN Hui-jun, GAO Zi-you, WU Jian-juan. A bi-level pro-gramming model and solution algorithm for the location of logistics distribution centers[J]. Applied Mathematical Model-ling, 2008, 32(4): 610-616. doi: 10.1016/j.apm.2007.02.007 [8] YANG Li-xing, JI Xiao-yu, GAO Zi-you, et al. Logistics distribution centers location problem and algorithm under fuzzy environment[J]. Journal of Computational and Applied Mathematics, 2007, 208(2): 303-315. doi: 10.1016/j.cam.2006.09.015 [9] 黄宇. 快递配送中心配送模型及应用研究[D]. 长沙: 长沙理工大学, 2010.HUANG Yu. Research on express distribution center distri-bution model and its application[D]. Changsha: Changsha University of Science and Technology, 2010. (in Chinese). [10] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66. doi: 10.1109/4235.585892 [11] MULLEN R J, MONEKOSSO D, BARMAN S, et al. A review of ant algorithms[J]. Expert Systems with Applications, 2009, 36(6): 9608-9617. doi: 10.1016/j.eswa.2009.01.020 [12] CHEN C H, TING C J. Combining Lagrangian heuristic and ant colony system to solve the single source capacitated facility location problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2008, 44(6): 1099-1122. doi: 10.1016/j.tre.2007.09.001 [13] 王非, 孙浩杰, 罗卫华, 等. 指定备选点的配送中心选址-库存模型[J]. 长安大学学报: 自然科学版, 2012, 32(2): 91-95. https://www.cnki.com.cn/Article/CJFDTOTAL-XAGL201203018.htmWANG Fei, SUN Hao-jie, LUO Wei-hua, et al. Location-inventory model of distribution center with appointed alterna-tive location[J]. Journal of Chang'an University: Natural Science Edition, 2012, 32(2): 91-95. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XAGL201203018.htm [14] 李卫江, 郭晓汾, 张毅, 等. 基于MATLAB优化算法的物流中心选址[J]. 长安大学学报: 自然科学版, 2006, 26(3): 76-79. https://www.cnki.com.cn/Article/CJFDTOTAL-XAGL200603019.htmLI Wei-jiang, GUO Xiao-fen, ZHANG Yi, et al. Logistics center location based on MATLAB optimization algorithm[J]. Journal of Chang'an University: Natural Science Edition, 2006, 26(3): 76-79. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XAGL200603019.htm [15] 冯富宝. 集合覆盖问题研究[D]. 济南: 山东大学, 2006.FENG Fu-bao. Research on set cover problem[D]. Jinan: Shandong University, 2006. (in Chinese). [16] 张燕平, 张铃, 吴涛. 不同粒度世界的描述法——商空间法[J]. 计算机学报, 2004, 27(3): 328-333. doi: 10.3321/j.issn:0254-4164.2004.03.006ZHANG Yan-ping, ZHANG Ling, WU Tao. The representation of different granular worlds: aquotient space[J]. Chinese Journal of Computers, 2004, 27(3): 328-333. (in Chinese). doi: 10.3321/j.issn:0254-4164.2004.03.006 [17] 覃文文, 戢晓峰. 基于K-means聚类的快递企业客户细分方法[J]. 世界科技研究与发展, 2011, 33(6): 955-958. doi: 10.3969/j.issn.1006-6055.2011.06.003QIN Wen-wen, JI Xiao-feng. Researches on customer segmenta-tion of express enterprise based on K-means clustering[J]. World Sci-tech R and D, 2011, 33(6): 955-958. (in Chinese). doi: 10.3969/j.issn.1006-6055.2011.06.003 [18] 寿涌毅, 赖昌涛, 吕如福. 班轮船舶调度多目标优化模型与蚁群算法[J]. 交通运输工程学报, 2011, 11(4): 84-88. http://transport.chd.edu.cn/article/id/201104013SHOU Yong-yi, LAI Chang-tao, LU Ru-fu. Multi-objective optimization model and colony optimization of liner ship scheduling[J]. Journal of Traffic and Transportation Engin-eering, 2011, 11(4): 84-88. (in Chinese). http://transport.chd.edu.cn/article/id/201104013 [19] STUTZLE T, HOOS H. Max-min ant system[J]. Future Generation Computer System, 2000, 16(8): 889-914. [20] 孙启鹏, 吴群琪. 运输需求生成机理及其规律[J]. 长安大学学报: 社会科学版, 2008, 10(2): 7-11, 15. https://www.cnki.com.cn/Article/CJFDTOTAL-XBJZ200802004.htmSUN Qi-peng, WU Qun-qi. Transport demand generating mechanism in corridor and its typical law[J]. Journal of Chang'an University: Social Science Edition, 2008, 10(2): 7-11, 15. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XBJZ200802004.htm [21] RANDALL M. Solution approaches for the capacitated single allocation hub location problem using ant colony optimization[J]. Computational Optimization Applications, 2008, 39(2): 239-261. [22] CHEN J F. A heuristics for the capacitated single allocation hub location problem[J]. Lecture Notes in Electrical Engin-eering, 2008(5): 185-196. [23] 胡郁葱, 商慧丽, 李敏. 容量限制条件下改进的地下快速路集散点选择模型[J]. 中国公路学报, 2012, 25(3): 135-140. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201203016.htmHU Yu-cong, SHANG Hui-li, LI Min. Improved depot choice model of underground expressway in the condition of capacity restraint[J]. China Journal of Highway and Trans-port, 2012, 25(3): 135-140. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201203016.htm [24] 徐红梅, 杨兆升, 闫长文, 等. 基于蚁群算法求解物流订单派送问题[J]. 长安大学学报: 自然科学版, 2007, 27(6): 84-86. https://www.cnki.com.cn/Article/CJFDTOTAL-XAGL200706018.htmXU Hong-mei, YANG Zhao-sheng, YAN Chang-wen, et al. Solving appoint order form job problem based on ant colony system[J]. Journal of Chang'an University: Natural Science Edition, 2007, 27(6): 84-86. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XAGL200706018.htm -
点击查看大图
图(9) / 表(4)
计量
- 文章访问数: 929
- HTML全文浏览量: 188
- PDF下载量: 1204
- 被引次数: 0
