时变路况下自动卡车专用道网络设计优化

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

摘要/Abstract

摘要：

科学规划交通路网中的自动卡车专用道网络，对保障自动卡车货运安全与高效至关重要。本文研究了一类新的考虑交通网络中路段车流量随时间段变化的自动卡车专用道网络设计优化问题，规划不同时段的专用道设置方案和自动卡车运输网络，在实现自动卡车运输快速高效目标的同时，最小化专用道对普通交通造成的负面影响。本文首先将该问题构建为了一个混合整数非线性规划模型，随后，根据问题性质将非线性模型等价转化为线性模型。为有效求解模型，开发了一种基于实数编码的改进自适应大邻域搜索算法（improved adaptive large neighborhood search， IALNS），设计了重复比例破坏算子等6个定制算子以提高算法的寻优能力。最后，大量不同规模的算例测试结果表明，求解小规模算例时，利用IALNS算法能在4秒内得到与最优解平均差距为1.4%的满意解；求解中大规模算例时，与仅考虑随机破坏和修复算子的IALNS算法相比，利用IALNS算法能获得平均改进率为8.46%的更优解，验证了所设计算子的有效性。此外，与未考虑时变路况的方案相比，考虑时变路况的方案平均可以减少1.36%的负面影响，表明了考虑时变路况的必要性。

关键词: 自动卡车, 专用道网络, 时变路况, 路径规划, 自适应大邻域搜索算法

Abstract:

Scientifically planning dedicated lanes for automated trucks within a transportation network is crucial for ensuring safe and efficient freight transportation using automated trucks. A new optimization problem in designing a dedicated automated truck network is investigated， considering traffic flow variations across different time periods within the transportation network. The dedicated lane setup schemes and automated truck transportation networks for different time periods are proposed， ensuring rapid and efficient automated truck transport while minimizing the negative impact of the dedicated lanes on regular traffic. Firstly， the problem is formulated as a mixed-integer nonlinear programming model and subsequently transformed into an equivalent mixed-integer linear programming model. To solve it effectively， a tailored improved adaptive large neighborhood search （IALNS） algorithm with real-number encoding is developed to address the problem’s characteristics. Six tailored operators， such as the repeated proportional destroy operator， are designed to enhance its effectiveness. Finally， extensive numerical experiments show that， in small-scale instances， the average difference between the optimal solutions and those obtained by the tailored IALNS is only 1.40%， and the computation times are all less than 4 seconds. For large-scale instances， compared with the IALNS considering only random destroy and repair operators， the tailored IALNS obtains better solutions， with an average improvement of 8.46%， confirming the effectiveness of the designed operators. Additionally， considering time-varying road conditions， as opposed to ignoring them， reduces negative impacts by an average of 1.36%， verifying the necessity of including time-varying road conditions in the study.

Key words: automated truck, dedicated lane network, time-varying road conditions, route planning, adaptive large neighborhood search

中图分类号:

U495

吴鹏,冀书婕,田丽君. 时变路况下自动卡车专用道网络设计优化[J]. 中国管理科学, 2026, 34(10): 94-106.

Peng Wu,Shujie Ji,Lijun Tian. Optimal Dedicated Automated Truck Network Design under Time-varying Road Conditions[J]. Chinese Journal of Management Science, 2026, 34(10): 94-106.

图/表 10

图1

表1

符号说明"

