Decentralized Cooperative Merging of Platoons of Connected and Automated Vehicles at Highway On-Ramps

Sharmila Devi Kumaravel, Andreas A. Malikopoulos, Ramakalyan Ayyagari This research was supported in part by ARPAE’s NEXTCAR program under the award number DE- AR0000796 and by the Delaware Energy Institute (DEI). This support is gratefully acknowledged.Sharmila Devi Kumaravel and Ramakalyan Ayyagari are with Department of Instrumentation and Control Engineering, National Institute of Technology, Tiruchirappalli, India [email protected]; [email protected]Andreas A. Malikopoulos is with the Department of Mechanical Engineering, University of Delaware, Newark, DE 19716 USA [email protected]

Abstract

In this paper, we present an optimization framework for cooperative merging of platoons of connected and automated vehicles at highway on-ramps. The framework includes (1) an optimal scheduling algorithm, through which, each platoon derives the sequence and time to enter the highway safely, and (2) the formulation of an optimal control problem the solution of which allows each platoon to derive its optimal control input (acceleration/deceleration) in terms of fuel consumption. We evaluate the efficacy of the proposed optimization framework through VISSIM-MATLAB simulation environment. The proposed framework significantly reduces the crossing time and fuel consumption of platoons at the highway on-ramps compared to the baseline scenario where the vehicles on the minor road yield to the vehicles on the highway.

I INTRODUCTION

Highway on-ramp is one of the main sources of traffic bottlenecks as the capacity of the road section is lesser than the neighboring roads. Several research efforts in the literature have used ramp metering to maximize the capacity of the highway by regulating the inflow of vehicles from on-ramps. Athan [1] formulated a vehicle merging problem and facilitated the safe merging of vehicles without severe acceleration and deceleration except in emergency conditions. An overview of various research efforts in the literature that regulated flow of vehicles using ramp metering can be found in [2]. In these approaches, there is no communication between the merging vehicles and extreme care is expected from the drivers while merging from on-ramps. The advances in connected vehicle technologies and automated driving can avoid human errors and offer better opportunities to improve the mobility of commuters [3].

Cooperative merging control of connected and automated vehicles (CAVs) can reduce congestion and provide significant benefits in terms of road capacity, fuel consumption, travel time, and vehicle emissions [4]. Merging control algorithms for cooperative vehicles were presented in [5, 6] to create appropriate gap between vehicles from on-ramps to enter the motorway. In another effort, an optimal control framework for cooperative merging was presented to minimize fuel consumption [7]. A detailed summary of various approaches for coordination of CAVs at highway on-ramps can be found in [4].

Recently, an optimal control framework was developed to minimize travel time and fuel consumption of vehicles [8]. The research effort in [9] formulated an optimal control problem to minimize the engine effort and passenger discomfort. Some research efforts facilitated safe merging using optimization techniques [10], reinforcement learning [11] and multi-agent Q-learning [12]. The majority of research efforts in the literature have developed merging control algorithms without determining optimal merging sequence. Several effective solutions to compute optimal sequence can be achieved through scheduling theory [13]. Many scheduling theory-based control algorithms have been proposed in the literature to optimally coordinate the vehicles at various transportation scenarios [14, 15, 16, 17, 18, 19].

In our proposed framework, We model the problem of cooperative merging at highway on-ramps as a job-shop scheduling problem, and present an optimal scheduling algorithm through which each platoon derives the sequence and time to enter the highway safely. Then, we present an optimal control problem where each platoon derives the optimal control input (acceleration/deceleration) in terms of fuel consumption of the platoons at the highway.

The remainder of the paper is organized as follows. In Section II, we present the problem formulation and the optimal scheduling algorithm. In Section III, we provide an analytical solution for the optimal control problem. In Section IV, we evaluate the efficacy of the proposed framework through simulations, and present simulation results. We conclude with a discussion in Section V.

II PROBLEM FORMULATION

We consider a traffic scenario where a secondary road with single-lane merges onto another single-lane main road and P1, P2, P3 and P4 are the platoons of CAVs at merging roadways (Fig. 1).

Refer to caption — Figure 1: Platoons of connected and automated vehicles at highway on-ramps.

The region where the secondary road merges onto the main road is called the merging zone (MZ) and has a length $L_{\_}{MZ}$ . The merging zone is a conflict area where a potential lateral collision could occur. There is also a control zone (CZ) inside of which the vehicles can communicate with each other. The length of the control zone is $L_{\_}{CZ}$ . A coordinator stores information about the geometry of the merging roadways and broadcasts this information back to the vehicles. Note that the coordinator does not take part in the decision-making process. In our modeling framework, we impose the following assumptions:

Assumption 1: The communication between the coordinator and CAVs occurs without any errors and delays.

