Co-Evolutionary path optimization by Ripple-Spreading algorithm

Xiao-Bing Hu, Ming-Kong Zhang, Qi Zhang and Jian-Qin Liao

Transportation Research Part B: Methodological, 2017, vol. 106, issue C, 411-432

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.

Keywords: Co-evolution; Path optimization; Agent-based model; Ripple-Spreading Algorithm (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261516308931
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:106:y:2017:i:c:p:411-432

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2017.06.007

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().