基于全局视角的智慧城市无人驾驶管控机制及车辆调度问题研究

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

Abstract

Abstract:

As policy guidance and automatic driving technologies mature and popularize， unmanned driving has become an important development trend of smart city traffic， which will lead to a dramatic change in the control logic of urban traffic. Currently， both manual driving and automated driving are essentially on a local decision traffic mode based on the perspective of the individual vehicle， e.g.， a single vehicle planning its own route and making decisions about collision avoidance. In future smart cities， global scheduling of urban traffic resources and vehicles based on a global perspective will maximize the efficiency of the smart city， and will also become a new mode of traffic operation in a driverless environment. In this mode， the urban traffic control platform uniformly plans the driving route， decides the time of arrival at each intersection and the collision avoidance scheme. In view of this， firstly， the smart city traffic development blueprint is drawn from the aspects of global scheduling mechanism， road network environment and collision avoidance rules. The mode is then defined as a multi-level unmanned vehicle-simultaneous scheduling broken line routing problem considering the number of turns in irregular road network. To solve the problem， a mathematical model with the goal of “the shortest total running time + the least number of turns” is established. To quickly obtain a high-quality scheduling scheme， three optimization strategies are proposed to improve A* algorithm. Finally， 80 scale instances are set up to simulate the road network environment. 32 small-scale instances are used to assess the accuracy of the model and the efficiency of the algorithm， and 48 large-scale instances are used to compare the performance of the traditional A-star algorithm and the algorithm proposed in this paper. Results show that the algorithm proposed in this paper can reduce the number of turns to 1/2 of the traditional A* algorithm， and shorten the overall time of the vehicles to be scheduled by 0.49 h. Especially in large-scale problems， the reduction of the number of turns and the total time-saving effect are more significant. Compared with the traditional A* algorithm， the modified algorithm can reduce the average solution time by 0.061s. The research results can provide decision support for urban traffic management departments to plan and control future traffic and design global scheduling schemes.

Key words: smart city, unmanned driving, global scheduling, path planning, improved A-star algorithm

CLC Number:

F572

Kunpeng Li, Xuefang Han. Research on Autonomous Driving Control Mechanism and Vehicle Scheduling in Smart City Based on Global Perspective[J]. Chinese Journal of Management Science, 2024, 32(12): 140-152.

Figures/Tables 14

符号	定义	符号	定义
$N$	网络中东西方向的道路集合， $N = 1,2, . . ., n$	$l i k$	车辆k到达路口i前，其行驶路段对应的等级
$M$	网络中南北方向的道路集合， $M = 1,2, . . ., m$	$d i j$	路段(i, j)的长度
$I$	十字路口节点集合， $I = {1,2, ⋯, n * m}$	$K$	路网中正在行驶的车辆集合， $K = {1,2, …, k}$
$R$	路段集合， $R = r 12, r 1 (1 + m), ⋯, r (n * m) (n * m - n), r (n * m) (n * m - 1)$	$K i$	路网中经过路口i的车辆集合， $K i = {1,2, …, k i}$
G	路段等级集合， $g i j = g j i$ ， $G = g 12, . . ., g i (i + 1), g i (i - 1), g i (i + m), g i (i - m), . . ., g (n * m) (n * m - 1)$	$V$	待调度车辆集合， $V = V 1 ⋃ V 2 = {1,2, …, v 1, …, v}$ 。其中， $V 1 = {1,2, …, v 1}$ 表示普通车辆， $V 2 = v 1 + 1, …, v$ 表示特殊车辆
F_ij	辅助参数，当路口i与j连通时为1，否则为0；	$s v, f v$	待调度车辆v出发地和目的地对应的路口
$s p e e d$	无人驾驶车辆的行驶速度	$x v i j$	0-1变量，待调度车辆v经过路段 $r i j$ 时为1，否则为0
$w t$	车辆在路口避让一辆车的等待时间	$y v i m$	0-1变量，待调度车辆v需在路口i等待车辆m先经过时为1，否则为0
$p e l$	车辆转弯一次的惩罚时间	$z v i j$	0-1变量，待调度车辆v从路口i到路口j需要转弯时为1，否则为0
st	待调度车辆发出行驶请求的时间	$e t v i$	实数变量，表示待调度车辆v预计到达路口i的时刻
$t y p e i k$	表示路网中经过路口i的车辆k对应的等级。 $t y p e i k = 0$ 时，车辆k为普通车辆， $t y p e i k = 1$ 时为特殊车辆	$a t v i$	实数变量，表示待调度车辆v实际到达路口i的时刻
B	足够大的正整数，用于公式线性化

