1.一种求解旅游行程规划问题的新分支定界方法,其特征在于,包括如下步骤:步骤S1:在规划起始时刻之前采集所有游客的信息,其中,采集的游客信息至少包括每位游客的旅游总时长,每位游客在接受每个景点的服务后所能获得的效用;
步骤S2:在算法运行之前,确定算法计算所需的参数;其中包括每个景点服务一位游客所需的服务时间,每个景点的资源约束,即每个景点能够同时服务的游客的数量,所有任意两个景点之间的旅行时间;
步骤S3:以所有游客的总效用为目标函数,建立混合整数线性规划模型;
步骤S4:对上述模型,设计了新分支定界算法进行求解,最终得到游客总效用最大的旅游路线规划方案;
所述S3中,混合整数线性规划模型进一步定义如下:步骤S31:定义0-1决策变量x
步骤S32:建立如下的总效用最大化优化模型:
约束条件为:
所述步骤S4所包括的新分支定界算法进一步包括如下步骤:步骤S41:构造算法的数据结构,具体如下:
每个解采用N+H个部分排列来表示N个游客和H个景点之间的联系;每个游客从起点即景点0出发,终止于终点即景点H+1;每个游客的旅游路径用T步骤S42:算法的分支过程具体如下:
依次为每个游客规划一条旅游路线,规划顺序对最终结果没有影响,因为所有可能的路线都会被测试;新分支定界算法按照先来先服务的基本原则为每个游客分配旅游路径,在每次迭代中,算法按照从小到大的序号从当前游客未访问的景点中选择一个景点;游客可以选择在本次迭代中访问选定的景点并生成分支;如果当前游客选择参观选定的景点,则算法进入下一次迭代;否则选择下一个景点,并生成一个新分支;如果当前游客选择不访问最后一个景点或已访问所有景点,则游客访问终点,算法开始为下一个游客分配路线;采用递归来实现分支;
步骤S43:算法的定界过程如下:
分支定界算法的效率主要取决于定界即剪枝的效率,具体如下:当第p个游客的路径已经分配结束后,算法计算如下线性整数规划模型,用来在分支过程中中止没有效率的分支:约束条件为:
其中
求解上述混合线性整数规划模型,如果求解器无解,或当前