IEEE Computational Intelligence Magazine - May 2021 - 98

not only covers the time-dependent
high-value utility edges but also bypasses
some high-risky regions.
For normal road users, on one hand,
with our proposed system, they can simply avoid the time-dependent most
risky driving route to keep safe. On the
other hand, if a user has a flexible schedule, our system can also inform the
time-dependent highest risky scores at
different departure times to facilitate the
user to determine a better and safer
departure time.
VI. Conclusions and Future Work

In this paper, we have investigated a more
realistic path-planning problem, which
allows both the travel time and the utility
score on the edge to be time-dependent.
We have proposed a 2TD algorithm to
solve the problem effectively and efficiently. Extensive experimental results
based on one synthetic and four realworld road networks have verified that it
outperforms the other two baselines both
in terms of the obtained path utility score
and the running time.
In the near future, we plan to extend
and deepen the work in the following
directions. Firstly, to further improve the
algorithm, we intend to understand and
quantify the " true gap " between the
exactly optimal solution and our optimal solution in a controlled size of road
network under different experimental
settings. Secondly, we expect to extend
our proposed algorithm to work adaptively for more complex situations, for
example, users need to optimize two or
more kinds of utility simultaneously.
Finally, we would like to deploy our system on mobile devices, recruit some
volunteers to test our system in actual
settings, and collect feedback on how to
further improve the service.
Acknowledgments

The work was supported by the National
Natural Science Foundation of China
(No. 61872050 and 62072064), the
Chongqing Basic and Frontier Research
Program (No. cstc2018jcyjAX0551).
Chao Chen and Liping Gao contributed
equally to this work. Chao Chen is the
corresponding author of this paper.

98

References