Assumption 2: The platoons of CAVs enters the control zone as stable platoons, i.e., all the vehicles in the platoon move at a consensual speed and maintain the desired space between vehicles [20].

Assumption 3: The value of $L_{\_}{CZ}$ should be sufficiently large so that a platoon can reach the speed limit before entering the merging zone.

The first assumption may be strong, but it is relatively straightforward to relax it as long as the measurement noise and delays are bounded. We impose the second assumption since our main focus is to facilitate the safe merging of CAVs entering as platoons at highway on-ramps rather than the stability and formation of the platoons. However, future research should relax this assumption and study the implications of the proposed solution on the stability and formation of platoons. The third assumption is to enable the slower platoons with an initial speed less than the speed limit to reach the speed limit before they reach the merging zone.

II-A Vehicle Model and Constraints

Let $\displaystyle N(t)\in\mathbb{N}$ be the number of platoons of CAVs arriving at the control zone at time $\displaystyle t\in\mathbb{R}^{+}$ . Each platoon receives a unique identification number $\displaystyle k\in\mathbb{N}$ from the coordinator at the time of entry into control zone. The queue of platoons of CAVs in the control zone is denoted by $\mathcal{N}(t)=\{1,\ldots,N(t)\}$ . Let ${C}_{\_}k=\{1,\ldots,n_{\_}k\}$ , $n_{\_}k\in\mathbb{N}$ , be the number of vehicles in each platoon $\displaystyle k\in\mathcal{N}(t)$ . We assume that each vehicle $\displaystyle j\in C_{\_}k$ is governed by the second order dynamics

	$\displaystyle\dot{p}_{\_}j=v_{\_}j(t),$
	$\displaystyle\dot{v}_{\_}j=u_{\_}j(t),$		(1)

where $\displaystyle p_{\_}j(t)\in\mathcal{P}_{\_}j$ , $\displaystyle v_{\_}j(t)\in\mathcal{V}_{\_}j$ , $\displaystyle u_{\_}j(t)\in\mathcal{U}_{\_}j$ denote position, speed, and, acceleration/deceleration.

Let $\displaystyle t_{\_}{j}^{0}$ and $t_{\_}{j}^{m}$ be the time at which the leader vehicle $\displaystyle j\in C_{\_}k$ enters the control zone and merging zone, respectively. Let $\displaystyle x_{\_}j(t)=[p_{\_}j(t)\quad v_{\_}j(t)]^{T}$ denote the state of each vehicle $\displaystyle j\in C_{\_}k$ with ${x_{\_}j}^{0}=[p_{\_}j^{0}\quad v_{\_}j^{0}]^{T}$ as initial state, where $\displaystyle p_{\_}j^{0}=p_{\_}j(t_{\_}j^{0})=0$ , taking values in the state space $\displaystyle\mathcal{X}_{\_}j=\mathcal{P}_{\_}j\times\mathcal{V}_{\_}j$ . The control input and speed of each vehicle $\displaystyle j\in C_{\_}k$ is bounded with the following constraints

	$\displaystyle u_{\_}{\min}\leq u_{\_}j(t)\leq u_{\_}{\max},$		(2)
	$\displaystyle 0\leq v_{\_}{\min}\leq v_{\_}j(t)\leq v_{\_}{\max},$		(3)

where $\displaystyle u_{\_}{\min},u_{\_}{\max}$ are the minimum and maximum control inputs and $\displaystyle v_{\_}{\min},v_{\_}{\max}$ are the minimum and maximum speed limits, respectively.

II-B Optimal Scheduling Algorithm for Platoons Crossing the Merging Zone

In this section, we apply scheduling theory to derive a control algorithm that provides the optimal schedule for each platoon to enter the merging zone. We consider a job-shop scheduling problem to find the optimal sequence and schedule for the platoons at merging roadways. A job-shop scheduling problem addresses the scheduling of multiple jobs on a single machine or several machines. It optimally allocates the jobs on the machines with an objective to improve the performance criteria. We model the problem of cooperative merging of platoons at highway on-ramps as a job-shop scheduling problem. We consider merging roadways as a single machine and the platoons of CAVs as jobs.

Let $t_{\_}k^{\text{in}}$ be the time that a platoon $\displaystyle k\in\mathcal{N}(t)$ takes to reach the merging zone. We consider the speed at which the platoon enters the control zone as initial speed of the platoon. We consider two cases to compute the time at which each platoon reaches the merging zone. In Case 1, we consider that the initial speed of platoons is the same as the speed limit. In Case 2, we consider that the initial speed of platoons is less than the speed limit. Let $\displaystyle v_{\_}{k}^{0}=v_{\_}k(t_{\_}k^{0})$ be the initial speed of the platoon $\displaystyle k\in C_{\_}k$ .

