速度时变下多越库中心协同的库门分配及车辆路径优化

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

摘要/Abstract

摘要：

针对速度时变下多越库中心协同的库门分配及车辆路径优化问题，综合考虑多越库中心共同配送、车辆行驶速度时变、客户服务时间窗等因素，以集配货及仓库间转运的车辆派遣成本、车辆能耗成本、库内运输成本以及客户惩罚成本之和最小化为目标，建立优化模型。根据问题特征设计变邻域搜索算法求解，在集货、配货、库门分配阶段进行区间内的邻域搜索，通过插入、交换、2-opt等邻域结构寻优，以提高算法搜索速度、改善求解质量。通过多组算例验证了算法的有效性，并针对越库中心数量、多越库配送模式、车辆行驶速度、车辆类型进行相应的敏感性分析，研究结果表明：（1）考虑多越库中心协同配送得出的车辆调度及库门分配方案能有效降低越库中心运营成本，提高物流配送效率；（2）本文设计的变邻域搜索算法通过区间内邻域搜索增强了算法的寻优能力，提高了求解质量；（3）采用电动车配送比燃油车或混合车队配送节约运输成本，各物流企业应加大对电动车辆的使用，优先考虑派遣电动车进行配送服务。本文的研究结果不仅丰富了越库配送模式下的车辆路径问题研究，也为物流企业科学制订配送方案提供理论依据。

关键词: 多越库中心, 库门分配, 速度时变, 库间转运, 变邻域搜索算法

Abstract:

The thesis is about the optimization of time-dependent vehicle routing problem with multiple cross-docks and door assignment， considering collaborative distribution of multiple cross-docks， time-dependent speed and time windows of customers. An optimization model is established to minimize the sum of pick up， delivery and transfer vehicles’ dispatching cost， vehicles’ energy cost， forklifts’ transportation cost and penalty cost on earliness and tardiness. A variable neighborhood search algorithm is designed according to the characteristics of the problem. In order to improve algorithm’s searching speed and solving quality， neighborhood search is simultaneously carried out in the interval of pick up， delivery， door assignment and cross-docking operation process， and the neighborhood structure includes inserting， switching and 2-opt. The validity of the algorithm is verified by multi-group examples. The results show that：（1） Considering the time-dependent vehicle speed and collaborative distribution of multiple cross-docks， the vehicle scheduling and cross-dock door assignment scheme could effectively reduce the operation cost and improve logistics distribution efficiency of urban areas. （2） The neighborhood search within each interval enhances the optimization ability of variable neighborhood search algorithm designed in this paper， improves the solution quality and provides an effective algorithm for solving the cross-dock door assignment and vehicle routing problem optimization. （3） Compared with fuel vehicle delivery and mixed fleet vehicle delivery， electric vehicle delivery could save cost. Therefore， logistics enterprises should increase the use of electric vehicles and give priority to dispatching electric vehicles for delivery services. The research results expand and enrich the research of vehicle routing problem with cross-docking， and provide theoretical basis for logistics enterprises to formulate the decision distribution scheme scientifically.

Key words: multiple cross-docks, dock-door assignment, time-dependent speed, cross-docking transfer, variable search algorithm

中图分类号:

TP301.6

范厚明,白雪,田攀俊,张跃光. 速度时变下多越库中心协同的库门分配及车辆路径优化[J]. 中国管理科学, 2024, 32(4): 108-119.

Houming Fan,Xue Bai,Panjun Tian,Yueguang Zhang. Door Assignment and Time-dependent Vehicle Routing Problem with Multiple Cross-Docks[J]. Chinese Journal of Management Science, 2024, 32(4): 108-119.

图/表 17

图1

图2

表1

模型中的符号及含义"

