Re-Routing Strategy of Connected and Automated Vehicles Considering Coordination at Intersections Heeseung Bang Student Member IEEE Andreas A. Malikopoulos Senior Member IEEE

2025-04-29 0 0 508.65KB 6 页 10玖币

侵权投诉

Re-Routing Strategy of Connected and Automated Vehicles

Considering Coordination at Intersections

Heeseung Bang, Student Member, IEEE, Andreas A. Malikopoulos, Senior Member, IEEE

Abstract— In this paper, we propose a re-routing strategy

for connected and automated vehicles (CAVs), considering

coordination and control of all the CAVs in the network. The

objective for each CAV is to ﬁnd the route that minimizes

the total travel time of all CAVs. We coordinate CAVs at

signal-free intersections to accurately predict the travel time

for the routing problem. While it is possible to ﬁnd a system-

optimal solution by comparing all the possible combinations

of the routes, this may impose a computational burden. Thus,

we instead ﬁnd a person-by-person optimal solution to reduce

computational time while still deriving a better solution than

selﬁsh routing. We validate our framework through simulations

in a grid network.

I. INTRODUCTION

OVER the last two decades, connected and automated

vehicles (CAVs) have attracted considerable attention

since they can improve safety, fuel economy, and other

trafﬁc conditions. To reduce fuel consumption and travel

time, several research efforts have focused on efﬁcient

coordination and control of CAVs at different trafﬁc

scenarios such as merging roadways [1]–[3], signal-free

intersections [4]–[7], and corridors [8]–[10]. These efforts

have developed different coordination methods to reduce

stop-and-go driving, which has resulted in shorter travel time

with less energy use.

As another way to alleviate trafﬁc issues, a signiﬁcant

number of research efforts have considered the routing

problem of CAVs, which derived a solution for a single CAV

and applied it to multiple vehicles. Chen and Cassandras

[11] considered the dynamic vehicle assignment problem

in a shared mobility system to optimizes the travel times

of CAVs and the waiting times of passengers. Tsao et al.

[12] presented a similar approach for ride-sharing using

model predictive control with ﬁxed trafﬁc conditions. While

these methods ﬁnd the efﬁcient route for a single CAV,

they are not veriﬁed for multiple CAVs applications. Some

other approaches proposed in the literature include graph

search algorithms [13], reinforcement learning techniques

[14]–[16], and mixed-integer linear programs [17]–[19].

Furthermore, other research efforts considered variation of

basic formulations by including different types of vehicles

[19], [20], adding battery constraints [21], and considering

interaction with infrastructures [22], [23].

This work was supported by NSF under Grants CNS-2149520 and

CMMI-2219761.

The authors are with the Department of Mechanical Engineering,

University of Delaware, Newark, DE 19716, USA. (emails:

heeseung@udel.edu; andreas@udel.edu.)

In addition to a single CAV, many studies have also

focused on larger-scale interactions between multiple CAVs.

In the majority of these studies, a travel latency function

was used to estimate travel delay caused by other CAVs

[24]–[26]. Recent research efforts have developed a method

for routing and relocating CAVs in more complex networks

[27] and considered situations where charging scheduling of

electric CAVs is required [28]. However, none of these efforts

considered the impact of microscopic phenomena such as

coordination and control of CAVs on trafﬁc conditions.

To the best of our knowledge, there have been only a few

studies focusing on the routing problem with consideration

of interactions between CAVs and their actual movements.

Chu et al. [29] solved the routing problem for each CAV

considering trafﬁc by employing a dynamic lane reversal

approach. However, they simply approximated the travel

time of CAVs proportional to the number of CAVs on each

road segment. Likewise, Mostaﬁzi et al. [30] developed a

decentralized routing framework with a heuristic algorithm,

but they estimated travel speeds inversely proportional to

the number of CAVs on the roads. In our previous work

[31], we introduced a new routing framework combined

with the coordination of CAVs. the framework predicts

trafﬁc conditions from coordination information and ﬁnds

the optimal route for each new travel request. However, we

have imposed an assumption that a new CAV does not affect

previously planned trajectories. This assumption sometimes

causes the situation where a CAV entering the network has

no solution because it yields all the roads that it can travel

through. In addition, all CAVs only ﬁnd their route at the

beginning of the trip because, once the trajectory is ﬁxed, it

does not get affected by any other CAVs’ decisions, which

is quite a strong assumption to apply in reality.

In this paper, we propose a re-routing framework for CAVs

with consideration of trafﬁc conditions resulting from each

CAV’s decision. The framework is built upon our previous

work [31], which consists of two parts: (i) at an intersection

level, we formulate a coordination problem to predict travel

time and acquire an exact trajectory, and (ii) we formulate a

routing problem using the predicted travel time at a network

level. To avoid computational challenge, we generate some

candidate routes for each CAV and ﬁnd the best combination

of the routes to reduce the complexity of the problem and

make it possible to apply this framework to more extensive

networks. The main contribution of this work is to advance

the state-of-the-art congestion-aware routing problem in a

way that makes the problem more realistic by relaxing

those assumptions. Another contribution is that we provide

arXiv:2210.00396v2 [eess.SY] 19 Feb 2023

RouterCoordinators

CAVs

Candidate Route

Predicted

Travel Time

Entry/Trajectory Information

Other CAVs

Information

Fig. 1: The concept diagram of the routing process.

