基于时间框架的多日游行程规划及其优化方法

张久滕， 吴小竹， 陈崇成， 方 荟, 2， 刘先锋， 方 东

(1. 福州大学福建省空间信息工程研究中心， 空间数据挖掘与信息共享教育部重点实验室， 福建 福州 350116； 2. 闽江学院计算机科学系， 福建 福州 350108； 3. 福州林景行信息技术有限公司， 福建 福州 350117)

0 引言

旅行者在去到一个不熟悉的城市旅游时， 通常面临的问题是选择哪些受欢迎的兴趣点(points of interest， POIs)以及确定每一天的行程安排. 这涉及诸多限制条件， 比如每一个POI的参观时间、 POI的时间窗口(开放和关闭时间)、 POI之间的距离、 旅游总时间限制等， 考虑上述不同的参数以及约束条件的问题统称为旅游行程规划问题(tourist trip design problem, TTDP)[1-2].

近年来， 自驾游以一种张扬个性为主题的旅游方式兴起. 它从旅行者的实际需求和景点的实际情况出发， 自主选择服务进行组合. 因此， 针对自驾游的特点为旅行者提供满足其需求的行程安排具有意义.

本研究基于定向问题建立旅游行程规划模型， 提出一种旅游行程规划算法(tourist trip design algorithm， TTDA). 算法包括时间框架的建立、 有效旅游路线的生成以及基于遗传算法的路线优化3个过程. 最后通过在望路者文化旅游网提供的数据集上进行实验， 验证提出的算法在生成解的质量上相对于绝对最优解， 有着比较好的评分最优率gap以及收敛效果， 能够满足绝大部分用户的出行需求.

1 相关研究

1.1 基本定向问题

定向问题(orienteering problem， OP)也被认为是旅行推销员问题、 最大集合问题. 在旅游行程规划领域， 该问题可以定义为： 给定多个POIs集合(包括起点和终点)以及一个最大时间约束， 其中每个POI包含一个评分值和一个停留时间， 总目标是在不超过最大时间约束的条件下找到一条从起点到终点的旅游路线， 并且使得该旅游路线的总评分值最大.

旅行中的路线优化是OP的一个典型应用. Chao等提出一种新的启发式算法， 包括路线初始化和路线优化过程. 初始化过程得到一条合理的旅游路线， 优化过程对初始化过程获得的路线进行改善. 除此之外， Vansteenwegen等、 Brilhante等、 Gionis等、杨理云等学者都对基于定向问题的旅游行程规划进行过深入研究.

1.2 定向问题的扩展

根据现实中要解决的实际问题需要， 基本的定向问题经常扩展为其它形式的问题， 主要包括团队定向问题(team orienteering problem， TOP)， 带时间窗的团队定向问题(team orienteering problem with time windows， TOPTW)， 时间依赖型定向问题(time dependent orienteering problem， TDOP)[10].

TOP相比于OP是要找到多条最优的旅游路线. Chiang等[11]提出了一种用户自适应旅游规划系统来解决TOP， 给出一个时间框架(TF)的概念模型， TF会根据用户从前端传来的旅游天数， 自动将一条完整的多日游旅游路线分割成多条单日的旅游路线， 每一天的路线都由一个24 h系统所控制， 若当天的旅游总时间超过了24 h， 则自动从下一天开始规划新的行程.

TOPTW是对每个POI增加一个时间窗口(即POI的开放和关闭时间)的约束. Vansteenwegen等采用迭代式局部搜索的办法来解决TOPTW， 对于时间窗的要求， 通过设置的一个“惩罚函数”来降低用户提前到达POIs的评分值. Sylejmani等[12]采用硬时间窗的要求， 即不允许用户提前到达每个POI， 最终结果表明该方法能够显著减少计算的时间.

TDOP与OP的主要区别在于POIs之间的交通时间， 对于OP来说， 两点之间的交通时间是个常量， 而对于TDOP， POIs之间的交通时间则取决于POIs之间的交通方式、 交通流量等. 对于这类问题， Rahim等采用改进的遗传算法， 他们首先对3种不同的交通方式(步行、 地铁、 公共汽车)下的最短路径进行分析； 其次， 采用遗传算法对不同交通组合条件下的旅游路线进行优化. 与上述工作相比， 研究旅游行程规划问题(TTDP)是从旅行者的实际需求出发， 综合考虑到行程起终点的位置、 每天的游玩时间约束、 每个POI的时间窗口， 同时为每一天的行程提供午餐地以及住宿地安排， 最终为用户提供一条最优的旅游路线.

2 问题描述

图1 两天的旅游路线实例Fig.1 Example of two days tour route

