Multi-criteria journey planning for enhancing user experience in multimodal transportation systems

• Main Author: He, Peilan
• Other Authors: Lam Siew Kei
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/151191
• Institution: Nanyang Technological University

A key enabler to the success of public transportation system is a dependable and responsive journey planner that can cater to personalized journey preferences. Existing journey planners tend to restrict travel criteria and suffer from inaccurate journey time predictions due to their inability to accommodate traffic uncertainties. In this research, scalable techniques for multi-criteria journey planning on multimodal public transport networks (MMPTN) have been proposed to achieve a dependable and responsive journey planning system that can enhance passengers’ travel experience. A scalable MMPTN model was proposed to represent Singapore’s multiple travel modalities such as the bus, Mass Rapid Transit (MRT), Light Rail Transit (LRT), and pedestrian networks. The proposed unified model effectively characterizes multiple travel criteria, various transfer opportunities, and traffic uncertainties. A transfer graph (TG), representing all possible transfer opportunities among all the public transport services, was also proposed to accelerate multi-criteria journey search. Extensively evaluations of the performance of journey routes for each travel criteria have been carried out by devising several cost functions. Historical bus trajectories, obtained from the Land Transport Authority (LTA), Singapore were analyzed to identify factors that significantly impacted the accuracy of journey time estimation. This led to the proposal of a novel partition and combination framework (PCF) to accurately predict the travel time of bus journeys by accounting for both the passengers riding times on multiple bus trips as well as waiting times at transfer points. In particular, the proposed PCF partitions a given journey into multiple components comprising of waiting times at each transfer points (waiting time components) and bus riding times on each service line segment (riding time components), thereby facilitating accurate prediction of the journey times. Next, a Long Short-Term Memory (LSTM) model was proposed to predict the riding time components together with an Interval-based Historical Average (IHA) technique for predicting the waiting time components. The prediction results are combined to improve the overall estimation accuracy of a complete journey. Experiments with real bus travel data from LTA, Singapore, show high prediction accuracy for all cases considered. Two exact algorithms for multi-criteria journey planning have been devised based on the proposed MMPTN model and journey time prediction method. The first algorithm employs a novel two-stage process to search for Pareto-optimal solutions. Stage I identifies all feasible routes while stage II evaluates all feasible routes using cost functions to construct the Pareto-optimal solution set. It is noteworthy that the first algorithm discards dominated (inferior) solutions only once after complete journey routes are obtained, thereby resulting in excessive runtimes. However, it provides for a more dependable solution. The second algorithm, proposed in this research, overcomes the limitations of the first algorithm by using a round-based routing strategy to remove dominated journey solutions based on partial routes. It has been established that the second algorithm is more suited for lowering computation time at the expense of marginal degradation in output quality. The effectiveness of the two exact algorithms have been extensively evaluated with Singapore’s bus/MRT travel data. Compared to existing methods, the proposed exact algorithms have been shown to determine Pareto-optimal journeys despite larger number of travel criteria and evolving traffic conditions. In order to accelerate multi-criteria journey planning, a machine learning based MaxMin Ant System (ML-MMAS) was proposed. It relies on a self-learning approach with the Ant Colony Optimization (ACO) algorithm (e.g., MMAS) to learn a pheromone function/model based on incremental solutions generated by MMAS. The pheromone model can directly produce high-quality pheromone trails to construct solutions for any new instance, without the need to initialize and update the pheromone trails from scratch. Experiments based on the historical passenger demands obtained from LTA, Singapore show that ML-MMAS is 5-8 times faster than MMAS without degrading the solution quality. Moreover, when compared to exact algorithms, MM-MMAS obtains a speedup of 8-10 times with acceptable deviations from the optimal solutions. The proposed techniques have been integrated into a framework to recommend responsive and dependable solutions for multi-criterion based personalized journey planning queries. Finally, the proposed techniques are also well suited for large public transportation networks consisting of increased number of travel modalities and transfer options, thereby demonstrating their applicability for enhancing the user experience in large-scale deployments