Case 1: $\displaystyle v_{\_}{k}^{0}=v_{\_}{\max}$
We compute $\displaystyle{t_{\_}{k}^{\text{in}}}$ using $\displaystyle v_{\_}{\max}$ , i.e.,

\displaystyle t_{\_}{k}^{in}=\frac{L_{\_}{CZ}}{v_{\_}{\max}}.

(4)

Case 2: $\displaystyle v_{\_}{k}^{0}<v_{\_}{\max}$
Let $\displaystyle t_{\_}{k}^{a}$ be the time taken by the platoon $k$ to accelerate to the speed limit. Then,

\displaystyle t_{\_}{k}^{a}=\frac{v_{\_}{\max}-v_{\_}{k}^{0}}{u_{\_}{\max}}.

(5)

Let $\displaystyle d_{\_}{k}^{a}$ be the distance traveled during acceleration, then,

\displaystyle d_{\_}{k}^{a}=\frac{{({v_{\_}{\max}})^{2}}-(v_{\_}{k}^{0})^{2}}{2u_{\_}{\max}},

(6)

and thus,

\displaystyle t_{\_}{k}^{in}=t_{\_}{k}^{a}+\frac{L_{\_}{CZ}-d_{\_}{k}^{a}}{v_{\_}{\max}}.

(7)

Let $t_{\_}k^{\text{out}}$ be the time that a platoon $k\in\mathcal{N}(t)$ takes to exit the merging zone. Then,

\displaystyle t_{\_}{k}^{\text{out}}=\frac{L_{\_}{MZ}}{v_{\_}{\max}}+(|C_{\_}k|-1)\times t_{\_}k^{h}+t_{\_}{g},

(8)

where $|C_{\_}k|$ is the number of CAVs in platoon $\displaystyle k\in\mathcal{N}(t)$ , $\displaystyle t_{\_}{g}$ is the safe time gap provided to ensure safety of platoons entering and leaving the merging zone, and $\displaystyle t_{\_}{k}^{h}$ is the headway between consecutive CAVs in the platoon $k$ .

Definition 1: The completion time $t_{\_}k^{c}$ is the time taken by the platoon to completely exit the merging zone.The completion time $t_{\_}k^{c}$ of platoon $\displaystyle k\in\mathcal{N}(t)$ is

\displaystyle t_{\_}k^{c}\coloneqq t_{\_}k^{\text{in}}+t_{\_}k^{\text{out}}.

(9)

Definition 2: The total completion time $T_{\_}C$ of platoons to cross the merging zone is

\displaystyle T_{\_}C\coloneqq\sum\limits_{\_}{k=1}^{N}t_{\_}{k}^{c}.

(10)

Definition 3: Let $w_{\_}k$ be the weight assigned to each platoon $k\in\mathcal{N}(t)$ based on the priority. The total weighted completion time $T_{\_}{WC}$ of platoons is

\displaystyle T_{\_}{WC}\coloneqq\sum\limits_{\_}{k=1}^{N}w_{\_}kt_{\_}{k}^{c}.

(11)

We model the problem of cooperative merging of platoons of CAVs at highway on-ramps as $1||T_{\_}{WC}$ job-shop scheduling problem [21], where 1 represents a single machine, and $T_{\_}{WC}$ represents the total weighted completion time. A schedule is optimal if it minimizes $T_{\_}{WC}$ . The objective of the modeled $1||T_{\_}{WC}$ scheduling problem is to minimize the crossing time, i.e., the total weighted completion time of platoons at highway on-ramps. Each platoon leader solves $1||T_{\_}{WC}$ problem to derive the time to enter the merging zone with the objective to minimize the crossing time of platoons at the merging zone, i.e., total weighted completion time of platoons. The platoons entering the merging zone from the main roadway are given higher priority than platoons entering from the secondary road. The higher priority to platoons in main roadway allow them to enter the merging zone before the platoons entering from the secondary road. The weights $w_{\_}k$ are assigned based on the priority of the platoon. We aim to avoid the deceleration of vehicles in the main roadway. Hence, $w_{\_}k$ for platoons entering the main roadway is assigned greater value than the the platoons entering from the secondary road. Each platoon leader communicates with the coordinator to acquire the information about the geometry and topology of the merging roadways. In addition, the platoon leaders broadcast their attributes including the link number, lane number, unique identification number, the speed at which they enter the control zone, maximum acceleration, maximum speed limit, number of followers in the platoon, safe time gap, headway and speed limit to other platoon leaders and coordinator.