根据上节所述， TTDP可以理解为： 在给定的多个POIs集合(包括景点、 住宿地和午餐地3类 )中， 每个POI包含一个评分值、 一个停留时间和一个时间窗口； 从给定的起点开始， 在多个约束条件下， 通过分析、 排除、 选择哪些景点、 午餐地以及住宿地， 最后回到终点， 使得路线所经过POIs的总评分之和最高. 图1表现了这样一个搜索过程. TTDP模型的决策变量可以用如下的多维数组来表示：

TTDP=(S,R,H,V,F,D, ST,t,Tmax,P)

其中：S={s1,s2, …,sa}代表景点POIs集合；R={r1,r2, …,rb}代表午餐地POIs集合；H={h1,h2, …,hc}代表住宿地POIs集合；V={v1,v2, …,vn}代表所有的POIs集合；V=S∪R∪H，sa∈S，rb∈R，hc∈H；F={f1,f2, …,fg}代表限制因素集合；D={d1,d2, …,de}代表旅游天数集合； ST={sta1, sta2, …, stan}代表停留时间集合， 它对应V中每一个POI的参观时间；t:(tx,ty)是自驾游交通时间集合， 由一个二维数组表示， 代表连续访问两个POI所花费的交通时间；Tmax是最大时间约束；P={P1,P2…,Pn}是所有点的评分集合， 代表V中每一个点的受欢迎程度. 因此， TTDP的数学模型表示为：

目标函数(1)表示参观POIs的总评分最大，yi表示是否经过第i个POI， 是则为“1”， 不是则为“0”； 条件(2)是午饭时间约束， earlyTime代表最早午饭时间， lastTime代表最晚午饭时间； 条件(3)是指找到一个离X点一定时间距离范围内， 评分最高的Y点， timeRange就是指时间距离， 这个函数的目标是用来找到合适的午餐地和住宿地POI； 条件(4)确保路线满足最大时间预算， 即花费的交通时间和在每个POI的参观时间之和不能超过这个最大时间约束，xij代表是否经过边(i，j)， 是则为“1”， 不是则为“0”； 条件(5)表示行程必须从点A出发， 最后回到B点， 这里A为行程规划的起点，B为行程规划的终点(若A与B是同一个位置， 那就表示旅游开始的起点和终点固定且相同)； 条件(6)保证了节点路线的连通性并且每个景点最多只能访问一次； 条件(7)表示从起点出发的开始时刻； 条件(8)和(9)为时间窗口约束，Tarrive(i)为到达第i个POI的时刻，Tleave(i)为离开第i个POI的时刻， 到达i点的时刻必须大于i的开始时间小于i的关闭时间， 并且离开i点时也要小于其关闭时间； 条件(10)确保变量取值必须为整数.

图2 时间框架Fig.2 Time framework(TF)

3 旅游行程规划算法

3.1 时间框架

Chiang等[11]提到一个多日游的时间框架， 如图2所示. 该框架将一条完整的多日游旅游路线分割成多个单日的旅游路线， 每一天的旅游路线包括一个出发地POI、 一个结束地POI、 一个午餐地POI和若干景点POIs， 每一个POI包含3个时间块属性： 天数、 停留时间和POI类别， 时间块表示为TF=(de， stan，vn)，de∈D， stan∈ST，vn∈V， 其中，V=S∪R∪H，sa∈S，rb∈R，hc∈H. 时间框架的优点是将多日旅游路线分割成多个单日的旅游路线， 因此可以清晰地知道每一天的旅游路线情况， 此外， 时间块包含每一个POI的属性信息， 能够保证同一个景点不会被重复访问.

从行程规划的起点开始， 逐个往时间框架里面插入符合条件的POI， 作为下一个要访问的点， 由于每天的行程要提供住宿的地方， 因此除最后一天外， 将住宿地作为单日行程规划结束的标志， 同时第二天的出发地是前一天晚上的住宿地， 如此不断地重复这个过程直到插入终点为止， 从而生成一条完整的多日游旅游路线.

3.2 有效旅游路线的生成

有效路线的生成指的是为了满足模型所规定的所有约束条件而获得的一条合理旅游路线. 研究采用逐点分析的方法， 根据遗传算法的操作步骤得到多个不同的POIs的排列顺序， 针对每个POIs的排列顺序， 逐个分析、 排除和插入符合条件的POIs， 得到一条符合条件的有效旅游路线. 具体的算法描述如下.

输入： 当前POIs的排列顺序， 最大时间约束Tmax， 起始点A和终点B， 午餐时间LunchTime， 行程的开始时刻Tstart.

输出： 一条有效的旅游路线.

步骤1 出发地POI的选择. 判断当天是否是行程规划的第一天， 若是， 则将行程的起始点A加到时间框架中去； 若否， 则添加前一天的住宿地. 添加出发地后， 更新时间框架以及初始化算法的变量值.

