IEEE Computational Intelligence Magazine - May 2021 - 78

Application
Notes

Chao Chen, Liping Gao,
Xuefeng Xie, and Liang Feng
Chongqing University, CHINA
Yasha Wang
Peking University, CHINA

2TD Path-Planner: Towards a More Realistic Path Planning System
Over Two-Fold Time-Dependent Road Networks
Abstract

P

lanning driving routes is a common yet challenging task. Previous solutions that often suggest
the shortest or time-dependent fastest
paths for drivers are incompatible with
the diversity of user requirements.
Recent years are witnessing an increasing need of utility gained along the
driving path and more advanced pathplanners are developed correspondingly, such as the safest and the most
beautiful paths. Similar to the travel
time on the edge, the utility score
actually changes with the time as well.
In this paper, targeting a more realistic
path planning system, we allow both
time cost and utility on the edge to
vary from time to time. Over such
two-fold time-dependent road network, we aim to discover the optimal
driving path for the given user query.
To address this NP-hard problem, we
propose an approximated algorithm
called 2TD Path-Planner, which mainly consists of three components, i.e.,
edge reachability computing, chromosome encoding, and chromosome
decoding. Specifically, an edge timetable and four heuristic rules are proposed to guarantee the planning

efficiency and a desired degree of population diversity. The one with the
highest utility score among the population would be picked as the optimal
solution. We implement two different
forms of utility with distinct timechanging frequency (i.e., beauty and
risky), and evaluate the proposed algorithm based on one synthetic and four
real-world road networks. Results
show that it outperforms other baselines in terms of the obtained path
utility score and the running time.

Digital Object Identifier 10.1109/MCI.2021.3061879
Date of current version: 12 April 2021

Corresponding Author: Chao Chen (ivanchao.chen@gmail
.com).

78

©SHUTTERSTOCK.COMO/ONE PHOTO

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | MAY 2021

I. Introduction

Planning driving routes between two
points over spatial road networks is one
of the most common travel planning
activities [1]-[4]. Traditional route planners usually focus on finding the shortest path over road networks. However,
in real cases, people tend to pay more
attention to the total travel time of the
route (i.e., the fastest path) [5]. Unlike
the distance property on each edge
which is static over time, the travel time
property is often dynamic and timedependent in nature, i.e., it varies from
time to time due to different traffic conditions. As a result, the planning of the

1556-603X/21©2021IEEE



IEEE Computational Intelligence Magazine - May 2021

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - May 2021