[1] C. Chen et al., " MA-SSR: A memetic algorithm for
skyline scenic routes planning leveraging heterogeneous
user-generated digital footprints, " IEEE Trans. Veh. Technol., vol. 66, no. 7, pp. 5723-5736, 2017. doi: 10.1109/
TVT.2016.2639550.
[2] D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck, " Customizable route planning in road networks, "
Transp. Sci., vol. 51, no. 2, pp. 566-591, 2015. doi:
10.1287/trsc.2014.0579.
[3] Y. Ding, C. Chen, S. Zhang, B. Guo, Z. Yu, and Y.
Wang, " Greenplanner: Planning personalized fuel-efficient driving routes using multi-sourced urban data, " in
Proc. IEEE Int. Conf. Pervasive Comput. Commun. (PerCom),
2017, pp. 207-216. doi: 10.1109/PERCOM.2017.7917867.
[4] S. Funke and S. Storandt, " Personalized route planning in road networks, " in Proc. 23rd SIGSPATIAL Int.
Conf. Adv. Geographic Inf. Syst., 2015, p. 45.
[5] J. F. Campbell, " Selecting routes to minimize urban
travel time, " Transp. Res. B, Methodol., vol. 26, no. 4, pp.
261-274, 1992. doi: 10.1016/0191-2615(92)90037-W.
[6] H. Sheng et al., " Mining hard samples globally and
efficiently for person re-identification, " IEEE Internet
Things J., vol. 7, no. 10, pp. 1-1, 2020. doi: 10.1109/
JIOT.2020.2980549.
[7] Z. Zhou, N. Chawla, Y. Jin, and G. Williams, " Big
data opportunities and challenges: Discussions from data
analytics perspectives, " IEEE Comput. Intell. Mag., vol. 9,
no. 4, pp. 62-74, 2014. doi: 10.1109/MCI.2014.2350953.
[8] Y. Li and M. L. Yiu, " Route-saver: leveraging route apis
for accurate and efficient query processing at location-based
services, " IEEE Trans. Knowl. Data Eng., vol. 27, no. 1, pp.
235-249, 2014. doi: 10.1109/TKDE.2014.2324597.
[9] D. Delling and D. Wagner, " Time-dependent route
planning, " in Robust and Online Large-scale Optimization,
Springer-Verlag, 2009, pp. 207-230.
[10] C. Chen, S. Jiao, S. Zhang, W. Liu, L. Feng, and Y.
Wang, " TripImputor: Real-time imputing taxi trip purpose leveraging multi-sourced urban data, " IEEE Trans.
Intell. Transp. Syst., vol. 19, no. 10, pp. 3292-3304, 2018.
doi: 10.1109/TITS.2017.2771231.
[11] D. Quercia, R. Schifanella, and L. M. Aiello, " The
shortest path to happiness: Recommending beautiful,
quiet, and happy routes in the city, " in Proc. 25th ACM
Conf. Hypertext Soc. Media, 2014, pp. 116-125.
[12] N. Runge, P. Samsonov, D. Degraen, and J.
Schöning, " No more autobahn! Scenic route generation
using Google's street view, " in Proc. 21st Int. Conf. Intell.
User Interf., ACM, 2016, pp. 147-151.
[13] Y.-T. Zheng et al., " GPSView: A scenic driving route
planner, " ACM Trans. Multimedia Comput., Commun.,
Appl. (TOMM), vol. 9, no. 1, p. 3, 2013.
[14] S. Levy, W. Xiong, E. Belding, and W. Y. Wang,
" SafeRoute: learning to navigate streets safely in an urban
environment, " 2018, arXiv:1811.01147.
[15] X. Ma, M.-T. Sun, G. Zhao, and X. Liu, " An efficient path pruning algorithm for geographical routing in
wireless networks, " IEEE Trans. Veh. Technol., vol. 57, no.
4, pp. 2474-2488, 2008. doi: 10.1109/TVT.2007.912332.
[16] C. Wu, Y. Ji, F. Liu, S. Ohzahata, and T. Kato, " Toward practical and intelligent routing in vehicular ad hoc
networks, " IEEE Trans. Veh. Technol., vol. 64, no. 12, pp.
5503-5519, 2015. doi: 10.1109/TVT.2015.2481464.
[17] J. Bao, Y. Zheng, D. Wilkie, and M. Mokbel, " Recommendations in location-based social networks: a survey, " GeoInformatica, vol. 19, no. 3, pp. 525-565, 2015.
doi: 10.1007/s10707-014-0220-8.
[18] E. Galbrun, K. Pelechrinis, and E. Terzi, " Urban
navigation beyond shortest route: The case of safe paths, "
Inform. Syst., vol. 57, pp. 160-171, 2016. doi: 10.1016/j.
is.2015.10.005.
[19] P. Samuel Castro, D. Zhang, C. Chen, S. Li, and
G. Pan, " From taxi GPS traces to social and community
dynamics: A survey, " ACM Comput. Surveys (CSUR), vol.
46, no. 2, p. 17, 2013.
[20] G. Jossé et al., " Knowledge extraction from crowdsourced data for the enrichment of road networks, " Geoinformatica, vol. 21, no. 4, pp. 763-795, 2017. doi: 10.1007/
s10707-017-0306-1.
[21] C. Chen, L. Gao, X. Xie, and Z. Wang, " Enjoy the
most beautiful scene now: A memetic algorithm to solve
two-fold time-dependent arc orienteering problem, "

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | MAY 2021

