A new look at departure time choice equilibrium models with heterogeneous users

Akamatsu, Takashi and Wada, Kentaro and Iryo, Takamasa and Hayashi, Shunsuke (2020): A new look at departure time choice equilibrium models with heterogeneous users.

Abstract

This paper presents a systematic approach for analyzing the departure-time choice equilibrium (DTCE) problem of a single bottleneck with heterogeneous commuters. The approach is based on the fact that the DTCE is equivalently represented as a linear programming problem with a special structure, which can be analytically solved by exploiting the theory of optimal transport combined with a decomposition technique. By applying the proposed approach to several types of models with heterogeneous commuters, it is shown that (i) the essential condition for emerging equilibrium “sorting patterns,” which have been known in the literature, is that the schedule delay functions have the “Monge property,” (ii) the equilibrium problems with the Monge property can be solved analytically, and (iii) the proposed approach can be applied to a more general problem with more than two types of heterogeneities.

• Item Type: MPRA Paper
• Language: English
• Keywords: departure time choice equilibrium, linear programming, optimal transport, sorting
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; R - Urban, Rural, Regional, Real Estate, and Transportation Economics > R4 - Transportation Economics > R41 - Transportation: Demand, Supply, and Congestion ; Travel Time ; Safety and Accidents ; Transportation Noise

References

Aggarwal, A., Park, J., 1988. Notes on searching in multidimensional monotone arrays, in: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, IEEE. pp. 497–512.

Akamatsu, T., 2007. A system of tradable bottleneck permits for general networks. JSCE Journal of Infrastructure Planning and Management 63, 287–301.

Akamatsu, T., Sato, S., Nguyen, L.X., 2006. Tradable time-of-day bottleneck permits for morning commuters. JSCE Journal of Infrastructure Planning and Management 62, 605–620.

Akamatsu, T., Wada, K., 2017. Tradable network permits: A new scheme for the most efficient use of network capacity. Transportation Research Part C: Emerging Technologies 79, 178–195.

Akamatsu, T., Wada, K., Hayashi, S., 2015. The corridor problem with discrete multiple bottlenecks. Transportation Research Part B: Methodological 81, 808–829.

Arnott, R., 1998. Congestion tolling and urban spatial structure. Journal of Regional Science 38, 495–504.

Arnott, R., de Palma, A., Lindsey, R., 1994. The welfare effects of congestion tolls with heterogeneous commuters. Journal of Transport Economics and Policy 28, 139–161.

Arnott, R., de Palma, A., Lindsey, R., 1988. Schedule delay and departure time decisions with heterogeneous commuters. Transportation Research Record 476, 56–57.

Arnott, R., de Palma, A., Lindsey, R., 1990. Economics of a bottleneck. Journal of Urban Economics 27, 111–130. Arnott, R., de Palma, A., Lindsey, R., 1992. Route choice with heterogeneous drivers and group-specific congestion costs. Regional Science and Urban Economics 22, 71–102.

Ban, X.J., Pang, J.S., Liu, H.X., Ma, R., 2012. Continuous-time point-queue models in dynamic network loading. Transportation Research Part B: Methodological 46, 360–380.

Bein, W.W., Brucker, P., Park, J.K., Pathak, P.K., 1995. A Monge property for the d-dimensional transportation problem. Discrete Applied Mathematics 58, 97–109.

van den Berg, V., Verhoef, E.T., 2011. Winning or losing from dynamic bottleneck congestion pricing? Journal of Public Economics 95, 983–992.

Berliant, M., Tabuchi, T., 2018. Equilibrium commuting. Economic Theory 65, 609–627.

Burkard, R.E., 2007. Monge properties, discrete convexity and applications. European Journal of Operational Research 176, 1–14.

Cambanis, S., Simons, G., Stout, W., 1976. Inequalities for Ek(x, y) when the marginals are fixed. Zeitschrift fu ̈r Wahrscheinlichkeitstheorie und Verwandte Gebiete 36, 285–294.

