Planning ideal transit routes in the complex urban environment can improve the performance and efficiency of public transportation systems effectively. However, finding such routes is computationally difficult due to the huge solution space constituted by billions of possible routes. Considering the limited scalability of exact search methods, heuristic search methods were proposed to boost the efficiency and incorporate flexible constraints. Nevertheless, the existing methods conceal multiple criteria in an objective, and thus evaluating the performance of the generated route becomes challenging due to the lack of comparable alternatives. Inspired by the prior study, we formulate the definition of pareto-optimal transit routes based on multiple criteria. However, extracting these routes remains challenging because: A) the sheer volume of possible transit routes; and B) the sparsity of pareto-optimal routes. We address these challenges by developing an efficient search framework: for challenge A, a random search method is developed based on Monte Carlo tree search where the unproductive solution subspaces are pruned progressively to reduce the search cost; and for challenge B, an estimation method is derived to guide the search process by assessing the value for each solution subspace. The superior effectiveness of our approach in approximating the pareto-optimal transit routes was demonstrated by the comprehensive evaluation based on the real-world data.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Pareto-Optimal Transit Route Planning With Multi-Objective Monte-Carlo Tree Search


    Contributors:
    Weng, Di (author) / Chen, Ran (author) / Zhang, Jianhui (author) / Bao, Jie (author) / Zheng, Yu (author) / Wu, Yingcai (author)


    Publication date :

    2021-02-01


    Size :

    2102703 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Multi-Objective Monte-Carlo Tree Search based aerial maneuvering control

    Xiang Chen, / Xinguo Zhang, / Weijia Wang, et al. | IEEE | 2016


    Pareto Improver: Learning Improvement Heuristics for Multi-Objective Route Planning

    Zheng, Zhi / Yao, Shunyu / Li, Genghui et al. | IEEE | 2024


    Multi-Agent Assisted Shortest Path Planning using Monte Carlo Tree Search

    Bhadoriya, Abhay Singh / Darbha, Swaroop / Rathinam, Sivakumar et al. | AIAA | 2023



    Multi-Agent Assisted Shortest Path Planning Using Monte Carlo Tree Search

    Bhadoriya, Abhay Singh / Darbha, Swaroop / Rathinam, Sivakumar et al. | TIBKAT | 2023