Please use this identifier to cite or link to this item:
Title: ML-MMAS: self-learning ant colony optimization for multi-criteria journey planning
Authors: He, Peilan
Jiang, Guiyuan
Lam, Siew-Kei
Sun, Yidan
Keywords: Engineering::Computer science and engineering
Issue Date: 2022
Source: He, P., Jiang, G., Lam, S. & Sun, Y. (2022). ML-MMAS: self-learning ant colony optimization for multi-criteria journey planning. Information Sciences, 609, 1052-1074.
Journal: Information Sciences
Abstract: Ant Colony Optimization (ACO) algorithms have been widely employed for solving optimization problems. Their ability to find optimal solutions depends heavily on the parameterization of the pheromone trails. However, the pheromone parameterization mechanisms in existing ACO algorithms have two major shortcomings: 1) pheromone trails are instance-specific; hence they need to be generated for each new problem instance, 2) solution is constructed based on static pheromone trails, which ignores the impact of the evolving decisions on the final solution. In this paper, we study the personalized journey route planning problem on multimodal public transport networks (MMPTN) that considers multiple travel criteria. The problem is addressed with a weighted sum method, which provides a journey route that best matches passenger's preference vector consisting of multiple travel criteria. We propose a Machine Learning (ML) based Max–Min Ant System (called ML-MMAS) to solve optimization problems by incorporating ML techniques into Ant Colony Optimization algorithms. ML-MMAS learns a pheromone function to directly produce prominent pheromone trails in order to construct solutions for any new instance, without the need to initialize and update the pheromone trails from scratch. We propose a self-learning framework to train the ML-MMAS using incremental solutions generated by MMAS, hence avoiding the need for pre-computed optimal solutions. Specifically, we develop a deep learning-based pheromone prediction model. We design several groups of features to train the model to characterize the evolving states of the search space during solution construction. Finally, we propose a solution component embedding (SCE) model to learn representations of solution components (transit services), which takes into account the transferability among transit services and passenger transfer preferences. The SCE model enables the extraction of high-quality features for the solution components. It can also be directly applied to solve other optimization problems with solutions that can be modeled as sequences of solution components. We evaluate the proposed ML-MMAS by comparing with exact algorithms and the underlying MMAS, using the MMPTN and passenger demands of Singapore. Results show that ML-MMAS is significantly faster than both the exact algorithm and the original MMAS, while achieving near-optimal solutions.
ISSN: 0020-0255
DOI: 10.1016/j.ins.2022.07.150
Rights: © 2022 Elsevier Inc. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Citations 50

Updated on Jan 28, 2023

Web of ScienceTM
Citations 50

Updated on Jan 26, 2023

Page view(s)

Updated on Jan 30, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.