基于两阶段启发式算法的物流配送选址-路径问题研究

doi:10.12005/orms.2017.0084

运筹与管理 ›› 2017, Vol. 26 ›› Issue (4): 70-75.DOI: 10.12005/orms.2017.0084

基于两阶段启发式算法的物流配送选址-路径问题研究

王道平, 徐展, 杨岑

北京科技大学东凌经济管理学院, 北京 100083

收稿日期:2013-12-04 出版日期:2017-04-25
作者简介:王道平(1964-),男,北京人,教授,博士生导师,研究方向为供应链管理、知识管理等;徐展(1991-),男,北京人,硕士研究生,研究方向为供应链管理;杨岑(1985-),女,山西人,博士研究生,研究方向为供应链管理、知识管理、系统工程。
基金资助:
国家自然科学基金资助项目(71172169);中央高校基本科研业务经费资助项目(FRF-BR-16-002B)

Study on Location-routing Problem of Logistics Distribution Based on Two-stage Heuristic Algorithm

WANG Dao-ping, XU Zhan, YANG Cen

Donglinks School of Economics and Management, Beijing University of Science and Technology, Beijing 100083,China

Received:2013-12-04 Online:2017-04-25

摘要/Abstract

摘要： 为了解决配送中心选址与带时间窗的多中心车辆路径优化组合决策问题,利用双层规划法建立了配送中心选址与车辆路径安排的多目标整数规划模型,针对该模型的特点,采用两阶段启发式算法进行了求解。首先,通过基于聚集度的启发式算法对客户进行分类,确定了备选配送中心的服务范围;然后,基于双层规划法,以配送中心选址成本最小作为上层规划目标,以车辆配送成本最小作为下层规划目标,建立了多目标整数规划模型;最后,利用改进的蚁群算法进行了求解。通过分析实例数据和Barreto Benchmark算例的实验结果,验证了该模型的有效性和可行性。

关键词: 运筹学, 选址-路径优化, 双层规划法, 蚁群算法, 客户重要度

Abstract: To solve the combined problem of distribution center location and multi-depot vehicle routing with time windows, using bi-level programming, the multi-objective integer planning model of distribution center location and vehicle routing is formulated. Taking into account the special feature of the model, we propose a suitable solving method. By utilizing two-stage heuristic algorithm, aggregation-based algorithm is firstly used to classify customers, and then, the memberships between customers and distributions center as well as the service area of alternative distribution center are determined. Secondly, based on bi-level programming, the multi-objective integer programming model is established. Its upper planning targets at the minimum cost of distribution center location, while lower planning at the minimum cost of vehicle transportation. Finally, by means of improved ant colony algorithm which introduces the crossover operator, objective values are obtained. Through the analysis of experimental data and Barreto Benchmark instances, we verify the feasibility and validity of the proposed model.

Key words: operational research, location-routing optimization, bi-level programming, ant colony algorithm, customer importance rate

中图分类号:

F252
O22

王道平, 徐展, 杨岑. 基于两阶段启发式算法的物流配送选址-路径问题研究[J]. 运筹与管理, 2017, 26(4): 70-75.

WANG Dao-ping, XU Zhan, YANG Cen. Study on Location-routing Problem of Logistics Distribution Based on Two-stage Heuristic Algorithm[J]. Operations Research and Management Science, 2017, 26(4): 70-75.

参考文献

