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

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

Abstract

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

CLC Number:

TP301.6

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.

Figures/Tables 17

符号	含义
$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

References 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
配送模式	独立配送	独立配送	共同配送	共同配送

Door Assignment and Time-dependent Vehicle Routing Problem with Multiple Cross-Docks

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 17

References 21

Related Articles 1

Metrics

Comments

Recommended 0

编号	集货			库间			库内			配货			总成本
编号	Case1	Case2	Case4	Case1	Case2	Case4	Case1	Case2	Case4	Case1	Case2	Case4	Case1	Case2	Case4
1	3340	3434	3431	2121	3865	3867	588	684	684	8767	10441	9267	14817	18424	17249
2	3333	3419	3414	2474	4215	3865	624	644	692	9332	10269	9254	15764	18547	17226
3	3342	3404	3406	2474	4215	3516	584	684	672	9549	9915	9782	15950	18218	17376
4	3319	3430	3440	2474	4214	4215	604	680	652	9490	10103	8969	15888	18427	17275
5	3361	3451	3419	2474	3865	3865	604	708	696	9244	10526	9262	15683	18549	17242
6	3376	3439	3413	2828	4216	4214	604	640	708	8636	10211	9010	15444	18506	17345
7	3332	3427	3401	2474	4215	3865	580	664	712	9075	10089	9243	15460	18395	17222
8	3372	3460	3425	2474	3863	4215	588	544	684	9004	10650	8687	15438	18517	17011
9	3361	3463	3439	2474	4214	3865	608	684	676	8929	10129	9349	15373	18490	17329
10	3330	3432	3432	2122	4215	4214	584	724	620	9241	9981	9103	15276	18351	17369
Avg	3347	3436	3422	2439	4110	3970	597	666	680	9127	10231	9193	15509	18442	17264