旅行社旅行路线安排问题.doc

1、旅行社旅行路线安排问题摘要本文从旅游系统理论、行为地理学和旅游经济学的角度对旅行社旅游线路定制问题进行了研究, 提出了旅行社旅游线路定制决策模型; 结合景点及游览时间表、景区公路交通图、景区宾馆标准间房价及旅游游客的部分表, 把景点定制下旅行社旅游行程线路问题转化为一个游憩中心的选址问题, 建立模型进行了研究。针对问题 1：根据题目建立成本最低的旅游路线即是在满足旅游要求的情况下，使旅游的路线最短，住宿费用最少，综合实际中旅游路线设计情况，旅行社带游客旅游完全部景点后要回到出发地 U 且游览的地点不重复，因此可以看作是更多约束的周游型旅游路线优化(TSP 问题) ，用多目标 01 规划来建立模

2、型。本题模型以规划为基础，以蚁群算法求解。基于此，本文将该题定义为旅游企业对旅游者旅游活动内容的时间和时空安排。针对问题 2：由问题一中所建立的模型，充分考虑到游客舒适度的要求，即：一天中坐车时间和参观景区的时间合理安排，两者总和尽可能不要超过 10小时，跟所给的条件，早餐时间安排在 7:00-7:30，午餐和晚餐时间各一个小时，且当前季节应该在 18:00 之前结束游览活动。因此同样可以看作 TSP 问题，用多目标 01 规划来建立模型。针对问题 3：本题要求确定各住宿点长期预订房间的数量。假设各个线路预定房间数量独立，可以首先由三日游一线数据得出游客数密度函数，通过期望近似处理日游客数，依

3、据每一区间日游客数变动和周末宾馆住宿优惠政策情形下，预定房间数目对人均住宿费用的影响，根据问题一二求出最优的住宿点C，详细分析得出在三日游一线曲线波动情况，得到最优住宿 C 点预定 98*2 间客房。以同样的方式处理其余各个线路，得到三日游二线最优住宿点 I 预定68*2 间客房，五日游线路最优住宿点 C 预定 90*2 间客房，V 预定 90*2 间，七日游线路最优住宿点 C，I，K，V，E 的各点预定房间数量为57，57*2，57，57，57 间。关键词：TSP 问题 01 规划一 、问题的重述面对蓬勃发展的巨大市场,旅游企业推出了大量丰富多彩的旅游线路以满足旅游者的需求。为了设计更好的旅

4、游线路,为了优化现有的线路设计,旅行社和旅游景区进行了大量的实践探索。本文试图在总结前人研究成果的基础上,把旅游线路问题的层次结构梳理清楚,并讨论运筹学和图论理论在旅游线路优化中的应用。在分析了上述基本问题之后,本文应用运筹学和图论的理论分别讨论了旅行社线路优化问题和旅游景区线路优化问题。具体的,讨论了最短路问题、旅行商问题和排程问题在旅行社线路优化中的应用;讨论了最小支撑树问题、覆盖问题和最大流问题在旅游景区线路优化中的运用,并在附录中给出了详细的电子表格解法。总之,本文是一种应用运筹学、图论理论讨论旅游企业科学管理的分析;本文是一种既考虑旅行社线路问题又考虑的旅游景区线路问题的微观层面的。

5、本文是一种在既定约束条件下实现最优目标的规范性分析;本文是一种既考虑管理者的要求又结合数学模型的定性分析与定量分析相结合的分析。就旅游者而言,对旅游线路的期望是最大化地满足其消费需要并使成本最小、日程安排最方便;对旅行社来说,他们则希望在满足旅游者需求的前提下,降低成本、提高效益,并可面对突发事件及时调整线路;旅游景区在规划设计时就要考虑景区内线路空间布局的合理性、科学性,在管理中也要考虑如何合理分流、控制游客数量的问题。显然,不管从哪个角度来说,旅游线路问题都是十分重要并值得深入研究的问题。本文拟解决以下问题：(1)分别设计三日游一线、三日游二线、五日游及七日游的旅行和住宿点，使旅行社住宿、