The optimal scheduling algorithm running in each platoon leader uses the information of initial speed, maximum acceleration, and maximum speed limit to compute the time that a platoon arrives at the merging zone. Then, it uses the information of the length of the merging zone, number of followers in the platoon, safe time gap, headway of each platoon, and speed limit to compute the time that the platoon exits the merging zone. Next, it computes the completion time of each platoon based on the weights assigned to the platoons. Then, it calculates the total weighted completion time of platoons. Further, the algorithm arranges the platoons in the non-decreasing order of weighted completion time. Finally, the algorithm computes the time at which each platoon has to enter the merging zone. The proposed scheduling algorithm yields an optimal schedule that minimizes the crossing time of platoons.

Data:

v_{\_}{k}^{0}

w_{\_}k

|C_{\_}k|

t_{\_}{k}^{h}

of each platoon

k

, current time

t

t_{\_}{g}

L_{\_}{CZ}

L_{\_}{MZ}

v_{\_}{\max}

u_{\_}{\max}

Result:

optimalSequence

and schedule

t_{\_}i^{m}

for platoons

1 Initialize variable

t_{\_}{last}^{l}\leftarrow 0

\triangleright

computation of total weighted completion time of platoons

2 for $k=1~{}to~{}N$ do

3 if $v_{\_}{\max}=v_{\_}{k}^{0}$ then

t_{\_}{k}^{\text{in}}\leftarrow L_{\_}{CZ}/v_{\_}{\max}

5 else if $v_{\_}{\max}<v_{\_}{k}^{0}$ then

t_{\_}{k}^{a}\leftarrow(v_{\_}{\max}-v_{\_}{k}^{0})/u_{\_}{\max}

d_{\_}{k}^{a}\leftarrow(v_{\_}{\max})^{2}-(v_{\_}{k}^{0})^{2}/2u_{\_}{\max}

t_{\_}k^{in}\leftarrow t_{\_}{k}^{a}+(L_{\_}{CZ}-d_{\_}{k}^{a})/v_{\_}{\max}

9 end if

11 end for

12for $k=1~{}to~{}N$ do

t_{\_}{k}^{\text{out}}\leftarrow L_{\_}{MZ}/v_{\_}{\max}+(|C_{\_}k|-1)*t_{\_}k^{h}+t_{\_}{g}

14 end for

15for $k=1~{}to~{}N$ do

t_{\_}{k}^{c}\leftarrow t_{\_}{k}^{in}+t_{\_}{k}^{\text{out}}

w_{\_}k^{c}\leftarrow t_{\_}{k}^{c}/w_{\_}k

18 end for

19Arrange platoons in non-decreasing order of

w_{\_}k^{c}

in an array

optimalSequence

\triangleright

Computation of time of entry of CAVs in Platoons

i=optimalSequence[1]

t_{\_}{i}^{m}\leftarrow t+t_{\_}{i}^{\text{in}}

t_{\_}{i}^{l}\leftarrow t+t_{\_}{i}^{c}

23 if $t_{\_}i^{m}<t_{\_}{last}^{l}$ then

t_{\_}i^{m}\leftarrow t_{\_}{last}^{l}

t_{\_}{i}^{l}\leftarrow t_{\_}{last}^{l}+t_{\_}{i}^{\text{out}}

26 end if

27for $j=2~{}to~{}N$ do

r=optimalSequence[j]

t_{\_}{r}^{m}\leftarrow t_{\_}{r-1}^{l}

t_{\_}{r}^{l}\leftarrow t_{\_}{r}^{m}

t_{\_}{r}^{\text{out}}

31 if $j==N$ then

last=optimalSequence[j]

t_{\_}{last}^{l}\leftarrow t_{\_}{j}^{l}

35 end if

37 end for

Algorithm 1 Computation of optimal sequence and schedule of platoons

Theorem 1: A schedule $\displaystyle\Lambda^{*}$ is optimal in minimizing the crossing time of the platoons, i.e., the total weighted completion time if and only if it places the platoons in the order of non-decreasing weighted completion time $\displaystyle w_{\_}{k}^{c}$ .

