考虑车辆限行和装箱约束的车辆路径优化方法

徐翔斌; 任晨昊

doi:10.3963/j.jssn.1674-4861.2021.03.010

考虑车辆限行和装箱约束的车辆路径优化方法

doi: 10.3963/j.jssn.1674-4861.2021.03.010

徐翔斌^,,
任晨昊

华东交通大学交通运输与物流学院南昌 330013

基金项目:

国家自然科学基金项目 71761013

江西省自然科学基金面上项目 20181BAB201010

详细信息

通讯作者:
徐翔斌（1975—），博士，教授.研究方向：物流与供应链管理.E-mail：xuxiangbin@ecjtu.edu.cn

中图分类号: U492.3
计量
- 文章访问数: 329
- HTML全文浏览量: 148
- PDF下载量: 14
- 被引次数: 0
出版历程
- 收稿日期: 2020-05-23

An Optimization Method of Vehicle Routing Considering Vehicle Restrictions and Two-dimensional Loading Constraints

XU Xiangbin^,,
REN Chenhao

School of Transportation and Logistics, East China Jiaotong University, Nanchang 330013, China

摘要

摘要: 在实际配送过程中，考虑到部分城市道路存在限制大型配送车辆通行的现状，以及运输途中车厢内物品满足后进先出等装载约束能有效提高装卸效率的特点，将车辆限行和二维装箱约束加入到需求可拆分车辆路径问题中。同时考虑到车辆的使用成本和行驶成本，以车辆总配送成本最小为目标构建考虑车辆限行和二维装箱约束的需求可拆分车辆路径问题数学模型，设计了启发式算法来求解该模型，其中模拟退火算法确定需求拆分下的车辆配送路径，且在当前最优解判断时调用BLF算法检验物品的二维装箱约束，来减少频繁调用BLF算法的时间。数值案例验证了模型和算法的实用性，且所提出的算法的求解结果波动不大于0.8%，能在合理的时间范围内求解得到较好的配送方案，在车辆限行区域内采用双车型配送能节省15.17%~31.27%的总配送成本。
- 城市交通 /
- 车辆路径 /
- 车辆限行 /
- 启发式算法 /
- 二维装箱约束 /
- 需求可拆分
Abstract: Considering vehicle restrictions in some urban roads and the vehicle-loading constraints such as Last-In-First-Out (LIFO) unloading rule, vehicle restrictions and two-dimensional loading constraints are added to the split routing of delivery vehicles in real distributions. A 2LVR-SDVRP mathematical model is constructed to minimize the total distribution costs consisting of the fixed cost and transportation cost. A heuristic algorithm is proposed to solve the model. Wherein, SA determines distribution routing, and BLF examines the vehicle-loading constraints when the current optimal solution routes are determined, which reduces the time of frequently calling the BLF algorithm. The practicability of the model and the algorithm is verified by a case study. Besides, the proposed algorithm can solve a better distribution scheme within a reasonable time range, with the fluctuation of optimal solutions no more than 0.8%. The total distribution costs of dual-vehicle distribution are from 15.17% to 31.27% less than those of single-vehicle under vehicle restrictions.
- urban traffic /
- vehicle routing /
- vehicle restrictions /
- heuristic algorithm /
- two-dimensional loading constraints /
- split delivery

HTML全文

图 1 车辆限行下的配送路径图

Figure 1. Distribution routes under vehicle restrictions

下载: 全尺寸图片幻灯片

图 2 车厢内物品位置示意图

Figure 2. Positions of items in the carriage

下载: 全尺寸图片幻灯片

图 3 算法流程图

Figure 3. Flow of the algorithm

下载: 全尺寸图片幻灯片

图 4 路径内邻域构造

Figure 4. Neighborhood structures within a path

下载: 全尺寸图片幻灯片

图 5 路径间邻域构造

Figure 5. Neighborhood structures between paths

下载: 全尺寸图片幻灯片

图 6 重复配送调整

Figure 6. Adjusting repeated distribution

下载: 全尺寸图片幻灯片

图 7 物品覆盖处理

Figure 7. Deal with covering items

下载: 全尺寸图片幻灯片

图 8 客户坐标位置

Figure 8. Coordinate position of customers

下载: 全尺寸图片幻灯片

图 9 最优路线图

Figure 9. Optimal route

下载: 全尺寸图片幻灯片

图 10 不同客户规模下平均求解时间

Figure 10. Average solving time under different customer sizes

下载: 全尺寸图片幻灯片

图 11 求解波动情况

Figure 11. Fluctuations of optimal solutions

下载: 全尺寸图片幻灯片

图 12 不同车型方案结果对比

Figure 12. Comparison of results under different vehicle models

下载: 全尺寸图片幻灯片

表 1 客户需求信息

Table 1. Customers' demand information

客户编号	横坐标/m	纵坐标/m	需求量	物品宽/cm	物品长/cm	物品重量/t
1	12.8	8.5	2	75	90	0.4
2	18.4	3.4	2	45	165	0.2
3	15.4	16.6	2	30	60	0.2
4	18.9	15.2	1	75	75	0.6
5	15.5	11.6	3	75	225	0.2
6	3.9	10.6	2	45	90	0.4
7	10.6	7.6	1	60	135	0.4
8	8.6	8.4	3	75	105	0.6
9	12.5	2.1	1	60	60	0.2
10	13.8	5.2	4	60	165	0.4
11	6.7	16.9	2	30	90	0.6
12	14.8	2.6	2	45	165	0.4
13	1.8	8.7	3	75	60	0.2
14	17.1	11.0	1	45	105	0.2
15	7.4	1.0	1	30	195	0.4
16	0.2	2.8	3	45	105	0.4
17	11.9	19.8	1	90	180	0.4
18	13.2	15.1	4	75	75	0.4
19	6.4	5.6	1	60	165	0.2
20	9.6	14.8	1	45	150	0.4

下载: 导出CSV

表 2 车辆参数

Table 2. Vehicle parameters

车型编号	发车成本/元	限载量/t	车厢宽/cm	车厢长/cm	单位行驶成本/(元/km)	单次最远里程/km
1	200	1.8	100	200	2	50
2	250	3	200	300	2.5	80

下载: 导出CSV

表 3 最优配送方案

Table 3. Optimal distribution plan

路径编号	路径	路径成本/元	装载量/t	车型编号
路径1	0—18(1)—17—11—20—0	305.25	2.4	2
路径2	0—6—13—19—0	260.44	1.6	1
路径3	0-18(3)-3-4-14—5—0	292.25	3	2
路径4	0—2—12—9—15—16—0	366.52	3	2
路径5	0—7—10—1—0	297.30	2.8	2
路径6	0—8—0	229.93	1.8	1

下载: 导出CSV

表 4 测试算例求解结果

Table 4. Results of the test examples

客户规模	限行区域客户数	CPLEX		本文算法
客户规模	限行区域客户数	最优解/元	求解时间/s	求解结果/元	求解时间/s
5	0	331.74	13.45	331.74	69.08
8	1	801.17	267.69	801.17	106.56
11	1			894.34	152.53
14	2			1 192.98	177.28

下载: 导出CSV

表 5 不同限行区域客户数下的求解结果

Table 5. Results under different numbers of customers in the vehicle-restricting area

客户规模	无限行区域	限行区域客户数为1		限行区域客户数为2		限行区域客户数为3
客户规模	总成本/元	总成本/元	变化率/%	总成本/元	变化率/%	总成本/元	变化率/%
8	656.74	801.17	21.99	811.34	23.54	867.01	32.02
11	873.71	894.34	2.36	912.10	4.39	963.59	10.29
14	1 180.89	1 191.15	0.87	1 192.98	1.02	1 255.37	6.31
17	1 459.35	1 464.46	0.35	1 468.81	0.65	1 467.26	0.54

下载: 导出CSV

参考文献(20)

[1]	DROR M, TRUDEAU P. Savings by split delivery routing[J]. Transportation Science, 1989, 23(2): 141-145. doi: 10.1287/trsc.23.2.141
[2]	ARCHETTI C, SAVELSBERGH M W, SPERANZA M G. Worst-case analysis for split delivery vehicle routing problems[J]. Transportation Science, 2006, 40(2): 226-234. doi: 10.1287/trsc.1050.0117
[3]	NOWAK M, ERGUNÖ, WHITE III C C. Pickup and delivery with split loads[J]. Transportation Science, 2008, 42(1): 32-43. doi: 10.1287/trsc.1070.0207
[4]	ARCHETTI C, FEILLET D, GENDREAU M, et al. Complexity of the VRP and SDVRP[J]. Transportation Research Part C: Emerging Technologies, 2011, 19(5): 741-750. doi: 10.1016/j.trc.2009.12.006
[5]	SILVA M M, SUBRAMANIAN A, OCHI L S. An iterated local search heuristic for the split delivery vehicle routing problem[J]. Computers & Operations Research, 2015, (53): 234-249. http://www.sciencedirect.com/science/article/pii/s0305054814002159
[6]	LUO Zhixing, QIN Hu, ZHU Wenbin, et al. Branch and price and cut for the split-delivery vehicle routing problem with time windows and linear weight-related cost[J]. Transportation Science, 2016, 51(2): 668-687. http://arxiv.org/abs/1401.6483
[7]	彭勇, 罗佳. 需求可拆分车辆路径优化模型与BLF-GA算法设计[J]. 广西民族大学学报: 自然科学版, 2017, 23(2): 67-73. https://www.cnki.com.cn/Article/CJFDTOTAL-GXMZ201702012.htm PENG Yong, LUO Jia. Researching on optimization model and BLF-GA algorithm of split delivery vehicle routing problem with two-dimensional loading constraints[J]. Journal of Guangxi University for Nationalities(Natural Science Edition), 2017, 23(2): 67-73. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-GXMZ201702012.htm
[8]	张得志, 何亦扬, 龚浩翔. 随机需求订单可拆分的多目标车辆路径问题[J]. 铁道科学与工程学报, 2018, 15(5): 235-244. https://www.cnki.com.cn/Article/CJFDTOTAL-CSTD201805031.htm ZHANG Dezhi, HE Yiyang, GONG Haoxiang. Multi-objective vehicle routing problem with stochastic demand and split deliveries[J]. Journal of Railway Science and Engineering, 2018, 15(5): 235-244. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-CSTD201805031.htm
[9]	BIANCHESSI N, DREXL M, IRNICH S. The split delivery vehicle routing problem with time windows and customer inconvenience constraints[J]. Transportation Science, 2019, 53(4): 1067-1084. doi: 10.1287/trsc.2018.0862
[10]	ZHANG Yuankai, SUN Lijun, HU Xiangpei, et al. Order consolidation for the last-mile split delivery in online retailing[J]. Transportation Research Part E: Logistics and Transportation Review, 2019(122): 309-327. http://www.sciencedirect.com/science/article/pii/S1366554518304046
[11]	LI Jiliu, QIN Hu, BALDACCI R, et al. Branch-and price-andcut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows[J]. Transportation Research Part E: Logistics and Transportation Review, 2020(140): 1-22.
[12]	徐菱, 胡小林, 胡小亮. 时间窗约束下需求可拆分的拣选与配送联合优化问题研究[J]. 交通运输工程与信息学报, 2020, 18(2): 18-29. https://www.cnki.com.cn/Article/CJFDTOTAL-JTGC202002003.htm XU Ling, HU Xiaolin, HU Xiaoliang. Integrated optimization of picking and split delivery problem under time windows[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 18(2): 18-29. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JTGC202002003.htm
[13]	YANNIS G, GOLIAS J, ANTONIOU C. Effects of urban delivery restrictions on traffic movements[J]. Transportation Planning and Technology, 2006, 29(4): 295-311. doi: 10.1080/03081060600905566
[14]	胡云超, 申金升, 黄爱玲. 城市货运交通管制情景下城市配送多目标优化效益研究[J]. 交通运输系统工程与信息, 2012, 12(6): 119-125+144. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201206017.htm HU Yunchao, SHEN Jinsheng, HUANG Ailing. Multi-objective optimization for city distribu-tion under urban freight restriction[J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12(6): 119-125+144. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201206017.htm
[15]	赵璐. 面向集团客户的城市蔬菜配送车辆路径问题研究[D]. 上海: 上海交通大学, 2014. ZHAO Lu. Vehicle routing problem of urban vegetable distribution system which foodservice operators[D]. Shanghai: Shanghai Jiaotong University, 2014. (in Chinese)
[16]	SHI Feng, XU Guanming, LIU Bing, et al. Optimization method of alternate traffic restriction scheme based on elastic demand and mode choice behavior[J]. Transportation Research Part C: Emerging Technologies, 2014(39): 36-52. http://www.sciencedirect.com/science/article/pii/S0968090X1300243X
[17]	赖平仲, 汤洋, 杨珍花, 等. 考虑城市货运车辆交通管制的配送优化[J]. 大连海事大学学报, 2015, 41(4): 59-66. https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS201504011.htm LAI Pingzhong, TANG Yang, YANG Zhenhua, et al. Distribution optimization relating to traffic control of urban freight[J]. Journal of Dalian Maritime University, 2015, 41(4): 59-66. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS201504011.htm
[18]	杨雨, 李庚, 王蓉, 等. 限行政策对道路交通流的影响研究——以天津市为例[J]. 交通信息与安全, 2016, 34(1): 116-122. https://www.cnki.com.cn/Article/CJFDTOTAL-JTJS201601019.htm YANG Yu, LI Geng, WANG Rong, et al. A study of the impact of vehicle restriction policies on traffic flow: A case study of Tianjin[J]. Journal of Transport Information and Safety, 2016, 34(1): 116-122. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JTJS201601019.htm
[19]	葛显龙, 徐玖平, 王伟鑫. 交通限行条件下基于车辆协作的城市物流换乘联运问题研究[J]. 中国管理科学, 2017, 25(10): 130-139. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK201710014.htm GE Xianglong, XU Jiuping, WANG Weixin. The vehicle coordination strategy and transfer combined transport to urban distribution problem under traffic restrictions[J]. Chinese Journal of Management Science, 2017, 25(10): 130-139. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK201710014.htm
[20]	FELIPE Á, ORTUÑO M T, RIGHINI G, et al. A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges[J]. Transportation Research Part E: Logistics and Transportation Review, 2014(71): 111-128. http://www.sciencedirect.com/science/article/pii/S1366554514001574