Local and global information in online stochastic shortest path problem and competitive analysis
*Mohsen AbdolhosseinzadehCorresponding authormohsen.ab@ubonab.ac.irDepartment of Mathematics and Computer SceinceUniversity of BonabBonab, 5551395133, IranView full profile → , Mehdi Djahangiridjahangiri.mehdi@maragheh.ac.irDepartment of MathematicsUniversity of MaraghehMaragheh, 5518779840, IranView full profile → , Mir Mohammad Alipouralipour@ubonab.ac.irDepartment of Computer EngineeringUniversity of BonabBonab, 5551395133, IranView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 11 Jul 2023
- Published Online:
- 03 Feb 2025
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JIOS-1584
- Pages:
- 2111–2127
Abstract
Keywords
Subject Classifications
References
[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ: Prentice-Hall (1993).
[2] M. K. Ardakani and L. Sun, “Decremental algorithm for adaptive routing incorporating traveler information,” Comput. Oper. Res., vol. 39, no. 12, pp. 3012–3020 (2012).
[3] B. Awerbuch and R. Kleinberg, “Online linear optimization and adaptive routing,” J. Comput. Syst. Sci., vol. 74, no. 1, pp. 97–114 (2008).
[4] J. Balogh, J. Békési, G. Dósa, L. Epstein, and A. Levin, “Online bin packing with cardinality constraints resolved,” J. Comput. Syst. Sci., vol. 112, pp. 34–49 (2020).
[5] J. Balogh, J. Békési, G. Dósa, J. Sgall, and R. van Stee, “The optimal absolute ratio for online bin packing,” J. Comput. Syst. Sci., vol. 102, pp. 1–17 (2019).
[6] M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali, Linear Programming and Network Flows. Hoboken, NJ: John Wiley & Sons (2008).
[7] G. N. Bifulco, G. E. Cantarella, F. Simonelli, and P. Veloná, “Advanced traveller information systems under recurrent traffic conditions: Network equilibrium and stability,” Transp. Res. Part B: Methodol., vol. 92, pp. 73–87 (2016).
[8] A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis. Cambridge, U.K.: Cambridge University Press (2005).
[9] S. D. Boyles, “An exact label-correcting algorithm for the online shortest path problem in cyclic transportation networks,” Tech. Report (2012).
[10] B. Chen, Z. Ding, Y. Wu, J. Zhou, and Y. Chen, “An optimal global algorithm for route guidance in advanced traveler information systems,” Inf. Sci., vol. 555, pp. 33–45 (2021).
[11] J. Chen, M. Li, R. Jiang, and M.-B. Hu, “Effects of the amount of feedback information on urban traffic with advanced traveler information system,” Phys. Lett. A, vol. 381, pp. 2934–2938 (2017).
[12] Z. He, W. Guan, and S. Ma, “A traffic-condition-based route guidance strategy for a single destination road network,” Transp. Res. Part C: Emerg., vol. 32, pp. 89–102 (2013).
[13] A. György, T. Linder, G. Lugosi, and G. Ottucsák, “The on-line shortest path problem under partial monitoring,” J. Mach. Learn. Res., vol. 8, no. 10, pp. 2369–2403 (2007).
[14] A. Kalai and S. Vempala, “Efficient algorithms for online decision problems,” J. Comput. Syst. Sci., vol. 71, no. 3, pp. 291–307 (2005).
[15] X. Kong and C. D. Schunn, “Global vs. local information processing in visual/spatial problem solving: The case of traveling salesman problem,” Cogn. Syst. Res., vol. 8, pp. 192–207 (2007).
[16] Z. Lin and Z. Bai, Probability Inequalities. Berlin, Germany: Springer Science & Business Media (2011).
[17] J. S. Provan, “A polynomial-time algorithm to find shortest paths with recourse,” Networks, vol. 41, no. 2, pp. 115–125 (2003).
[18] M. R. C. Raj and R. Sukumaran, “On applying stochastic network calculus for Gilbert-Elliot fading channel in underwater wireless communication networks,” J. Inf. Optim. Sci., vol. 39, pp. 1591–1605 (2018).
[19] S. M. Ross, Introduction to Probability Models. 10th ed. Waltham, MA: Academic Press (2006).
[20] D. Sever, L. Zhao, N. Dellaert, E. Demir, T. Van Woensel, and T. De Kok, “The dynamic shortest path problem with time-dependent stochastic disruptions,” Transp. Res. Part C: Emerg. Technol., vol. 92, pp. 42–57 (2018).
[21] M. Yildirimoglu, I. I. Sirmatel, and N. Geroliminis, “Hierarchical control of heterogeneous large-scale urban road networks via path assignment and regional route guidance,” Transp. Res. Part B: Methodol., vol. 118, pp. 106–123 (2018).