a method that always yields a person-by-person optimal

solution, which is a series of the best choice for each CAV.

The remainder of this paper is structured as follows.

In Section II, we formulate the routing problem and

coordination problem. In Section III, we present algorithms

to solve the problems and discuss the optimality of the

solution. We validate our method through the simulations

results in Section IV. Finally, in Section V, we conclude

and discuss some directions for future work.

II. PROBLEM STATEMENT

In this paper, we develop a framework that consists

of multiple optimization problems at two different levels.

The upper level contains a routing framework for a road

network. We consider having a ﬁnite number of candidate

routes and formulate optimization problems to ﬁnd the best

combination of those routes. At the low level, we coordinate

CAVs to cross intersections fast without violating any safety

constraints, and a travel time computed from coordination

is directly involved in the upper-level optimization as a cost

function. The detailed problem formulation will be explained

next.

A. Trips and Routing on Road Network

We consider a road network given by a directed graph

G= (V,E), where Vis a set of nodes and Eis a set of

edges (roads). Each node is a junction point of two different

intersections (exiting from one intersection and entering

another one), and each node can simultaneously function

as the origin for one trip and the destination for another

trip. In the network, there exists a router that communicates

with CAVs and selects the best combination of routes and a

coordinator for each intersection which shares the geometry

of intersections and trajectories of other CAVs (Fig. 1).

Our framework considers a 100% penetration rate of CAVs

in the road network. Let N(t) = {1, . . . , N(t)}be a set

of CAVs traveling in the network at time t∈R≥0, where

N(t)∈Nis the total number of CAVs at moment. For each

CAV i∈ N (t), we have trip information Ii= (oi, di, ts

which consists of origin oi∈ V, destination di∈ V, and the

starting time of travel ts

i≤t. This implies that we receive

trip information only when a new CAV starts a trip and do

not have any information about trips departing in the near

future. We assume that each CAV joins the network and

departs from oiat time ts

iand that there are enough CAVs at

the origin nodes. To relax this assumption, one can consider

a whole trip of CAVs departing from and returning to stations

[31] or relocation of empty CAVs [28].

In our previous work [31], we assumed that a newly

introduced CAV does not affect previous CAVs’ trajectories.

This assumption made it possible to solve a substantial

centralized problem in a computationally distributed manner.

However, this is a strong assumption in reality and also

yields cases where no solution exists when a new CAV is

introduced. To relax this assumption, we let the router to

re-route all the CAVs in the network within new candidate

routes whenever a new CAV joins the network and ﬁnds a

system-optimal solution.

At every time t, when a new CAV joins the network, we

generate M∈Ndifferent candidate routes for each CAV

i∈ N (t), which connect the current location of CAV ito the

destination di. We denote M={1, . . . , M}to be an index

set of those routes and let Pi={Pi,1,...,Pi,M }denote a

set of all candidate routes for the CAV i, where Pi,m ⊂ E

is a m-th candidate route of the CAV i. This paper assumes

that a ﬁnite number of candidate routes are determined by a

high-level decision maker and given to the router. Next, we

deﬁne an assignment matrix to match the CAVs to one of

their candidate routes.

Deﬁnition 1. Let assignment matrix A(t)be a binary matrix

that maps all CAVs i∈ N (t)to a unique route Pi,m for

m∈ M.

Note that A(t)=[A1,...,AN(t)], where Ai=

[ai,1, . . . , ai,M ]Tis an assignment vector for CAV i∈ N (t).

The assignment matrix can be determined by solving an

optimization problem, which we deﬁne next.

Problem 1 (Optimal Routing).We ﬁnd a system-optimal

combination of the routes by solving the following problem

min

AnX

i∈N (t)X

m∈M

ai,mTi(A(t), m)o(1)

subject to: X

m∈M

ai,m = 1,∀i∈ N (t),

ai,m ∈ {0,1},∀i∈ N (t), m ∈ M,

where Ti(A(t), m)is the travel time of CAV ifollowing the

m-th candidate route. The constraints ensure each CAV to

be assigned to a unique route.

The travel time Ti(A(t), m)can be computed using the

coordination framework, which will be presented later in this

section.

B. Coordination at Intersections

Given the routes of all the trips, we now model

intersections and coordinate CAVs to travel without any

collision. Let L={1, . . . , L}denote a set of signal-

free intersections, where L∈Nis the total number of

intersections. We let Nl(t)⊂ N (t)denote a set, which

includes all the CAVs in the intersection l∈ L. Each

intersection consists of four entry nodes, four exit nodes,

and twelve edges connecting each entry node to the exit

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Re-RoutingStrategyofConnectedandAutomatedVehiclesConsideringCoordinationatIntersectionsHeeseungBang,StudentMember,IEEE,AndreasA.Malikopoulos,SeniorMember,IEEEAbstractInthispaper,weproposeare-routingstrategyforconnectedandautomatedvehicles(CAVs),consideringcoordinationandcontrolofalltheCAVsinthenetw...

展开>> 收起<<

Re-Routing Strategy of Connected and Automated Vehicles Considering Coordination at Intersections Heeseung Bang Student Member IEEE Andreas A. Malikopoulos Senior Member IEEE.pdf

共6页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Re-Routing Strategy of Connected and Automated Vehicles Considering Coordination at Intersections Heeseung Bang Student Member IEEE Andreas A. Malikopoulos Senior Member IEEE

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: