Online Routing Over Parallel Networks: Deterministic Limits and Data-driven Enhancements

References

• Agrawal S, Wang Z, Ye Y (2014) A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4):876–890.Link, Google Scholar
• Avrahami N, Azar Y (2007) Minimizing total flow time and total completion time with immediate dispatching. Algorithmica 47(3):253–268.Crossref, Google Scholar
• Bansal N, Dhamdhere K (2007) Minimizing weighted flow time. ACM Trans Algorithms 3(4):39–es.Crossref, Google Scholar
• Beesley ME (1965) The value of time spent in travelling: Some new evidence. Economica 32(126):174–185.Crossref, Google Scholar
• Bilali A, Isaac G, Amini S, Motamedidehkordi N (2019) Analyzing the impact of anticipatory vehicle routing on the network performance. Transportation Res. Proc. 41:494–506.Crossref, Google Scholar
• Blom M, Krumke SO, de Paepe WE, Stougie L (2001) The online TSP against fair adversaries. INFORMS J. Comput. 13(2):138–148.Link, Google Scholar
• Cabannes T, Vincentelli MAS, Sundt A, Signargout H, Porter E, Fighiera V, Ugirumurera J, Bayen AM (2018) The impact of GPS-enabled shortest path routing on mobility: A game theoretic approach. Proc. Trans. Res. Board 97th Annual Meeting (Transportation Research Board, Washington, DC), 7–11.Google Scholar
• Calafiore GC, Campi MC (2006) The scenario approach to robust control design. IEEE Trans. Automat. Contr. 51(5):742–753.Crossref, Google Scholar
• Caltrans (2010) US 101 South, corridor system management plan, 2010. Accessed July 1, 2020, https://dot.ca.gov/.Google Scholar
• Cole R, Dodis Y, Roughgarden T (2003) Pricing network edges for heterogeneous selfish users. Symposium on Theory of Computing (Association for Computing Machinery, New York), 521–530.Google Scholar
• Devanur NR, Hayes TP (2009) The adwords problem: Online keyword matching with budgeted bidders under random permutations. Proc. 10th ACM Conf. Electronic Commerce, EC ‘09 (Association for Computing Machinery, New York), 71–78.Google Scholar
• Devanur NR, Jain K, Sivan B, Wilkens CA (2011) Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Proc. 12th ACM Conf. Electronic Commerce, EC ‘11 (Association for Computing Machinery, New York) 29–38.Google Scholar
• Dong J, Mahmassani HS, Lu CC (2006) How reliable is this route?: Predictive travel time and reliability for anticipatory traveler information systems. Transportation Res. Record 1980(1):117–125.Crossref, Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. 2009 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 117–126.Google Scholar
• Fleischer L, Jain K, Mahdian M (2004) Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 277–285.Google Scholar
• Garatti S, Campi M (2019) Risk and complexity in scenario optimization. Math. Program. 191(2022)243–279.Google Scholar
• Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Sci. Cybernetics 4(2):100–107.Crossref, Google Scholar
• Hwang D, Jaillet P, Manshadi V (2018) Online resource allocation under partially predictable demand. Comput. Theory eJournal 69(3), 683–1013.Google Scholar
• Jaillet P, Wagner MR (2008) Generalized online routing: New competitive ratios, resource augmentation, and asymptotic analyses. Oper. Res. 56(3):745–757.Link, Google Scholar
• Koutsoupias E, Papadimitriou CH (2000) Beyond competitive analysis. SIAM J. Comput. 30(1):300–317.Crossref, Google Scholar
• Krichene W, Reilly JD, Amin S, Bayen AM (2017) Stackelberg Routing on Parallel Transportation Networks (Springer International Publishing, Cham, Switzerland), 1–35.Crossref, Google Scholar
• Li J, Zhang HM (2011) Fundamental diagram of traffic flow: New identification scheme and further evidence from empirical data. Transp. Res. Rec. 2260(1):50–59.Crossref, Google Scholar
• Lipton RJ, Tomkins A (1994) Online interval scheduling. SODA 94:302–311.Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoret. Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) AdWords and generalized online matching. J. ACM 54(5):22–es.Crossref, Google Scholar
• Motwani R, Saraswat V, Torng E (1998) Online scheduling with lookahead: Multipass assembly lines. INFORMS J. Comput. 10(3):331–340.Link, Google Scholar
• Nash JF (1950) Equilibrium points in n-person games. Proc. Natl. Acad. Sci. 36(1):48–49.Crossref, Google Scholar
• Ostrovsky M, Schwarz M (2019) Carpooling and the economics of self-driving cars. Proc. 2019 ACM Conf. Econom. Comput., 581–582.Google Scholar
• Patriksson M (2015) The Traffic Assignment Problem: Models and Methods (Dover Publications, Mineola, NY).Google Scholar
• Pigou A (1920) The Economics of Welfare (Macmillan, London).Google Scholar
• Pinson N, Spieksma FC (2019) Online interval scheduling on two related machines: The power of lookahead. J. Comb. Optim. 38(1):224–253.Crossref, Google Scholar
• Potts CN, Strusevich VA (2009) Fifty years of scheduling: A survey of milestones. J. Oper. Res. Soc. 60:s41–s68.Crossref, Google Scholar
• Pruhs K, Sgall J, Torng E (2004) Online scheduling. Leung JY, ed. Handbook of Scheduling—Algorithms, Models, and Performance Analysis (Chapman & Hall/CRC, Abingdon, UK). Google Scholar
• Roughgarden T (2018) Beyond worst-case analysis. ACM 62(3), 88–96.Crossref, Google Scholar
• Roughgarden T, Tardos E (2002) How bad is selfish routing? J. ACM. 49:236–259.Crossref, Google Scholar
• Statista (2018) Most popular mapping apps in the United States as of April 2018, by monthly users (in millions). Accessed February 4, 2021, https://www.statista.com/statistics/865413/most-popular-us-mapping-apps-ranked-by-audience/.Google Scholar
• Statistical Atlas (2018) Household income in San Francisco, California. Accessed January 20, 2021, https://statisticalatlas.com/place/California/San-Francisco/Household-Income#figure/household-income-percentiles.Google Scholar
• Sun B, Zeynali A, Li T, Hajiesmaili M, Wierman A, Tsang DH (2020) Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging. Proc. ACM Meas. Anal. Comput. Syst. 4(3):1–32.Google Scholar
• TomTom (2021) TomTom developer portal. Accessed January 25, 2021, https://developer.tomtom.com/.Google Scholar
• Varaiya P (2005) What we’ve learned about highway congestion. Access Magazine 1(27):2–9.Google Scholar
• Yang H, Huang HJ (2005) Mathematical and Economic Theory of Road Pricing (Emerald Publishing, Bingley, UK).Crossref, Google Scholar
• Zhou Y, Chakrabarty D, Lukose R (2008) Budget constrained bidding in keyword auctions and online knapsack problems. Papadimitriou C, Zhang S, eds. Internet and Network Economics, (Springer, Berlin Heidelberg), 566–576.Crossref, Google Scholar