[1] Fisher M L. Vehicle routing with time window: two optimization algorithms[J]. Operations Research, 1997, 45(3): 488-492.
[2] Osman I H. Metastrategy simulated annealing and tabu search algorithm for combinatorial optimization problems[J]. Annals of Operations Research, 1993, 41(3): 421-451.
[3] Patrice Perny, Olivier Spanjaard. A preference-based approach to spanning trees and shortest paths problems[J]. European Journal of Operational Research, 2005, 162(3): 584-601.
[4] 罗勇,陈治亚.基于改进遗传算法的物流配送路径优化[J].系统工程,2012,30(8):118-122.
[5] Polacek M R, Hartl R F, Doerner K, et al. A variable neighborhood search for the multi depot vehicle routing problem with time windows[J]. Journal of Heuristics, 2004, 10(6): 613-627.
[6] Cordeau J F, Laporte G, Mercier A. An improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows[J]. Journal of the Operational Research Society, 2004, 55(5): 542-546.
[7] 李敏,郭强,刘红丽.多车场多配送中心的物流配送问题研究[J].计算机工程与应用,2007,43(8):202-204,208.
[8] 李相勇,田澎.带时间窗和随机时间车辆路径问题:模型和算法[J].系统工程理论与实践,2009,29(8):81-90.
[9] Oded Berman, Zvi Drezner, George Wesolowsky O. Satisfying partial demand in facilities location[J]. IIE Transactions, 2002, 34(11): 971-978.
[10] Maro Vlachopoulou, George Silleos, Vassiliki Manthou. Geographic information system in warehouse site selection decisions[J]. International Journal of Production Economics, 2001, 71(1-3): 205-212.
[11] 秦固.基于蚁群优化的多物流配送中心选址算法[J].系统工程理论与实践,2006,26(4):120-124.
[12] 蒋忠中,汪定伟.B2C电子商务中配送中心选址优化的模型与算法[J].控制与决策,2005,20(10):1125-1128.
[13] Albareda-Sambola M, Teodor Gabriel Crainic. A compact model and tight bounds for a combined location-routing problem[J]. Computers and Operations Research, 2005, 32(3): 407-428.
[14] Christophe Duhamel, Philippe Lacomme, Christian Prins, et al. A GRASP×ELS approach for the capacitated location-routing problem[J]. Computers and Operations Research, 2010, 37(11): 1912-1923.
[15] Hokey Min, Vaidyanathan Jayaraman, Rajesh Srivastava. Combined location routing problems: a synthesis and future research directions[J]. European Journal of Operational Research, 2001, 6(108): 1-15.
[16] 张潜,高立群,胡祥培等.物流配送路径多目标优化的聚类-改进遗传算法[J].控制与决策,2003,18(4):418-422.
[17] 于滨,靳鹏欢,杨忠振.两阶段启发式算法求解带时间窗的多中心车辆路径问题[J].系统工程理论与实践,2012,32(8):1793-1800.
[18] Mirabi M, Fatemi Ghomi S M T, Jolai F. Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem[J]. Robotics and Computer-Integrated Manufacturing, 2010, 26(6): 564-569.
[19] Subramanian A, Penna P H V, Uchoa E, et al. A hybrid algorithm for the heterogeneous fleet vehicle routing problem[J]. European Journal of Operational Research, 2012, 221(2): 285-295.
[20] Barreto, Ferreira, Paix o, et al. Using clustering analysis in a capacitated location-routing problem[J]. European Journal of Operational Research, 2007, 179(3): 968-977.

基于两阶段启发式算法的物流配送选址-路径问题研究

Study on Location-routing Problem of Logistics Distribution Based on Two-stage Heuristic Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	丁肇炜, 杨建华, 王艾, 王欣. 面向突发事件的安保巡逻选址-路径优化研究[J]. 运筹与管理, 2021, 30(8): 1-6.
[2]	唐颖峰, 陈世平. 分布式数据流处理系统管理中负载均衡问题建模与求解[J]. 运筹与管理, 2021, 30(4): 155-162.
[3]	刘长石, 王松, 罗亮, 邓胜前. 时变路网条件下联合配送的开放式车辆路径问题[J]. 运筹与管理, 2021, 30(11): 26-33.
[4]	任剑锋, 叶春明, 杨枫. 带时间窗的车间搬运机器人路径优化建模及算法研究[J]. 运筹与管理, 2020, 29(5): 52-60.
[5]	陈萍, 董文哲, 于信尧. 新能源移动充电车路径优化问题研究[J]. 运筹与管理, 2020, 29(2): 12-18.
[6]	汪洪涛, 张翔, 王珂. 1996~2017年《Operations Research》期刊发文统计分析[J]. 运筹与管理, 2020, 29(2): 229-239.
[7]	王诺, 丁凯, 吴迪, 吴暖. 面向远海岛礁群的双向物流网络规划[J]. 运筹与管理, 2019, 28(6): 118-128.
[8]	陈江涛, 吕建秋. 基于知识图谱的运筹学发展现状及趋势研究[J]. 运筹与管理, 2019, 28(1): 194-199.
[9]	张萌,王能民. 重大事故规避的危险品运输车辆路径优化研究[J]. 运筹与管理, 2018, 27(8): 1-9.
[10]	刘艳秋,徐世达,蔡超. 部分联合运输策略下的物流车辆路径优化问题研究[J]. 运筹与管理, 2018, 27(8): 10-19.
[11]	张建同, 杨文娟. 基于优先级的进离港航班排序优化问题研究[J]. 运筹与管理, 2018, 27(6): 115-121.
[12]	王书勤, 黄茜. 军事定向越野路径优化问题建模及混合蚁群算法求解[J]. 运筹与管理, 2018, 27(4): 105-111.
[13]	高沛然, 张金隆, 艾学轶, 李明, 马自香. PLS-DEMATEL方法及其应用研究——以组织敏捷性的IT影响因素分析为例[J]. 运筹与管理, 2018, 27(3): 126-132.
[14]	郭小威, 李保刚, 滕克难. 基于可用度的复杂结构装备检修时机决策模型[J]. 运筹与管理, 2018, 27(2): 11-14.
[15]	韩文民, 陈婷, 高龙龙, 李正义, 翁红兵. 急件订单干扰下虚拟单元重调度[J]. 运筹与管理, 2018, 27(2): 68-78.