An Optimization Model and Algorithm for Heterogeneous Vehicle Routing Problem of Supermarket Distribution Considering the Characteristics of Goods
-
摘要: 为解决商超配送业务中因多货物特性和道路限行政策导致的车辆路径规划方案优化程度不足、货物特性与运输车型匹配精准度欠佳及配送成本高的问题，研究了考虑货物特性的多车型带时间窗车辆路径问题。考虑了货物对车型的特殊要求、道路限行、运输过程中车辆油耗变化等因素，引入货物特性参数并融合货物特性与配送车辆车型的匹配关系约束，构建该问题的整数规划模型。为求解该问题，对免疫遗传算法改进，设计基于货物和时间窗的路径分割和车型选择的解编码策略；结合变邻域下降思想，引入多种变异算子提高算法局部搜索能力；加入次优解保留机制，提高种群多样性。以北京市某物流公司商超配送计划优化为例，利用提出的改进免疫遗传算法进行求解；与改进的混合粒子群优化算法、遗传算法和免疫遗传算法对比，成本分别降低了2.24%、3.03%和4.82%，所用车辆数分别减少1、1和2；当算例规模扩大后，本文提出的算法得到的配送方案的配送成本相较于对比算法分别降低0.35%、15.99%和16.14%，所用车辆数分别减少1、3和2。对变异算子组合进行分析，实验发现：引入的3-opt算子和move算子能够提升算法性能，且不同的算子组合能呈现出不同的效果，因此在实际应用中，需要根据企业的实际需求选定变异算子的组合。Abstract: To address the issues of insufficient optimization of delivery route planning, low accuracy in matching goods characteristics with multiple types of vehicles, and high delivery costs in the supermarket delivery process caused by diverse goods characteristics and road traffic restrictions, this study investigates the heterogeneous vehicle routing problem with time window considering the characteristics of goods. This paper takes into account the special requirements of goods, including vehicle types, road restrictions, changes in vehicle fuel consumption during transportation, and other factors. It incorporates parameters for goods characteristics and integrates the matching relationship constraints between goods characteristics and the types of delivery vehicles to construct an integer programming model. An improved Immune Genetic Algorithm is proposed to address the issue by designing a coding and encoding strategy for path segmentation and vehicle selection based on goods and time window; combining with a variety of mutation operators in a variable neighborhood descent process to improve the local search ability, and adding a suboptimal solution retention mechanism to enhance the diversity of the population. The improved algorithm is used to solve the supermarket distribution plan of a logistics company in Beijing. Compared with Hybrid Particle Swarm Optimization, Genetic Algorithm, and Immune Genetic Algorithm, the cost decreases by 2.24%, 3.03%, and 4.82%, and the numbers of vehicles are decreased by 1, 1, and 2. The experiment results with the extension instance show that the cost decreases by 0.35%, 15.99%, and 16.14%, and the numbers of vehicles are decreased by 1, 3, and 2. Finally, the different combination of mutation operators is analyzed, and the results reveal that the introduced 3-opt and move operators are beneficial for the performance of the algorithm, and the different combination of operators performs various effects. Therefore, it is necessary to select a combination of operators based on the actual needs of the enterprise in practice.
-
图 3 考虑多种因素的路径分割示意图
Figure 3. Schematic diagram of path segmentation considering multiple factors
表 1 模型符号及变量定义
Table 1. Model symbols and variable definitions
符号类别 符号 定义 集合 K 配送过程使用的车辆集合 M 配送中心的所有车型的集合 Ms 配送中心特殊车型集合Ms⊆M 参数 B 无穷大的数 cm 车型m的固定发车成本 cf 柴油单价 dij 客户i/配送中心到客户j/配送中心的距离 ej 客户j时间窗开始时间 lj 客户j时间窗结束时间 atjkm 车型m车辆k到达客户j的时间 tijkm 车型m车辆k从客户i到客户j的行驶时间 stikm 客户i的平均等待时长 utim 客户i的卸货时长 Fijkm 车型m车辆k从客户i行驶到客户j的油耗量 pi 客户i的货物体积 qi 客户i的货物重量 Qkm 车型m车辆k的额定载重 Vkm 车型m车辆k的额定容积 vkm 车型m车辆k行驶速度 vu 卸货速率 yi （0-1特征值）客户i的货物是特殊货物则为1，否则为0 ξm 车型m的点位费 ζm 燃料与空气质量比 κm 柴油热量值 ψm 转换系数 μm 发动机摩擦因子 Nem 发动机转速 Vm 发动机排量 ρ 空气密度 Arm 车辆迎风面 g 重力加速度 mem 车辆自重 ϕ 道路角度 Cd 空气阻力系数 Cr 滚动抵抗系数 εm 车辆传动系效率 ϖm 柴油机效率系数 决策变量 xijkm 决策变量（0-1变量）车型m车辆k从客户i/配送中心行驶到客户j/配送中心 zikms 决策变量（0-1变量）客户i的货物由车型ms车辆k装运 
下载: 导出CSV
表 2 生物免疫系统、AIS与本文所研究问题的对应关系
Table 2. The relationship between the algorithms of biological immune system, AIS and the problems studied
生物免疫系统 人工免疫系统算法 本文所研究问题 抗原 优化目标 目标函数 抗体 可行解 车辆行驶路径 亲和度 可行解的目标值 车辆行驶总成本 免疫处理 抗体细胞的选择、克隆、变异 对路径进行选择、复制和邻域搜索 克隆抑制 选择更好的可行解 选择更好的车辆路径
下载: 导出CSV
表 3 车辆相关参数
Table 3. Parameters of vehicle
参数及符号 车型 1 2 3 4 5 燃料与空气质量比ζ 1 1 1 1 1 柴油热量值κ/(kJ/g) 44 44 44 44 44 转换系数ψ/(g/L) 737 737 737 737 737 发动机摩擦因子μ 0.2 0.2 0.2 0.2 0.2 发动机转速Ne/ (rps) 53 53 53 43 38 发动机排量V/(L) 2 2 2.5 3.8 4.5 空气密度ρ/(kg/m3) 1.2 1.2 1.2 1.2 1.2 车辆迎风面Ar/(m2) 3.24 4.16 6.79 7.77 9.82 重力加速度g/(m × s-2) 9.8 9.8 9.8 9.8 9.8 车辆自重me/(kg) 2 510 2 164 2 995 4 350 8 275 道路角度ϕ/(°) 0 0 0 0 0 空气阻力系数Cd 0.7 0.7 0.7 0.7 0.7 滚动抵抗系数Cr 0.01 0.01 0.01 0.01 0.01 车辆传动系效率ε 0.4 0.4 0.4 0.4 0.4 柴油机效率系数ϖ 0.9 0.9 0.9 0.9 0.9 车辆额定载重Qkm/kg 2 000 3 000 6 000 10 000 13 000 车辆额定容积Vkm/m3 4 6 15 17 30 固定发车成本cm/元 350 350 450 550 650 点位费/元 50 50 100 110 140 是否为特殊车辆 是 是 是 否 否
下载: 导出CSV
表 4 IGA_VND相关参数设置
Table 4. The related parameter setting of IGA_VND
antiNum cloneNum iterMax a/% Pa Pc 100 10 1 000 50 0.01 0.2
下载: 导出CSV
表 5 实验结果表
Table 5. Experiment results
实验编号 总成本/元 求解时间/s 车辆使用数量 1 4 961.30 77.15 6.00 2 4 990.52 68.57 6.00 3 4 972.65 62.27 6.00 4 4 821.82 62.44 5.00 5 4 976.69 71.24 6.00 6 5 001.86 80.38 6.00 7 4 954.78 79.72 6.00 8 4 990.52 63.23 6.00 9 4 976.69 61.99 6.00 10 4 961.30 62.28 6.00 平均 4 960.81 68.93 5.90
下载: 导出CSV
表 6 配送路径及所用车型
Table 6. Distribution routes and the vehicle type
车型 路径 5 0-15-20-11-0 3 0-5-6-16-3-0 3 0-13-14-12-0 3 0-4-2-8-7-9-0 5 0-18-19-10-17-1-0
下载: 导出CSV
表 7 不同算法实验结果对比
Table 7. Experimental results of comparison algorithms
统计量 IGA_VND HPSO GA IGA 油耗成本/元 1 591.82 1 452.09 1 492.65 1 425.80 出车成本/元 2 650 2 900 2 900.00 3 050.00 总点位费/元 580.00 580.00 580.00 590.00 使用车辆数/辆 5 6 6 7 特种车辆数/辆 3 4 4 6 总成本 4 821.82 4 932.09 4 972.65 5 065.80
下载: 导出CSV
表 8 扩大规模算例下实验结果对比
Table 8. Comparison of experimental results for the extension scale of instance
统计量 IGA_VND HPSO GA IGA 油耗成本/元 1 426.08 1 194.28 1 469.16 1 620.70 出车成本/元 3 100.00 3 350.00 3 950.00 3 800.00 总点位费/元 640.00 640.00 730.00 740.00 使用车辆数/辆 6 7 9 8 特种车辆数/辆 3 4 7 5 总成本 5 166.08 5 184.28 6 149.16 6 160.70
下载: 导出CSV
表 9 不同变异算子组合实验结果比较
Table 9. Comparison of experimental results of different mutation operators
实验组号 算子 油耗成本 出车成本 总点位费 使用车辆数 特种车辆数 总成本 1 swap，2-opt，3-opt 1 538.22 2 650.00 580.00 5 3 4 768.22 2 swap，2-opt，move 1 520.35 2 650.00 580.00 5 3 4 750.35 3 swap，3-opt，move 1 525.60 2 650.00 540.00 5 2 4 715.60 4 2-opt，3-opt，move 1 536.94 2 650.00 540.00 5 2 4 726.94 5 2-h-opt，3-opt，move 1 512.24 2 650.00 540.00 5 2 4 702.24
下载: 导出CSV
-
[1] 马祥丽, 张惠珍, 马良. 带时间窗物流配送车辆路径问题的蝙蝠算法[J]. 计算机工程与应用, 2016, 52(11): 254-258, 264.MA X L, ZHANG H Z, MA L. Bat algorithm for vehicle routing problem of logistics distribution with time windows[J]. Computer Engineering and Applications, 2016, 52(11): 254-258, 264. (in Chinese) [2] 张锐. 2021年中国物流行业并购活动回顾及发展趋势[J]. 供应链管理, 2022, 3(11): 59-82.ZHANG R. Review and development trend of China's logistics industry M&A activities in 2021[J]. Supply Chain Management, 2022, 3(11): 59-82. (in Chinese) [3] 潘晓, 鹿冬娜, 王书海. 基于订单拆分的容量限制商超配送路径规划[J]. 华东师范大学学报(自然科学版), 2022, (5): 147-164.PAN X, LU D N, WANG S H. Capacitated route planning for supermarket distribution based on order splitting[J]. Journal of East China Normal University(Natural Science), 2022, (5): 147-164. [4] 张泽昊. Y物流公司的多车型车辆路径问题研究[D]. 济南: 山东财经大学, 2022.ZHANG Z H. Research on the routing problem of multi-model vehicles of Y logistics companies[D]. Jinan: Shandong University of Finance and Economics, 2022. (in Chinese) [5] 杜琛, 李怡靖. 基于客户满意度和最小损耗的冷链配送路径问题研究[J]. 工业工程与管理, 2020, 25(6): 163-171.DU C, LI Y J. Research on cold chain distribution routing problem based on customer satisfaction and minimum loss[J]. Industrial Engineering and Management, 2020, 25(6): 163-171. (in Chinese) [6] 陈靖, 吴一帆. 考虑有限车辆载运能力的生鲜品集配策略研究[J]. 管理学报, 2018, 15(9): 1380-1392.CHEN J, WU Y F. Research on shipment consolidation policy for fresh products by considering limited vehicle capacity[J]. Chinese Journal of Management, 2018, 15(9): 1380-1392. (in Chinese) [7] 丁秋雷, 胡祥培, 位娟, 等. 动态需求下蓄冷式多温共配多目标优化模型及算法[J]. 运筹与管理, 2021, 30(12): 13-19.DING Q L, HU X P, WEI J, et al. Research on multi-objective optimization model and algorithm of cold storage multi-temperature joint delivery under dynamic demand[J]. Operations Research and Management Science, 2021, 30 (12): 13-19. (in Chinese) [8] 殷亚, 张惠珍. 易腐生鲜货品车辆路径问题的改进混合蝙蝠算法[J]. 计算机应用, 2017, 37(12): 3602-3607.YIN Y, ZHANG H Z. Improved hybrid bat algorithm for vehicle routing problem of perishable fresh goods[J]. Journal of ComputerApplications, 2017, 37(12): 3602-3607. (in Chinese) [9] 狄卫民, 杜慧莉, 张鹏阁. 考虑动态拥堵的多车型绿色车辆路径问题优化[J]. 计算机工程与设计, 2021, 42(9): 2614-2620.DI W M, DU H L, ZHANG P G. Operation of multi-vehicle green vehicle routing problem considering dynamic congestion[J]. Computer Engineering and Design, 2021, 42(9): 2614-2620. (in Chinese) [10] 赵志学, 李夏苗, 周鲜成. 考虑拥堵区域的多车型绿色车辆路径问题优化[J]. 计算机应用, 2020, 40(3): 883-890.ZHAO Z X, LI X M, ZHOU X C. Green vehicle routing problem optimization for multi-type vehicles considering traffic congestion areas[J]. Journal of Computer Applications, 2020, 40(3): 883-890. (in Chinese) [11] 徐东洋, 李昆鹏, 郑飘, 等. 多车场多车型多品类供需未匹配与可任意拆分取送货车辆路径问题优化[J]. 管理学报, 2020, 17(7): 1086-1095.XU D Y, LI K P, ZHENG P, et al. The optimization research of multi-category unpaired supply-demand and arbitrary split pickup and delivery vehicle routing problem with multi-depot and multi-type trucks[J]. Chinese Journal of Management, 2020, 17(7): 1086-1095. (in Chinese) [12] 朱晨晨. 多车场多车型车辆路径问题的优化研究[J]. 企业科技与发展, 2021(2): 94-96, 99.ZHU C C. Research on optimization of vehicle routing problem with multi-model and multi-depot[J]. Enterprise Technology and Development, 2021, (2): 94-96, 99. (in Chinese) [13] 缪红萍, 李宏光. 基于免疫遗传算法的TSP求解[J]. 仪器仪表学报, 2004(增刊1): 963-965.MIU H P, LI H G. Immune genetic algorithm for traveling salesman problem[J]. Chinese Journal of Science Instrument, 2004(S1): 963-965. (in Chinese) [14] 魏云飞, 黄德才. 求解非满载车辆调度问题的免疫遗传算法[J]. 浙江工业大学学报, 2005(5): 511-515.WEI Y F, HUANG D C. Solving vehicle scheduling problem with nonfull load by means of immune genetic algorithm[J]. Journal of Zhejiang University of Technology, 2005(5): 511-515. (in Chinese) [15] 徐小峰, 姜明月, 邓忆瑞. 整合逆向物流协同配送动态路径优化问题研究[J]. 管理科学学报, 2021, 24(10): 106-126.XU X F, JIANG M Y, DENG Y R. Dynamic vehicle routing problem with simultaneous pickup and delivery in collaborative distribution under demand concurrent[J]. Journal of Management Sciences in China, 2021, 24(10): 106-126. (in Chinese) [16] 徐东洋, 李昆鹏, 崔利刚, 等. 供需未匹配的多车场多车型多货品可拆分取送货车辆路径问题[J]. 中国管理科学, 2021, 29(1): 127-137.XU D Y, LI K P, CUI L G, et al. Multi-commodity unpaired supply-demand and split pickup and delivery vehicle routing problem with multi-depot and multi-type trucks[J]. Chinese Journal of Management Science, 2021, 29(1): 127-137. (in Chinese) [17] 肖智豪, 胡志华, 朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 计算机应用, 2022, 42(9): 2926-2935.XIAO Z H, HU Z H, ZHU L. Hybrid adaptive large neighborhood search algorithm for solving time-dependent vehicle routing problem in cold chain logistics[J]. Journal of Computer Applications, 2022, 42(9): 2926-2935. (in Chinese) [18] FRANCESCHETTI A, HONHON D, WOENSEL T V, et al. The time-dependent pollution-routing problem[J]. Transportation Research Part B: Methodological, 2013, 56(56): 265-293. [19] 王莉莉, 赵云飞. 基于GA、RBF和改进Cao方法的空中交通流预测方法[J]. 交通信息与安全, 2023, 41(1): 115-123. doi: 10.3963/j.jssn.1674-4861.2023.01.012WANG L L, ZHAO Y F. A method for predicting air traffic flow based on a combined GA, RBF, and improved Cao method[J]. Journal of Transport Information and Safety, 2023, 41(1): 115-123. (in Chinese)). doi: 10.3963/j.jssn.1674-4861.2023.01.012 [20] 张颖钰, 吴立云, 贾胜钛. 带时间窗的多中心半开放式VRPSDP问题研究[J]. 系统仿真学报, 2023, 35(11): 2464-2475.ZHANG Y Y, WU L Y, JIA S T. The multi-depot half open vehicle routing problem with simultaneous delivery-pickup and time windows[J]. Journal of System Simulation, 2023, 35 (11): 2464-2475. (in Chinese) [21] 张磊. 基于人工免疫系统的群体机器人故障检测研究[D]. 上海: 上海师范大学, 2022.ZHANG L. Research on swarm robot fault detection based on artificial immune system[D]. Shanghai: Shanghai Normal University, 2022. (in Chinese) [22] 肖振华. 多粒度调节的人工免疫系统及在故障检测中的应用[D]. 武汉: 武汉大学, 2020.XIAO Z H. Multi-granularity modulated artificial immune system and its application in fault detection[D]. Wuhan: Wuhan University, 2020. (in Chinese) [23] 周璐辉, 岳雪芝. 混合粒子群算法求解带时间窗的路径规划问题[J/OL]. (2025-02-07).[2025-06-15]. http://kns.cnki.net/kcms/detail/51.1307.TP.20250506.1415.010.html .ZHOU L H, YUE X Z. Hybrid particle swarm optimization for solving vehicle routing problems with time windows[J/ OL]. (2025-02-07).[2025-06-15].http://kns.cnki.net/kcms/detail/51.1307.TP.20250506.1415.010.html . -
点击查看大图
图(11) / 表(9)
计量
- 文章访问数: 24
- HTML全文浏览量: 8
- PDF下载量: 3
- 被引次数: 0