Chen, H., Liu, Y., Nie, Y.M., 2015. Solving the step-tolled bottleneck model with general user heterogeneity. Transportation Research Part B: Methodological 81, 210–229.

Cohen, Y., 1987. Commuter welfare under peak-period congestion tolls: Who gains and who loses? International Journal of Transport Economics 14, 239–266.

Daganzo, C.F., 1985. The uniqueness of a time-dependent equilibrium distribution of arrivals at a single bottleneck. Transportation Science 19, 29–37.

Doan, K., Ukkusuri, S., Han, L., 2011. On the existence of pricing strategies in the discrete time heterogeneous single bottleneck model. Transportation Research Part B: Methodological 45, 1483–1500.

Dubuc, S., Kagabo, I., Marcotte, P., 1999. A note on the uniqueness of solutions to the transportation problem. INFOR: Information Systems and Operational Research 37, 141–148.

Fosgerau, M., 2015. Congestion in the bathtub. Economics of Transportation 4, 241–255.

Fosgerau, M., de Palma, A., 2012. Congestion in a city with a central bottleneck. Journal of Urban Economics 71, 269–277.

Fu, H., Akamatsu, T., Wada, K., 2018. Dynamic traffic assignment in a corridor network: Optimum vs. equilibrium. Presented at the 7th International Symposium on Dynamic Traffic Assignment.

Gubins, S., Verhoef, E.T., 2014. Dynamic bottleneck congestion and residential land use in the monocentric city. Journal of Urban Economics 80, 51–61.

Han, K., Friesz, T.L., Yao, T., 2013. A partial differential equation formulation of Vickrey’s bottleneck model, part I: Methodology and theoretical analysis. Transportation Research Part B: Methodological 49, 55–74. 40

Hendrickson, C., Kocur, G., 1981. Schedule delay and departure time decisions in a deterministic model. Transportation Science 15, 62–77.

Herbert, J.D., Stevens, B.H., 1960. A model for the distribution of residential activity in urban areas. Journal of Regional Science 2, 21–36.

Hoffman, A.J., 1963. On simple linear programming problems, in: Klee, V. (Ed.), Convexity: Proceedings of Symposia in Pure Mathematics, American Mathematical Society, Providence, RI. pp. 317–327.

Hoffman, A.J., 1985. On greedy algorithms that succeed, in: Anderson, I. (Ed.), Survey in Combinatrics, Cambridge University Press, Cambridge. pp. 97–112.

Iryo, T., Yoshii, T., 2007. Equivalent optimization problem for finding equilibrium in the bottleneck model with departure time choices, in: Heydecker, B. (Ed.), Selected Proceedings of the 4th IMA International Conference on Mathematics in Transport, Emerald, London. pp. 231–244.

Iryo, T., Yoshii, T., Asakura, Y., 2005. Mathematical analysis of equilibrium in departure time choice problems. JSCE Journal of Infrastructure Planning and Management IV-66, 105–118.

Jin, W.l., 2015. Point queue models: A unified approach. Transportation Research Part B: Methodological 77, 1–16. Kantorovich, L., 1942. On the transfer of masses. Doklady Akademii Nauk USSR 37, 227–229.

Kantorovich, L., 1948. On a problem of Monge. Uspekhi Mathematicheskikh Nauk 3, 225–226 (in Russian). Kuwahara, M., Akamatsu, T., 1993. Dynamic equilibrium assignment with queues for one-to-many OD pattern, in: Daganzo, C.F. (Ed.), Proceedings of the 12th International Symposium on Transportation and Traffic Theory, Elsevior, Berkeley. pp. 185–204.

Kuwahara, M., Akamatsu, T., 1997. Decomposition of the reactive dynamic assignments with queues for a many-to-many origin-destination pattern. Transportation Research Part B: Methodological 31, 1–10.