符号	说明
集合
$G$	交通网络， $G = N, A, P$ ， $N$ 是节点集合， $A$ 是路段集合， $P$ 是时间段集合
$N$	网络中的节点集合， $i, j ∈ N$
$A$	网络中的路段集合， $A = i, j i, j ∈ N, i ≠ j$
$P$	网络中时间段集合， $p ∈ P$
$K$	任务的集合， $k ∈ K$
$O$	任务起点的集合， $o k ∈ O ⊆ N$
$D$	任务终点的集合， $d k ∈ D ⊆ N$
参数
$T i j$	普通车辆在路段 $(i, j)$ 上的自由流行驶时间
$τ i j p'$	设置专用道前，时间段 $p$ 内普通车辆在路段 $(i, j)$ 上的行驶时间
$τ i j p''$	设置专用道后，时间段 $p$ 内普通车辆在路段 $(i, j)$ 上的行驶时间
$q i j p$	时间段 $p$ 内路段 $(i, j)$ 上普通车辆的车流量
$c a p i j$	路段 $(i, j)$ 的道路通行能力，即单位时间内路段上能够通过的最大的车辆数量
$m i j$	路段 $(i, j)$ 上的车道数
$α, β$	BPR函数待定参数，由实际交通状况决定
$c i j p$	时间段 $p$ 内在路段 $(i, j)$ 上设置专用道的负面影响
$h p$	时间段 $p$ 的节点时刻， $h b, h b + 1$ 表示第 $b$ 个时间段
$p k$	完成任务 $k$ 的时间限制
$t o k k$	任务 $k$ 从对应起点 $o k$ 出发的时刻
$τ i j$	自动卡车在路段 $(i, j)$ 上的自由流行驶时间
决策变量
$t i k$	任务 $k$ 到达节点 $i$ 的时刻
$a i p k$	若任务 $k$ 在时间段 $p$ 内到达点 $i$ ， $a i p k = 1$ ；否则为0
$x i j k$	若任务 $k$ 经过设有专用道的路段 $(i, j)$ ， $x i j k = 1$ ；否则为0
$z i j p$	若路段 $(i, j)$ 在时间段 $p$ 内设置专用道， $z i j p = 1$ ；否则为0

表1

图2

图3

表2

表3

Wilcoxon符号秩检验"

算例	T_1000_ T_1500	T_500_ T_1500	T_100_T_1500	T_50_ T_1500	T_500_ T_1000	T_100_ T_1000	T_50_ T_1000	T_100_ T_500	T_50_ T_500	T_50_ T_100
Ins_20_4	0.144	0.680	0.121	0.301	0.344	1.000	0.932	0.173	0.414	0.799
Ins_30_8	0.643	0.905	0.070	0.443	0.858	0.041	0.260	0.061	0.309	0.581
Ins_35_10	0.623	0.778	0.452	0.551	0.933	0.774	0.583	0.569	0.683	0.905
Ins_40_12	0.683	0.064	0.047	0.078	0.249	0.025	0.109	0.507	0.532	0.802
Ins_50_14	0.733	0.427	0.041	0.003	0.691	0.100	0.078	0.023	0.060	0.730
Ins_60_16	0.048	0.167	0.820	0.594	0.460	0.022	0.023	0.125	0.084	0.776
Ins_70_18	0.861	0.478	0.060	0.069	0.249	0.388	0.109	0.065	0.013	0.294
Ins_80_20	0.691	0.820	0.148	0.075	0.364	0.022	0.012	0.064	0.100	0.861
Ins_90_20	0.334	0.551	0.064	0.084	0.156	0.345	0.470	0.027	0.017	1.000
	α_0.25_α_0.05	α_0.5_α_0.05	α_0.75_α_0.05	α_0.95_α_0.05	α_0.5_α_0.25	α_0.75_α_0.25	α_0.95_α_0.25	α_0.75_α_0.5	α_0.95_α_0.5	α_0.95_α_0.75
Ins_20_4	0.669	0.581	0.832	0.235	0.291	0.762	0.194	0.595	0.013	0.085
Ins_30_8	0.672	0.385	0.877	0.437	0.108	0.325	0.892	0.574	0.073	0.311
Ins_35_10	0.662	0.855	0.538	0.465	0.475	0.656	0.754	0.504	0.811	0.750
Ins_40_12	0.071	0.036	0.045	0.105	0.944	0.657	0.776	0.755	0.388	0.432
Ins_50_14	0.177	0.682	0.583	0.124	0.091	0.136	0.778	0.650	0.047	0.233
Ins_60_16	0.798	0.527	0.054	0.442	0.721	0.046	0.087	0.025	0.176	0.271
Ins_70_18	0.594	0.753	0.016	0.753	0.505	0.047	0.169	0.023	0.362	0.233
Ins_80_20	0.925	0.610	0.859	0.047	0.311	0.271	0.084	0.919	0.041	0.030
Ins_90_20	0.334	0.363	0.551	0.865	0.050	0.496	0.826	0.346	0.177	0.433
	λ_0.25_ λ_0.05	λ_0.5_λ_0.05	λ_0.75_λ_0.05	λ_0.95_λ_0.05	λ_0.5_λ_0.25	λ_0.75_λ_0.25	λ_0.95_λ_0.25	λ_0.75_λ_0.5	λ_0.95_λ_0.5	λ_0.95_λ_0.75
