##### Document Text Contents

Page 1

Two Applications of Intelligent Transportation

System

by

Hao Zhou

A dissertation submitted in partial ful�llment

of the requirements for the degree of

Doctor of Philosophy

(Industrial and Operations Engineering)

in The University of Michigan

2013

Doctoral Committee:

Professor Romesh Saigal, Chair

Professor Mingyan Liu

Assistant Professor G�abor Orosz

Assistant Professor Siqian Shen

Page 50

where |p| is the number of links contained in p, and ap

(i)

is the ith link in path p. And

we define the travel time of a path p as T p 1:

T p =

|p|∑

k=1

Tap

(k)

3.2.4.2 Vehicles

There are N vehicles, denoted by set N = {1, 2, . . . , N}, using the traffic network.

Vehicle i ∈ N will enter the network at time Ai.

The traffic controller’s job is to assign a path to each vehicle. The path assignment

for vehicle i is a vector xi = (x

1

i , x

2

i , . . . , x

P

i ), where x

j

i = 1 means vehicle i is assigned

to path j, and 0 otherwise. Obviously, a valid assignment xi requires that

∑P

j=1 x

j

i =

1.

Each vehicle has a utility function Ui(xi) that maps a valid assignment xi to a

real number:

Ui(xi) : {0, 1}P → R

It can be interpreted as the benefit vehicle i gets when travelling under assignment

xi.

Although this utility function can be of any form, for the purpose of demonstrating

our model, we use a linear utility function:

Ui(xi) =

∑

j∈P

v

j

ix

j

i

where v

j

i is the value of travelling in path j, by vehicle i. Note that the actual bid,

v̂

j

i , made by vehicle i for path j, may be different from the true value v

j

i .

1T p does not change as no congestion is allowed

38

Page 51

3.2.4.3 Time

The entire planning period is discretized into a set of intervals of equal length δ,

denoted as T = {1, 2, . . . , T}. δ is set small enough so that the travel time of any

link in the network is an integer multiple of δ, but not too small so as to make the

problem computationally difficult (issues of computation will be discussed in section

3.3 ).

The typical planning period δT can be set to 24 hours, or to the duration of the

peak hours when congestion is likely to happen.

3.2.5 Optimization Problem

Given a path assignment matrix for all drivers, x = (x1, x2, . . . , xN), and the bids

v̂

j

i for vehicle i and path j, we evaluate the system performance using the sum of the

utility of all vehicles (also called social utility function) U:

U(x) =

∑

i∈N

Ui(xi)

=

∑

i∈N

∑

j∈P

v̂

j

ix

j

i

Assuming that all links are congestion free, we define the following delay operator

τ

j

l for each l ∈ L, j ∈ P:

τ

j

l =

k:a

j

(k)

=l∑

k=1

T

a

j

(k)

in other words, τ

j

l is the time to travel to the entrance of link l, given that the

vehicle is on path j.

39

Page 100

Pigou, A. C. (1912), Wealth and welfare, Macmillan and Co., limited.

Rajamani, R., and S. Shladover (2001), An experimental comparative study of

autonomous and co-operative vehicle-follower control systems, Transportation

Research Part C: Emerging Technologies, 9(1), 15 – 31, doi:10.1016/S0968-

090X(00)00021-8.

Rajamani, R., and C. Zhu (2002), Semi-autonomous adaptive cruise control sys-

tems, Vehicular Technology, IEEE Transactions on, 51(5), 1186 – 1192, doi:

10.1109/TVT.2002.800617.

Rajamani, R., H.-S. Tan, B. K. Law, and W.-B. Zhang (2000), Demonstration of

integrated longitudinal and lateral control for the operation of automated vehicles

in platoons, Control Systems Technology, IEEE Transactions on, 8(4), 695 –708,

doi:10.1109/87.852914.

Rassenti, S. J., V. L. Smith, and R. L. Bulfin (1982), A combinatorial auction mecha-

nism for airport time slot allocation, The Bell Journal of Economics, pp. 402–417.

Schrank, D., and T. Lomax (1999), The 1999 annual mobility report: information for

urban america.