符号	含义
$V$	$V = V 0 ? V 1 ? V 2$ 为所有节点的集合，其中 $V 0$ 为越库中心的集合， $V 1$ 为供应商节点的集合， $V 2$ 为客户点的集合
$l i j$	节点 $i$ 和节点 $j$ 之间的距离（单位：千米）
$k f$	集货车集合 $K f$ 中任意一辆，燃油车
$k t$	转运车集合 $K t$ 中任意一辆，电动车
$k e$	配货车集合 $K e$ 中任意一辆，电动车
$Q f$	集货车 $k f$ 的最大载重量（单位：吨）
$Q t$	转运车 $k t$ 的最大载重量（单位：吨）
$Q e$	配货车 $k e$ 的最大载重量（单位：吨）
$t i j$	车辆在节点 $i 、 j$ 之间的行驶时间（单位：小时）
$Q i j k f h$	集货车 $k f$ 在供应商节点 $i 、 j$ 之间对 $h$ 类货物的载重量（单位：吨）
$Q i j k t h$	转运车 $k t$ 在越库中心节点 $i 、 j$ 之间对 $h$ 类货物的载重量（单位：吨）
$Q i j k e h$	配货车 $k e$ 在客户点 $i 、 j$ 之间对 $h$ 类货物的载重量（单位：吨）
$B$	电动车的电池容量（单位：千瓦时）
$f i j$	燃油车在节点 $i 、 j$ 之间的耗油量（单位：升）
$e i j$	电动车在节点 $i 、 j$ 之间的耗电量（单位：千瓦时）
$ε m i n$	电动车电池允许的最低荷电状态
$h$	货物种类集合 $H$ 中任意一种货物
$t h$	$h$ 类货物的单位重量装卸时间（单位：小时/吨）
$p i h$	供应商节点 $i$ 处对 $h$ 类货物的供货量（单位：吨）
$d i h$	客户点 $i$ 处对 $h$ 类货物的需求量（单位：吨）
$u i j h$	由越库中心 $i$ 转运至越库中心 $j$ 的 $h$ 类货物量（单位：吨）
$T i k f$	集货车 $k f$ 到达节点 $i$ 的时刻
$T i k e$	配货车 $k e$ 到达节点 $i$ 的时刻
$T k e d$	配货车 $k e$ 离开越库中心的时刻
$[T s, T f]$	$T s$ 为越库中心库内作业最晚开始时刻， $T f$ 为越库中心配送开始时刻
$[E T i, L T i]$	客户点 $i$ 的时间窗
$m$	入库门集合 $M$ 中任意一个入库门
$n$	出库门集合 $N$ 中任意一个出库门
$l m n$	入库门 $m$ 到出库门 $n$ 的距离（单位：米）
$s$	库内叉车集合 $S$ 中任意一辆
$Q s$	库内叉车 $s$ 的最大载重量（单位：吨）
$c 1$	燃油车单位派遣成本（单位：元/辆）
$c 2$	电动车单位派遣成本（单位：元/辆）
$c 3$	单位燃油价格（单位：元/升）
$c 4$	单位电量价格（单位：元/千瓦时）
$c 5$	库内叉车 $s$ 的单位运输成本（单位：元/米）
$c 6$	配货车辆早于 $E T i$ 到达客户点 $i$ 处的单位惩罚成本（单位：元/小时）
$c 7$	配货车辆晚于 $L T i$ 到达客户点 $i$ 处的单位惩罚成本（单位：元/小时）
$x i j k f$	决策变量，表示集货车 $k f$ 是否从节点 $i$ 行驶到节点 $j$ ，是为1，否为0
$x i j k t$	决策变量，表示转运车 $k t$ 是否从节点 $i$ 行驶到节点 $j$ ，是为1，否为0
$x i j k e$	决策变量，表示配货车 $k e$ 是否从节点 $i$ 行驶到节点 $j$ ，是为1，否为0
$y m n s$	决策变量，表示叉车 $s$ 是否从入库门 $m$ 行驶到出库门 $n$ ，是为1，否为0
$z m k f$	决策变量，表示集货车 $k f$ 是否分配给入库门 $m$ ，是为1，否为0
$z m k t$	决策变量，表示转运车 $k t$ 是否分配给入库门 $m$ ，是为1，否为0
$z n k e$	决策变量，表示配货车 $k e$ 是否分配给出库门 $n$ ，是为1，否为0

表1

图3

图4

图5

图6

表3

表4

表5

表6

表7

表8

图8

图9

图10

图11

参考文献 21

