一类多日均衡满意度的旅行规划算法

徐侃; 郑骏

doi:10.3969/j.issn.1000-5641.2018.02.006

一类多日均衡满意度的旅行规划算法

doi: 10.3969/j.issn.1000-5641.2018.02.006

徐侃,
郑骏^,

华东师范大学计算机科学与软件工程学院, 上海 200062

详细信息

作者简介:
徐侃, 男, 硕士研究生, 研究方向为普适计算.E-mail:2540788463@qq.com

通讯作者:
郑骏, 男, 教授级高级工程师, 博士生导师, 研究方向为Web应用技术.E-mail:jzheng@cc.ecnu.edu.cn

中图分类号: TP315.69
计量
- 文章访问数: 159
- HTML全文浏览量: 71
- PDF下载量: 374
- 被引次数: 0
出版历程
- 收稿日期: 2017-01-23
- 刊出日期: 2018-03-25

Balancing travel satisfaction algorithm for multi-day trip planning

XU Kan,
ZHENG Jun^,

School of Computer Science and Software Engineering, East China Normal University, Shanghai 200062, China

摘要

摘要: 基于位置的服务是确定移动用户所在位置并根据位置来提供的一种服务，其中，旅行规划是众多服务应用中的热点之一.通过基于位置的服务，人们可以根据自己的偏好制订不同的旅行规划.然而，在大多数研究中，旅行规划只关注于在所有兴趣点中制订一条符合旅行要求的路线.当游客决定在所在城市游玩多日时，这些研究所制订的路线给游客所带来的旅行满意度就会逐天递减，不符合多日旅程线路规划的制订.为了提高游客旅行时多日旅行满意度的稳定性问题，将天数因素作为多日旅行规划的参数之一，通过获取兴趣点集合的相关信息，如位置、评分、类别等，构建兴趣点网络模型，利用启发式算法得出最佳的路线，制订有效的多日旅行规划.实验结果证明，所提出的算法可以高效地得到多条旅行均衡的高质量旅行路线.
- 多日旅行规划 /
- 基于位置服务 /
- 普适计算
Abstract: Location-based service is a kind of service that obtains the location of mobile user and provides it according to location. Among them, one of the active topics is trip planning. People can make different trip planning to meet their multiple requirements by location-based service. However, in most studies, trip planning only focus on searching one route in many locations according to user's demands. When people are trying to visit the city more than one day, the travel satisfaction of the routes provided by previous researches would reduce by day. Hence, the previous work cannot meet the requirement of multi-day trip planning. To improve the satisfaction stability of multi-day trip planning, we use trip day as one of the multi-day travel planning parameters. We acquire points of interest (POIs) information (e.g., location, scoring, category, etc.) and construct a POI network model, obtain optimal trip routes through heuristic algorithm, develop an effective multi-day travel planning. The experimental results demonstrate that our proposed method can plan a multi-day trip with high quality and more balanced route.
- multi-day trip planning /
- location-based service /
- ubiquitous computing

HTML全文

图 1 多日旅行规划示例

Fig. 1 A example of multi-day trip planning

下载: 全尺寸图片幻灯片

图 2 旅行效益值/类型数量关系图

Fig. 2 Trip score by varying number of POI types

下载: 全尺寸图片幻灯片

图 3 平均每天旅行时间/类型数量关系图

Fig. 3 Average per day trip time by varying number of POI types

下载: 全尺寸图片幻灯片

图 4 计算时间/类型数量关系图

Fig. 4 Computation time cost by varying number of POI types

下载: 全尺寸图片幻灯片

图 5 旅行效益值/旅行天数关系图

Fig. 5 Trip score by varying trip days

下载: 全尺寸图片幻灯片

图 6 平均每天旅行时间/旅行天数关系图

Fig. 6 Average per day trip time by varying trip days

下载: 全尺寸图片幻灯片

图 7 计算时间/旅行天数关系图

Fig. 7 Computation time cost by varying trip days

下载: 全尺寸图片幻灯片