Sheffi, Y. (2004), Combinatorial auctions in the procurement of transportation ser-

vices, Interfaces, 34(4), 245–252.

Shladover, S., et al. (1991), Automated vehicle control developments in the path

program, Vehicular Technology, IEEE Transactions on, 40(1), 114 –130, doi:

10.1109/25.69979.

Smith, R. S., and F. Y. Hadaegh (2007), Closed-loop dynamics of cooperative vehicle

formations with parallel estimators and communication, Automatic Control, IEEE

Transactions on, 52(8), 1404–1414.

Swaroop, D., and J. Hedrick (1996), String stability of interconnected systems, Au-

tomatic Control, IEEE Transactions on, 41(3), 349 –357, doi:10.1109/9.486636.

Teodorović, D., K. Triantis, P. Edara, Y. Zhao, and S. Mladenović (2008), Auction-

based congestion pricing, Transportation Planning and Technology, 31(4), 399–416.

Toh, R. S., and S.-Y. Phang (1997), Curbing urban traffic congestion in singapore: a

comprehensive review, Transportation Journal, 37(2), 24–33.

Varaiya, P. (1993), Smart cars on smart roads: problems of control, Automatic Con-

trol, IEEE Transactions on, 38(2), 195 –207, doi:10.1109/9.250509.

Varaiya, P., and S. Shladover (1991), Sketch of an ivhs systems architecture, in Vehicle

Navigation and Information Systems Conference, 1991, vol. 2, pp. 909 – 922, doi:

10.1109/VNIS.1991.205835.

88

Page 101

Vickrey, W. (1961), Counterspeculation, auctions, and competitive sealed tenders,

The Journal of Finance, 16(1), 8–37.

Vickrey, W. S. (1969), Congestion theory and transport investment, The American

Economic Review, 59(2), 251–260.

Zhang, Y., B. Kosmatopoulos, P. Ioannou, and C. Chien (1999), Autonomous intel-

ligent cruise control using front and back information for tight vehicle following

maneuvers, IEEE Transactions on Vehicular Technology,, 48(1), 319 –328, doi:

10.1109/25.740110.

89

Two Applications of Intelligent Transportation

System

by

Hao Zhou

A dissertation submitted in partial ful�llment

of the requirements for the degree of

Doctor of Philosophy

(Industrial and Operations Engineering)

in The University of Michigan

2013

Doctoral Committee:

Professor Romesh Saigal, Chair

Professor Mingyan Liu

Assistant Professor G�abor Orosz

Assistant Professor Siqian Shen

Page 50

where |p| is the number of links contained in p, and ap

(i)

is the ith link in path p. And

we define the travel time of a path p as T p 1:

T p =

|p|∑

k=1

Tap

(k)

3.2.4.2 Vehicles

There are N vehicles, denoted by set N = {1, 2, . . . , N}, using the traffic network.

Vehicle i ∈ N will enter the network at time Ai.

The traffic controller’s job is to assign a path to each vehicle. The path assignment

for vehicle i is a vector xi = (x

1

i , x

2

i , . . . , x

P

i ), where x

j

i = 1 means vehicle i is assigned

to path j, and 0 otherwise. Obviously, a valid assignment xi requires that

∑P

j=1 x

j

i =

1.

Each vehicle has a utility function Ui(xi) that maps a valid assignment xi to a

real number:

Ui(xi) : {0, 1}P → R

It can be interpreted as the benefit vehicle i gets when travelling under assignment

xi.

Although this utility function can be of any form, for the purpose of demonstrating

our model, we use a linear utility function:

Ui(xi) =

∑

j∈P

v

j

ix

j

i

where v

j

i is the value of travelling in path j, by vehicle i. Note that the actual bid,

v̂

j

i , made by vehicle i for path j, may be different from the true value v

j

i .

1T p does not change as no congestion is allowed

38

Page 51

3.2.4.3 Time

The entire planning period is discretized into a set of intervals of equal length δ,

denoted as T = {1, 2, . . . , T}. δ is set small enough so that the travel time of any

link in the network is an integer multiple of δ, but not too small so as to make the

problem computationally difficult (issues of computation will be discussed in section

3.3 ).

