IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v106y2017icp411-432.html
   My bibliography  Save this article

Co-Evolutionary path optimization by Ripple-Spreading algorithm

Author

Listed:
  • Hu, Xiao-Bing
  • Zhang, Ming-Kong
  • Zhang, Qi
  • Liao, Jian-Qin

Abstract

Static path optimization (SPO) is a foundation of computational intelligence, but in reality, the routing environment is usually time-varying (e.g., moving obstacles, spreading disasters and uncertainties). Thanks to scientific and technical advances in many relevant domains nowadays, changes in the routing environment are often more or less predictable. This study mainly focuses on path optimization in a given dynamic routing environment (POGDRE). A common practice to deal with dynamic routing environment is to conduct online re-optimization (OLRO), i.e., at each time t, environmental parameters are measured/predicted first, and then the best path is re-calculated by resolving SPO based on the newly measured/predicted environmental parameters. In theory, POGDRE is equivalent to time-dependent path optimization (TDPO), which is usually resolved as SPO on a time-expanded hypergraph (TEHG) with a significantly enlarged size. In other words, during a single online run of OLRO-based methods or a single run of TEHG-based methods, the route network is actually fixed and static. Inspired by the multi-agent co-evolving nature reflected in many methods of evolutionary computation, this paper proposes a methodology of co-evolutionary path optimization (CEPO) to resolve the POGDRE. Distinguishing from OLRO and TEHG methods, in CEPO, future routing environmental parameters keep changing during a single run of optimization on a network of original size. In other words, the routing environment co-evolves with the path optimization process within a single run. This paper then reports a ripple-spreading algorithm (RSA) as a realization of CEPO to resolve the POGDRE with both optimality and efficiency. In just a single run of RSA, the optimal actual travelling trajectory can be achieved in a given dynamic routing environment. Simulation results clearly demonstrate the effectiveness and efficiency of the proposed CEPO and RSA for addressing the POGDRE.