表 1 路径规划参数

Tab. 1 Attributes of path planning

参数	意义
$a$, $A$	$a$表示兴趣点, $A$表示兴趣点集合
$t(a)$	兴趣点$a$的游玩时间
$s(a)$	兴趣点$a$的评分
$r$, $R$	$r$表示一条路线, $R$表示路线集
$t(r_{i, j})$	表示兴趣点$i$到兴趣点$j$转移的交通时间
$tp$, $TP$	$tp$表示单日旅行, 由兴趣点集合组成; $TP$表示多日旅行, 由单日旅行组成
$D$	表示旅行的天数
$t(tp)$, $T(tp)$	$t(tp)$表示单日旅行时间, $T(tp)$表示总天数旅行总时间
$s(tp)$, $S(tp)$	$s(tp)$表示单日旅行兴趣点评分, $S(tp)$表示总天数旅行兴趣点总评分

下载: 导出CSV

算法1评分最高添加
输入: 出发地点$v_0$, 旅行天数$D$, 兴趣点类别的游玩顺序集合$Seq=\{q_1, q_2, \cdots, q_D\}$, 每一天的游玩顺序$q_i=\{c_1, c_2, \cdots, c_m\}$
输出: $D$天的旅行行程
1. $TP=\{tp_1, tp_2, \cdots, tp_k, \cdots, tp_D\}$ //初始化多日行程
2. for$k$:=1 to $D$ do
3. $tp_k=\{v_0\}$ //初始化每天行程, 行程初始节点为$v_0$
4. end for
5. for $k$:=1 to $D$ do
6. for $i$: =1 to $m$ do
7. tempPOI$\leftarrow $Find the highest score POI in $c_i$ //将$c_i$中最高评分的兴趣点添加到旅行线路中
8. $tp_k=tp_k\cup$ tempPOI
9. Delete tempPOI //将已经选择的兴趣点排除候选兴趣点集
10. return $TP$

下载: 导出CSV

算法2 同步评分最高添加
输入:出发地点$v_0$, 旅行天数$D$, 兴趣点类别的游玩顺序集合$Seq=\{q_1, q_2, \cdots, q_D\}$, 每一天的游玩顺序$q_i=\{c_1, c_2, \cdots, c_m\}$
输出: $D$天的旅行行程
1. $TP=\{tp_1, tp_2, \cdots, tp_k, \cdots, tp_D\}$ //初始化多日行程
2. for $k$:=1 to $D$ do
3. $tp_k=\{v_0\}$ //初始化每天行程, 行程初始节点为$v_0$
4. end for
5. while (POIType==$c_1$)
6. for $k$:=1 to $D$ do
7. tempPOI$\leftarrow $Find the highest score POI in $s_1$
8. $tp_k=tp_k\cup$ tempPOI
9. Delete tempPOI
10. end while
11. for $i$:=2 to $m$ do
12. $TP=TP$.sort() by $s(tp)$ //将$D$天的当前旅行线路中的兴趣点评分之和排序, 线路评分较低的线路优先选择
13. for $k$:=1 to $D$ do
14. tempPOI$\leftarrow $Find the highest score POI in $c_i$ //将$c_i$中最高评分的兴趣点添加到旅行线路中
15. $TP[k]=TP[k]\cup$ tempPOI
16. Delete tempPOI
17. return $TP$

下载: 导出CSV

参考文献(20)