The typical planning period δT can be set to 24 hours, or to the duration of the

peak hours when congestion is likely to happen.

3.2.5 Optimization Problem

Given a path assignment matrix for all drivers, x = (x1, x2, . . . , xN), and the bids

v̂

j

i for vehicle i and path j, we evaluate the system performance using the sum of the

utility of all vehicles (also called social utility function) U:

U(x) =

∑

i∈N

Ui(xi)

=

∑

i∈N

∑

j∈P

v̂

j

ix

j

i

Assuming that all links are congestion free, we define the following delay operator

τ

j

l for each l ∈ L, j ∈ P:

τ

j

l =

k:a

j

(k)

=l∑

k=1

T

a

j

(k)

in other words, τ

j

l is the time to travel to the entrance of link l, given that the

vehicle is on path j.

39

Page 100

Pigou, A. C. (1912), Wealth and welfare, Macmillan and Co., limited.

Rajamani, R., and S. Shladover (2001), An experimental comparative study of

autonomous and co-operative vehicle-follower control systems, Transportation

Research Part C: Emerging Technologies, 9(1), 15 – 31, doi:10.1016/S0968-

090X(00)00021-8.

Rajamani, R., and C. Zhu (2002), Semi-autonomous adaptive cruise control sys-

tems, Vehicular Technology, IEEE Transactions on, 51(5), 1186 – 1192, doi:

10.1109/TVT.2002.800617.

Rajamani, R., H.-S. Tan, B. K. Law, and W.-B. Zhang (2000), Demonstration of

integrated longitudinal and lateral control for the operation of automated vehicles

in platoons, Control Systems Technology, IEEE Transactions on, 8(4), 695 –708,

doi:10.1109/87.852914.

Rassenti, S. J., V. L. Smith, and R. L. Bulfin (1982), A combinatorial auction mecha-

nism for airport time slot allocation, The Bell Journal of Economics, pp. 402–417.

Schrank, D., and T. Lomax (1999), The 1999 annual mobility report: information for

urban america.

Sheffi, Y. (2004), Combinatorial auctions in the procurement of transportation ser-

vices, Interfaces, 34(4), 245–252.

Shladover, S., et al. (1991), Automated vehicle control developments in the path

program, Vehicular Technology, IEEE Transactions on, 40(1), 114 –130, doi:

10.1109/25.69979.

Smith, R. S., and F. Y. Hadaegh (2007), Closed-loop dynamics of cooperative vehicle

formations with parallel estimators and communication, Automatic Control, IEEE

Transactions on, 52(8), 1404–1414.

Swaroop, D., and J. Hedrick (1996), String stability of interconnected systems, Au-

tomatic Control, IEEE Transactions on, 41(3), 349 –357, doi:10.1109/9.486636.

Teodorović, D., K. Triantis, P. Edara, Y. Zhao, and S. Mladenović (2008), Auction-

based congestion pricing, Transportation Planning and Technology, 31(4), 399–416.

Toh, R. S., and S.-Y. Phang (1997), Curbing urban traffic congestion in singapore: a

comprehensive review, Transportation Journal, 37(2), 24–33.

Varaiya, P. (1993), Smart cars on smart roads: problems of control, Automatic Con-

trol, IEEE Transactions on, 38(2), 195 –207, doi:10.1109/9.250509.

Varaiya, P., and S. Shladover (1991), Sketch of an ivhs systems architecture, in Vehicle

Navigation and Information Systems Conference, 1991, vol. 2, pp. 909 – 922, doi:

10.1109/VNIS.1991.205835.

88

Page 101

Vickrey, W. (1961), Counterspeculation, auctions, and competitive sealed tenders,

The Journal of Finance, 16(1), 8–37.

Vickrey, W. S. (1969), Congestion theory and transport investment, The American

Economic Review, 59(2), 251–260.

Zhang, Y., B. Kosmatopoulos, P. Ioannou, and C. Chien (1999), Autonomous intel-

ligent cruise control using front and back information for tight vehicle following

maneuvers, IEEE Transactions on Vehicular Technology,, 48(1), 319 –328, doi:

10.1109/25.740110.

89