Suggested Citation

  • Hu, Xiao-Bing & Zhang, Ming-Kong & Zhang, Qi & Liao, Jian-Qin, 2017. "Co-Evolutionary path optimization by Ripple-Spreading algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 411-432.
  • Handle: RePEc:eee:transb:v:106:y:2017:i:c:p:411-432
    DOI: 10.1016/j.trb.2017.06.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261516308931
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.trb.2017.06.007?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Liu, Siyuan & Qu, Qiang, 2016. "Dynamic collective routing using crowdsourcing data," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 450-469.
    2. Thomas, Barrett W. & White III, Chelsea C., 2007. "The dynamic shortest path problem with anticipation," European Journal of Operational Research, Elsevier, vol. 176(2), pages 836-854, January.
    3. Lam, William H.K. & Shao, Hu & Sumalee, Agachai, 2008. "Modeling impacts of adverse weather conditions on a road network with uncertainties in demand and supply," Transportation Research Part B: Methodological, Elsevier, vol. 42(10), pages 890-910, December.
    4. Yi, Wenqi & Nozick, Linda & Davidson, Rachel & Blanton, Brian & Colle, Brian, 2017. "Optimization of the issuance of evacuation orders under evolving hurricane conditions," Transportation Research Part B: Methodological, Elsevier, vol. 95(C), pages 285-304.
    5. Angelelli, E. & Arsik, I. & Morandi, V. & Savelsbergh, M. & Speranza, M.G., 2016. "Proactive route guidance to avoid congestion," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 1-21.
    6. Madireddy, Manini & Kumara, Soundar & Medeiros, D.J. & Shankar, Venky N., 2015. "Leveraging social networks for efficient hurricane evacuation," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 199-212.
    7. Li, Chen & Qi, Xiangtong & Song, Dongping, 2016. "Real-time schedule recovery in liner shipping service with regular uncertainties and disruption events," Transportation Research Part B: Methodological, Elsevier, vol. 93(PB), pages 762-788.
    8. Ahuja, Ravindra & Orlin, James & Pallottino, Stefano & Scutella, Maria, 2003. "Dynamic Shortest Paths Minimizing Travel Times And Costs," Working papers 4390-02, Massachusetts Institute of Technology (MIT), Sloan School of Management.
    9. 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.
    10. Du, Lili & Han, Lanshan & Chen, Shuwei, 2015. "Coordinated online in-vehicle routing balancing user optimality and system optimality through information perturbation," Transportation Research Part B: Methodological, Elsevier, vol. 79(C), pages 121-133.
    11. Huang, Michael & Smilowitz, Karen R. & Balcik, Burcu, 2013. "A continuous approximation approach for assessment routing in disaster relief," Transportation Research Part B: Methodological, Elsevier, vol. 50(C), pages 20-41.
    12. Faturechi, Reza & Miller-Hooks, Elise, 2014. "Travel time resilience of roadway networks under disaster," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 47-64.
    13. Wang, Judith Y.T. & Ehrgott, Matthias & Chen, Anthony, 2014. "A bi-objective user equilibrium model of travel time reliability in a road network," Transportation Research Part B: Methodological, Elsevier, vol. 66(C), pages 4-15.
    14. Huang, Yixiao & Zhao, Lei & Van Woensel, Tom & Gross, Jean-Philippe, 2017. "Time-dependent vehicle routing problem with path flexibility," Transportation Research Part B: Methodological, Elsevier, vol. 95(C), pages 169-195.
    15. Sung, Kiseok & Bell, Michael G. H. & Seong, Myeongki & Park, Soondal, 2000. "Shortest paths in a network with time-dependent flow speeds," European Journal of Operational Research, Elsevier, vol. 121(1), pages 32-39, February.
    16. Goerigk, Marc & Deghdak, Kaouthar & T’Kindt, Vincent, 2015. "A two-stage robustness approach to evacuation planning with buses," Transportation Research Part B: Methodological, Elsevier, vol. 78(C), pages 66-82.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhengbo Hao & Yizhe Wang & Xiaoguang Yang, 2024. "Every Second Counts: A Comprehensive Review of Route Optimization and Priority Control for Urban Emergency Vehicles," Sustainability, MDPI, vol. 16(7), pages 1-25, March.
    2. Jie, Ke-Wei & Liu, San-Yang & Sun, Xiao-Jun & Xu, Yun-Cheng, 2023. "A dynamic ripple-spreading algorithm for solving mean–variance of shortest path model in uncertain random networks," Chaos, Solitons & Fractals, Elsevier, vol. 167(C).

    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. Esposito Amideo, A. & Scaparra, M.P. & Kotiadis, K., 2019. "Optimising shelter location and evacuation routing operations: The critical issues," European Journal of Operational Research, Elsevier, vol. 279(2), pages 279-295.
    2. Liu, Bingsheng & Sheu, Jiuh-Biing & Zhao, Xue & Chen, Yuan & Zhang, Wei, 2020. "Decision making on post-disaster rescue routing problems from the rescue efficiency perspective," European Journal of Operational Research, Elsevier, vol. 286(1), pages 321-335.
    3. Bell, Michael G.H. & Trozzi, Valentina & Hosseinloo, Solmaz Haji & Gentile, Guido & Fonzone, Achille, 2012. "Time-dependent Hyperstar algorithm for robust vehicle navigation," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(5), pages 790-800.
    4. Wen, Liang & Çatay, Bülent & Eglese, Richard, 2014. "Finding a minimum cost path between a pair of nodes in a time-varying road network with a congestion charge," European Journal of Operational Research, Elsevier, vol. 236(3), pages 915-923.
    5. Xu, Xiangdong & Chen, Anthony & Cheng, Lin & Yang, Chao, 2017. "A link-based mean-excess traffic equilibrium model under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 95(C), pages 53-75.
    6. Zhaoqi Zang & Xiangdong Xu & Kai Qu & Ruiya Chen & Anthony Chen, 2022. "Travel time reliability in transportation networks: A review of methodological developments," Papers 2206.12696, arXiv.org, revised Jul 2022.
    7. Ivana Semanjski & Sidharta Gautama, 2019. "A Collaborative Stakeholder Decision-Making Approach for Sustainable Urban Logistics," Sustainability, MDPI, vol. 11(1), pages 1-11, January.
    8. Zhang, Guowei & Jia, Ning & Zhu, Ning & Adulyasak, Yossiri & Ma, Shoufeng, 2023. "Robust drone selective routing in humanitarian transportation network assessment," European Journal of Operational Research, Elsevier, vol. 305(1), pages 400-428.
    9. Teppei Kato & Kenetsu Uchida & William H. K. Lam & Agachai Sumalee, 2021. "Estimation of the value of travel time and of travel time reliability for heterogeneous drivers in a road network," Transportation, Springer, vol. 48(4), pages 1639-1670, August.
    10. Jianbin Xin & Benyang Yu & Andrea D’Ariano & Heshan Wang & Meng Wang, 2022. "Time-dependent rural postman problem: time-space network formulation and genetic algorithm," Operational Research, Springer, vol. 22(3), pages 2943-2972, July.
    11. Tan, Zhijia & Yang, Hai & Guo, Renyong, 2014. "Pareto efficiency of reliability-based traffic equilibria and risk-taking behavior of travelers," Transportation Research Part B: Methodological, Elsevier, vol. 66(C), pages 16-31.
    12. Liu, Siyuan & Qu, Qiang, 2016. "Dynamic collective routing using crowdsourcing data," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 450-469.
    13. Shuang Wang & Jing Lu & Liping Jiang, 2019. "Time Reliability of the Maritime Transportation Network for China’s Crude Oil Imports," Sustainability, MDPI, vol. 12(1), pages 1-18, December.
    14. Wu, Xing, 2015. "Study on mean-standard deviation shortest path problem in stochastic and time-dependent networks: A stochastic dominance based approach," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 275-290.
    15. Kun Yang & Rachel A. Davidson & Humberto Vergara & Randall L. Kolar & Kendra M. Dresback & Brian A. Colle & Brian Blanton & Tricia Wachtendorf & Jennifer Trivedi & Linda K. Nozick, 2019. "Incorporating inland flooding into hurricane evacuation decision support modeling," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 96(2), pages 857-878, March.
    16. 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.
    17. Asghari, Mohammad & Jaber, Mohamad Y. & Mirzapour Al-e-hashem, S.M.J., 2023. "Coordinating vessel recovery actions: Analysis of disruption management in a liner shipping service," European Journal of Operational Research, Elsevier, vol. 307(2), pages 627-644.
    18. Yichen Lu & Chao Yang & Jun Yang, 2022. "A multi-objective humanitarian pickup and delivery vehicle routing problem with drones," Annals of Operations Research, Springer, vol. 319(1), pages 291-353, December.
    19. A. Anaya-Arenas & J. Renaud & A. Ruiz, 2014. "Relief distribution networks: a systematic review," Annals of Operations Research, Springer, vol. 223(1), pages 53-79, December.
    20. Milan Janić, 2018. "Modelling the resilience of rail passenger transport networks affected by large-scale disruptive events: the case of HSR (high speed rail)," Transportation, Springer, vol. 45(4), pages 1101-1137, July.

    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:eee:transb:v:106:y:2017:i:c:p:411-432. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    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.