(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111660109.4 (22)申请日 2021.12.31 (71)申请人 杭州电子科技大 学 地址 310018 浙江省杭州市下沙高教园区 二号路 (72)发明人 雒兴刚　冯鹏威　刘昕睿　姬朋立　 张忠良　阮渊鹏　蔡灵莎　 (74)专利代理 机构 浙江永鼎律师事务所 3 3233 专利代理师 阮玉欣 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/06(2012.01) G06Q 50/14(2012.01) (54)发明名称 一种求解旅游行程规划问题的新分支定界 方法 (57)摘要 本发明公开了一种求解旅游行程规划问题 的新分支定界方法， 步骤S1： 在算法开始之前采 集所有游客的信息； 步骤S2： 确定优化模型求解 计算所需的参数； 步骤S3： 在考虑旅游资源资源 限制的基础上， 建立一个混合整数线性规划的优 化模型来计算规划方案； 步骤S4： 针对该优化模 型， 利用新分支定界算法进行求解， 最终得到游 客总效用最大的旅游路线规划方案， 该方案是全 局最优解。 本发 明从对全域旅游的角度来考虑我 国的旅游路线规划问题， 可以改善传统旅游中可 能出现的局部拥堵问题， 有助于提高旅游服务系 统效率和提高游客旅游满意度。 权利要求书3页 说明书8页 附图1页 CN 114511136 A 2022.05.17 CN 114511136 A 1.一种求 解旅游行程 规划问题的新分支定界方法， 其特 征在于， 包括如下步骤： 步骤S1： 在规划起始时刻 之前采集所有游客的信息， 其中， 采集的游客信息至少包括每 位游客的旅游总时长， 每位游客在接受每 个景点的服 务后所能获得的效用； 步骤S2： 在算法运行之前， 确定算法计算所需的参数； 其中主要包括每个景点服务一位 游客所需的服务时间， 每个景点的资源约束， 即每个景点能够同时服务的游客的数量， 所有 任意两个景点之间的旅行时间； 步骤S3： 以所有游客的总效用为目标函数， 建立混合整数线性 规划模型； 步骤S4： 对上述优化模型， 设计了新分支定界算法进行求解， 最终得到游客总效用最大 的旅游路线规划方案； 所述S3中， 混合整数线性 规划模型进一 步定义如下： 步骤S31： 定义0 ‑1决策变量xijk， 当游客i选择从景点k到景点j时为1， 否则为0； 0 ‑1决策 变量zijm， 当游客i访问景点j时占用了资源n时为1， 否则为0； 0 ‑1决策变量qiljm， 在景点j时 对于资源m， 当游客i先于游客j被服务时为1， 否则为0； sij为游客i在景点j的起始服务时间； uij是用于防止回环的辅助变量； ttjk.为景点j和k之间的旅行时间， Rik是游客i游玩景点k的 效用； scj(为旅游资源的总负荷； stj为景点k的服务时间； tli.为游客i的总时长； N和H为游 客总数和景点的综述； 步骤S32： 建立如下的总效用最大化优化模型： S.T. 权　利　要　求　书 1/3 页 2 CN 114511136 A 2所述步骤S4所包括的新分支定界算法进一 步包括如下步骤： 步骤S41： 构造算法的数据结构， 具体如下： 每个解采用N+H个部分排列 来表示N个游客和H个景点之间的联系； 每个游客从起点(景 点0)出发， 终止于终点(景点H+1)； 每个游客的旅游路径用Tk(k＝1,2,...,N)表示， 即表示 为一个景点的排列； 因为资源限制约束， 每个景点必须按照一定的次序来服务游客， 这可以 用一个游客排列来表示， 即Rl(l＝1,2,...,H)； 当一个游客访问一个景点时， 他在旅游 路径 和游客排列上讲占用一个 位置； 例如， 给定N＝2和H＝6； 其中， T1和T2分别表示两个游客的旅 游路径； 因为两个游客都访问景点5或景点2， 因此两个游 客在景点5或景点2将产生队列， 也 存在一个排队的次序； R5和R2表示了在景点5或景点2上的游客 排列， 即排队顺序； 步骤S42： 算法的分支过程具体如下： 依次为每个游客规划一条旅游路线， 规划顺序对最终结果没有影响， 因为所有可能的 路线都会被测试； 新分支定界算法按照先来先服务的基本原则为每个游客分配旅游路径， 在每次迭代中， 算法按照 从小到大 的序号从当前游客未访问的景点中选择一个景点； 游客 可以选择在本次迭代中访问选定的景点并生成分支； 如果当前游客选择参观选定的景点， 则算法进入下一次迭代； 否则选择下一个景点， 并生成一个新分支； 如果当前游客选择不访 问最后一个景点 或已访问所有 景点， 则游客访问终点， 算法开始 为下一个游客分配路线； 采 用递归来实现分支； 步骤S43： 算法的定界过程如下： 分支定界算法的效率主要取决于定界即剪枝的效率， 具体如下： 当第p个游客的路径已 经分配结束后， 算法计算如下线性整数规划模型， 用来在分支过程中 中止没有效率的分支： subject to: 权　利　要　求　书 2/3 页 3 CN 114511136 A 3