Abstract
This paper formally introduces a linear complementarity system (LCS) formulation for a continuous-time, multi-user class, dynamic user equilibrium (DUE) model for the determination of trip timing decisions in a simplified single bottleneck model. Existence of a Lipschitz solution trajectory to the model is established by a constructive time-stepping method whose convergence is rigorously analyzed. The solvability of the time-discretized subproblems by Lemke’s algorithm is also proved. Combining linear complementarity with ordinary differential equations and being a new entry to the mathematical programming field, the LCS provides a computational tractable framework for the rigorous treatment of the DUE problem in continuous time; this paper makes a positive contribution in this promising research venue pertaining to the application of differential variational theory to dynamic traffic problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Arnott R., De Palma A., Lindsey R.: Schedule delay and departure time decisions with heterogeneous commuters. Trans. Res. Rec. 1197, 56–67 (1988)
Arnott R., De Palma A., Lindsey R.: A structural model of peak-period congestion: a traffic bottleneck with elastic demand. Am. Econ. Rev. 83, 161–179 (1993)
Blumberg, M., Bar-Gera, H.: Consistent node arrival order in dynamic network loading models. Trans. Res. B Methodol. (in press)
Camlibel, M.K.: Complementarity Methods in the Analysis of Piecewise Linear Dynamical Systems. Ph.D. thesis, Center for Economic Research, Tilburg University, The Netherlands (2001)
Camlibel, M.K., Iannelli, L., Vasca, F.: Passivity and complementarity. Math. Program. Ser. A (in press)
Camlibel M.K., Pang J.S., Shen J.: Lyapunov stability of complementarity and extended systems. SIAM J. Optim. 17, 1056–1101 (2006)
Cottle R.W., Pang J.S., Stone R.E.: The Linear Complementarity Problem. Academic Press, Cambridge (1992)
Daganzo C.: The uniqueness of a time-dependent equilibrium distribution of arrivals at a single bottleneck. Trans. Sci. 19, 29–37 (1985)
Han L., Pang J.S.: Non-zenoness of a class of differential quasi-variational inequalities. Math. Program. Ser. A 121, 171–199 (2010)
Han L., Tiwari A., Camlibel K., Pang J.S.: Convergence of time-stepping schemes for passive and extended linear complementarity systems. SIAM J. Numer. Anal. 47, 1974–1985 (2009)
Heemels, W.P.M.H.: Linear Complementarity Systems: A Study in Hybrid Dynamics. Ph.D. thesis, Department of Electrical Engineering, Eindhoven University of Technology, The Netherlands (1999)
Heemels, W.P.M.H., Schumacher, J.M., Weiland, S.: Well-posedness of linear complementarity systems. In: Proceedings of the 38th IEEE Conference on Decision and Control, Phoenix, Arizona, pp. 3037–3042 (1999)
Heemels W.P.M.H., Schumacher J.M., Weiland S.: Linear complementarity systems. SIAM J. Appl. Math. 60, 1234–1269 (2000)
Hendrickson C., Kocur G.: Schedule delay and departure time decisions in a deterministic model. Trans. Sci. 15, 62–77 (1981)
Lang S.: Real and Functional Analysis, 3rd edn. Springer, Berlin (1993)
Lindsey R.: Existence, uniqueness, and trip cost function properties of user equilibrium in the bottle neck model with multiple user class. Trans. Sci. 38, 293–314 (2004)
Newell G.: The morning commute for nonidentical travelers. Trans. Sci. 21, 74–88 (1987)
Pang J.S., Shen J.: Strongly regular differential variational systems. IEEE Trans. Autom. Control 52, 242–255 (2007)
Pang J.S., Stewart D.E.: Differential variational inequalities. Math. Program. Ser. A 113, 345–424 (2008)
Ramadurai G., Ukkusuri S., Zhao J., Pang J.S.: A linear complementarity formulation for a single bottleneck model with heterogeneous commuters. Trans. Rese. B Methodol. 44(2), 193–214 (2010)
Schumacher J.M.: Complementarity systems in optimization. Math. Program. Ser. B 101, 263–296 (2004)
Shen J., Pang J.S.: Linear complementarity systems: Zeno states. SIAM J. Control Optim. 44, 1040–1066 (2005)
Shen J., Pang J.S.: Semicopositive linear complementarity systems. Int. J. Robust Nonlinear Control 17, 1367–1386 (2007)
Smith M.J.: The existence of a time-dependent equilibrium distribution of arrivals at single bottleneck. Trans. Sci. 18, 385–394 (1984)
Van Der Zijpp N., Koolstra K.: Multiclass continuous-time equilibrium model for departure time choice on single-bottleneck network. Trans. Res. Rec. 1783, 134–141 (2002)
Vickrey W.S.: Congestion theory and transport investment. Am. Econ. Rev. 59, 251–261 (1969)
Vickrey W.S.: Pricing, metering, and efficiently using urban transportation facilities. Highw. Res. Rec. 476, 36–48 (1973)
Author information
Authors and Affiliations
Corresponding author
Additional information
The work of this Jong-Shi Pang is based on research supported by the National Science Foundation under grants DMS-0754374, CMMI-0969600, and EFRI-1024984.
Rights and permissions
About this article
Cite this article
Pang, JS., Han, L., Ramadurai, G. et al. A continuous-time linear complementarity system for dynamic user equilibria in single bottleneck traffic flows. Math. Program. 133, 437–460 (2012). https://doi.org/10.1007/s10107-010-0433-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-010-0433-z