Ins_20_4	0.207	0.944	0.473	0.526	0.352	1.000	0.766	0.273	0.777	0.590
Ins_30_8	0.725	0.667	0.395	0.483	0.572	0.673	0.260	0.315	0.205	0.200
Ins_35_10	0.646	0.308	0.894	0.208	0.165	0.929	0.166	0.245	0.046	0.903
Ins_40_12	0.041	0.162	0.078	0.115	0.363	0.311	0.776	0.695	0.510	0.308
Ins_50_14	0.650	0.826	0.191	0.027	0.778	0.532	0.212	0.233	0.112	0.650
Ins_60_16	0.445	0.437	0.283	0.314	0.717	0.725	0.044	0.860	0.131	0.157
Ins_70_18	0.401	0.570	0.294	0.033	0.706	0.409	0.132	0.694	0.109	0.050
Ins_80_20	0.477	0.047	0.164	0.289	0.074	0.345	0.649	0.140	0.140	0.778
Ins_90_20	0.955	0.363	0.022	0.496	0.470	0.033	0.414	0.256	0.776	0.427
	η_500_η_100	η_1000_η_100	η_2000_η_100	η_3000_η_100	η_1000_η_500	η_2000_η_500	η_3000_η_500	η_2000_η_1000	η_3000_η_1000	η_3000_η_2000
Ins_20_4	0.002	0.001	0.001	0.001	0.858	0.248	0.027	0.194	0.023	0.157
Ins_30_8	0.002	0.001	0.001	0.001	0.016	0.013	0.008	0.400	0.279	0.786
Ins_35_10	0.397	0.148	0.017	0.012	0.753	0.116	0.049	0.109	0.028	0.411
Ins_40_12	0.002	0.001	0.001	0.001	0.041	0.004	0.002	0.007	0.002	0.421
Ins_50_14	0.001	0.001	0.001	0.001	0.156	0.003	0.009	0.039	0.019	0.806
Ins_60_16	0.001	0.001	0.001	0.001	0.005	0.007	0.002	0.036	0.030	0.528
Ins_70_18	0.001	0.001	0.001	0.001	0.005	0.001	0.001	0.031	0.001	0.085
Ins_80_20	0.001	0.001	0.001	0.001	0.054	0.001	0.002	0.015	0.002	0.432
Ins_90_20	0.001	0.001	0.001	0.001	0.005	0.002	0.001	0.410	0.006	0.100

表3

表4

小规模算例实验结果"

算例	CPLEX		R_ALNS			IALNS
算例	Z_C	CPU Time(s)	Z_R	CPU Time(s)	Gap₁ (%)	Z_A	CPU Time(s)	$G a p 2$ (%)	Z_Amin	CPU Time(s)	Gap₃ (%)
Ins_20_2	46.94	0.06	49.74	2.46	5.98	46.94	2.73	0.00	46.94	2.79	0.00
Ins_20_4	84.05	11.63	88.60	2.64	5.41	84.94	2.65	1.06	84.05	2.89	0.00
Ins_25_4	117.78	28.66	123.63	2.93	4.97	119.73	3.15	1.66	117.78	2.96	0.00
Ins_25_6	141.83	65.88	149.64	2.92	5.51	143.27	3.04	1.02	141.83	3.04	0.00
Ins_30_6	178.63	1278.86	187.22	2.90	4.81	181.83	3.03	1.79	178.63	2.95	0.00
Ins_30_8	247.10	2113.00	266.02	2.83	7.66	251.13	2.91	1.63	247.10	2.89	0.00
Ins_35_8	288.97	2581.98	320.33	2.91	10.85	292.33	3.09	1.17	288.97	3.15	0.00
Ins_35_10	295.59	4165.86	340.71	2.91	15.26	304.01	3.11	2.85	295.59	3.14	0.00
Ins_40_10	-	18000.0	388.81	3.07	-	362.95	3.08	-	358.61	3.05	-
Average					7.56			1.40			0.00