路口	(i→n₁)	(i→n₂)	(i→n₃)	(i→n₄)
g_v	8/50+0.03=0.19	5/50+0.06=0.16	6/50+0=0.12	/
h_v	2×4/50=0.16	2×4/50=0.16	3×4/50=0.24	/
p_v	0.03	0	0.03	/
d_v	-0.19 $\| α \|$	-0.16 $\| α \|$	0.12 $\| α \|$	/
F_v	0.38-0.19 $\| α \|$	0.32-0.16 $\| α \|$	0.39+0.12 $\| α \|$	+∞

算例	CPLEX						改进A^*算法					Gap1 (%)
算例	Upper（h）	Lower（h）	Time0 （s）	DT0 （h）	WT0（h）	Turn0	Obj1 （h）	Time1 （s）	DT1 （h）	WT1（h）	Turn1	Gap1 (%)
5-2-1-1	1.060	1.060	0.26	0.94	0.090	1	1.130	0.002	1.04	0.060	1	0.00	6.19
5-2-2-1	1.805	1.805	33.70	1.52	0.165	4	1.870	0.003	1.60	0.150	4	0.00	3.48
5-4-1-1	1.110	1.110	0.56	0.96	0.090	2	1.110	0.002	0.96	0.090	2	0.00	0.00
5-4-2-1	1.375	1.375	4.13	1.18	0.105	3	1.440	0.003	1.26	0.090	3	0.00	4.51
5-6-1-1	1.555	1.555	9.56	1.24	0.225	3	1.625	0.005	1.34	0.225	2	0.00	4.31
5-6-2-1	1.430	1.430	4.77	1.22	0.090	4	1.430	0.002	1.22	0.090	4	0.00	0.00
5-8-1-1	0.850	0.850	0.22	0.58	0.210	2	0.870	0.006	0.54	0.300	1	0.00	2.30
5-8-2-1	1.470	1.470	4.64	1.14	0.270	2	1.470	0.007	1.14	0.270	2	0.00	0.00
10-2-1-1	2.210	1.816	7201.27	1.94	0.180	3	2.290	0.021	1.96	0.180	5	17.81	3.49
10-2-2-1	2.725	2.277	7200.36	2.38	0.225	4	2.820	0.021	2.52	0.210	3	16.46	3.37
10-2-4-1	3.655	2.830	7200.45	3.16	0.345	5	3.685	0.023	3.22	0.345	4	22.57	0.81
10-2-4-2	5.570	4.040	7231.02	4.88	0.450	8	5.830	0.024	4.96	0.510	12	27.47	4.46
10-2-6-1	6.315	4.540	7243.56	5.64	0.525	5	6.325	0.021	5.62	0.495	7	28.11	0.16
10-2-6-2	8.880	5.840	7200.42	7.68	0.960	8	8.925	0.036	7.62	0.975	11	34.23	0.50
10-4-1-1	1.955	1.580	7201.55	1.40	0.435	4	2.060	0.114	1.64	0.270	5	19.16	5.10
10-4-2-1	1.780	1.613	7200.16	1.42	0.270	3	1.780	0.027	1.42	0.270	3	9.36	0.00
10-4-4-1	4.120	2.730	7200.17	3.04	0.870	7	4.395	0.022	3.30	0.855	8	33.74	6.26
10-4-4-2	7.145	4.577	7200.36	5.42	1.455	9	7.365	0.025	5.64	1.545	6	35.94	2.99
10-4-6-1	7.560	4.800	7200.78	5.76	1.560	8	7.970	0.06	6.14	1.590	8	36.51	5.14
10-4-6-2	8.730	5.435	7200.53	6.78	1.710	8	8.880	0.108	6.96	1.620	10	37.74	1.69
10-6-1-1	1.840	1.840	5764.83	1.42	0.330	3	2.065	0.025	1.72	0.285	2	0.00	10.90
10-6-2-1	3.075	1.940	7200.45	2.28	0.645	5	3.225	0.034	2.52	0.555	5	36.91	4.65
10-6-4-1	4.285	2.706	7200.3	3.10	0.945	8	4.280	0.025	2.90	1.290	3	36.86	-0.12
10-6-4-2	5.730	3.730	7202.88	4.32	1.170	8	6.100	0.025	4.72	1.170	7	34.90	6.07
10-6-6-1	7.160	4.002	7205.23	4.94	1.920	10	7.420	0.027	5.14	1.980	10	44.10	3.50
10-6-6-2	5.240	3.500	7239.05	3.80	1.110	11	5.370	0.026	4.08	1.050	8	33.21	2.42
10-8-1-1	1.720	1.720	2934.7	1.12	0.540	2	1.745	0.029	1.16	0.555	1	0.00	1.43
10-8-2-1	2.500	1.845	7203.34	1.72	0.630	5	2.510	0.029	1.76	0.630	4	26.20	0.40
10-8-4-1	6.375	3.479	7204.48	4.20	2.055	4	6.325	0.055	4.12	2.085	4	45.43	-0.79
10-8-4-2	6.055	3.330	7200.34	4.12	1.755	6	6.265	0.027	4.30	1.815	5	45.00	3.35
10-8-6-1	10.495	5.010	7200.28	6.49	3.765	8	10.670	0.032	6.74	3.720	7	52.26	1.64
10-8-6-2	8.950	4.460	7200.31	5.74	3.000	7	8.805	0.029	5.76	2.745	10	50.16	-1.65

