{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:50Z","timestamp":1740109310669,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,11,1]],"date-time":"2021-11-01T00:00:00Z","timestamp":1635724800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,1]],"date-time":"2021-11-01T00:00:00Z","timestamp":1635724800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["016.Vidi.189.087","614.001.510"],"award-info":[{"award-number":["016.Vidi.189.087","614.001.510"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Flows over time have received substantial attention from both an optimization and (more recently) a game-theoretic perspective. In this model, each arc has an associated delay for traversing the arc, and a bound on the rate of flow entering the arc; flows are time-varying. We consider a setting which is very standard within the transportation economic literature, but has received little attention from an algorithmic perspective. The flow consists of users who are able to choose their route but also their departure time, and who desire to arrive at their destination at a particular time, incurring a <jats:italic>scheduling cost<\/jats:italic> if they arrive earlier or later. The total cost of a user is then a combination of the time they spend commuting, and the scheduling cost they incur. We present a combinatorial algorithm for the natural optimization problem, that of minimizing the average total cost of all users (i.e., maximizing the social welfare). Based on this, we also show how to set tolls so that this optimal flow is induced as an equilibrium of the underlying game.<\/jats:p>","DOI":"10.1007\/s10107-021-01725-z","type":"journal-article","created":{"date-parts":[[2021,11,1]],"date-time":"2021-11-01T13:02:46Z","timestamp":1635771766000},"page":"177-206","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Algorithms for flows over time with scheduling costs"],"prefix":"10.1007","volume":"192","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4243-1530","authenticated-orcid":false,"given":"Dario","family":"Frascaria","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neil","family":"Olver","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,11,1]]},"reference":[{"key":"1725_CR1","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall (1993)"},{"issue":"1","key":"1725_CR2","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0094-1190(90)90028-L","volume":"27","author":"R Arnott","year":"1990","unstructured":"Arnott, R., de Palma, A., Lindsey, R.: Economics of a bottleneck. J. Urban Econ. 27(1), 111\u2013130 (1990)","journal-title":"J. Urban Econ."},{"key":"1725_CR3","doi-asserted-by":"crossref","unstructured":"Baumann, N., Skutella, M.: Solving evacuation problems efficiently\u2014earliest arrival flows with multiple sources. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 399\u2013410 (2006)","DOI":"10.1109\/FOCS.2006.70"},{"key":"1725_CR4","doi-asserted-by":"crossref","unstructured":"Bhaskar, U., Fleischer, L., Anshelevich, E.: A Stackelberg strategy for routing flow over time. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pp. 192\u2013201 (2011)","DOI":"10.1137\/1.9781611973082.18"},{"issue":"1","key":"1725_CR5","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1287\/opre.2015.1348","volume":"63","author":"R Cominetti","year":"2015","unstructured":"Cominetti, R., Correa, J., Larr\u00e9, O.: Dynamic equilibria in fluid queueing networks. Oper. Res. 63(1), 21\u201334 (2015)","journal-title":"Oper. Res."},{"key":"1725_CR6","doi-asserted-by":"crossref","unstructured":"Cominetti, R., Correa, J.R., Olver, N.: Long term behavior of dynamic equilibria in fluid queuing networks. In: Proceedings of the 19th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 161\u2013172 (2017)","DOI":"10.1007\/978-3-319-59250-3_14"},{"key":"1725_CR7","doi-asserted-by":"crossref","unstructured":"Correa, J.R., Cristi, A., Oosterwijk, T.: On the price of anarchy for flows over time. In: Proceedings of the 2019 ACM Conference on Economics and Computation, (EC), pp. 559\u2013577 (2019)","DOI":"10.1145\/3328526.3329593"},{"key":"1725_CR8","doi-asserted-by":"crossref","unstructured":"Disser, Y., Skutella, M.: The simplex algorithm is NP-mighty. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pp. 858\u2013872 (2015)","DOI":"10.1137\/1.9781611973730.59"},{"issue":"3","key":"1725_CR9","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0167-6377(98)00037-6","volume":"23","author":"L Fleischer","year":"1998","unstructured":"Fleischer, L., Tardos, E.: Efficient continuous-time dynamic network flow algorithms. Oper. Res. Lett. 23(3), 71\u201380 (1998)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"1725_CR10","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1287\/opre.6.3.419","volume":"6","author":"LR Ford","year":"1958","unstructured":"Ford, L.R., Fulkerson, D.R.: Constructing maximal dynamic flows from static flows. Oper. Res. 6(3), 419\u2013433 (1958)","journal-title":"Oper. Res."},{"key":"1725_CR11","doi-asserted-by":"crossref","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press (1962)","DOI":"10.1515\/9781400875184"},{"key":"1725_CR12","doi-asserted-by":"crossref","unstructured":"Frascaria, D., Olver, N., Verhoef, E.T.: Emergent hypercongestion in Vickrey bottleneck networks. Accepted to Transportation Research Part B: Methodological. Preprint available as Tinbergen Institute Discussion Paper TI 2020-002\/VIII (2020)","DOI":"10.1016\/j.trb.2020.07.010"},{"issue":"1","key":"1725_CR13","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1307\/mmj\/1028998140","volume":"6","author":"D Gale","year":"1959","unstructured":"Gale, D.: Transient flows in networks. Michigan Math. J. 6(1), 59\u201363 (1959)","journal-title":"Michigan Math. J."},{"key":"1725_CR14","unstructured":"Harks, T.: Pricing in resource allocation games based on lagrangean duality and convexification. Preprint, arXiv:1907.01976 (2019)"},{"issue":"1","key":"1725_CR15","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1287\/mnsc.28.1.106","volume":"28","author":"JJ Jarvis","year":"1982","unstructured":"Jarvis, J.J., Ratliff, H.D.: Some equivalent objectives for dynamic network flow problems. Manag. Sci. 28(1), 106\u2013109 (1982)","journal-title":"Manag. Sci."},{"issue":"1","key":"1725_CR16","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s00224-010-9299-y","volume":"49","author":"R Koch","year":"2011","unstructured":"Koch, R., Skutella, M.: Nash equilibria and the price of anarchy for flows over time. Theory Comput. Syst. 49(1), 71\u201397 (2011)","journal-title":"Theory Comput. Syst."},{"key":"1725_CR17","doi-asserted-by":"crossref","unstructured":"K\u00f6hler, E., M\u00f6hring, R.H., Skutella, M.: Traffic networks and flows over time. In: Algorithmics of Large and Complex Networks - Design, Analysis, and Simulation, pp. 166\u2013196 (2009)","DOI":"10.1007\/978-3-642-02094-0_9"},{"issue":"2","key":"1725_CR18","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1287\/opre.21.2.517","volume":"21","author":"E Minieka","year":"1973","unstructured":"Minieka, E.: Maximal, lexicographic, and dynamic network flows. Oper. Res. 21(2), 517\u2013527 (1973)","journal-title":"Oper. Res."},{"key":"1725_CR19","doi-asserted-by":"crossref","unstructured":"Nisan, N., Roughgarden, T., Tardos, \u00c9., Vazirani, V.V. (eds) Algorithmic Game Theory. Cambridge University Press (2007)","DOI":"10.1017\/CBO9780511800481"},{"issue":"4","key":"1725_CR20","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1287\/moor.15.4.640","volume":"15","author":"AB Philpott","year":"1990","unstructured":"Philpott, A.B.: Continuous-time flows in networks. Math. Oper. Res. 15(4), 640\u2013661 (1990)","journal-title":"Math. Oper. Res."},{"key":"1725_CR21","doi-asserted-by":"crossref","unstructured":"Reiland, T.W.: Optimality conditions and duality in continuous programming ii. the linear problem revisited. J. Math. Anal. Appl., 77(2), 329\u2013343 (1980)","DOI":"10.1016\/0022-247X(80)90230-9"},{"key":"1725_CR22","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01585695","volume":"53","author":"HE Romeijn","year":"1992","unstructured":"Romeijn, H.E., Smith, R.L., Bean, J.C.: Duality in infinite dimensional linear programming. Math. Program. 53, 79\u201397 (1992)","journal-title":"Math. Program."},{"key":"1725_CR23","unstructured":"Sering, L., Skutella, M.: Multi-source multi-sink Nash flows over time. In: 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, (ATMOS), pp. 12:1\u201312:20 (2018)"},{"key":"1725_CR24","doi-asserted-by":"crossref","unstructured":"Sering, L., Koch, L.V.: Nash flows over time with spillback. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pp. 935\u2013945 (2019)","DOI":"10.1137\/1.9781611975482.57"},{"key":"1725_CR25","unstructured":"Sharkey, T.C.: Infinite Linear Programs. Wiley (2011)"},{"key":"1725_CR26","doi-asserted-by":"crossref","unstructured":"Skutella, M.: An introduction to network flows over time. In: Research Trends in Combinatorial Optimization, pp. 451\u2013482 (2009)","DOI":"10.1007\/978-3-540-76796-1_21"},{"issue":"1","key":"1725_CR27","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.ecotra.2015.01.001","volume":"4","author":"KA Small","year":"2015","unstructured":"Small, K.A.: The bottleneck model: an assessment and interpretation. Econ. Transp. 4(1), 110\u2013117 (2015)","journal-title":"Econ. Transp."},{"issue":"2","key":"1725_CR28","first-page":"251","volume":"59","author":"W Vickrey","year":"1969","unstructured":"Vickrey, W.: Congestion theory and transport investment. Am. Econ. Rev. 59(2), 251\u201360 (1969)","journal-title":"Am. Econ. Rev."},{"issue":"7","key":"1725_CR29","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1287\/opre.19.7.1602","volume":"19","author":"WL Wilkinson","year":"1971","unstructured":"Wilkinson, W.L.: An algorithm for universal maximal dynamic flows in a network. Oper. Res. 19(7), 1602\u20131612 (1971)","journal-title":"Oper. Res."},{"issue":"4","key":"1725_CR30","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/S0191-2615(97)00041-6","volume":"32","author":"H Yang","year":"1998","unstructured":"Yang, H., Meng, Q.: Departure time, route choice and congestion toll in a queuing network with elastic demand. Transp. Res. Part B: Methodol. 32(4), 247\u2013260 (1998)","journal-title":"Transp. Res. Part B: Methodol."},{"key":"1725_CR31","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01580132","volume":"5","author":"N Zadeh","year":"1973","unstructured":"Zadeh, N.: A bad network problem for the simplex method and other minimum cost flow algorithms. Math. Program. 5, 255\u2013266 (1973)","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01725-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01725-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01725-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T17:21:48Z","timestamp":1646846508000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01725-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,1]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1725"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01725-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2021,11,1]]},"assertion":[{"value":"30 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}