表4

表5

表6

表7

参考文献 21

[1]	中华人民共和国交通运输部. 2024年交通运输行业主要统计指标［EB/OL］.（2025-03-31）［2025-04-16］..
	Ministry of Transport of the People’s Republic of China. Key statistical indicators for transportation industry in 2024［EB/OL］.（2025-03-31）［2025-04-16］..
[2]	中华人民共和国交通运输部. 2023年交通运输行业发展统计公报［EB/OL］.（2024-06-18）［2025-04-16］..
	Ministry of Transport of the People’s Republic of China. Statistical bulletin on the development of transportation industry in 2023［EB/OL］.（2024-06-18）［2025-04-16］. .
[3]	Fang Y F， Chu F， Mammar S， et al. An optimal algorithm for automated truck freight transportation via lane reservation strategy［J］. Transportation Research Part C： Emerging Technologies， 2013， 26： 170-183.
[4]	Song M T， Chen F， Ma X X. Organization of autonomous truck platoon considering energy saving and pavement fatigue［J］. Transportation Research Part D： Transport and Environment， 2021， 90： 102667.
[5]	Gungor O E， She R， Al-Qadi I L， et al. One for all： Decentralized optimization of lateral position of autonomous trucks in a platoon to improve roadway infrastructure sustainability［J］. Transportation Research Part C： Emerging Technologies， 2020， 120： 102783.
[6]	Hu Q L， Gu W H， Wu L X， et al. Optimal autonomous truck platooning with detours， nonlinear costs， and a platoon size constraint［J］. Transportation Research Part E： Logistics and Transportation Review， 2024， 186： 103545.
[7]	Wu Y F， Chu C B， Chu F， et al. Heuristic for lane reservation problem in time constrained transportation［C］//Proceedings of 2009 IEEE International Conference on Automation Science and Engineering，Bangalore， India， August 22-25， IEEE， 2009： 543-548.
[8]	Wu P， Chu F， Che A， et al. An efficient two-phase exact algorithm for the automated truck freight transportation problem［J］. Computers & Industrial Engineering， 2017， 110： 59-66.
[9]	吴鹏，颜宝卿. 基于双层规划的自动卡车运输专用网络设计优化［J］. 控制与决策， 2023， 38（9）： 2691-2700.
	Wu P， Yan B Q. Optimal design of dedicated network for automated truck transportation based on bi-level programming［J］. Control and Decision， 2023， 38（9）： 2691-2700.
[10]	Fang Y F， Chu F， Mammar S， et al. A cut-and-solve-based algorithm for optimal lane reservation with dynamic link travel times［J］. International Journal of Production Research， 2014， 52（4）： 1003-1015.
[11]	Li T， Wang N M， Jiang B， et al. A bi-objective lane reservation problem considering dynamic traffic flow［J］. IEEE Transactions on Intelligent Transportation Systems， 2023， 24（1）： 367-381.
[12]	吴兵，王海山，王艳丽. 考虑到达预测误差的短间距交叉口公交信号优先方法［J］. 同济大学学报（自然科学版）， 2023， 51（1）： 91-98.
	Wu B， Wang H S， Wang Y L. An active transit signal priority method considering short-term prediction error［J］. Journal of Tongji University （Natural Science）， 2023， 51（1）： 91-98.
[13]	Zhan X Y， Zheng Y， Yi X W， et al. Citywide traffic volume estimation using trajectory data［J］. IEEE Transactions on Knowledge and Data Engineering， 2017， 29（2）： 272-285.
[14]	Bureau of Public Roads. Traffic assignment manual［M］. Washington DC： Urban Planning Division， US Department of Commerce， 1964.
[15]	章可怡，石咏，郭海湘，等. 基于卡车-无人机协同的山区自然灾害应急物资调度优化决策研究［J］. 中国管理科学， 2025， 33（2）： 150-160.
	Zhang K Y， Shi Y， Guo H X， et al. Optimal decision-making for dispatching emergency supplies for natural disasters in mountainous areas based on truck-drone collaboration［J］. Chinese Journal of Management Science， 2025， 33（2）： 150-160.