6、行车和人工总成本尽可能节省。(2)考虑到游客的舒适度要求，即一天中坐车的时间和参观景区的时间总和不超过 10 个小时，针对此问题制定各条旅行路线的行程安排表。(3)分析人均住宿费用关于长期预订客房数变化的波动情况，制定各住宿点长期预订的房间的数量。(4)不同日期出发的旅游客数不同，考虑最优路线是否需要调整旅游线路和长期客房预订数。为了节省车辆、油耗及人工费用，讨论是否存在不同旅行线路的游客在旅行前期合并出行的优化方案。研究三日游一线和三日游二线的景点划分的合理性，对当前所有旅行线路的旅游景点安排提出建议。(5)分析上述最优旅行线路的设计方法是否可以推广到 15 天以上行程的自助游行线路快速计算

7、。二、问题的分析2.1 问题一本题要求设计三日游一线、三日游二线、五日游三线及七日游的路线和住宿点，使得旅行社住宿行车和人工总成本尽可能节省。根据题目建立成本最低的旅游路线即是在满足旅游要求的情况下，使旅游的路线最短，住宿费用最少，综合实际中旅游路线设计情况，旅行社带游客旅游完全部景点后要回到出发地U 且游览的地点不重复，因此可以看作是更多约束的周游型旅游路线优化 (TSP问题) ，用多目标 0-1 规划来建立模型。2.2 问题二本题要求考虑游客的适度要求：一天坐车时间和参观景区的时间要合理安排，两者总和尽可能不要超过 10 个小时。针对上述问题考虑原则上一天行程20:00 之前结束，景点接待