Proof: Let $p$ , $q$ , and $r\in\mathcal{N}(t)$ be the platoons in the control zone arriving at time $\displaystyle t$ and $\frac{t_{\_}r^{c}}{w_{\_}r}<\frac{t_{\_}p^{c}}{w_{\_}p}<\frac{t_{\_}q^{c}}{w_{\_}q}$ . Let $\Lambda$ be the schedule in which platoons are not arranged in the order of non-decreasing weighted completion times $\displaystyle w_{\_}{k}^{c}$ of platoons. Then in schedule $\Lambda$ , platoon $q$ precedes platoon $p$ and $\frac{t_{\_}q^{c}}{w_{\_}q}>\frac{t_{\_}p^{c}}{w_{\_}p}$ . Let $\Lambda^{*}$ be the another schedule in which platoon $p$ precedes platoon $q$ . We know that $t_{\_}p^{c}$ , $t_{\_}q^{c}$ , and $t_{\_}r^{c}$ are the completion time of platoons $p$ , $q$ , and $r$ , respectively. Let $w_{\_}p$ , $w_{\_}q$ , and $w_{\_}r$ be the weights assigned to platoons $p$ , $q$ , and $r$ , respectively.
Let $T_{\_}{WC}(\Lambda)$ and $T_{\_}{WC}(\Lambda^{*})$ be the total weighted completion time of the platoons in the schedule $\Lambda$ and $\Lambda^{*}$ , respectively. The total weighted completion time of schedules $(\Lambda)$ and $(\Lambda^{*})$ are

	$\displaystyle T_{\_}{WC}(\Lambda)$	$\displaystyle=$	$\displaystyle w_{\_}r(t+t_{\_}r^{c})+w_{\_}q(t+t_{\_}r^{c}+t_{\_}q^{c})$		(12)
			$\displaystyle+w_{\_}p(t+t_{\_}r^{c}+t_{\_}q^{c}+t_{\_}p^{c}),$		(12)

	$\displaystyle T_{\_}{WC}(\Lambda^{*})$	$\displaystyle=$	$\displaystyle w_{\_}r(t+t_{\_}r^{c})+w_{\_}p(t+t_{\_}r^{c}+t_{\_}p^{c})$		(13)
			$\displaystyle+w_{\_}q(t+t_{\_}r^{c}+t_{\_}p^{c}+t_{\_}q^{c}).$		(13)

T_{\_}{WC}(\Lambda^{*})-T_{\_}{WC}(\Lambda)=w_{\_}qt_{\_}p^{c}-w_{\_}pt_{\_}q^{c}<0.

(14)

This contradicts the optimality of schedule $\Lambda$ . Hence, schedule $\Lambda^{*}$ in which platoons arranged in the order of non-decreasing weighted completion time $\displaystyle w_{\_}{k}^{c}$ is optimal.

II-C Optimal Control Problem

Each platoon leader computes the time to enter the merging zone using the optimal scheduling algorithm. Then, each leader derives the optimal control input to enter the merging zone in a schedule specified by the scheduling algorithm. The position of platoons in the queue designates the time that a platoon enters the merging zone. Here, we have two cases: 1) If $t_{\_}k^{m}=t_{\_}k^{in}$ , then the leader solves a time optimal control problem, and 2) if $t_{\_}k^{m}>t_{\_}k^{in}$ , then the leader solves an energy optimal control problem to derive the optimal control input. The leader broadcasts the derived schedule and optimal control input to the following vehicles until the last follower has completely crossed the merging zone.

II-C1 Time Optimal Control Problem

For each leader $\displaystyle j\in C_{\_}k$ , we formulate the following time optimal control problem,

\displaystyle\min_{\_}{u_{\_}{j}\in\mathcal{U}_{\_}j}J_{\_}1^{j}(u_{\_}j(t))=\int_{\_}{t_{\_}j^{0}}^{t_{\_}j^{m}}dt=t_{\_}{j}^{m}-t_{\_}{j}^{0},

(15)

subject to: (1), (2), (3), $\displaystyle p_{\_}j(t_{\_}j^{0})=0$ , $\displaystyle p_{\_}j(t_{\_}{j}^{m})=L_{\_}{CZ}$ ,
and given $\displaystyle t_{\_}j^{0},v_{\_}{j}^{0},t_{\_}{j}^{m}$ ,
where $t_{\_}j^{0}$ and $t_{\_}{j}^{m}$ is the time at which the leader enters the control zone and merging zone, respectively.

II-C2 Energy Optimal Control Problem

For each leader $\displaystyle j\in C_{\_}k$ , we formulate the following energy optimal control problem,

\displaystyle\min_{\_}{u_{\_}{j}\in\mathcal{U}_{\_}j}J_{\_}2^{j}(u_{\_}j(t))=\frac{1}{2}\int_{\_}{t_{\_}j^{0}}^{t_{\_}j^{m}}u_{\_}j^{2}(t)\;dt,

(16)

subject to: (1), (2), (3), $\displaystyle p_{\_}j(t_{\_}j^{0})=0$ , $\displaystyle p_{\_}j(t_{\_}{j}^{m})=L_{\_}{CZ}$ and given $\displaystyle t_{\_}j^{0},v_{\_}{j}^{0},t_{\_}{j}^{m}$ ,

where $t_{\_}j^{0}$ and $t_{\_}{j}^{m}$ is the time at which the leader enters the control zone and merging zone, respectively.

III Analytical Solution

In this section, we present the closed-form analytical solutions for the time (15) and energy (16) optimal control problems for each leader $\displaystyle j\in C_{\_}k$ .

III-A Analytical Solution of the Time Optimal control problem

