Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/105608
Title: | Parallel hyper-heuristic algorithm for multi-objective route planning in a smart city | Authors: | Yao, Y Peng, Z Xiao, B |
Issue Date: | Nov-2018 | Source: | IEEE transactions on vehicular technology, Nov. 2018, v. 67, no. 11, p. 10307-10318 | Abstract: | Most of the commercial navigation products provide route planning service for users. However, they only consider a single metric such as distance, time, or other costs, while ignoring a critical criterion: safety. In a smart city, people may prefer to find a safe walking route to avoid the potential crime risk as well as obtain a short distance. This problem can be specified as a multi-objective optimization problem (MOOP). Many methods were proposed in the past to solve the multi-objective route planning, the multi-objective evolutionary approach (MOEA) is considered as the most popular one. However, MOEA is non-optimized when used in a large-scale road network and becomes computationally expensive when handling a large population size. In this paper, we propose a multi-objective hyper-heuristic (MOHH) framework for walking route planning in a smart city. In the search framework, we design a set of low level heuristics to generate new routes. Moreover, we adopt reinforcement learning mechanism to select good low-level heuristics to accelerate searching speed. We further improve the reinforcement learning-based multi-objective hyper-heuristic (RL-MOHH) algorithm and implement a parallel version (RL-PMOHH) on general purpose graphic process unit. Extensive experiments are conducted on the safety-index map constructed from the historical urban data of the New York city. Comprehensive experimental results show that the proposed RL-PMOHH is almost 173, 5.3, and 3.1 times faster than the exact multi-objective optimization algorithm, the RL-MOHH algorithm, and the parallel NSGA-II algorithm, respectively. Moreover, both RL-MOHH and RL-PMOHH can obtain more than 80% Pareto optimal solutions in a large-scale road network. | Keywords: | Hyper-heuristics Multi-objective optimization problem (MOOP) Parallel computing Route planning Safety index |
Publisher: | Institute of Electrical and Electronics Engineers | Journal: | IEEE transactions on vehicular technology | ISSN: | 0018-9545 | EISSN: | 1939-9359 | DOI: | 10.1109/TVT.2018.2868942 | Rights: | © 2018 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The following publication Y. Yao, Z. Peng and B. Xiao, "Parallel Hyper-Heuristic Algorithm for Multi-Objective Route Planning in a Smart City," in IEEE Transactions on Vehicular Technology, vol. 67, no. 11, pp. 10307-10318, Nov. 2018 is available at https://doi.org/10.1109/TVT.2018.2868942. |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Peng_Parallel_Hyper-Heuristic_Algorithm.pdf | Pre-Published version | 5.24 MB | Adobe PDF | View/Open |
Page views
18
Citations as of Jul 7, 2024
Downloads
1
Citations as of Jul 7, 2024
SCOPUSTM
Citations
58
Citations as of Jul 4, 2024
WEB OF SCIENCETM
Citations
51
Citations as of Jul 4, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.