8、游客时间每天早上 6:30 到下午 18:30。结合模型一考虑。综合实际中旅游路线设计，因此可以看作是更多约束的周游型旅游路线优化(TSP 问题)，用多目标 0-1 规划来建立模型。2.3 问题三假设旅行社针对不同线路预定不同住宿地房间数 ，)10.2,;4,31(jiRj当预定房间数目大于需要客房数目时，就不需要考虑增加新客房，当需要客房数目大于预定房间数目，针对不同的时间段，需要考虑不同住宿地点酒店的优惠政策。为了节省旅行社住宿消费，应尽量考虑适合的房间预定数量，保证得到尽量多的优惠政策，然而不造成过高空房闲置。2.4 问题四本题要求考虑首先不同日期宾馆的住宿费用变化，而问题一中考虑到的住

9、宿价格是不变的。针对此情况我们考虑住宿成本以每天人均住宿费用描述。从而可以根据问题一所建立的模型求解出发的旅游团队的最优路线是否相同。在考虑周五出发客数比平时增加 20%的情况下，通过观察可以求出三日游两条路线的最优住宿点人均住宿费用，如果人均费用在增加游客数 20%的时候并没有大幅度增加，可认为旅行路线住宿点不需要调整。且对预订房间的数量不需要增加。在研究三日游一线和三日游二线的景点划分的合理性上，本文通过比较旅游景点游览时间与坐车行程时间的比较，以及住宿费用的比较提出尽可能选择景区游览时间大于坐车时间，住宿宾馆应尽量选择价格合理的标准间旅馆。三、问题基本假设(1)假设出行旅游时天气均是良好

10、；(2)假设单一景点逗留型旅游，对本次旅行路线的设定没有影响；(3)假设每一位旅客都服从导游及旅行社的安排，不擅自停留耽误行程；(4)假设如五一、十一黄金周不会出现超大的旅客流量。不会影响交通；(5)假设每个景点只游览一次，当考虑住宿时，该地点可重复经过。(6)假设旅行社带游客旅游完全部景点后要回到出发地 U。(7)假设中晚餐不再车上吃，且晚餐在一天的旅行结束后吃。(8)假设旅游人数都住在一个住宿点(9)假设每次出游的人数随机且相互独立四、符号说明ijx表示各边对应的决策变量ijw表示各边对应的长度表示节点数量jit,表示 D 中第 i 个位置上的点到第 j 个位置上的点的时间kjix,表示第

11、 i 天是否选择从第个位置 到第 k 个位置参观旅游或住宿jH表示 D 中第 k 位置的住宿费用信息启发式因子期望启发式因子信息素挥发系数iHce*Pr表示标准间市场价1iN客房数目 Ni新增客房数目五、模型假设及求解根据题目建立成本最低的旅游路线即是在满足旅游要求的情况下，使旅游的路线最短，住宿费用最少，综合实际中旅游路线设计情况，旅行社带游客旅游完全部景点后要回到出发地 U 且游览的地点不重复，因此可以看作是更多约束的周游型旅游路线优化(TSP 问题)，用多目标 0-1 规划来建立模型。5.1.1 0-1 规划基本模型当整数规划问题中的决策变量 仅限于 0 或 1 两个数值，则该问题称为

12、0-1ix整数规划，简称 0-1 规划，其一般模型为(5.1.1).),21(0,.,ma(in)11njxmibtsczjjijj 或 ，5.1.2 周游型旅游路线优化模型周游型旅游路线问题是由出发地出发,途中刚好不重复的遍游所有的景点,最后回到出发地,形成一个闭合的环型路线的问题。该类问题至今也没有完美解决，是个 NPC 类问题，可由 TSP 问题建模，模型如下：目标函数： (5.1.2) aijijiwx1)(2mn约束条件 1：所有决策变量 为二分变量，即ij 10或ijx约束条件 2：总边数 (5.1.3)axaiji1)(约束条件 3：横行和 (5.1.4)2ji约束条件 4：纵列

13、和 (5.1.4)1aijx约束条件 5：横对称 (5.1.5) );(11abjijmabiijb xCxR其中， 表示各边对应的决策变量， 表示各边对应的长度， 为表示节点的ijxijwa数量。5.1.3 0-1 规划成本最小的旅游路线优化模型根据上一节 TSP 问题模型的设计原理，结合本题的要求建立模型。根据题意旅游路线设计中要考虑住宿的问题，对于住宿点不能区分是经过该点还是住在该点，因此为了更方便建模和求解将住宿点用两个符号分别表示，其一表示住宿点，其二表示经过该点，例如点 B，在该地既可以游览又可以住宿，则将B 表示为游览点，而 B来表示住宿点，而两点之间的距离则为 0。为了更好的表

14、示各个地点，本文将游览点和住宿点统一放到数组 中，用 表示相Dindex应的点，其中 表示为D 个 住 宿 点的 点个 是 住 宿 点 却 不 是 景 点个 景 点 名 称名 称名 称名 称名 称名 称 pm pmpm111则可以将图转换为以 中各点的排序下的邻接矩阵 ，N(5.1.6)002,1, ,2,212,1 pnmpn pnmtt tttN其中， 表示 中第 个位置上的点到第 个位置上的点的时间。jit,Dij假设 0-1 变量 表示第 天是否选择从第 个位置到第 个位置去旅游或住宿，kjix, k即 个 位 置 去 旅 游 或 住 宿个 位 置 到 第天 不 选 择 从 第第 个

15、位 置 去 旅 游 或 住 宿个 位 置 到 第天 选 择 从 第第 jikji01,旅游的天数为 ，景点数为 (算上出发点)，住宿点个数为 个，不是景点的住dmn宿点个数为 个，则建立目标函数：p行车总时间最短： (5.1.7)kjdipnjiNX,1,住宿费用最少： (5.1.8)kjimjiH,其中， 表示 中第 个位置的住宿费用，当该位置不是住宿点时将其设为kjH,Dk0，即 为 对 应 的 住 宿 费个 npnmpnnpm aa ,01)()(110 对于目标函数进行约束：(1)旅游路线起始点的约束：对于整条旅游路线来说起始点为 U，则第一天必从 U 出发到某个点，而最后一天必从某点

16、回到 U，即(5.1.9)11,mkX(5.1.10),3jj对于每天的旅游路线，除最后一天外，每天都必须有住宿的地方，即(5.1.11)12,11, diXpmnjjkji ，(2)旅游路线连续性的约束：对于每天来说，旅游路线都必须是连续的，也就是每个点的出入度是一样的，即(5.1.12)pmkdiXpmnjjkipmnjkji 2;,11,1,对于所有天来说，整个旅游路线必须是连续的，即(5.1.13)niXpnjjkipnjkji 1;2,1,1,(5.1.14)pkXdipmnjjidjmkji 2,1,(3)游览点的约束：对于游览点，旅行社设计路线时必须经过且次数只能是一次，即(5.

17、1.15)kdipmnjkji 21,(4)旅游时间的约束：一天旅行从 7:00 开始，18:00 结束，除去早中餐的时间一天的游览时间有 9.5 个小时，而一天的行程最迟可以在 20:00 的时候结束，则加上晚饭和回住宿地的时间不能超过 11.5 个小时，即(5.1.16)diTXNkjikjpmjki ,15.9*,1, (5.1.17)ikjinjkkji ,.,其中， 为景点游览时间矩阵，其元素排列顺序与 一一对应。T D5.1.4 蚁群算法和回溯思想求解模型由于路线的选择和住宿的选择之间相互关联，同时考虑两者的情况下，求解过程十分复杂且变量过多导致求解效率很低。考虑在游览时间固定的情

18、况下，实际中一般都先确定好游览路线，再来确定住宿的位置。另外，住宿点的选择对路线有很大的依赖关系，并且行程的时间主要受路线的影响，且本题中住宿费用变化较为平缓。因此，为了简化求解过程，本文通过先确定所有景点的游览顺序，再根据该顺序寻找最优的住宿点来近似求解。确定所有景点的游览顺序实质就是周游型旅游路线优化，根据 5.1.2 将模型转化为 mijjiNx1,2n.tsmxmiji1)(2ji1mijxmbjijbii ,1其中， ，为景点之间的邻接矩阵。 为各景点间):1,(mN ):,(D的顺序表示。由于问题中所用点数量数量不多，则本文采用基本蚁群算法来求解。其步骤如下：(1) 初始化各路径上

19、的信息量 ，且 ，设置信息启发式因子 ，)0(ij0)(ij期望启发式因子 ，信息素挥发系数 ，启发函数 和 。tij)(tkij(2) 将 q 个蚂蚁分布到 m 个景点中。(3) 每个蚂蚁 计算该时刻 下景点 到景点 的状态转移概率 ，kti tpkijelswialodjifttPalowedsisiskjtijk0)(*)()( 并以轮盘赌博的方式选择下一个景点，并前进。判断是否已遍历完所有景点，是则继续执行,否则跳到下一步。(4) 根据更新每条路径上的信息量。(5) 如果满足结束条件，即循环次数大于或等于最大迭代次数，算法结束否则，否则返回(2) 继续执行。根据以上步骤求得景点游览顺序

20、矩阵 S。接着根据该顺序寻找住宿点使住宿费和增加的行程时间最小。本文用回溯的思想来寻找住宿点，在寻找住宿点前应先将行程时间和住宿费用作归一化处理，观察到行程及游览的时间从 0 以0.5 的间隔到 6，而住宿费以 300 以 50 的间隔到 450，两者之间的数据个数相差很大，因此，先将住宿费补齐后再进行归一化处理，本文采用离差标准化法进行归一化，即 )min()ax(HHTT得到归一化后的数据，见表(5.1.1),(5.1.2)表 5.1.1 时间归一化对照表原 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6)()( )(*11tt tnmkijij ijijij归 0

21、 0.091 0.182 0.273 0.364 0.455 0.546 0.634 0.728 0.819 0.91 1表 5.1.2 住宿费归一化对照表原数据 300 350 400 450归一化后 0 0.1111 0.2222 0.3333数据归一化后，用回溯法寻找住宿点，其步骤如下：(1) 初始化行程时间 ；0t(2) 从 中按顺序取出景点 ，求 ，如果SiSD,1iSDiSiDTNt则执行下一步，否则继续步骤(2)。5.9t(3) 寻找景点 附近的整段行程为 11.5 范围内的可住宿点 ，如果1-i h找不到，则跳到步骤(5)。(4) 分别计算增加各个住宿点 后所增加的时间 ，比较

22、 与jhjd*jhjH，如果前者大于后者，则选择 为住宿点，否则选择 为住宿点。所*mhHdmj有住宿点选好返回步骤(1) ，没有则跳到步骤(6) 。(5) 修改昨天的住宿点，选择在那天另外可住的点，如果没有则修改前天的住宿点并选择那天另外可住的点，以此类推找到点后，返回步骤(1)。(6) 根据选好的住宿点，各个住宿点所在的局部路径。根据以上的步骤最终求得最优的住宿解，从而解出了最优的旅游路线。5.1.5 各种旅游路线设计三日游一线路线设计针对本题中三日游一线路线设计过程如下：(1) 确定 ，EDCBAUD确定 05.05.101.1.2000N(2) 设置 ， ， ， ， 和 ，)(ij26

23、QijijNt1)(kkijLQt)(利用 matlab 编程(见附录)蚁群算法，求得 ，即3452DUBCEAU(3) 利用 matlab 编程回溯法，求得两个住宿点都为 。(4) 局部优化后，最终的旅游路线为 根据中相同的过程，求得各种需求的路线： 三日游二线路线设计最优路线为： UIHIJKU五日游路线设计最优路线为： UBCEWGVFDA 七日游路线设计最优路线为：UBKJIHIGVFCDECAU 5.2 舒适度要求的旅游路线规划根据题意，在总成本最短的同时还要考虑游客的舒适度，也就是一天中坐车时间和参观景区的时间要合理安排，即两者总时间不找过 10 小时，且在同一个景点旅游的时候不能

24、吃饭。因此，只要在 5.1 建立的模型中，将约束 4 修改为(5.2.1.)diTXNkjipmnjkkji ,10,1, 即可。因此，可以根据 5.1 所用的方法求得最后的路径。由于题中所给点数不多，本文为了方便，则在 5.1 求得的结果上进行对该条件的验证，对不满足的住宿点进行局部的修改最终取得结果。在确定每条路径后，根据在同一个景点旅游的时候不能吃饭的原则和实际情况指定了每条旅游路线的行程时间安排明细表(见附录 2)。5.3 长期预订客房分析5.3.1 长期预订房间问题描述假设旅行社针对不同线路预定不同住宿地房间数目为,当预定房间数目大于需要客房数目时，就不需要考虑增加新客房，当需要客房

25、数目大于预定房间数目，针对不同的时间段，需要考虑不同住宿地点酒店的优惠政策。为了节省旅行社住宿消费，应尽量考虑适合的房间预定数量，保证得到尽量多的优惠政策，然而不造成过高空房闲置。5.3.2 长期预订房间模型的描述题目假设宾馆对 30 个及以上标间的 7 天及以上连续预定客户市场价 6 折优惠，通过观察表 3 数据发现任意旅游线路日游客数分布基本大于 30 人，小于30 的概率不大于十分之一，故可以在正常的经营模式下认定旅行社预定客房数目大于 30 间。由于当前正值旅游旺季，酒店的优惠政策，以及旅游人数规模，正常经营模式旅行社会连续预定客房，且连续天数认为应当大于 7 天。把十个住宿地 B、C

26、 、D、E、G、H、I、K、U、V 、W 标记为 、 、1H2、 、 、 、 、 、 、 。其中的标准间市场价格为：3H45678910，其中 i=1,2,10。标记星期一，星期二到星期六，星期日为)(*Priice,(i=1,2,7)。针对不同时间段，各个旅店对新增加的客房优惠政策有wki别，新增加客户通过优惠政后旅行社实际给 支付的客房费用 为：i )(_PriAice(5.3.0.) elsHiceorwkAicei ii ， ，)(Pr 10,984,3217.0*)(_Pr假设预定的客房数目为 ，新增加客房数目为 ，实际游客人数需要的iN1iN客房数目为 ，实际旅行社需要给支付的总住宿费用为 ：i )(_iHPayActve(5.3.1.)iiii Hiceceayctive 2*)(_Pr6.0*)(r)(_求出路线可以知道选择哪些宾馆作为入住宾馆，我们假设四条线路确定好的线路入住宾馆集合为 人均平均费用:ijjHo,(5.3.2.)()_10ji ij oNumctvevpayAverg