1	Shahabi-Shahmiri R， Asian S， Tavakkoli-Moghaddam R， et al. A routing and scheduling problem for cross-docking networks with perishable products， heterogeneous vehicles and split delivery［J］. Computers & Industrial Engineering， 2021， 157（3）： 107299.
2	Chen M C， Hsiao Y H， Reddy R H， et al. The self-learning particle swarm optimization approach for routing pickup and delivery of multiple products with material handling in multiple cross-docks［J］. Transportation Research Part E： Logistics and Transportation Review， 2016， 91： 208-226.
3	Maknoon Y， Laporte G. Vehicle routing with cross-dock selection［J］. Computers & Operations Research， 2017， 77： 254-266.
4	Yu V F， Jewpanya P， Redi A A N P， et al. Adaptive neighborhood simulated annealing for the heterogeneous fleet vehicle routing problem with multiple cross-docks［J］. Computers & Operations Research， 2021， 129（2）： 105205.
5	Alinaghian M， Naderipour M. A novel comprehensive macroscopic model for time-dependent vehicle routing problem with multi-alternative graph to reduce fuel consumption： a case study［J］. Computers & Industrial Engineering， 2016， 99： 210-222.
6	Xiao Y， Konak A. The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion［J］. Transportation Research Part E： Logistics and Transportation Review， 2016， 88： 146-166.
7	Bajegani E A， Mollaverdi N， Alinaghian M. Time-dependent vehicle routing problem with backhaul with FIFO assumption： variable neighborhood search and mat-heuristic variable neighborhood search algorithms［J］. International Journal of Industrial Engineering Computations， 2021， 12： 15-36.
8	Niu Y， Yang Z， Chen P， et al. Optimizing the green open vehicle routing problem with time windows by minimizing comprehensive routing cost［J］. Journal of Cleaner Production， 2018， 171： 962-971.
9	Froger A， Mendoza J E， Jabali O， et al. Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions［J］. Computers & Operations Research， 2019， 104： 256-294.
10	Lu J， Chen Y， Hao J K， et al. The time-dependent electric vehicle routing problem： model and solution［J］. Expert Systems with Applications， 2020， 161： 113593.
11	郭放，杨珺，杨超.考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究［J］.中国管理科学，2019， 27（8）： 118-128.
	Guo F， Yang J， Yang C. Study on heterogeneous electric vehicle routing and batterycharging problem with the consideration of differentiated service cost［J］. Chinese Journal of Management Science，2019， 27（8）： 118-128.
12	Zhou C， Qian K， Allan M， et al. Modeling of the cost of EV battery wear due to V2G application in power systems［J］. IEEE Trans on Energy Conversion， 2011， 26（4）： 1041-1050.
13	Pelletier S， Jabali O， Laporte G， et al. Battery degradation and behaviour for electric vehicles： review and numerical analyses of several models［J］. Transportation Research Part B： Methodological， 2017， 103： 158-187.
14	Ehmke J F， Campbell A M， Thomas B W. Vehicle routing to minimize time-dependent emissions in urban areas［J］. European Journal of Operational Research， 2016， 251（2）： 478-494.
15	Bektaş T， Laporte G. The pollution-routing problem［J］. Transportation Research Part B： Methodological， 2011， 45（8）： 1232-1250.
16	Mima S， Criqui P. The future of fuel cells in a long term inter-technology competition framework［M］. Berlin， Heidelberg： Springer Berlin Heidelberg， 2003.
17	Kreith F， West R E.Gauging efficiency， well to wheel［J］. Mechanical Engineering， 2003， 125：1-8.
18	Li L.， Liu Q. Acceleration curve optimization for electric vehicle based on energy consumption and battery life［J］. Energy， 2019， 169： 1039-1053.
19	Yu V F， Jewpanya P， Redi A. Open vehicle routing problem with cross-docking［J］. Computers & Industrial Engineering， 2016， 94： 6-17.
20	范厚明，田攀俊，吕迎春，等.越库配送下考虑时空距离的库门分配与车辆调度优化［J］.中国管理科学，2022，30（2）： 137-149.
	Fan H M， Tian P J， LV Y C， et al. Cross-dock door assignment and vehicle routing problem of considering temporal-spatial distance［J］. Chinese Journal of Management Science， 2022， 30（2）：137-149.
21	胡大伟，刘成清，胡卉，等.基于低碳视角的两阶段开放式选址路径问题——燃油车与电动车对比［J］.系统工程理论与实践， 2020， 40（12）： 3230-3242.
	Hu D W， Liu C Q， Hu H， et al. The two-echelon open location routing problem based on low carbon perspective：fuel vehicles vs. electric vehicles［J］. Systems Engineering-Theory & Practice， 2020， 40（12）： 3230-3242.