算例	改进A*算法			传统A*算法			Δ1 （h）	Δ2	Δ3 （s）
算例	Obj1（h）	Turn1	Time1（s）	Obj2（h）	Turn2	Time2（s）	Δ1 （h）	Δ2	Δ3 （s）
20-2-10-1	22.885	35	0.329	23.230	68	0.328	0.345	33	-0.001
20-2-10-2	22.950	25	0.316	23.635	62	0.330	0.685	37	0.014
20-2-20-1	44.350	42	0.309	45.070	103	0.336	0.720	61	0.027
20-2-20-2	38.910	40	0.329	39.300	89	0.337	0.390	49	0.008
20-2-40-1	57.785	62	0.348	58.700	122	0.343	0.915	60	-0.005
20-2-40-2	79.330	91	0.333	80.500	189	0.318	1.170	98	-0.015
20-4-10-1	25.705	18	0.332	26.080	57	0.351	0.375	39	0.019
20-4-10-2	27.115	23	0.328	28.130	72	0.331	1.015	49	0.003
20-4-20-1	46.030	41	0.330	46.905	101	0.352	0.875	60	0.022
20-4-20-2	38.660	31	0.360	39.185	61	0.345	0.525	30	-0.015
20-4-40-1	74.445	60	0.309	74.735	148	0.374	0.290	88	0.065
20-4-40-2	77.490	75	0.326	78.930	156	0.355	1.440	81	0.029
20-6-10-1	30.720	13	0.322	31.345	59	0.387	0.625	46	0.065
20-6-10-2	23.725	18	0.326	23.825	45	0.325	0.100	27	-0.001
20-6-20-1	42.275	38	0.330	42.865	91	0.323	0.590	53	-0.007
20-6-20-2	46.000	38	0.321	46.175	106	0.407	0.175	68	0.086
20-6-40-1	82.405	56	0.324	84.310	155	0.340	1.905	99	0.016
20-6-40-2	94.310	63	0.319	96.355	194	0.346	2.045	131	0.027
20-8-10-1	32.600	15	0.438	32.540	51	0.343	-0.060	36	-0.095
20-8-10-2	34.250	21	0.370	34.615	80	0.348	0.365	59	-0.022
20-8-20-1	50.805	29	0.337	51.985	87	0.338	1.180	58	0.001
20-8-20-2	45.170	26	0.332	45.355	61	0.364	0.185	35	0.032
20-8-40-1	103.140	59	0.333	105.240	193	0.373	2.100	134	0.040
20-8-40-2	102.135	60	0.350	102.745	155	0.473	0.610	95	0.123
40-2-10-1	40.325	31	4.742	39.320	83	4.699	-1.005	52	-0.043
40-2-10-2	42.655	37	4.771	43.850	110	4.865	1.195	73	0.094
40-2-20-1	90.140	77	4.718	90.470	200	4.741	0.330	123	0.023
40-2-20-2	84.740	71	4.733	85.360	195	4.686	0.620	124	-0.047
40-2-40-1	150.155	112	4.858	152.080	311	4.792	1.925	199	-0.066
40-2-40-2	145.275	125	4.772	145.810	335	4.822	0.535	210	0.050
40-4-10-1	45.225	26	4.710	45.595	100	4.902	0.370	74	0.192
40-4-10-2	46.035	35	4.691	45.310	100	5.094	-0.725	65	0.403
40-4-20-1	61.760	36	4.782	61.925	101	5.011	0.165	65	0.229
40-4-20-2	108.765	72	4.819	108.200	204	4.962	-0.565	132	0.143
40-4-40-1	155.200	82	4.788	156.970	305	4.811	1.770	223	0.023
40-4-40-2	184.695	102	4.779	185.595	364	4.796	0.900	262	0.017
40-6-10-1	54.805	23	4.765	53.345	88	4.919	-1.460	65	0.154
40-6-10-2	54.320	19	4.718	54.355	107	4.970	0.035	88	0.252
40-6-20-1	106.975	45	4.786	108.035	174	4.902	1.060	129	0.116
40-6-20-2	93.750	45	4.770	94.440	168	4.785	0.690	123	0.015
40-6-40-1	199.900	61	4.764	198.970	272	5.054	-0.930	211	0.290
40-6-40-2	196.705	58	4.860	197.310	264	4.808	0.605	206	-0.052
40-8-10-1	56.045	21	4.946	56.235	103	4.780	0.190	82	-0.166
40-8-10-2	56.125	16	4.784	56.200	66	5.065	0.075	50	0.281
40-8-20-1	98.100	36	4.779	98.135	153	4.959	0.035	117	0.180
40-8-20-2	125.110	29	4.785	125.220	198	4.718	0.110	169	-0.067
40-8-40-1	202.205	63	4.751	201.025	289	4.896	-1.180	226	0.145
40-8-40-2	193.525	57	4.782	193.630	260	5.143	0.105	203	0.361
Ave.	—	—	—	—	—	—	0.490	100	0.061