Contents
IEEE Computational Intelligence Magazine - May 2021 - Cover1
IEEE Computational Intelligence Magazine - May 2021 - Cover2
IEEE Computational Intelligence Magazine - May 2021 - Contents
IEEE Computational Intelligence Magazine - May 2021 - 2
IEEE Computational Intelligence Magazine - May 2021 - 3
IEEE Computational Intelligence Magazine - May 2021 - 4
IEEE Computational Intelligence Magazine - May 2021 - 5
IEEE Computational Intelligence Magazine - May 2021 - 6
IEEE Computational Intelligence Magazine - May 2021 - 7
IEEE Computational Intelligence Magazine - May 2021 - 8
IEEE Computational Intelligence Magazine - May 2021 - 9
IEEE Computational Intelligence Magazine - May 2021 - 10
IEEE Computational Intelligence Magazine - May 2021 - 11
IEEE Computational Intelligence Magazine - May 2021 - 12
IEEE Computational Intelligence Magazine - May 2021 - 13
IEEE Computational Intelligence Magazine - May 2021 - 14
IEEE Computational Intelligence Magazine - May 2021 - 15
IEEE Computational Intelligence Magazine - May 2021 - 16
IEEE Computational Intelligence Magazine - May 2021 - 17
IEEE Computational Intelligence Magazine - May 2021 - 18
IEEE Computational Intelligence Magazine - May 2021 - 19
IEEE Computational Intelligence Magazine - May 2021 - 20
IEEE Computational Intelligence Magazine - May 2021 - 21
IEEE Computational Intelligence Magazine - May 2021 - 22
IEEE Computational Intelligence Magazine - May 2021 - 23
IEEE Computational Intelligence Magazine - May 2021 - 24
IEEE Computational Intelligence Magazine - May 2021 - 25
IEEE Computational Intelligence Magazine - May 2021 - 26
IEEE Computational Intelligence Magazine - May 2021 - 27
IEEE Computational Intelligence Magazine - May 2021 - 28
IEEE Computational Intelligence Magazine - May 2021 - 29
IEEE Computational Intelligence Magazine - May 2021 - 30
IEEE Computational Intelligence Magazine - May 2021 - 31
IEEE Computational Intelligence Magazine - May 2021 - 32
IEEE Computational Intelligence Magazine - May 2021 - 33
IEEE Computational Intelligence Magazine - May 2021 - 34
IEEE Computational Intelligence Magazine - May 2021 - 35
IEEE Computational Intelligence Magazine - May 2021 - 36
IEEE Computational Intelligence Magazine - May 2021 - 37
IEEE Computational Intelligence Magazine - May 2021 - 38
IEEE Computational Intelligence Magazine - May 2021 - 39
IEEE Computational Intelligence Magazine - May 2021 - 40
IEEE Computational Intelligence Magazine - May 2021 - 41
IEEE Computational Intelligence Magazine - May 2021 - 42
IEEE Computational Intelligence Magazine - May 2021 - 43
IEEE Computational Intelligence Magazine - May 2021 - 44
IEEE Computational Intelligence Magazine - May 2021 - 45
IEEE Computational Intelligence Magazine - May 2021 - 46
IEEE Computational Intelligence Magazine - May 2021 - 47
IEEE Computational Intelligence Magazine - May 2021 - 48
IEEE Computational Intelligence Magazine - May 2021 - 49
IEEE Computational Intelligence Magazine - May 2021 - 50
IEEE Computational Intelligence Magazine - May 2021 - 51
IEEE Computational Intelligence Magazine - May 2021 - 52
IEEE Computational Intelligence Magazine - May 2021 - 53
IEEE Computational Intelligence Magazine - May 2021 - 54
IEEE Computational Intelligence Magazine - May 2021 - 55
IEEE Computational Intelligence Magazine - May 2021 - 56
IEEE Computational Intelligence Magazine - May 2021 - 57
IEEE Computational Intelligence Magazine - May 2021 - 58
IEEE Computational Intelligence Magazine - May 2021 - 59
IEEE Computational Intelligence Magazine - May 2021 - 60
IEEE Computational Intelligence Magazine - May 2021 - 61
IEEE Computational Intelligence Magazine - May 2021 - 62
IEEE Computational Intelligence Magazine - May 2021 - 63
IEEE Computational Intelligence Magazine - May 2021 - 64
IEEE Computational Intelligence Magazine - May 2021 - 65
IEEE Computational Intelligence Magazine - May 2021 - 66
IEEE Computational Intelligence Magazine - May 2021 - 67
IEEE Computational Intelligence Magazine - May 2021 - 68
IEEE Computational Intelligence Magazine - May 2021 - 69
IEEE Computational Intelligence Magazine - May 2021 - 70
IEEE Computational Intelligence Magazine - May 2021 - 71
IEEE Computational Intelligence Magazine - May 2021 - 72
IEEE Computational Intelligence Magazine - May 2021 - 73
IEEE Computational Intelligence Magazine - May 2021 - 74
IEEE Computational Intelligence Magazine - May 2021 - 75
IEEE Computational Intelligence Magazine - May 2021 - 76
IEEE Computational Intelligence Magazine - May 2021 - 77
IEEE Computational Intelligence Magazine - May 2021 - 78
IEEE Computational Intelligence Magazine - May 2021 - 79
IEEE Computational Intelligence Magazine - May 2021 - 80
IEEE Computational Intelligence Magazine - May 2021 - 81
IEEE Computational Intelligence Magazine - May 2021 - 82
IEEE Computational Intelligence Magazine - May 2021 - 83
IEEE Computational Intelligence Magazine - May 2021 - 84
IEEE Computational Intelligence Magazine - May 2021 - 85
IEEE Computational Intelligence Magazine - May 2021 - 86
IEEE Computational Intelligence Magazine - May 2021 - 87
IEEE Computational Intelligence Magazine - May 2021 - 88
IEEE Computational Intelligence Magazine - May 2021 - 89
IEEE Computational Intelligence Magazine - May 2021 - 90
IEEE Computational Intelligence Magazine - May 2021 - 91
IEEE Computational Intelligence Magazine - May 2021 - 92
IEEE Computational Intelligence Magazine - May 2021 - 93
IEEE Computational Intelligence Magazine - May 2021 - 94
IEEE Computational Intelligence Magazine - May 2021 - 95
IEEE Computational Intelligence Magazine - May 2021 - 96
IEEE Computational Intelligence Magazine - May 2021 - 97
IEEE Computational Intelligence Magazine - May 2021 - 98
IEEE Computational Intelligence Magazine - May 2021 - 99
IEEE Computational Intelligence Magazine - May 2021 - 100
IEEE Computational Intelligence Magazine - May 2021 - Cover3
IEEE Computational Intelligence Magazine - May 2021 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202311
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202308
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202305
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202302
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202211
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202208
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202205
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202202
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202111
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202108
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202105
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202102
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202011
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202008
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202005
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202002
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201911
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201908
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201905
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201902
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201811
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201808
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201805
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201802
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter12
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall12
https://www.nxtbookmedia.com