多油品供给受限下多油库被动配送车辆路径问题研究

doi:10.16381/j.cnki.issn1003-207x.2018.1472

摘要/Abstract

摘要： 成品油供给不足将导致加油站油品订单无法完全满足，如何安排有限油品的合理配送对保障能源供给安全至关重要。为此，本文考虑有限供给下不同客户配送的优先次序，开展配送计划、车辆调度和路径优化等油品配送网络规划活动，对多油品供给受限情况下多油库被动配送车辆路径问题（Multiple Depot Vehicle Routing Problem，MDVRP）进行深入研究。首先，文章构建了考虑需求优先等级和配送成本的多油品多油库车辆路径规划多目标优化模型。其次，采用多目标粒子群优化算法（Multi-Objective Particle Swarm Optimization，MOPSO）对模型进行求解，以实现车辆高效调度和油品配送路径优化。最后，基于CNPC在青岛市部分油库和加油站点的数据信息，构建油品配送网络进行实证检验。算例结果显示，配送车辆路径经过优化后，生成Pareto非劣解集，配送成本显著降低，配送满足率明显提高，这也进一步验证了该模型及相关算法的可行性和有效性。

关键词: MDVRP, 资源受限, 成品油配送, 多目标优化, MOPSO

Abstract: The insufficient supply of refined oil will cause that the oil gas stationcan't fully meet the orders. How to arrange the reasonable distribution of limited oil is essential to ensure the safety of energy supply. To this end, the distribution priority of different customers under limited supply is considered, distribution planning, vehicle scheduling, path optimization and other oil distribution network planning activities are carried out, in-depth study on the Multiple Depot Vehicle Routing Problem (MDVRP) with multi-oil supply constraints is conducted. Firstly, a multi-objective optimization model of vehicle routing for multi-oil products and multi-oil depots is constructed, which considers the priority of demand and the cost of distribution. Secondly, the Multi-Objective Particle Swarm Optimization (MOPSO) is used to solve the model to achieve efficient vehicle scheduling and oil distribution routing optimization. Finally, based on the data information of CNPC in some oil depots and fueling stations in Qingdao, an oil distribution network is constructed for empirical testing. The results of the example show that the Pareto optimal set is generated after the optimization of vehicle routing, the distribution cost is significantly reduced, and the delivery satisfaction rate is significantly improved, which further verifies the feasibility and effectiveness of the model and related algorithms.The model and algorithm can be further extended to various supply and demand situations, which is helpful to solve the distribution problem of refined oil products with different priority of gas stations.

Key words: MDVRP, resource constrained, refined oil distribution, multi-objective optimization, MOPSO

中图分类号:

F252.5

徐小峰, 林姿汝, 周鹏. 多油品供给受限下多油库被动配送车辆路径问题研究[J]. 中国管理科学, 2021, 29(5): 157-165.

XU Xiao-feng, LIN Zi-ru, ZHOU Peng. Research on Vehicle Routing Problem of Multiple Oil Depot Passive Distribution under Multi Oil Supply Constraints[J]. Chinese Journal of Management Science, 2021, 29(5): 157-165.

参考文献