References 23

1	吴俊杰，郑凌方，杜文宇，等. 从风险预测到风险溯源：大数据赋能城市安全管理的行动设计研究［J］. 管理世界， 2020， 36（8）： 189-202.
	Wu J J， Zheng L F， Du W Y， et al. From risk predicting to risk tracing： An action design research on big data-enables urban security management［J］.Journal of Management World， 2020， 36（8）： 189-202.
2	蹇娅婷，田丽君，吴鹏.自动驾驶背景下停车换乘点和共享停车位的优化管理［J］.中国管理科学，2024， DOI：https：//doi.org/10.16381/j.cnki.issn1003-207x.2022.1516 .
	Jian Y T， Tian L J， Wu P. Optimal management of park-and-ride point and shared parking spaces in the era of autonomous vehicles［J］. Chinese Journal of Management Science， 2024， DOI：https：//doi.org/10.16381/j.cnki.issn1003-207x.2022.1516 .
3	Cascetta E， Cartenì A， Francesco L D. Do autonomous vehicles drive like humans？ A turing approach and an application to SAE automation Level 2 cars［J］. Transportation Research Part C： Emerging Technologies， 2022， 134： 1-15.
4	姚旭生，马寿峰，叶顺强，等.驻足观望还是捷足先登？行人和无人驾驶车冲突演化博弈分析［J］.中国管理科学， 2024， 32（7）： 138-149.
	Yao X S， Ma S F， Ye S Q， et al. Yield or Go？Evolutionary game analysis of pedestrian and autonomous vehicle conflicts［J］. Chinese Journal of Management Science，2024， 32（7）： 138-149.