算例	SA		ANSA		VNS		GAP(%)
算例	10	30	10	30	10	30	10	30
ins0	6848	7550	6823	7559.8	6823	7376	0	-2
ins1	6741	7787	6741	7805.9	6741	7644	0	-2
ins2	9269	7747	9269	7625	9269	7232	0	-5
ins3	7255	7677	7295	7661.8	7295	7245	1	-5
ins4	6524	7225	6991	7414.8	6591	7141	1	-1
ins5	7613	7053	7392	6942.8	7334	6712	-1	-3
ins6	11990	7720	11713	7763.9	11713	7877	0	2
ins7	8158	7710	8158	7540.4	8158	7588	0	1
ins8	7120	7883	6989	7711.1	6989	8048	0	4
ins9	6056	7735	5970	7726.1	5970	7914	0	2
Avg	7757.4	7608.7	7734.1	7575.2	7688.3	7477.7	0.1	-1

编号	横坐标	纵坐标	货种1	货种2	货种3
1	-20	12.5	4.280	-	-
2	-31	8.5	3.440	-	-
3	-18	27.5	3.710	-	-
4	-24.5	20.5	3.630	-	-
5	-7.5	-7	-	3.890	-
6	-5	-13	-	3.622	-
7	-6	-2	-	3.930	-
8	-13	-7.5	-	4.000	-
9	48	52.5	-	-	3.953
10	53	44.5	-	-	3.912
11	38.5	60	-	-	4.023
12	60	38	-	-	3.970

编号	成本（元）
编号	集货	库间	库内	配货	总和
1	3323.84	2474.26	576.00	8659.22	15033.33
2	3350.41	2121.14	600.00	8944.62	15016.17
3	3380.97	2474.05	604.00	8737.99	15197.02
4	3341.99	2121.39	608.00	9009.15	15080.53
5	3343.82	2121.50	588.00	8785.31	14838.62
6	3349.89	2474.04	604.00	8384.72	14812.65
7	3319.59	2474.15	600.00	7868.67	14262.41
8	3355.41	2121.40	596.00	9017.44	15090.25
9	3347.17	2474.63	588.00	8518.14	14927.94
10	3326.47	2121.09	604.00	8901.17	14952.72
Avg	3343.95	2297.77	596.80	8682.64	14921.16
Best	3319.59	2474.15	600.00	7868.67	14262.41

车辆	路径	载重	载率	库门
1	D₁-2-1-D₁	7.720	96.5	D₁-入库门1
2	D₁-4-3-D₁	7.340	91.8	D₁-入库门1
3	D₁-8-7-D₁	7.930	99.1	D₁-入库门2
4	D₁-5-6-D₁	7.512	93.9	D₁-入库门2
5	D₂-12-10-D₂	7.882	98.5	D₂-入库门1
6	D₂-11-9-D₂	7.976	99.7	D₂-入库门1
7	D₁-107-51-53-100-D₂	2.622	87.4	D₁-出库门2
8	D₂-63-105-35-29-16-D₁	2.812	93.7	D₂-出库门1
9	D₁-46-81-22-70-D₁	2.660	88.7	D₁-出库门3
10	D₁-91-60-80-76-103-D₁	2.698	89.9	D₁-出库门2
11	D₂-87-93-45-82-19-26-D₂	2.888	96.3	D₂-出库门3
12	D₁-67-14-31-90-61-25-D₁	2.812	93.7	D₁-出库门1
13	D₁-37-32-101-72-28-D₁	2.736	91.2	D₁-出库门2
14	D₁-39-77-55-73-21-D₁	2.584	86.1	D₁-出库门2
15	D₁-104-62-102-30-47-D₁	2.698	89.9	D₁-出库门2
16	D₁-75-18-71-38-99-86-D₁	2.888	96.3	D₁-出库门2
17	D₁-20-85-92-64-42-40-59-D₂	2.584	86.1	D₁-出库门1
18	D₁-41-88-66-56-D₁	2.394	79.8	D₁-出库门3
19	D₁-33-50-97-36-D₂	2.850	95	D₁-出库门3
20	D₁-49-15-89-65-58-106-84-17-D₁	2.964	98.8	D₁-出库门3
21	D₁-52-79-43-78-94-68-83-44-D₁	2.926	97.5	D₁-出库门2
22	D₂-74-108-57-24-96- 13-95-48-34-D₁	2.926	97.5	D₂-出库门1
23	D₂-98-27-69-54-23-D₁	2.318	77.3	D₂-出库门3

	Case1	Case2	Case3	Case4
越库数量	2	3	2	3
配送模式	独立配送	独立配送	共同配送	共同配送