[1]	WANG H Y, QIAN J. Geographic location-based service reliability prediction[C]//Proceedings of the 20142nd International Conference on Advanced Cloud and Big Data. 2014: 267-274.
[2]	JIANG L C, YUE P, GUO X. Semantic location-based services[C]//Proceedings of the 2016 IEEE International Geoscience and Remote Sensing Symposium. IEEE Xplore, 2016: 3606-3609.
[3]	ZHENG Y, ZHANG L Z, XIE X, et al. Mining interesting locations and travel sequences from GPS trajectories[C]//International Conference on World Wide Web. 2009: 791-800.
[4]	BALAN R K, NGUYEN K X, JIANG L. Real-time trip information service for a large taxi fleet[C]//International Conference on Mobile Systems. 2011: 99-112.
[5]	YIN H G, WANG C H, YU N H, et al. Trip mining and recommendation from geo-tagged photos[C]//Proceedings of the 2012 IEEE International Conference on Multimedia and Expo Workshops. IEEE Xplore, 2012: 540-545.
[6]	ARASE Y, XIE X, HARA T, et al. Mining people's trips from large scale geo-tagged photos[C]//International Conference on Multimedea. 2010: 133-142.
[7]	NOULAS A, SCELLATO S, LATHIA N, et al. A random walk around the city: New venue recommendation in location-based social networks[C]//Proceedings of the 2012 International Conference on Privacy, Security, Risk and Trust and 2012 International Conference on Social Computing. 2012: 144-153.
[8]	LI F F, CHENG D H, HADJIELEFTHERIOU M, et al. On trip planning queries in spatial databases[C]//Proceedings of the 9th International Conference on Advances in Spatial and Temporal Databases. 2005: 273-290.
[9]	SHARIFZADEH M, KOLAHDOUZAN M, SHAHABI C. The optimal sequenced route query[J]. The VLDB Journal, 2008, 17(4):765-787. doi: 10.1007/s00778-006-0038-6
[10]	NUZZOLO A, COMI A, ROSATI L. Normative optimal strategies: A new approach in advanced transit trip planning[C]//Proceedings of the 2016 IEEE 19th International Conference on Intelligent Transportation Systems. 2016: 35-40.
[11]	CHIA W C, YEONG L S, LEE F J X, et al. Trip planning route optimization with operating hour and duration of stay constraints[C]//Proceedings of the 201611th International Conference on Computer Science & Education. 2016: 395-400
[12]	LOPES R B, COELHO T, SANTOS B S. Visually supporting location and routing decisions in tourist trip planning: An exploratory approach[C]//Proceedings of the 201620th International Conference Information Visualization. 2016: 236-241.
[13]	DAI J Q, LIU G F, XU J J, et al. An efficient trust-oriented trip planning method in road networks[C]//Proceedings of the 2014 IEEE 11th Intl Conf on Ubiquitous Intelligence and Computing and 2014 IEEE 11th Intl Conf on Autonomic and Trusted Computing and 2014 IEEE 14th Intl Conf on Scalable Computing and Communications and Its Associated Workshops. 2014: 487-494.
[14]	LU E H C, LIN C Y, TSENG V S. Trip-mine: An efficient trip planning approach with travel time constraints[C]//Proceedings of the 2011 IEEE 12th International Conference on Mobile Data Management. IEEE, 2011: 152-161.
[15]	BRILHANTE I, MACEDO J A, NARDINI F M, et al. Where shall we go today? Planning touristic tours with TripBuilder[C]//International Conference on Information and Knowledge Management. 2013: 757-762.
[16]	ZHANG J Z, WEN J, MENG X F. Multi-tag route query based on order constraints in road networks[J]. Chinese Journal of Computers, 2012, 35(11):2317-2326. doi: 10.3724/SP.J.1016.2012.02317
[17]	CHEN H, KU W S, SUN M T, et al. The multi-rule partial sequenced route query[C]//Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2008: Article No 10.
[18]	KANZA Y, LEVIN R, SAFRA E, et al. Interactive route search in the presence of order constraints[J]. Proceedings of the VLDB Endowment, 2010, 3(1/2):117-128. http://dl.acm.org/citation.cfm?id=1920861
[19]	CHEN C, ZHANG D Q, GUO B, et al. TripPlanner:Personalized trip planning leveraging heterogeneous crowdsourced digital footprints[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(3):1259-1273. doi: 10.1109/TITS.2014.2357835
[20]	BAO J L, YANG X C, WANG B, et al. An efficient trip planning algorithm under constraints[C]//Proceedings of the 201310th Web Information System and Application Conference. IEEE Xplore, 2013: 429-434.