1.一种求解旅游行程规划问题的新分支定界方法，其特征在于，包括如下步骤：步骤S1：在规划起始时刻之前采集所有游客的信息，其中，采集的游客信息至少包括每位游客的旅游总时长，每位游客在接受每个景点的服务后所能获得的效用；

步骤S2：在算法运行之前，确定算法计算所需的参数；其中包括每个景点服务一位游客所需的服务时间，每个景点的资源约束，即每个景点能够同时服务的游客的数量，所有任意两个景点之间的旅行时间；

步骤S3：以所有游客的总效用为目标函数，建立混合整数线性规划模型；

步骤S4：对上述模型，设计了新分支定界算法进行求解，最终得到游客总效用最大的旅游路线规划方案；

所述S3中，混合整数线性规划模型进一步定义如下：

步骤S31：定义0‑1决策变量xijk，当游客i选择从景点k到景点j时为1，否则为0；0‑1决策变量zijm，当游客i访问景点j时占用了资源m时为1，否则为0；0‑1决策变量qiljm，在景点j时，对于资源m，当游客i先于游客l被服务时为1，否则为0；sij为游客i在景点j的起始服务时间；

uij是用于防止回环的辅助变量；ttjk为景点j和k之间的旅行时间，Rik是游客i游玩景点k的效用；scj为景点j旅游资源的总负荷；stj为景点j的服务时间；tli为游客i的总时长；N和H为游客总数和景点的总数；

步骤S32：建立如下的总效用最大化优化模型：

约束条件为：

所述步骤S4所包括的新分支定界算法进一步包括如下步骤：

步骤S41：构造算法的数据结构，具体如下：

每个解采用N+H个部分排列来表示N个游客和H个景点之间的联系；每个游客从起点即景点0出发，终止于终点即景点H+1；每个游客的旅游路径用Tk，k＝1,2,...,N表示，即表示为一个景点的排列；因为资源限制约束，每个景点必须按照一定的次序来服务游客，用一个游客排列来表示，即Rl，l＝1,2,...,H；当一个游客访问一个景点时，他在旅游路径和游客排列上讲占用一个位置；

步骤S42：算法的分支过程具体如下：

依次为每个游客规划一条旅游路线，规划顺序对最终结果没有影响，因为所有可能的路线都会被测试；新分支定界算法按照先来先服务的基本原则为每个游客分配旅游路径，在每次迭代中，算法按照从小到大的序号从当前游客未访问的景点中选择一个景点；游客可以选择在本次迭代中访问选定的景点并生成分支；如果当前游客选择参观选定的景点，则算法进入下一次迭代；否则选择下一个景点，并生成一个新分支；如果当前游客选择不访问最后一个景点或已访问所有景点，则游客访问终点，算法开始为下一个游客分配路线；采用递归来实现分支；

步骤S43：算法的定界过程如下：

分支定界算法的效率主要取决于定界即剪枝的效率，具体如下：当第p个游客的路径已经分配结束后，算法计算如下线性整数规划模型，用来在分支过程中中止没有效率的分支：约束条件为：

其中 表示前p个游客已经指派方案确定时所对应的决策变量取值；

求解上述混合线性整数规划模型，如果求解器无解，或当前 对应的上界小于当前最好解，或者已经分配完了所有的游客，则算法回溯；否则算法继续为下一个游客指派路径。