5	霍治方，刘刚. 智能化转型背景下自动驾驶产业化的中国实践［J］.中国科技论坛， 2024（7）： 95-109.
	Huo Z F， Liu G. China's practice of industrializing autonomous driving in the context of intelligent transformation［J］. Forum on Science and Technology in China， 2024（7）： 95-109.
6	Chouhan A P， Banda G. Autonomous intersection management： A heuristic approach［J］. IEEE Access， 2018（6）： 53287-53295.
7	Robert S， Mark H. When human beings are like drunk robots： Driverless vehicles， ethics， and the future of transport［J］. Transportation Research Part C： Emerging Technologies， 2017， 80： 206-215.
8	何洪文，孙逢春，李梦林. 我国综合交通工程科技现状及未来发展［J］.中国工程科学，2023，25（6）： 202-211.
	He H W， Sun F C， Li M L. Current status and future development of integrated transportation technology in china［J］. Strategic Study of CAE， 2023， 25（6）： 202-211.
9	林添良，姚瑜，许文杰，等. 基于环境识别的电动工程机械无人驾驶行走方法［J］. 机械工程学报， 2021， 57（10）： 42-49.
	Lin T L， Yao Y， Xu W J， et al. Driverless walking method of electric construction machinery based on environment recognition［J］. Journal of Mechanical Engineering， 2021， 57（10）： 42-49.
10	Adnan N， Nordin S M， Bahruddin M A B， et al. How trust can drive forward the user acceptance to the technology？ In-vehicle technology for autonomous vehicle［J］. Transportation Research Part A： Policy and Practice， 2018， 118： 819-836.
11	Eliane H N， Roukaya I， Dorien K， et al. How to measure the impacts of shared automated electric vehicles on urban mobility［J］. Transportation Research Part D： Transport and Environment， 2021， 93： 1-18.
12	徐向阳，胡文浩，董红磊，等. 自动驾驶汽车测试场景构建关键技术综述［J］. 汽车工程， 2021， 43（4）： 610-619.
	Xu X Y， Hu W H， Dong H L， et al. Review of key technologies for autonomous vehicle test scenario construction［J］. Automotive Engineering， 2021， 43（4）： 610-619.
13	Rahman M H， Mohamed A A， Wu Y N. A multi-vehicle communication system to assess the safety and mobility of connected and automated vehicles［J］. Transportation Research Part C： Emerging Technologies， 2021， 124：1-12.
14	禹乐文，罗霞，刘仕焜.复杂车路环境下自动驾驶车辆换道仿真研究［J］.计算机仿真，2021，38（5）： 146-152.
	Yu L W， Luo X， Liu S K. Research on simulation of lane-changing for autonomous vehicles under complex road conditions［J］. Computer Simulation， 2021， 38（5）： 146-152.
15	魏民祥，滕德成，吴树凡. 基于Frenet坐标系的自动驾驶轨迹规划与优化算法［J］. 控制与决策， 2021， 36（4）： 815-824.
	Wei M X， Teng D C， Wu S F. Trajectory planning and optimization algorithm for automated driving based on Frenet coordinate system［J］. Control and Decision， 2021， 36（4）： 815-824.
16	Qian L P， Feng A Q， Yu N N， et al. Vehicular networking enabled vehicle state prediction via two-level quantized adaptive kalman filtering［J］. IEEE Internet of Things Journal， 2020， 7（8）： 7181-7193.
17	Pan X， Chen B， Timotheou S， et al. A convex optimal control framework for autonomous vehicle intersection crossing［J］. IEEE Transactions on Intelligent Transportation Systems， 2023， 24： 163–177.
18	Hao R， Zhang Y X， Ma W J， et al. Managing connected and automated vehicles with flexible routing at “lane-allocation-free” intersections［J］. Transportation Research Part C： Emerging Technologies， 2023， 152： 1-23.
19	Chow A H F， Sha R， Li S. Centralised and decentralised signal timing optimisation approaches for network traffic control［J］. Transportation Research Part C： Emerging Technologies， 2020， 113： 108-123.
20	王雷，王欣，刘德海，等. 智能网联下无人驾驶汽车配送路径优化方法［J］.系统科学与数学， 2020， 40（11）： 1984-1998.
	Wang L， Wang X， Liu D H， et al. Route optimization methodology for unmanned vehicle distribution in intelligent network ［J］. Journal of Systems Science and Mathematical Sciences， 2020， 40（11）： 1984-1998.