Frontiers Computer Sci., vol. 14, no. 2, pp. 364-377, 2020.
doi: 10.1007/s11704-019-8364-1.
[22] Y. Lu, G. Jossé, T. Emrich, U. Demiryurek, M. Renz,
C. Shahabi, and M. Schubert. " Scenic routes now: Efficiently solving the time-dependent arc orienteering problem, " in Proc. ACM Conf. Inf. Knowledge Manag., 2017, pp.
487-496.
[23] C. Archetti, Á. Corberán, I. Plana, J. M. Sanchis, and
M. Grazia Speranza, " A branch-and-cut algorithm for the
orienteering arc routing problem, " Comput. Oper. Res.,
vol. 66, pp. 95-104, 2016. doi: 10.1016/j.cor.2015.08.003.
[24] D. Gavalas, C. Konstantopoulos, K. Mastakas, G.
Pantziou, and N. Vathis, " Approximation algorithms
for the arc orienteering problem, " Inform. Process. Lett.,
vol. 115, no. 2, pp. 313-315, 2015. doi: 10.1016/j.
ipl.2014.10.003.
[25] C. Coello and A. C, " Evolutionary multi-objective optimization: a historical view of the field, " IEEE
Comput. Intell. Mag., vol. 1, no. 1, pp. 28-36, 2006. doi:
10.1109/MCI.2006.1597059.
[26] J. Kim, M. Cha, and T. Sandholm, " Socroutes: Safe
routes based on tweet sentiments, " in Proc. 23rd Int. Conf.
World Wide Web, 2014, pp. 179-182.
[27] M. H. Sharker, H. A. Karimi, and J. C. Zgibor, " Health-optimal routing in pedestrian navigation services, " in Proc. 1st ACM SIGSPATIAL Int.
Workshop Use GIS Public Health, 2012, pp. 1-10. doi:
10.1145/2452516.2452518.
[28] J. Li, " Research on team orienteering problem with
dynamic travel times, " JSW, vol. 7, no. 2, pp. 249-255,
2012. doi: 10.4304/jsw.7.2.249-255.
[29] A. Garcia, P. Vansteenwegen, O. Arbelaitz, W.
Souffriau, and M. T. Linaza, " Integrating public transportation in personalised electronic tourist guides, "
Comput. Oper. Res., vol. 40, no. 3, pp. 758-774, 2013.
doi: 10.1016/j.cor.2011.03.020.
[30] P. Vansteenwegen, W. Souffriau, G. V. Berghe, and
D. V. Oudheusden, " Iterated local search for the team
orienteering problem with time windows, " Comput.
Oper. Res., vol. 36, no. 12, pp. 3281-3290, 2009. doi:
10.1016/j.cor.2009.03.008.
[31] A. Gunawan, Z. Yuan, and H. C. Lau, A Mathematical Model and Metaheuristics for Time Dependent Orienteering
Problem. PATAT, 2014.
[32] D. Gavalas, C. Konstantopoulos, K. Mastakas, G. Pantziou, and N.Vathis, " Efficient heuristics for the time dependent
team orienteering problem with time windows, " in Proc. Int.
Conf. Appl. Algorithms, 2014, pp. 152-163.
[33] M. Dorigo, M. Birattari, and T. Stützle, " Ant colony
optimization, " IEEE Comput. Intell. Mag., vol. 1, no. 4,
pp. 28-39, 2006. doi: 10.1109/CI-M.2006.248054.
[34] R. A. Abbaspour and F. Samadzadegan, " Timedependent personal tour planning and scheduling in metropolises, " Expert Syst. Appl., vol. 38, no. 10, pp. 12,439-
12,452, 2011. doi: 10.1016/j.eswa.2011.04.025.
[35] C. Verbeeck, K. Sörensen, E.-H. Aghezzaf, and P.
Vansteenwegen, " A fast solution method for the time-dependent orienteering problem, " Eur. J. Oper. Res., vol. 236,
no. 2, pp. 419-432, 2014. doi: 10.1016/j.ejor.2013.11.038.
[36] Y. Mei, F. D. Salim, and X. Li, " Efficient metaheuristics for the multi-objective time-dependent orienteering problem, " Eur. J. Oper. Res., vol. 254, no. 2, pp.
443-457, 2016. doi: 10.1016/j.ejor.2016.03.053.
[37] C. Chen, X. Chen, Z. Wang, Y. Wang, and D.
Zhang, " ScenicPlanner: planning scenic travel routes
leveraging heterogeneous user-generated digital footprints, " Front. Comput. Sci., vol. 11, no. 1, pp. 61-74, 2017.
doi: 10.1007/s11704-016-5550-2.
[38] C. Chen, D. Zhang, B. Guo, X. Ma, G. Pan, and Z.
Wu, " TripPlanner: personalized trip planning leveraging
heterogeneous crowdsourced digital footprints, " IEEE
Trans. Intell. Transp. Syst., vol. 16, no. 3, pp. 1259-1273,
2014. doi: 10.1109/TITS.2014.2357835.
[39] M. Alivand and H. Hochmair, " Extracting scenic routes from VGI data sources, " in Proc. 2nd
ACM SIGSPATIAL Int. Workshop on Crowdsourced
and Volunteered Geographic Inf., 2013, pp. 23-30. doi:
10.1145/2534732.2534743.
[40] U. Demiryurek, F. Banaei-Kashani, C. Shahabi, and
A. Ranganathan, " Online computation of fastest path
in time-dependent spatial networks, " in Proc. Int. Symp.
Spatial and Temporal Databases, 2011, pp. 92-111.
IEEE Computational Intelligence Magazine - May 2021

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