[1] 王博弘,梁永图,张浩然,等.成品油二次配送研究进展[J].油气储运,2018,37(2):121-126.
[2] 李敏, 倪少权, 周凌,等. 基于订单邻域的成品油二次配送中带时间窗车辆路径规划问题[J]. 计算机集成制造系统, 2015, 21(8):2158-2169.
[3] 王旭坪, 詹红鑫, 孙自来,等. 基于蚁群禁忌混合算法的成品油多舱配送路径优化研究[J]. 系统工程理论与实践, 2017, 37(12):3215-3226.
[4] Xu Xiaofeng, Hao Jun, Deng Yirui, et al. Design optimization of resource combination for collaborative logistics network under uncertainty[J]. Applied Soft Computing, 2017, 560(7):684-691.
[5] Olivera A, Viera O. Adaptive memory programming for the vehicle routing problem with multiple trips[J]. Computers & Operations Research, 2005, 34(1):28-47.
[6] Brown G G, Graves G W. Real-time dispatch of petroleum tank trucks[J]. Management Science, 1979, 27(1):19-32.
[7] 余晓钟, 刘鸿渊, 陈健声. 基于缺货条件的成品油二次运输成本优化[J]. 西南石油大学学报(自然科学版), 2009, 31(5):167-170, 209.
[8] 王剑, 王红卫. 基于混合遗传算法的资源受限的运输任务调度[J]. 计算机工程与应用, 2007, 43(31):34-38.
[9] Wang Xuping, Zhan Hongxin, Zhang Jun. Research of oil product secondary distribution optimization based on collaborative distribution[J]. Procedia Computer Science, 2015, 60(1):1367-1376.
[10] 唐亮, 何杰, 靖可,等. 时间窗口约束下基于改进蚁群算法的协同制造调度研究[J]. 中国管理科学, 2018, 26(4):97-107.
[11] 陈玉光,陈志祥.基于准时送货和最小耗油的配送车辆路径问题研究[J].中国管理科学,2015,23(S1):156-164.
[12] 石琴, 陈朝阳, 覃运梅. 多目标物流网络优化模型的研究[J]. 中国管理科学, 2005,(4):40-43.
[13] 裴军, 刘心报, 范雯娟,等. 基于生产与运输集成的供应链调度优化问题[J]. 中国管理科学, 2012, 20(S2):586-593.
[14] Xu Xiaofeng, Hao Jun,Yu Lean, et al. Fuzzy optimal allocation model for task-resource assignment problem in collaborative logistics network[J]. IEEE Transactions on Fuzzy Systems, 2019,75(5):1112-1125.
[15] 葛显龙, 许茂增, 王伟鑫. 多车型车辆路径问题的量子遗传算法研究[J]. 中国管理科学, 2013, 21(1):125-133.
[16] 潘雯雯, 郭海湘, 周光勇,等. 基于两阶段算法的需求可拆分多车型车辆路径问题[J]. 中国管理科学, 2016, 24(S1):55-61.
[17] 郎茂祥, 胡思继. 用混合遗传算法求解物流配送路径优化问题的研究[J]. 中国管理科学, 2002, 10(5):51-56.
[18] Allahviranloo M, Chow J, Recker W W.Selective vehicle routing problems under uncertainty without recourse[J]. Transportation Research Part E, 2014, 62(2):68-88.
[19] 王华东, 李巍. 粒子群算法的物流配送路径优化研究[J]. 计算机仿真, 2012, 29(5):243-246.
[20] 关菲, 张强. 模糊多目标物流配送中心选址模型及其求解算法[J]. 中国管理科学, 2013, 21(S1):57-62.
[21] Luo Jianping, Chen Minrong. Multi-phase modified shuffled frog leaping algorithm with extremal optimization for the MDVRP and the MDVRPTW[J]. Computers & Industrial Engineering, 2014, 72(1):84-97.
[22] 毕志升, 郑炯彬, 蔡桂艳. 基于高维多目标优化的多车场车辆路径问题[J]. 计算机与数字工程, 2017, 45(7):1298-1304, 1317.
[23] 李霄玉, 姚骏. 解决多目标旅行商问题的改进NSGA-Ⅱ算法[J]. 工业控制计算机, 2018, 31(4):103-104.
[24] 郭海湘, 杨娟, 於世为,等. 带服务优先级的煤矿物资配送车辆路径问题[J]. 系统管理学报, 2012, 21(1):133-144.
[25] Ghoddousi P, Eshtehardian E, Jooybanpour S, et al. Multi-mode resource-constrained discrete time-cost-resource optimization in project scheduling using non-dominated sorting genetic algorithm[J]. Automation in Construction, 2013, 30(30):216-227.
[26] Chakrabortty R K, Sarker R A, Essam D L. Multi-mode resource constrained project scheduling under resource disruptions[J]. Computers and Chemical Engineering, 2016, 88(5):13-29.
[27] Xu Xiaofeng, Zhang Wei, Li Ning, et al. A bi-level programming model of resource matching for collaborative logistics network in supply uncertainty environment[J]. Journal of the Franklin Institute, 2015, 352(9):3873-3884.
[28] Geiger M J. A multi-threaded local search algorithm and computer implementation for the multi-mode, resource-constrained multi-project scheduling problem[J]. European Journal of Operational Research, 2017, 256(3):729-741.
[29] El-Abbasy M S, Elazouni A, Zayed T. MOSCOPEA:Multi-objective construction scheduling optimization using elitist non-dominated sorting genetic algorithm[J]. Automation in Construction,2016,71:153-170.
[30] Maghsoudlou H, Afshar-Nadjafi B, Niaki S T A. A multi-objective invasive weeds optimization algorithm for solving multi-skill multi-mode resource constrained project scheduling problem[J]. Computers and Chemical Engineering, 2016, 88:157-169.
[31] Deb K, Agrawal S, Pratap A, et al. A fast elitist non-dominated sorting genetic algorithms for multi-objective optimization:NSGA-II[J]Lecture Notes in Computer Science, 2000, 1917:849-858.
[32] 王金华, 尹泽勇. 基于NSGA-Ⅱ和MOPSO融合的一种多目标优化算法[J]. 计算机应用, 2007, 27(11):2817-2820, 2823.