[16]	Yen J Y. Finding the K shortest loopless paths in a network［J］. Management Science， 1971， 17（11）： 712-716.
[17]	张帅，刘思亮，张文宇. 电动车-无人机协同配送模式下带时间窗的车辆路径优化问题［J］. 中国管理科学， 2025， 33（4）： 131-141.
	Zhang S， Liu S L， Zhang W Y. Vehicle routing problems with time windows under the collaborative delivery mode of electric vehicle-drone［J］. Chinese Journal of Management Science， 2025， 33（4）： 131-141.
[18]	吴廷映，刘兵兵，余玉刚. 带取货点选择的电动车取送货路径优化的自适应大邻域搜索算法［J］. 中国管理科学， 2026，34 （4）： 144-155.
	Wu T Y， Liu B B， Yu Y G. An Adaptive large neighborhood search algorithm for electric vehicle pickup-and-delivery routing problem with pickup-points selection［J］. Chinese Journal of Management Science， 2026，34 （4）： 144-155.
[19]	Wu P， Che A D， Chu F， et al. An improved exact ε-constraint and cut-and-solve combined method for biobjective robust lane reservation［J］. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（3）： 1479-1492.
[20]	广州市交通运输局. 广州交通运输月报（2024）第 1期［EB/OL］.（2024-03-13）［2025-04-16］. .
	Guangzhou Municipal Transportation Bureau. Guangzhou transportation monthly report （2024） No.1［EB/OL］.（2024-03-13）［2025-04-16］..
[21]	Yu X P， Hu Y S， Wu P. The consistent vehicle routing problem considering driver equity and flexible route consistency［J］. Computers & Industrial Engineering， 2024， 187： 109803.

算例	R_ALNS				IALNS				Gap₄ (%)	Gap₅ (%)
算例	Z_R	CPU Time(s)	Z_Rmin	CPU Time(s)	Z_A	CPU Time(s)	Z_Amin	CPU Time(s)	Gap₄ (%)	Gap₅ (%)
Ins_40_10	388.81	3.07	365.31	3.02	362.95	3.08	358.61	3.05	-6.65	-1.83
Ins_40_12	452.35	3.94	408.49	4.22	400.96	4.01	363.12	4.07	-11.36	-11.11
Ins_50_12	491.36	5.20	467.22	5.13	450.75	5.14	434.70	5.11	-8.26	-6.96
Ins_50_14	540.35	5.39	488.65	5.48	492.70	5.47	464.51	5.50	-8.82	-4.94
Ins_60_14	697.84	5.68	642.19	5.71	611.29	6.04	595.96	6.51	-12.40	-7.20
Ins_60_16	744.47	6.19	677.86	6.42	668.52	6.46	616.79	6.70	-10.20	-9.01
Ins_70_16	912.50	6.75	876.19	6.73	844.31	6.87	804.37	6.83	-7.47	-8.20
Ins_70_18	1022.92	6.51	976.12	6.67	945.07	6.63	903.01	6.54	-7.61	-7.49
Ins_80_18	812.14	6.91	785.77	7.02	758.08	7.07	728.68	7.23	-6.66	-7.27
Ins_80_20	884.80	7.55	837.56	7.55	807.12	7.64	748.31	7.70	-8.78	-10.66
Ins_90_20	961.17	9.71	925.17	9.79	903.49	9.77	866.48	9.74	-6.00	-6.34
Ins_90_22	1043.14	10.02	1012.19	10.19	967.14	10.25	942.06	10.03	-7.29	-6.93
Average									-8.46	-7.33

算例	时间段	传统LRP研究	本研究	Gap(%)
Ins_30_8	3	250.96	247.10	-1.54
Ins_35_8	3	292.73	288.97	-1.28
Ins_35_10	3	299.35	295.59	-1.26
Average				-1.36