[1]张玉州,张子为.考虑动态客户需求的物资配送问题求解方法[J].西安交通大学学报,2020,54(08):124-131.[doi:10.7652/xjtuxb202008016]
 ZHANG Yuzhou,ZHANG Ziwei.A Strategy for Solving Material Distribution Considering Dynamic Customer Demand[J].Journal of Xi'an Jiaotong University,2020,54(08):124-131.[doi:10.7652/xjtuxb202008016]
点击复制

考虑动态客户需求的物资配送问题求解方法
分享到:

《西安交通大学学报》[ISSN:0253-987X/CN:61-1069/T]

卷:
54
期数:
2020年第08期
页码:
124-131
栏目:
出版日期:
2020-08-10

文章信息/Info

Title:
A Strategy for Solving Material Distribution Considering Dynamic Customer Demand
文章编号:
0253-987X(2020)08-0124-08
作者:
张玉州 张子为
安庆师范大学计算机与信息学院, 246133, 安徽安庆
Author(s):
ZHANG Yuzhou ZHANG Ziwei
School of Computer and Information, Anqing Normal University, Anqing, Anhui 246133, China
关键词:
动态客户需求 车辆路径问题 遗传算法 需求调节算子
Keywords:
dynamic customer demand vehicle routing problem genetic algorithm demand adjustment operator
分类号:
TP301
DOI:
10.7652/xjtuxb202008016
文献标志码:
A
摘要:
为明确需求预测方向和减少预测偏差,提出了一种考虑动态客户需求的物资配送问题求解方法。依据客户历史需求,以泊松分布模拟需求变化情况,建立需求预测模型,得到客户初始预测需求,并在此基础上建立了需求不确定的物资配送模型。为求解该模型,设计了一种预测需求可调节的遗传算法。在遗传算法局部搜索阶段,提出了需求调节算子。该算子以一定概率对客户初始预测需求进行调节,以符合泊松分布的需求变化量减少预测需求,同时对车辆间的顾客进行调整,顾客以调节后的预测需求挑选最小需求客户,移动该客户至其他最低载货车辆中并调整该车辆服务的顾客顺序,整个调节过程以最低配送成本为标准,保留最优配送路径。从标准车辆路径问题测试数据库中挑选10个典型样例进行测试,结果表明,与经典的最近邻算法和遗传算法对比,所提算法在所有算例中均取得了总成本最小值,在90%的算例中取得了运输成本最小值,在70%的算例中取得了车辆成本最小值。
Abstract:
To clarify the direction of demand forecast and reduce the forecast deviation, a strategy considering dynamic customer demand is proposed for material distribution. Following the historical demand of the customers, a Poisson distribution is used to simulate the changes in demand, and a demand forecasting model is established to obtain the initial forecasted demand for the customers. Then a material distribution model with uncertain demand is constructed. To solve the distribution model, a genetic algorithm with adjustable forecasting demand(GAAFD)is designed. In the local search stage of GAAFD, a demand adjustment operator is introduced. This operator adjusts the initial forecasted demand with a certain probability to obey Poisson distribution of the demand changes so that the forecasted demand can be reduced, and it simultaneously adjusts the customers between vehicles. The customers are moved to the other lowest cargo vehicle and sequenced for the vehicle service. The lowest delivery cost is treated as the purpose and the optimal delivery routes are saved. To verify the proposed GAAFD, ten typical test instances are selected from the benchmark test database of the vehicle routing problem, and compared with the representative algorithms, i.e. the classic nearest neighbor algorithm and genetic algorithm without the adjusting operator. The results show that for the ten test instances, GAAFD reaches the minimum total cost obtained in all instances, and in 90% of the instances the minimum transportation cost is achieved, in 70% of the instances the minimum vehicle cost is achieved.

参考文献/References:

[1] PSARAFTIS H N. Dynamic vehicle routing: status and prospects [J]. Annals of Operations Research, 1995, 61(1): 143-164.
[2] 周鲜成, 王莉, 周开军, 等. 动态车辆路径问题的研究进展及发展趋势 [J]. 控制与决策, 2019, 34(3): 449-458.
ZHOU Xiancheng, WANG Li, ZHOU Kaijun, et al. Research progress and development trend of dynamic vehicle routing problem [J]. Control and Decision, 2019, 34(3): 449-458.
[3] PILLAC V, GUÉRET C, MEDAGLIA A L. An event-driven optimization framework for dynamic vehicle routing [J]. Decision Support Systems, 2012, 54(1): 414-423.
[4] ARMAS J A, BATISTA B M. Variable neighborhood search for a dynamic rich vehicle routing problem with time windows [J]. Computers & Industrial Engineering, 2015, 85: 120-131.
[5] AZI N, GENDREAU M, POTVIN J Y. A dynamic vehicle routing problem with multiple delivery routes [J]. Annals of Operations Research, 2012, 199(1): 103-112.
[6] ABDALLAH A M F M, ESSAM D L, SARKER R A. On solving periodic re-optimization dynamic vehicle routing problems [J]. Applied Soft Computing, 2017, 55: 1-12.
[7] 胡乔宇, 杨琨, 刘冉. 考虑随机客户需求的两级车辆路径问题研究 [J]. 工业工程与管理, 2018, 23(5): 74-81.
HU Qiaoyu, YANG Kun, LIU Ran. Vehicle routing problem with stochastic demands in two-echelon logistics [J]. Industrial Engineering and Management, 2018, 23(5): 74-81.
[8] KUO R J, WIBOWO B S, ZULVIA F E. Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time [J]. Applied Mathematical Modelling, 2016, 40(23/24): 9990-10001.
[9] HAGHANI A, JUNG S. A dynamic vehicle routing problem with time-dependent travel times [J]. Computers & Operations Research, 2005, 32(11): 2959-2986.
[10] 段征宇, 雷曾翔, 孙硕, 等. 随机时变车辆路径问题的多目标鲁棒优化方法 [J]. 西南交通大学学报, 2019, 54(3): 565-572.
DUAN Zhengyu, LEI Zengxiang, SUN Shuo, et al. Multi-objective robust optimisation method for stochastic time-dependent vehicle routing problem [J]. Journal of Southwest Jiaotong University, 2019, 54(3): 565-572.
[11] 李桃迎, 吕晓宁, 李峰, 等. 考虑动态需求的外卖配送路径优化模型及算法 [J]. 控制与决策, 2019, 34(2): 406-413.
LI Taoying, LÜ Xiaoning, LI Feng, et al. Routing optimization model and algorithm for takeout distribution with multiple fuzzy variables under dynamics demand [J]. Control and Decision, 2019, 34(2): 406-413.
[12] 张景玲, 赵燕伟, 王海燕, 等. 多车型动态需求车辆路径问题建模及优化 [J]. 计算机集成制造系统, 2010, 16(3): 543-550.
ZHANG Jingling, ZHAO Yanwei, WANG Haiyan, et al. Modeling and algorithms for a dynamic multi-vehicle routing problem with customers' dynamic requests [J]. Computer Integrated Manufacturing Systems, 2010, 16(3): 543-550.
[13] 饶卫振, 金淳, 刘锋, 等. 一类动态车辆路径问题模型和两阶段算法 [J]. 交通运输系统工程与信息, 2015, 15(1): 159-166.
RAO Weizhen, JIN Chun, LIU Feng, et al. Model and two-stage algorithm on dynamic vehicle routing problem [J]. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(1): 159-166.
[14] 刘霞, 齐欢. 带时间窗的动态车辆路径问题的局部搜索算法 [J]. 交通运输工程学报, 2008, 8(5): 114-120.
LIU Xia, QI Huan. Local search algorithm of dynamic vehicle routing problem with time window [J]. Journal of Traffic and Transportation Engineering, 2008, 8(5): 114-120.
[15] ZHOU L, BALDACCI R, VIGO D, et al. A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution [J]. European Journal of Operational Research, 2018, 265(2): 765-778.
[16] FERREIRA J C, STEINER M T A, GUERSOLA M S. A vehicle routing problem solved through some metaheuristics procedures: a case study [J]. IEEE Latin America Transactions, 2017, 15(5): 943-949.
[17] OSTERMEIER M, HUBNER A. Vehicle selection for a multi-compartment vehicle routing problem [J]. European Journal of Operational Research, 2018, 269(2): 682-694.
[18] HU C, LU J, LIU X, et al. Robust vehicle routing problem with hard time windows under demand and travel time uncertainty [J]. Computers & Operations Research, 2018, 94: 139-153.
[19] 贺国光, 崔岩, 王桂珠. 单个交叉路口到车服从泊松分布条件下控制动态响应的仿真研究 [J]. 系统工程, 2002, 20(5): 65-71.
HE Guoguang, CUI Yan, WANG Guizhu. Simulation study on dynamic response under the condition of Poisson arrival for an intersection [J]. Systems Engineering, 2002, 20(5): 65-71.
[20] 高镜媚, 汪定伟. 基于仿真的优化及其在多级库存系统中的应用 [J]. 系统仿真学报, 2009, 21(22): 47-52.
GAO Jingmei, WANG Dingwei. Simulation-based optimization and its application in multi-echelon inventory system [J]. Journal of System Simulation, 2009, 21(22): 47-52.
[21] 温创新, 邱一凡, 孙军. 基于大数据和泊松分布的配件预测模型分析与建模 [J]. 计算机与数字工程, 2014, 42(8): 1412-1414.
WEN Chuangxin, QIU Yifan, SUN Jun. Fitting prediction model analysis and modeling based on bulk data and Possion distribution [J]. Computer & Digital Engineering, 2014, 42(8): 1412-1414.
[22] University of Malaga. Capacitated VRP instances [EB/OL]. [2020-03-10]. http:∥neo.lcc.uma.es/vrp/vrp-instances/.

备注/Memo

备注/Memo:
收稿日期: 2020-03-12。作者简介: 张玉州(1976—),男,教授。基金项目: 安徽省自然科学基金资助项目(1808085 MF173,1908085MF194); 安徽省高校省级自然科学研究重点资助项目(KJ2016A438)。
更新日期/Last Update: 2020-08-10