步骤2 景点POI的选择. 根据当前POIs的排列顺序， 首先判断点vi是否属于景点POI， 若是， 再判断该景点是否符合条件， 符合条件则保留， 判断的依据是该景点是否已经走过, 到达该点的时刻是否符合该点的时间窗口以及当前游玩的总时间消耗是否小于最大时间约束； 若否， 则跳转步骤4. 其中

式(11)～(13)中：T为当前游玩总时间消耗， 包括在每个POI的参观时间和交通时间之和；Tarrive(i)和Tleave(i)为到达和离开i点的时刻.

步骤3 午餐地POI的选择. 根据步骤2得到离开某景点之后的时刻， 判断离开该景点的时刻是否落在午饭时间LunchTime范围内， 若是， 则根据公式(3)在路线中添加一个午饭地点Y； 若否， 则跳转步骤4.

步骤4 判断当前POIs是否遍历结束， 若否， 则继续判断下一个POI是否符合条件， 跳转步骤2； 若是， 跳转步骤5.

步骤5 结束地POI的选择. 若所有的POIs遍历结束， 判断当天是否是最后一天的行程， 若否， 同样根据公式(3)添加一个住宿地Z作为当天行程的结束标志， 跳转步骤1开始规划下一天的行程； 若是， 则将行程的终点B添加到时间框架内， 全部行程结束.

步骤6 全部行程规划结束之后， 时间框架内的时间块被全部填充满,得到一条完整、有效的多日游旅游路线.根据时间框架内所有POIs的评分值计算旅游路线的评分值， 路线评分值即时间框架内所有旅游POIs的评分之和.

3.3 基于遗传算法的路线优化方法

遗传算法最早由美国的Holland教授[12]提出， 是通过模拟自然界进化过程形成的一种自适应全局优化概率搜索算法. 算法中的选择、 交叉和变异操作可以产生多条染色体， 每条染色体代表一个新的POIs排列顺序. 因此， 研究利用遗传算法中的选择、 交叉、 变异操作， 根据节3.2所述的方法， 针对每条染色体(即POIs的排列顺序)， 获得一条合理的旅游路线， 最后计算所有合理旅游路线的评分值并输出其中评分最高的一条旅游路线.

遗传算法中的选择操作采用保留最佳和轮盘赌选择的方法. 保留最佳选择能够让最优个体直接进入到子代， 延续了该种群优良的特性； 其余个体， 先计算每个个体的适应度值， 然后根据适应度值按照比例分配一个选择概率， 个体适应度值大， 其被选择的概率越高， 反之亦然.

交叉采用次序交叉方法[13]， 基本过程是： 随机生成两个交叉位置， 交换父代个体交叉点间的片段， 将k2的中间片段复制给k1的首部， 然后删除k1中与中间片段相同的基因， 然后将剩下的基因依次插入k1的后面，k2的也类似. 例如， 生成两个交叉位置r1=3，r2=7， 父代染色体k1={2 6 47 3 5 89 1}，k2={4 5 21 8 7 69 3}， 对父代染色体交叉， 交叉后，k1={1 8 7 6 2 4 3 5 9}，k2={7 3 5 8 4 2 1 6 9}. 变异的策略是采取随机交换变异， 对一条染色体随机获得两个位置， 将这两个位置上的点互换. 比如， 生成两个交叉位置r1=3，r2=7，k1={3 582 9 417 6}， 变异后，k1={3 5 1 2 9 4 8 7 6}. 具体的遗传算法描述如下.

输入： 种群规模Scale， 交叉概率Pc， 变异概率Pm， 最大进化次数Gmax.

输出： 一条最优旅游路线.

步骤1 采用整数编码的方式对所有的POIs进行编码， 即用不同的数字来表示每一个POI.

步骤2 采用随机方法生成初始种群， 从起点开始， 随机生成下一个POI， 一直到终点， 最终形成的一条POIs排列集合也就是一条染色体， 不断重复这样的过程， 从而生成多条不同的染色体.

步骤3 根据节3.2所述方法， 针对每条染色体， 得到一条合理的旅游路线， 根据公式(1)计算路线内所有POIs的评分之和， 即适应度值.

步骤4 将对应适应度值最大的那条染色体保留， 直接复制到子代， 不进行交叉和变异， 其余染色体根据适应度值按比例分配一个选择概率.

步骤5 根据交叉概率Pc和变异概率Pm进行交叉和变异操作， 产生新的染色体.

步骤6 判断当前进化次数G是否达到最大进化次数Gmax， 若是， 则跳转步骤7； 若否， 跳转至步骤3.

步骤7 输出最优旅游路线.

4 实验结果与分析

