Departure time choice equilibrium and optimal transport problems

Akamatsu, Takashi and Wada, Kentaro and Iryo, Takamasa and Hayashi, Shunsuke (2018): Departure time choice equilibrium and optimal transport problems.

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 the dynamic equilibrium distribution of departure times exhibits striking regularities under mild assumptions regarding schedule delay functions, in which commuters sort themselves according to their attributes, such as desired arrival times, schedule delay functions (value of times), and travel distances to a destination.

• 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 (3), 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 (4), 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 (3), 495–504.

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., 1992. Route choice with heterogeneous drivers and group-specific congestion costs. Regional Science and Urban Economics 22 (1), 71–102.

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

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 (3), 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 (2), 97–109.

Berliant, M., Tabuchi, T., 2018. Equilibrium commuting. Economic Theory 65 (3), 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 (4), 285–294.

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

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

Daganzo, C. F., 2013. System optimum and pricing for the day-long commute with distributed demand, autos and transit. Transportation Research Part B: Methodological 55, 98–117.

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 (9), 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 (2), 141–148.

Facchinei, F., Pang, J.-S., 2003. Finite-Dimensional Variational Inequalities and Complementarity Problems Volume I. Springer-Verlag New York.

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

Fosgerau, M., de Palma, A., 2012. Congestion in a city with a central bottleneck. Journal of Urban Economics 71 (3), 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.

Harker, P. T., Pang, J.-S., 1990. Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications. Mathematical Programming 48 (1-3), 161–220.

Hendrickson, C., Kocur, G., 1981. Schedule delay and departure time decisions in a deterministic model. Transportation Science 15 (1), 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 (2), 21–36.

Hoffman, A. J., 1963. On simple linear programming problems. In: Klee, V. (Ed.), Convexity: Proceedings of Symposia in Pure Mathematics. Vol. 7. 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 (779), 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 (2), 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), 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.

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.

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

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.

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

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

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

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 (2), 193–214.

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

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

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

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

Vickrey, W. S., 1969. Congestion theory and transport investment. American Economic Review 59 (2), 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 (2), 160–177.

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