Link Transmission Model-Based Linear Programming Formulation for Network Design

Abstract

This article presents a linear programming formulation to solve the network design problem using the link transmission model (LTM) as the underlying traffic flow model. The original LTM was adapted by incorporating link-sending and receiving flows using linear inequalities. Furthermore, route choice was relaxed, and transfer flow variables were used to model vehicles’ routing decisions within the network. The objective function of the linear program aimed to minimize the total difference between the cumulative vehicle numbers (CVN) at the upstream and at the downstream boundaries of each link subject to flow-conservation and budget constraints. CVN were represented using transfer flows from connected links. The resulting formulation is a linear program that represents a dynamic system optimum traffic flow pattern, embedding the LTM’s network loading procedure. In contrast to the single-destination system optimum dynamic traffic assignment, based on the cell transmission model, the proposed formulation requires considerably fewer decision variables, thus potentially providing a more scalable approach. The proposed formulation was implemented on an example network to illustrate the behavior of the model, and was compared with the cell-based formulation. We show that the model describes free-flow and congested traffic flow states accurately in terms of shock-wave propagation, queuing of vehicles, and optimal total system travel time.

Get full access to this article

View all access options for this article.

References

Wardrop

J. G.

Road Paper. Some Theoretical Aspects of Road Traffic Research. Proceedings of the Institution of Civil Engineers, Vol. 1, No. 3, 1952, pp. 325–362.

Beckmann

McGuire

Winsten

C. B.

Studies in the Economics of Transportation. Yale University Press, New Haven, CT, 1956.

Papageorgiou

Dynamic Modeling, Assignment, and Route Guidance in Traffic Networks. Transportation Research Part B: Methodological, Vol. 24, No. 6, 1990, pp. 471–495.

Gazis

D. C.

Modeling and Optimal Control of Congested Transportation Systems. Networks, Vol. 4, No. 2, 1974, pp. 113–124.

D’Ans

G. C.

Gazis

D. C.

Optimal Control of Oversaturated Store-and-Forward Transportation Networks. Transportation Science, Vol. 10, No. 1, 1976, pp. 1–19.

Vickrey

Congestion Theory and Transport Investment. American Economic Review, Vol. 59, No. 2, 1969, pp. 251–60.

Hendrickson

Kocur

Schedule Delay and Departure Time Decisions in a Deterministic Model. Transportation Science, Vol. 15, No. 1, 1981, pp. 62–77.

Arnott

de Palma

Lindsey

Departure Time and Route Choice for the Morning Commute. Transportation Research Part B: Methodological, Vol. 24, No. 3, 1990, pp. 209–228.

Ghali

M. O.

Smith

M. J.

A Model for the Dynamic System Optimum Traffic Assignment Problem. Transportation Research Part B: Methodological, Vol. 29, No. 3, 1995, pp. 155–170.

10.

Shen

Nie

Zhang

H. M.

On Path Marginal Cost Analysis and Its Relation to Dynamic System-optimal Traffic Assignment. Proceedings of the 17th International Symposium on Transportation and Traffic Theory, Elsevier, 2007, pp. 319–352.

11.

Qian

Z. S.

Shen

Zhang

System-optimal Dynamic Traffic Assignment with and Without Queue Spillback: Its Path-based Formulation and Solution via Approximate Path Marginal Cost. Transportation Research Part B: Methodological, Vol. 46, No. 7, 2012, pp. 874–893.

12.

Merchant

D. K.

Nemhauser

G. L.

A Model and an Algorithm for the Dynamic Traffic Assignment Problems. Transportation Science, Vol. 12, No. 3, 1978, pp. 183–199.

13.

Carey

Optimal Time-varying Flows on Congested Networks. Operations Research, Vol. 35, No. 1, 1987, pp. 58–69.

14.

Wie

B.-W.

A Convex Control Model of Dynamic System-optimal Traffic Assignment. Control Engineering Practice, Vol. 6, No. 6, 1998, pp. 745–753.

15.

Ziliaskopoulos

A. K.

A Linear Programming Model for the Single Destination System Optimum Dynamic Traffic Assignment Problem. Transportation Science, Vol. 34, No. 1, 2000, pp. 37–49.

16.

Carey

, Nonconvexity of the Dynamic Traffic Assignment Problem. Transportation Research Part B: Methodological, Vol. 26, No. 2, 1992, pp. 127–133.

17.

Shen

Zhang

System Optimal Dynamic Traffic Assignment: Properties and Solution Procedures in the Case of a Many-to-one Network. Transportation Research Part B: Methodological, Vol. 65, 2014, pp. 1–17.

18.

Yang

Meng

Departure Time, Route Choice and Congestion Toll in a Queuing Network with Elastic Demand. Transportation Research Part B: Methodological, Vol. 32, No. 4, 1998, pp. 247–260.

19.

Chang

G.-L.

Mahmassani

H. S.

Engquist

M. L.

System-optimal Trip Scheduling and Routing in Commuting Networks. Transportation Research Record: Journal of the Transportation Research Board, 1989. 1251: 54–65.

20.

Daganzo

C. F.

The Cell Transmission Model: A Dynamic Representation of Highway Traffic Consistent with the Hydrodynamic Theory. Transportation Research Part B: Methodological, Vol. 28, No. 4, 1994, pp. 269–287.

21.

Daganzo

C. F.

The Cell Transmission Model, Part II: Network Traffic. Transportation Research Part B: Methodological, Vol. 29, No. 2, 1995, pp. 79–93.

22.

Waller

S. T.

Mouskos

K. C.

Kamaryiannis

Ziliaskopoulos

A. K.

A Linear Model for the Continuous Network Design Problem. Computer-Aided Civil and Infrastructure Engineering, Vol. 21, No. 5, 2006, pp. 334–345.

23.

Ukkusuri

S. V.

Linear Programs for the User Optimal Dynamic Traffic Assignment Problem. PhD thesis. University of Illinois, Urbana-Champaign, 2002.

24.

Yperman

Logghe

Immers

, The Link Transmission Model: An Efficient Implementation of the Kinematic Wave Theory in Traffic Networks. Proceedings of 10th EURO Working Group on Transportation Meeting, Poznan, Poland. Publishing House of Poznan University of Technology, 2005, pp. 122–127.

25.

Long

Chen

Szeto

Shi

Link-based System Optimum Dynamic Traffic Assignment Problems with Environmental Objectives. Transportation Research Part D: Transport and Environment, 2016, Vol. 60, pp. 56–75.

26.

Levin

M. W.

Congestion-aware System Optimal Route Choice for Shared Autonomous Vehicles. Transportation Research Part C: Emerging Technologies, Vol. 82, 2017, pp. 229–247.

27.

Lighthill

M. J.

Whitham

G. B.

On Kinematic Waves. II. A Theory of Traffic Flow on Long Crowded Roads. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, Vol. 229, 1955, pp. 317–345.

28.

Richards

P. I.

Shock Waves on the Highway. Operations Research, Vol. 4, No. 1, 1956, pp. 42–51.

29.

Newell

A Simplified Theory of Kinematic Waves in Highway Traffic, Part II: Queueing at Freeway Bottlenecks. Transportation Research Part B: Methodological, Vol. 27, No. 4, 1993, pp. 289–303.

30.

Courant

Friedrichs

Lewy

Über die partiellen Differenzengleichungen der mathematischen Physik. Mathematische Annalen, Vol. 100, No. 1, 1928, pp. 32–74.