We derive the Hamiltonian function for each leader $j\in C_{\_}k$ with the state and control constraints as follows

	$\displaystyle H_{\_}j(t,p_{\_}j(t),v_{\_}j(t),u_{\_}j(t))=1+{\lambda_{\_}j^{p}}{v_{\_}j(t)}+\lambda_{\_}j^{v}u_{\_}j(t)$
	$\displaystyle+\mu_{\_}j^{a}(u_{\_}j(t)-u_{\_}{\max})+\mu_{\_}j^{b}(u_{\_}{\min}-u_{\_}j(t))$
	$\displaystyle+\mu_{\_}j^{c}(v_{\_}j(t)-v_{\_}{\max})+\mu_{\_}j^{d}(v_{\_}{\min}-v_{\_}j(t)),$		(17)

where $\displaystyle{\lambda_{\_}j^{p}}$ and $\displaystyle{\lambda_{\_}j^{v}}$ are costates and $\displaystyle{\mu_{\_}j^{a}}$ , $\displaystyle{\mu_{\_}j^{b}}$ , $\displaystyle{\mu_{\_}j^{c}}$ , and $\displaystyle{\mu_{\_}j^{d}}$ are Lagrange multipliers. We derive optimal control input for platoons with initial speed either equal to speed limit or less than speed limit while entering the control zone.
Case 1: $v_{\_}j^{0}\leq v_{\_}{\max}$
In this case, the optimal control input is

u_{\_}j^{*}(t)=\begin{cases}u_{\_}{\max},&\text{if $t_{\_}{j}^{0}\leq t\leq t_{\_}{j}^{0}+t_{\_}{j}^{a}$},\\ 0,&\text{if $t_{\_}{j}^{0}+t_{\_}{j}^{a}\leq t\leq t_{\_}{j}^{m}$}.\end{cases}

(18)

Substituting (18) in (1), we derive the optimal position and velocity

$\displaystyle p_{\_}j^{*}(t)=\frac{1}{2}u_{\_}jt^{2}+b_{\_}jt+c_{\_}j,$	$\displaystyle\text{if}~{}t_{\_}{j}^{0}\leq t\leq t_{\_}{j}^{0}+t_{\_}{j}^{a}$	(19)
$\displaystyle v_{\_}j^{*}(t)=u_{\_}jt+b_{\_}j,$	$\displaystyle\text{if}~{}t_{\_}{j}^{0}\leq t\leq t_{\_}{j}^{0}+t_{\_}{j}^{a}$	(20)
$\displaystyle p_{\_}j^{*}(t)=v_{\_}{\max}t+d_{\_}j,$	$\displaystyle\text{if}~{}t_{\_}{j}^{0}+t_{\_}{j}^{a}\leq t\leq t_{\_}{j}^{m}$	(21)
$\displaystyle v_{\_}j^{*}(t)=v_{\_}{\max},$	$\displaystyle\text{if}~{}t_{\_}{j}^{0}+t_{\_}{j}^{a}\leq t\leq t_{\_}{j}^{m}$	(22)

where $b_{\_}j$ , $c_{\_}j$ , and $d_{\_}j$ are integration constants computed using the initial and final conditions in (15).
Case 2: $v_{\_}j^{0}=v_{\_}{\max}$
The optimal control input based on [22] is

u_{\_}j^{*}(t)=0,\quad{t\in[t_{\_}{j}^{0},\quad t_{\_}{j}^{m}]}.

(23)

Substituting (23) in (1), we derive the optimal position and velocity,

	$\displaystyle p_{\_}j^{*}(t)$	$\displaystyle=v_{\_}{\max}t+d_{\_}j,\quad t\in[t_{\_}{j}^{0},~{}t_{\_}{j}^{m}],$		(24)
	$\displaystyle v_{\_}j^{*}(t)$	$\displaystyle=v_{\_}{\max},\quad t\in[t_{\_}{j}^{0},\quad t_{\_}{j}^{m}],$		(25)

where $d_{\_}j$ is integration constant computed using the initial and final conditions in (15).

III-B Analytical Solution of the Energy Optimal Control Problem

For this problem, the Hamiltonian function for each leader $j\in C_{\_}k$ is

	$\displaystyle H_{\_}j(t,p_{\_}j(t),v_{\_}j(t),u_{\_}j(t))=\frac{1}{2}u_{\_}j^{2}(t)+{\lambda_{\_}j^{p}}{v_{\_}j(t)}+\lambda_{\_}j^{v}u_{\_}j(t)$
	$\displaystyle+\mu_{\_}j^{a}(u_{\_}j(t)-u_{\_}{j,\max})+\mu_{\_}j^{b}(u_{\_}{j,\min}-u_{\_}j(t))$
	$\displaystyle+\mu_{\_}j^{c}(v_{\_}j(t)-v_{\_}{j,\max})+\mu_{\_}j^{d}(v_{\_}{j,\min}-v_{\_}j(t)),$		(26)