21	马晓磊，沈宣良，张钊，等. 基于拉格朗日松弛算法的自动驾驶公交调度优化研究［J］. 中国公路学报， 2019， 32（12）： 10-24.
	Ma X L， Shen X L， Zhang Z， et al. Optimization of autonomous bus scheduling based on Lagrangian relaxation［J］. China Journal of Highway and Transport， 2019， 32（12）： 10-24.
22	雷旭，李立，李光泽，等. 多车道交通流理论与应用研究综述［J］. 长安大学学报（自然科学版）， 2020， 40（4）： 78-90.
	Lei X， Li L， Li G Z， et al. Review of multilane traffic flow theory and application［J］. Journal of Chang'an University（Natural Science Edition）， 2020，40（4）：78-90.
23	张新艳，邹亚圣. 基于改进A*算法的自动导引车无碰撞路径规划［J］. 系统工程理论与实践， 2021， 41（1）： 240-246.
	Zhang X Y， Zou Y S. Collision-free path planning for automated guided vehicles based on improved A* algorithm［J］. Systems Engineering—Theory & Practice， 2021， 41（1）： 240-246.

模型求解结果	68	67	66	65	64	63	53	43	33	23	22	21
预计到达时间	6.5	6.58	6.77	6.865	7.015	7.13	7.24	7.335	7.445	7.545	7.66	7.80
实际到达时间	6.5	6.61	6.785	6.895	7.03	7.16	7.255	7.365	7.445	7.56	7.66	7.80
改进A*算法结果	68	67	57	56	46	36	26	25	24	23	22	21
预计到达时间	6.5	6.58	6.71	6.79	6.92	7.08	7.195	7.31	7.44	7.55	7.68	7.82
实际到达时间	6.5	6.61	6.71	6.82	6.92	7.095	7.21	7.34	7.47	7.58	7.68	7.82
传统A*算法结果	68	67	57	56	46	45	44	34	24	23	22	21
预计到达时间	6.5	6.58	6.71	6.79	6.92	7.04	7.17	7.305	7.44	7.55	7.68	7.82
实际到达时间	6.5	6.61	6.71	6.82	6.92	7.07	7.185	7.32	7.47	7.58	7.68	7.82

模型求解结果	13	23	33	43	53	63	73	83	84	85
预计到达时间	6.5	6.58	6.68	6.76	6.84	6.92	7	7.08	7.2	7.32
实际到达时间	6.5	6.58	6.68	6.76	6.84	6.92	7	7.08	7.2	7.32
改进A*算法结果	13	23	33	43	53	63	73	83	84	85
预计到达时间	6.5	6.58	6.68	6.76	6.84	6.92	7	7.08	7.2	7.32
实际到达时间	6.5	6.58	6.68	6.76	6.84	6.92	7	7.08	7.2	7.32
传统A*算法结果	13	23	24	25	35	45	55	65	75	85
预计到达时间	6.5	6.58	6.66	6.76	6.84	6.96	7.1	7.2	7.28	7.42
实际到达时间	6.5	6.58	6.66	6.76	6.84	6.96	7.1	7.2	7.28	7.42

求解方法	总时间	行驶时间（车1+车2）	等待时间（车1+车2）	转弯次数（车1+车2）
模型	2.21	1.12+0.82=1.94	0.18+0=0.18	2+1=3
改进A*算法	2.29	1.14+0.82=1.96	0.18+0=0.18	4+1=5
传统A*算法	2.48	1.14+0.92=2.06	0.18+0=0.18	6+2=8

Research on Autonomous Driving Control Mechanism and Vehicle Scheduling in Smart City Based on Global Perspective

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 23

Related Articles 1

Metrics

Comments

Recommended 0