IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i17p3639-d1223360.html
   My bibliography  Save this article

Non-Aggressive Adaptive Routing in Traffic

Author

Listed:
  • Madhushini Narayana Prasad

    (Department of Operations Research and Industrial Engineering, The University of Texas at Austin, 204 E. Dean Keeton Street, C2200, Austin, TX 78712, USA)

  • Nedialko Dimitrov

    (Department of Operations Research and Industrial Engineering, The University of Texas at Austin, 204 E. Dean Keeton Street, C2200, Austin, TX 78712, USA)

  • Evdokia Nikolova

    (Department of Electrical and Computer Engineering, The University of Texas at Austin, 2501 Speedway, Austin, TX 78712, USA)

Abstract

Routing a person through a traffic road network presents a tension between selecting a fixed route that is easy to navigate and selecting an aggressively adaptive route that minimizes travel time. In this paper, we propose a novel routing framework that strikes a balance between adaptability and simplicity. Specifically, we propose to create non-aggressive adaptive routes that seek the best of both these extremes in the navigation world. These selected routes still adapt to changing traffic conditions, but we limit the number of adjustments made en route. This framework improves the driver experience by providing a continuum of options between saving travel time and reducing navigation stress. We design strategies to model single and multiple route adjustments, and investigate numerous techniques to solve these models for better route selection. To alleviate the intractability of handling real-life traffic data, we devise efficient algorithms with easily computable lower and upper bounds. We finally perform computational experiments on our algorithms to demonstrate the benefits of limited adaptability in terms of reducing the travel time.

Suggested Citation

  • Madhushini Narayana Prasad & Nedialko Dimitrov & Evdokia Nikolova, 2023. "Non-Aggressive Adaptive Routing in Traffic," Mathematics, MDPI, vol. 11(17), pages 1-25, August.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:17:p:3639-:d:1223360
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/17/3639/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/17/3639/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. John S. Croucher, 1978. "A note on the stochastic shortest‐route problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 25(4), pages 729-732, December.
    2. Yinfeng Xu & Maolin Hu & Bing Su & Binhai Zhu & Zhijun Zhu, 2009. "The canadian traveller problem and its competitive analysis," Journal of Combinatorial Optimization, Springer, vol. 18(2), pages 195-205, August.
    3. Pretolani, Daniele, 2000. "A directed hypergraph model for random time dependent shortest paths," European Journal of Operational Research, Elsevier, vol. 123(2), pages 315-324, June.
    4. Gao, Song & Chabini, Ismail, 2006. "Optimal routing policy problems in stochastic time-dependent networks," Transportation Research Part B: Methodological, Elsevier, vol. 40(2), pages 93-122, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Stephen Boyles & S. Waller, 2011. "Optimal Information Location for Adaptive Routing," Networks and Spatial Economics, Springer, vol. 11(2), pages 233-254, June.
    2. Prakash, A. Arun, 2018. "Pruning algorithm for the least expected travel time path on stochastic and time-dependent networks," Transportation Research Part B: Methodological, Elsevier, vol. 108(C), pages 127-147.
    3. He Huang & Song Gao, 2018. "Trajectory-Adaptive Routing in Dynamic Networks with Dependent Random Link Travel Times," Transportation Science, INFORMS, vol. 52(1), pages 102-117, January.
    4. Vural Aksakalli & Ibrahim Ari, 2014. "Penalty-Based Algorithms for the Stochastic Obstacle Scene Problem," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 370-384, May.
    5. Pramesh Kumar & Alireza Khani, 2021. "Adaptive Park-and-ride Choice on Time-dependent Stochastic Multimodal Transportation Network," Networks and Spatial Economics, Springer, vol. 21(4), pages 771-800, December.
    6. A. Arun Prakash & Karthik K. Srinivasan, 2017. "Finding the Most Reliable Strategy on Stochastic and Time-Dependent Transportation Networks: A Hypergraph Based Formulation," Networks and Spatial Economics, Springer, vol. 17(3), pages 809-840, September.
    7. Arun Prakash, A., 2020. "Algorithms for most reliable routes on stochastic and time-dependent networks," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 202-220.
    8. Yang, Lixing & Zhou, Xuesong, 2014. "Constraint reformulation and a Lagrangian relaxation-based solution algorithm for a least expected time path problem," Transportation Research Part B: Methodological, Elsevier, vol. 59(C), pages 22-44.
    9. D'Acierno, Luca & Cartenì, Armando & Montella, Bruno, 2009. "Estimation of urban traffic conditions using an Automatic Vehicle Location (AVL) System," European Journal of Operational Research, Elsevier, vol. 196(2), pages 719-736, July.
    10. Pretolani, Daniele & Nielsen, Lars Relund & Andersen, Kim Allan & Ehrgott, Matthias, 2008. "Time-adaptive versus history-adaptive strategies for multicriterion routing in stochastic time-dependent networks," CORAL Working Papers L-2008-05, University of Aarhus, Aarhus School of Business, Department of Business Studies.
    11. Hoang, Nam H. & Vu, Hai L. & Lo, Hong K., 2018. "An informed user equilibrium dynamic traffic assignment problem in a multiple origin-destination stochastic network," Transportation Research Part B: Methodological, Elsevier, vol. 115(C), pages 207-230.
    12. Huili Zhang & Yinfeng Xu & Xingang Wen, 2015. "Optimal shortest path set problem in undirected graphs," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 511-530, April.
    13. Yang, Lixing & Zhou, Xuesong, 2017. "Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 68-91.
    14. Zhang, Huili & Tong, Weitian & Xu, Yinfeng & Lin, Guohui, 2015. "The Steiner Traveling Salesman Problem with online edge blockages," European Journal of Operational Research, Elsevier, vol. 243(1), pages 30-40.
    15. Nielsen, Lars Relund & Andersen, Kim Allan & Pretolani, Daniele, 2006. "Bicriterion a priori route choice in stochastic time-dependent networks," CORAL Working Papers L-2006-10, University of Aarhus, Aarhus School of Business, Department of Business Studies.
    16. Pi, Xidong & Qian, Zhen (Sean), 2017. "A stochastic optimal control approach for real-time traffic routing considering demand uncertainties and travelers’ choice heterogeneity," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 710-732.
    17. Davood Shiri & Hakan Tozan, 2022. "Online routing and searching on graphs with blocked edges," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1039-1059, September.
    18. Tsung-Sheng Chang & Linda K. Nozick & Mark A. Turnquist, 2005. "Multiobjective Path Finding in Stochastic Dynamic Networks, with Application to Routing Hazardous Materials Shipments," Transportation Science, INFORMS, vol. 39(3), pages 383-399, August.
    19. Kasun P Wijayaratna & Vinayak V Dixit & Laurent Denant-Boemont & S Travis Waller, 2017. "An experimental study of the Online Information Paradox: Does en-route information improve road network performance?," PLOS ONE, Public Library of Science, vol. 12(9), pages 1-17, September.
    20. Azadeh Tabatabaei & Mohammad Ghodsi, 2015. "Walking in streets with minimal sensing," Journal of Combinatorial Optimization, Springer, vol. 30(2), pages 387-401, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:11:y:2023:i:17:p:3639-:d:1223360. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.