where $\displaystyle{\lambda_{\_}j^{p}}$ and $\displaystyle{\lambda_{\_}j^{v}}$ are costates, and $\displaystyle{\mu_{\_}j^{a}}$ , $\displaystyle{\mu_{\_}j^{b}}$ , $\displaystyle{\mu_{\_}j^{c}}$ , and $\displaystyle{\mu_{\_}j^{d}}$ are the Lagrange multipliers and $\mu_{\_}j^{a}=\mu_{\_}j^{b}=\mu_{\_}j^{c}=\mu_{\_}j^{d}=0$ as the state and control constraints are not active. The optimal control input based on [23] is

\displaystyle u_{\_}j^{*}=a_{\_}jt+b_{\_}j,\quad t\in[t_{\_}{j}^{0},\quad t_{\_}{j}^{m}].

(27)

substituting (27) in (1), we get the optimal position and velocity,

	$\displaystyle p_{\_}j^{*}(t)$	$\displaystyle=\frac{1}{6}a_{\_}jt^{3}+\frac{1}{2}b_{\_}jt^{2}+c_{\_}jt+d_{\_}j,\quad t\in[t_{\_}{j}^{0},\quad t_{\_}{j}^{m}],$		(28)
	$\displaystyle v_{\_}j^{*}(t)$	$\displaystyle=\frac{1}{2}a_{\_}jt^{2}+b_{\_}jt+c_{\_}j,\quad t\in[t_{\_}{j}^{0},\quad t_{\_}{j}^{m}],$		(29)

where $a_{\_}j,~{}b_{\_}j,~{}c_{\_}j$ , and $d_{\_}j$ are integration constants computed using initial and final conditions in (16).

IV Simulation Results and Discussions

We model the traffic scenario where secondary road with single lane merges onto single lane main road in VISSIM 11.00 simulation environment. The size of platoons entering the main roadway varies from $1$ to $5$ vehicles. The size of platoons entering from the secondary road ranges from $1$ to $3$ vehicles. The length of the merging zone is designed to be $30~{}m$ . Based on Assumption 3, the length of the control zone is designed to be $150~{}m$ so that the platoons can reach the speed limit before entering the merging zone. The maximum speed limit is set as $25~{}m/s$ . The maximum acceleration and minimum deceleration limit are $3~{}m/s^{2}$ and $-3~{}m/s^{2}$ , respectively.

The optimal scheduling algorithm is implemented in MATLAB. The information of the platoons are collected in real-time through COM interface from the VISSIM simulation environment. Based on the collected information, each platoon leader calculates the time to enter the merging zone. Further, the optimal control input for each platoon to enter the merging zone is derived. The speed of platoons corresponding to the derived optimal control input is updated in real-time through COM interface in VISSIM.

We compare the performance of the proposed framework with a baseline scenario where the vehicles from secondary road stop and yield for vehicles entering from the main road. We design the volume of vehicles entering from the main road as $1060~{}vph$ . The volume of vehicles entering the secondary road is considered as $720~{}vph$ . The simulation is run for $900$ seconds. The performance measures of the vehicles under baseline scenario and proposed optimal framework are shown in Figs. 2, 3, 4, and 5. The proposed framework eliminated the stop-and-go driving behavior and resulted in negligible delay for platoons. The proposed framework reduced average travel time and fuel consumption by 54.3% and 57.8%, respectively. The average delay is reduced by 88.92% and the average speed of platoons is increased by 63.53% compared to the baseline scenario.

V Concluding Remarks and Discussions

In this paper, we presented an optimization framework for cooperative merging of platoons of CAVs at highway on-ramps. We modeled the problem as a job-shop scheduling problem and presented an algorithm to derive the schedule of each platoon to enter the merging zone. Then, we provided the analytical solution for the optimal control problem to minimize fuel consumption and crossing time of platoons at highway on-ramps. We validated the proposed framework through simulations, and we noticed significant improvements in fuel consumption, while minimizing stop-and-go driving behavior.

Ongoing efforts consider lane changes for coordination of CAVs at multi-lane roads [24] and multiple scenarios [25]. In our framework, we assumed that vehicles form stable platoons before arriving the control zone. Future research should focus on the stability and formation of the platoons along with cooperative merging in mixed traffic environment with human-driven vehicles and CAVs.

References