通过实验从路线结果评分值方面对提出的TTDA算法和文献[14]提供的变邻域搜索算法(variable neighborhood search, VNS)进行比较， 分别计算旅游路线从1至6 d的路线结果， 并对其评分值大小进行比较. 最后根据某旅行者旅游一天为例， 在Web端上展示线路效果， 并具体阐述该旅行者的路线时间安排顺序.

4.1 数据来源

以福州市POIs数据为例， POIs信息来源于望路者文化旅游网站所提供的数据(见表1)， 交通时间来源于百度开放接口API(见表2)， 包括1个起终点POI、 162个景点POIs、 25个午餐地POIs和14个住宿地POIs， 总共202个POIs数据. 表1中POIs的评分值和停留时间是根据所有用户的历史数据而计算出在每个POI的平均值， POI的评分范围从1～10(起终点不包含在内， 默认为0)， 停留时间范围从60～300 min(起终点和住宿地不包含在内， 默认为0).

表1 POIs信息列表

注： 数据来源于望路者文化旅游网站(http://whlyw.net/)， 2016-06-01

表2 POIs交通时间矩阵

续表2

4.2 参数设置

为解决自驾游旅行者在旅游当中的路线安排问题， 拟采用一种旅游行程规划算法来解决TTDP. 在上述公式(1)～(10)所定义的参数中， 将福州市火车站作为行程的起始点和终点； 行程规划的开始时刻Tstart=8:00； 每天的最大旅游时间约束Tmax=10 h； 午饭时间LunchTime规定在[11: 30，13: 30]范围之内； 公式(3)是找到午餐地和住宿地的函数， 将找到午餐地的timeRange设置为30 min， 找到住宿地的timeRange设置为50 min.

遗传算法中， 种群规模为Scale=50； 最大进化次数为Gmax=1 000； 交叉概率Pc和变异概率Pm使用文献[13]提供的动态交叉Pc=0.9-(0.9-0.65)×G/Gmax， 和变异概率Pm=0.01+(0.1-0.01)×G/Gmax，G为当前进化次数. 这样既能提高算法的局部搜索能力， 也使得算法可以快速收敛到全局最优解.

4.3 实验展示与分析

为了证明TTDA算法在解决多日旅游行程规划问题上要优于VNS算法， 实验采用福州市多个POIs数据， 进行6组实验， 分别生成福州市一日游至六日游的旅游路线， 并计算最后路线结果的总评分值. 由于每次实验所得到的路线总评分值都会略有不同， 因此， 采取多次实验取平均值的方法来减小这种随机误差. 对于每组实验， 运行20次取平均值， 得到旅游路线评分值结果， 并绘制对应的折线图(见图3). 从图3的不同旅游天数限制下路线评分对比可知， TTDA算法得到的路线评分值高于VNS算法得到的结果， 而且随着旅游天数的不断增大， TTDA算法的优势将会越来越大. 因此， 通过实验得出结论： TTDA算法在解决这种带多个约束条件的行程规划问题， 在路线结果的质量上要优于VNS算法得到的结果， 能够更加高效地解决游客旅游天数较多情况下的线路规划问题.

图4是通过调用百度提供的地图功能和驾车路线功能并在Web端显示的一条福州市一日游的旅游路线例子. 如图4所示， 一日游的旅游路线为： 福州站-福州国家森林公园-三坊七巷-福州大饭店-五一广场-福州站. 具体描述这一天的行程安排为： 早上8:00从福州站出发， 8:20到达福州国家森林公园， 10:20离开福州国家森林公园， 10:50到达三坊七巷， 12:50离开三坊七巷， 13:04到达福州大饭店吃饭， 14:04离开， 14:09到达五一广场， 17:29离开五一广场， 17:54到福州站， 一天行程结束.

图3 路线结果曲线图 Fig.3 Graph of tour route results

图4 一日游行程规划结果Fig.4 Result of one days trip design

5 结语

在定向问题的基础上构建了旅游行程规划问题的模型， 综合考虑行程的起终点位置、 每个POI的时间窗口、 旅游最大时间约束、 午餐地和住宿地安排等因素. 并提出了一种旅游行程规划算法TTDA， 该算法基于多日游的时间框架， 通过嵌入的遗传算法不断优化有效旅游路线， 最终向用户推荐一条最优的旅游路线. 最后通过实例验证提出的TTDA算法相较于VNS算法， 在解决旅游行程规划问题时能够获得质量更优异的解. 但研究还存在不足， 模型的目标函数设计单一， 只考虑了POIs的评分， 未来可从POIs的评分、 旅游消费等多个方面去设计目标函数； 规划的旅游路线本质上来说属于静态的路线， 没有考虑到因天气变化、 景区关闭、 交通拥挤等问题而不得不更改现有路线的情况， 未来可以考虑多种特殊条件之下的行程规划， 使推荐的路线能够动态变化以适应各种复杂情况.