Kuwahara, M., Newell, G.F., 1987. Queue evolution on freeways leading to a single core city during the morning peak. Proceedings of the 10th International Symposium on Transportation and Traffic Theory , 21–40.

Laih, C.H., 1994. Queueing at a bottleneck with single- and multi-step tolls. Transportation Research Part A: Policy and Practice 28, 197–208.

Larsson, T., Lindberg, P.O., Patriksson, M., Rydergren, C., 2002. On Traffic Equilibrium Models with a Nonlinear Time/Money Relation. Springer US, Boston, MA. pp. 19–31.

Li, Z.C., Huang, H.J., Yang, H., 2020. Fifty years of the bottleneck model: A bibliometric review and future research directions. Transportation Research Part B: Methodological 139, 311–342.

Lindsey, R., 2004. Existence, uniqueness, and trip cost function properties of user equilibrium in the bottleneck model with multiple user classes. Transportation Science 38, 293–314.

Lindsey, R.C., van den Berg, V.A., Verhoef, E.T., 2012. Step tolling with bottleneck queuing congestion. Journal of Urban Economics 72, 46–59.

Liu, Y., Nie, Y.M., Hall, J., 2015. A semi-analytical approach for solving the bottleneck model with general user heterogeneity. Transportation Research Part B: Methodological 71, 56–70.

More ́, J.J., 1974. Classes of functions and feasibility conditions in nonlinear complementarity problems. Mathematical Programming 6, 327–338.

Newell, G.F., 1987. The morning commute for nonidentical travelers. Transportation Science 21, 74–88.

Nie, Y.M., Zhang, M.H., 2009. Numerical solution procedures for the morning commute problem. Mathematical and Computer Modelling 49, 1295–1310.

Osawa, M., Fu, H., Akamatsu, T., 2018. First-best dynamic assignment of commuters with endogenous heterogeneities in a corridor network. Transportation Research Part B: Methodological 117, 811–831.

Pang, J.S., Han, L., Ramadurai, G., Ukkusuri, S., 2012. A continuous-time linear complementarity system for dynamic user equilibria in single bottleneck traffic flows. Mathematical Programming 133, 437–460.

Rachev, S.T., Ru ̈schendorf, L., 1998. Mass Transportation Problems: Volume 1: Theory; Volume 2: Applications. Springer Verlag.

Ramadurai, G., Ukkusuri, S.V., Zhao, J., Pang, J.S., 2010. Linear complementarity formulation for single bottleneck model with heterogeneous commuters. Transportation Research Part B: Methodological 44, 193–214.

Smith, M.J., 1984. The existence of a time-dependent equilibrium distribution of arrivals at a single bottleneck. Transportation Science 18, 385–394.

Takayama, Y., Kuwahara, M., 2017. Bottleneck congestion and residential location of heterogeneous commuters. Journal of Urban Economics 100, 65–79.

Takayama, Y., Kuwahara, M., 2020. Scheduling preferences, parking competition, and bottleneck congestion: A model of trip timing and parking location choices by heterogeneous commuters. Transportation Research Part C: Emerging Technologies 117, 102677.

Tchen, A.H., 1980. Inequalities for distributions with given marginals. The Annals of Probability 8, 814–827.

Vickrey, W.S., 1969. Congestion theory and transport investment. American Economic Review 59, 251–260.

Vickrey, W.S., 1973. Pricing, metering, and efficiently using urban transportation facilities. Highway Research Record 476, 36–48.

Villani, C., 2008. Optimal Transport: Old and New (Grundlehren der mathematischen Wissenschaften). Springer Verlag. Wada, K., Akamatsu, T., 2010. An e-market mechanism for implementing tradable bottleneck permits. JSCE Journal of Infrastructure Planning and Management 66, 160–177.

Wheaton, W.C., 1974. Linear programming and locational equilibrium. Journal of Urban Economics 1, 278–287.