[1] M. Athans, “A unified approach to the vehicle-merging problem,” Transp. Res.,vol. 3, no. 1, pp. 123–133, Apr. 1969.
[2] M. Papageorgiou and A. Kotsialos, “Freeway ramp metering: An overview,” IEEE transactions on intelligent transportation systems, vol. 3, no. 4, pp. 271–281, 2002.
[3] L. Zhao and A. A. Malikopoulos, “Enhanced mobility with connectivity and automation: A review of shared autonomous vehicle systems,” IEEE Intelligent Transportation Systems Magazine, 2020.
[4] J. Rios-Torres and A. A. Malikopoulos, “A survey on the coordination of connected and automated vehicles at intersections and merging at highway on-ramps,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 5, pp. 1066–1077, 2017.
[5] R. Scarinci, B. Heydecker, and A. Hegyi, “Analysis of traffic performance of a merging assistant strategy using cooperative vehicles,” IEEE Transactions on Intelligent Transportation Systems, vol. 16, no. 4, pp. 2094–2103, 2015.
[6] A. Mosebach, S. Röchner, and J. Lunze, “Merging control of cooperative vehicles,” IFAC-PapersOnLine, vol. 49, no. 11, pp. 168–174, 2016.
[7] J. Rios-Torres and A. A. Malikopoulos, “Automated and cooperative vehicle merging at highway on-ramps,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 4, pp. 780–789, 2017.
[8] W. Xiao and C. G. Cassandras, “Decentralized optimal merging control for connected and automated vehicles,” In 2019 American Control Conference (ACC), pp. 3315–3320, 2019.
[9] I. A. Ntousakis, I. K. Nikolos, and M. Papageorgiou, “Optimal vehicle trajectory planning in the context of cooperative merging on highways,” Transportation research part C: emerging technologies, vol. 71, pp. 464–488, 2016.
[10] G. Raravi, V. Shingde, K. Ramamritham, and J. Bharadia, “Merge algorithms for intelligent vehicles,” Proc. Next Gener. Des. Verif. Methodol. Distrib. Embed. Control Syst., pp. 51–65, 2007.
[11] P. Wang and C. Y. Chan, “Autonomous ramp merge maneuver based on reinforcement learning with continuous action space,” arXiv preprint arXiv:1803.09203, 2018.
[12] L. Schester and L. E. Ortiz, “Longitudinal position control for highway on-ramp merging: A multi-agent approach to automated Driving,” In 2019 IEEE Intelligent Transportation Systems Conference pp. 3461-3468, 2019.
[13] P. Brucker and P. Brucker, “Scheduling algorithms,” Vol. 3. Berlin: Springer, 2007.
[14] J. Wu, A. Abbas-Turki, and A. El Moudni, “Cooperative driving: an ant colony system for autonomous intersection management,” Applied Intelligence, vol. 37, no. 2, pp. 207–222, 2012.
[15] L. Bruni, A. Colombo, and D. Del Vecchio, “Robust multi-agent collision avoidance through scheduling,” In 52nd IEEE Conference on Decision and Control, pp. 3944–3950, 2013.
[16] N. Murgovski, G. R. de Campos, and J. Sjöberg, “Convex modeling of conflict resolution at traffic intersections,” In 2015 54th IEEE conference on decision and control, pp. 4708–4713, 2015.
[17] G.R. De Campos, F. Della Rossa, and A. Colombo, “Optimal and least restrictive supervisory control: Safety verification methods for human-driven vehicles at traffic intersections, In 2015 54th IEEE Conference on Decision and Control, pp. 1707–1712, 2015.
[18] B. Chalaki and A. A. Malikopoulos, “Time-optimal coordination for connected and automated vehicles at adjacent intersections,” arXiv preprint arXiv:1911.04082, 2020.
[19] M. A. Guney and I. A. Raptis, “Scheduling-Based Optimization for Motion Coordination of Autonomous Vehicles at Multilane Intersections,“ Journal of Robotics, 2020.
[20] W. S. Levine, and M. Athans, “On the optimal error regulation of a string of moving vehicles,” IEEE Transactions on Automatic Control, Vol. 11, no. 3, pp.355-361. 1966.
[21] W. E. Smith, “Various optimizers for single‐stage production,” Naval Research Logistics Quarterly, Vol. 3, no. 1‐2, pp. 59–66, 1956.
[22] S. D. Kumaravel, A. A. Malikopoulos, and R. Ayyagari, “Optimal coordination of platoons of connected and automated vehicles at signal-free intersections,” arXiv preprint arXiv:2001.04866, 2020.
[23] A. A. Malikopoulos, C. G. Cassandras, and Y. Zhang, “A decentralized energy-optimal control framework for connected automated vehicles at signal-free intersections,”Automatica, vol. 93, pp. 244–256, 2018.
[24] A. A. Malikopoulos, Beaver, L.E., and Chremos, I.V., “Optimal Time Trajectory and Coordination for Connected and Automated Vehicles,”Automatica, vol. 125, pp. 109469 2021.
[25] B. Chalaki and A. A. Malikopoulos, “Optimal Control of Connected and Automated Vehicles at Multiple Adjacent Intersections,” IEEE Trans. on Control Systems Tech., arXiv preprint arXiv:2008.02379, 2021.