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

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

2、 01 规划来建立 模型。本题模型以规划为基础，以蚁群算法求解。基于此，本文将该题定义为 旅游企业对旅游者旅游活动内容的时间和时空安排。 针对问题 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、的分析;本 文是一种既考虑旅行社线路问题又考虑的旅游景区线路问题的微观层面的。本 文是一种在既定约束条件下实现最优目标的规范性分析;本文是一种既考虑管理 者的要求又结合数学模型的定性分析与定量分析相结合的分析。就旅游者而言, 对旅游线路的期望是最大化地满足其消费需要并使成本最小、日程安排最方便; 对旅行社来说,他们则希望在满足旅游者需求的前提下,降低成本、提高效益,并 可面对突发事件及时调整线路;旅游景区在规划设计时就要考虑景区内线路空间 布局的合理性、科学性,在管理中也要考虑如何合理分流、控制游客数量的问题。 显然,不管从哪个角度来说,旅游线路问题都是十分重要并值得深入研究的问题。 本文拟解

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

7、的旅游景点安排提出建议。 (5)分析上述最优旅行线路的设计方法是否可以推广到 15 天以上行程的自 助游行线路快速计算。 二、问题的分析 2.1 问题一 本题要求设计三日游一线、三日游二线、五日游三线及七日游的路线和住 宿点，使得旅行社住宿行车和人工总成本尽可能节省。根据题目建立成本最低 的旅游路线即是在满足旅游要求的情况下，使旅游的路线最短，住宿费用最少， 综合实际中旅游路线设计情况，旅行社带游客旅游完全部景点后要回到出发地 U 且游览的地点不重复，因此可以看作是更多约束的周游型旅游路线优化 (TSP 问题) ，用多目标 0-1 规划来建立模型。 2.2 问题二 本题要求考虑游客的适度要求：

8、一天坐车时间和参观景区的时间要合理安 排，两者总和尽可能不要超过 10 个小时。针对上述问题考虑原则上一天行程 20:00 之前结束，景点接待游客时间每天早上 6:30 到下午 18:30。结合模型一考 虑。综合实际中旅游路线设计，因此可以看作是更多约束的周游型旅游路线优 化(TSP 问题)，用多目标 0-1 规划来建立模型。 2.3 问题三 假设旅行社针对不同线路预定不同住宿地房间数 ，)10.2,;4,31(jiRj 当预定房间数目大于需要客房数目时，就不需要考虑增加新客房，当需要客房 数目大于预定房间数目，针对不同的时间段，需要考虑不同住宿地点酒店的优 惠政策。为了节省旅行社住宿消费，应

9、尽量考虑适合的房间预定数量，保证得 到尽量多的优惠政策，然而不造成过高空房闲置。 2.4 问题四 本题要求考虑首先不同日期宾馆的住宿费用变化，而问题一中考虑到的住 宿价格是不变的。针对此情况我们考虑住宿成本以每天人均住宿费用描述。从 而可以根据问题一所建立的模型求解出发的旅游团队的最优路线是否相同。在 考虑周五出发客数比平时增加 20%的情况下，通过观察可以求出三日游两条路 线的最优住宿点人均住宿费用，如果人均费用在增加游客数 20%的时候并没有 大幅度增加，可认为旅行路线住宿点不需要调整。且对预订房间的数量不需要 增加。在研究三日游一线和三日游二线的景点划分的合理性上，本文通过比较 旅游景点

10、游览时间与坐车行程时间的比较，以及住宿费用的比较提出尽可能选 择景区游览时间大于坐车时间，住宿宾馆应尽量选择价格合理的标准间旅馆。 三、问题基本假设 (1)假设出行旅游时天气均是良好； (2)假设单一景点逗留型旅游，对本次旅行路线的设定没有影响； (3)假设每一位旅客都服从导游及旅行社的安排，不擅自停留耽误行程； (4)假设如五一、十一黄金周不会出现超大的旅客流量。不会影响交通； (5)假设每个景点只游览一次，当考虑住宿时，该地点可重复经过。 (6)假设旅行社带游客旅游完全部景点后要回到出发地 U。 (7)假设中晚餐不再车上吃，且晚餐在一天的旅行结束后吃。 (8)假设旅游人数都住在一个住宿点

11、(9)假设每次出游的人数随机且相互独立 四、符号说明ijx 表示各边对应的决策变量ijw 表示各边对应的长度 表示节点数量jit, 表示 D 中第 i 个位置上的点到第 j 个位 置上的点的时间kjix, 表示第 i 天是否选择从第个位置 到 第 k 个位置参观旅游或住宿jH 表示 D 中第 k 位置的住宿费用 信息启发式因子 期望启发式因子 信息素挥发系数iHce*Pr 表示标准间市场价1iN 客房数目 Ni 新增客房数目 五、模型假设及求解 根据题目建立成本最低的旅游路线即是在满足旅游要求的情况下，使旅游 的路线最短，住宿费用最少，综合实际中旅游路线设计情况，旅行社带游客旅 游完全部景点后

12、要回到出发地 U 且游览的地点不重复，因此可以看作是更多约 束的周游型旅游路线优化(TSP 问题)，用多目标 0-1 规划来建立模型。 5.1.1 0-1 规划基本模型 当整数规划问题中的决策变量 仅限于 0 或 1 两个数值，则该问题称为 0-1ix 整数规划，简称 0-1 规划，其一般模型为 (5.1.1) .),21(0,.,ma(in)11njxmibtsczjjijj 或 ， 5.1.2 周游型旅游路线优化模型 周游型旅游路线问题是由出发地出发,途中刚好不重复的遍游所有的景点,最 后回到出发地,形成一个闭合的环型路线的问题。该类问题至今也没有完美解决， 是个 NPC 类问题，可由 T

13、SP 问题建模，模型如下： 目标函数： (5.1.2) aijijiwx1)(2mn 约束条件 1：所有决策变量 为二分变量，即ij 10或ijx 约束条件 2：总边数 (5.1.3)axaiji1)( 约束条件 3：横行和 (5.1.4)2ji 约束条件 4：纵列和 (5.1.4)1 aijx 约束条件 5：横对称 (5.1.5) );(11abjijmabiijb xCxR 其中， 表示各边对应的决策变量， 表示各边对应的长度， 为表示节点的ijxijwa 数量。 5.1.3 0-1 规划成本最小的旅游路线优化模型 根据上一节 TSP 问题模型的设计原理，结合本题的要求建立模型。根据题 意

14、旅游路线设计中要考虑住宿的问题，对于住宿点不能区分是经过该点还是住 在该点，因此为了更方便建模和求解将住宿点用两个符号分别表示，其一表示 住宿点，其二表示经过该点，例如点 B，在该地既可以游览又可以住宿，则将 B 表示为游览点，而 B来表示住宿点，而两点之间的距离则为 0。为了更好的 表示各个地点，本文将游览点和住宿点统一放到数组 中，用 表示相Dindex 应的点，其中 表示为D 个 住 宿 点的 点个 是 住 宿 点 却 不 是 景 点个 景 点 名 称名 称名 称名 称名 称名 称 pm pmpm111 则可以将图转换为以 中各点的排序下的邻接矩阵 ，N (5.1.6) 002,1, ,

15、2,212,1 pnmpn pnmtt tttN 其中， 表示 中第 个位置上的点到第 个位置上的点的时间。jit,Dij 假设 0-1 变量 表示第 天是否选择从第 个位置到第 个位置去旅游或住宿，kjix, k 即 个 位 置 去 旅 游 或 住 宿个 位 置 到 第天 不 选 择 从 第第 个 位 置 去 旅 游 或 住 宿个 位 置 到 第天 选 择 从 第第 jikji01, 旅游的天数为 ，景点数为 (算上出发点)，住宿点个数为 个，不是景点的住dmn 宿点个数为 个，则建立目标函数：p 行车总时间最短： (5.1.7)kj dipnjiNX,1, 住宿费用最少： (5.1.8)k

16、ji mjiH, 其中， 表示 中第 个位置的住宿费用，当该位置不是住宿点时将其设为kjH,Dk 0，即 为 对 应 的 住 宿 费个 npnmpnnpm aa ,01)()(110 对于目标函数进行约束： (1)旅游路线起始点的约束： 对于整条旅游路线来说起始点为 U，则第一天必从 U 出发到某个点，而 最后一天必从某点回到 U，即 (5.1.9)11,mkX (5.1.10),3jj 对于每天的旅游路线，除最后一天外，每天都必须有住宿的地方，即 (5.1.11)12,11, diXpmnjjkji ， (2)旅游路线连续性的约束： 对于每天来说，旅游路线都必须是连续的，也就是每个点的出入度

17、是一 样的，即 (5.1.12)pmkdiXpmnjjkipmnjkji 2;,11,1, 对于所有天来说，整个旅游路线必须是连续的，即 (5.1.13)niXpnjjkipnjkji 1;2,1,1, (5.1.14)pkXdipmnjjidjmkji 2,1, (3)游览点的约束：对于游览点，旅行社设计路线时必须经过且次数只能是一次， 即 (5.1.15)kdipmnjkji 21, (4)旅游时间的约束：一天旅行从 7:00 开始，18:00 结束，除去早中餐的时间一 天的游览时间有 9.5 个小时，而一天的行程最迟可以在 20:00 的时候结束，则加 上晚饭和回住宿地的时间不能超过 1

18、1.5 个小时，即 (5.1.16)diTXNkjikjpmjki ,15.9*,1, (5.1.17)ikjinjkkji ,., 其中， 为景点游览时间矩阵，其元素排列顺序与 一一对应。T D 5.1.4 蚁群算法和回溯思想求解模型 由于路线的选择和住宿的选择之间相互关联，同时考虑两者的情况下，求 解过程十分复杂且变量过多导致求解效率很低。考虑在游览时间固定的情况下， 实际中一般都先确定好游览路线，再来确定住宿的位置。另外，住宿点的选择 对路线有很大的依赖关系，并且行程的时间主要受路线的影响，且本题中住宿 费用变化较为平缓。因此，为了简化求解过程，本文通过先确定所有景点的游 览顺序，再根据

19、该顺序寻找最优的住宿点来近似求解。 确定所有景点的游览顺序实质就是周游型旅游路线优化，根据 5.1.2 将模型 转化为 mijjiNx1,2n .tsmxmiji1)(2ji1mijx mbjijbii ,1 其中， ，为景点之间的邻接矩阵。 为各景点间):1,(mN ):,(D 的顺序表示。 由于问题中所用点数量数量不多，则本文采用基本蚁群算法来求解。其步骤如 下： (1) 初始化各路径上的信息量 ，且 ，设置信息启发式因子 ，)0(ij0)(ij 期望启发式因子 ，信息素挥发系数 ，启发函数 和 。tij)(tkij (2) 将 q 个蚂蚁分布到 m 个景点中。 (3) 每个蚂蚁 计算该时

20、刻 下景点 到景点 的状态转移概率 ，kti tpkij elswialodjifttPalowedsisiskjtijk0)(*)()( 并以轮盘赌博的方式选择下一个景点，并前进。判断是否已遍历完所有景点， 是则继续执行,否则跳到下一步。 (4) 根据更新每条路径上的信息量。 (5) 如果满足结束条件，即循环次数大于或等于最大迭代次数，算法结束否 则，否则返回(2) 继续执行。 根据以上步骤求得景点游览顺序矩阵 S。接着根据该顺序寻找住宿点使住 宿费和增加的行程时间最小。本文用回溯的思想来寻找住宿点，在寻找住宿点 前应先将行程时间和住宿费用作归一化处理，观察到行程及游览的时间从 0 以 0.

21、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 0.091 0.182 0.273 0.364 0.455 0.546 0.634 0.728 0.819 0.91 1 表 5.1.2 住宿费归一化对照表 原数据

22、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) 分别计算增加各个住宿点 后所增加的时间 ，比较 与jhjd*jhjH ，如果前者大于后者，则选择 为住宿点，否则选择 为住宿点。所*mhHdmj 有住宿点选好返回步骤(1) ，没有则跳到步骤(6

23、) 。 (5) 修改昨天的住宿点，选择在那天另外可住的点，如果没有则修改前天的 住宿点并选择那天另外可住的点，以此类推找到点后，返回步骤(1)。 (6) 根据选好的住宿点，各个住宿点所在的局部路径。 根据以上的步骤最终求得最优的住宿解，从而解出了最优的旅游路线。 5.1.5 各种旅游路线设计 三日游一线路线设计 针对本题中三日游一线路线设计过程如下： (1) 确定 ，EDCBAUD 确定 0505.101.1.2000N (2) 设置 ， ， ， ， 和 ，)(ij26QijijNt1)(kkijLQt)( 利用 matlab 编程(见附录)蚁群算法，求得 ，即3452DUBCEAU (3)

24、利用 matlab 编程回溯法，求得两个住宿点都为 。 (4) 局部优化后，最终的旅游路线为 根据中相同的过程，求得各种需求的路线： 三日游二线路线设计 最优路线为： UIHIJKU 五日游路线设计 最优路线为： UBCEWGVFDA 七日游路线设计 最优路线为： UBKJIHIGVFCDECAU 5.2 舒适度要求的旅游路线规划 根据题意，在总成本最短的同时还要考虑游客的舒适度，也就是一天中坐 车时间和参观景区的时间要合理安排，即两者总时间不找过 10 小时，且在同一 个景点旅游的时候不能吃饭。因此，只要在 5.1 建立的模型中，将约束 4 修改 为 (5.2.1.)diTXNkjipmnj

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

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

27、、 、 、 、 、 、 、 。其中的标准间市场价格为：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.

28、3.1.)iiii Hiceceayctive 2*)(_Pr6.0*)(r)(_ 求出路线可以知道选择哪些宾馆作为入住宾馆，我们假设四条线路确定好的线 路入住宾馆集合为 人均平均费用:ijjHo, (5.3.2.)()_10ji ij oNumctvevpayAverg 其中 为该旅游线路的住宿天数。)(jHoNum 5.3.3 对线路一的日游客近似处理 由题目表 3 三日游一线数据得出日游客数密度函数，可以得知在每一日游 客数区间概率，抽取每一子区间中间值作为日游客数，以简化计算，观测在表 一各日游客数下长期预定房间数对人均住宿费的影响。 (5.3.3.) 150302. 2981.03.

29、08978.62)(xNxxxf 表 5.3.1 日游客数统计信息 日游客 数 35 75 85 95 105 115 125 135 概率 0.02 0.08 0.1 0.3 0.3 0.1 0.08 0.02 前两问求出来线路一最优的住宿地点都在 C 点，游客住宿时间为 2 天，需要考 虑这一批游客可能在面对新增游客优惠政策时，可能有三种情形，两天都能享 受 7 折优惠，两天都不能享受 7 折优惠，一天享受 7 折优惠另外 一天不能，三 种情形发生的概率分别为 。23， 5.3.4 曲线绘制并确定长期预定房间数量 通过表一数据和不同优惠情形下，实际情况下，旅行社会至少预定 30 间客 房，

30、我们用值表一中日游客数作为预定房间数量的指标，并求出各类情形下人 均住宿费用。 20 40 60 80 100 120 140460 480 500 520 540 560 580 600 620 一一一一一一 一一 一一 一一一 图 5.3.1 线路一预定房间数量与人均住宿费用的关系 通过参考对线路一的分析，其余四条线路采用同样的模型处理，只是在旅 游天数和选择最优宾馆位置会有所不同，使得游客在新增房间享受的优惠政策 不同，同样我们可以绘制出各线路的人均住宿费曲线图。 0 20 40 60 80 100 120 140400 500 600 700 800 900 1000 1100 120

31、0 1300 一一一一一一 一一 一一 一一一 一一一一一一 图 5.3.2 其余三条线路预定房间数量与人均住宿费用的关系 通过观测两个图，我们可以发现在小方框里面的曲线波动幅度较小，故可 以在此认为旅行社在这个范围内预定客房都是相对较为合理的，四条路线较优 的预定房间范围分别是：。我们知道每个区间，都有一个小幅度上升区间，虽 然幅度不是很大值，我们需要从旅行社角度和统计学角度出发，希望尽取值靠 近预定期望值，所以我们取区间右侧值作为最优的预定房间数量。所以我们可 以得到各个路线的预定房间数量。 表 5.3.2 各线路最优住宿地点及住宿点长期预定房间数量 住宿地 C I K V 线路一 98*

32、2 0 0 0 线路二 0 68*2 0 0 线路三 90*2 0 0 90*2 线路四 57 57 57 57 5.4 旅游路线行程安排的优化方案 5.4.1 不同日期出发的旅游团队最优路线 根据题意旅游从不同日期出发，可能对旅行社的住宿成本产生影响。当旅 行社确定了预订房数后，当旅游的人数超过预订房数则增加的房费随着时间和 住宿点不同价格不同。因此，不同于问题一二中住宿成本只考虑了单一的住宿 费，本题中每个住宿点的住宿费随着人数和日期不同会产生变化。由于每条线 每次出游的人数不定，仅服从表 3-6 中的概率分布，为了能很好的描述选择每 个点后的住宿成本，本文用以确定好住宿点以及预订房数后的

33、人均住房费来描 述住房成本。当住房成本确定好后，按照问题一建立的模型来求解即可。 观察住宿点的优惠条件发现只有 U、V、W 在周五到周日的时候有优惠， 因此只要考虑这三点旁边的住宿的点所增加的行程和住宿成本即可。为了简化 求解的过程，本文只考虑这三点旁边的住宿的点的情况，以三日游一线的旅游 路线判断为例。 确定好住宿点和预订房数后，人均住房费即可算出。考虑到 W 住宿点每天 都有对于新增房间每天都有优惠，因此将其考虑进来，而 B、E 两个住宿点与 C 相同，在周五、周六及周日没有优惠，且在问题一二中住宿费不变的情况下 就以 C 为住宿点，因此在该题中只考虑 C 住宿点和 W 住宿点。住宿点的预

34、订 房数以问题三得出的结果为准。 (1) 一直选择 C 点为住宿点，则每天预订的房数 98*2，人均住宿费用计算如下： 周一到周四每天的费用为 (5.4.1) 2986.0352986.0352987)(4-1 xxF 由表 3 得， 的概率为 0.44， 时 每增加一的概率为 ， 为xP 的05 则周一到周四每天的费用为 (5.4.2)ii xFP105414 周五到周日每天的费用为 (5.4.2) 2986.0352986.03298)(7-5 xxF 则周五到周日每天的费用为 (5.4.3)iiFP1577 最后根据式（）用 matlab(见附录)求得该情况下每天的人均住宿费用为 223

35、.6 元。73451每 天 (2) 周五周六周日选择 W 为住宿点，则 C 没有连续订房，没有优惠可言则该种 情况下每天的人均住宿费用为 320 元。 320.035每 天F (3) 周五周六周日选择 W 为住宿点，C 点在周一到周四每天预订房数为 98*2， 其他时间为 30，与(1)中的方法同理，得出该种情况下每天的人均住宿费用 为 262.72 元 (4) 周五周六周日选择 W 为住宿点，周五周六周日为 98*2，其他时间为 30，同 理得每天的人均住宿费用为 280.6 元。 (5) 周五周六周日选择 W 为住宿点，周六周日为 98*2，其他时间为 30，C 点在 周一到周四预订房数为

36、 98*2，其他时间为 30，同理得每天的人均住宿费用 为 269.98 元。 (6) 一直选择 W 为住宿点，则预订的房数为 98*2，同理得每天的人均住宿费用 为 293.1 元。 由以上 6 中情况可以看出，后 5 种的人均住宿费用均高于(1)，则选择 C 处为住 宿点，且(1)是不考虑日期的情况下得出的最优住宿点，因此对于三日游一线来 说，不同日期出发最优的路线是相同的。如果后 5 种有高于费用(1)的，则根据 回溯法的第(4)步来决定是否需要修改住宿点。 与上述的过程类似，判断其他三条路线的结果如下： 对于三日游二线，五日游，七日游不同日期出发最优的路线均相同。 5.4.2 调整旅行

37、路线和客房预定数 当周五出发的三日游人数增加 20%时，可以求出三日游的两条线路最优住 宿点人均住宿费用，如果人均费用在增加游客数量 20%的时候并没有大幅度增 加，可认为旅游线路(住宿点)可能不需要调整，而且对预定房间数量不需要增 加。 游客数量增加情形下三日游线路一的人均住宿费用为： =471.3%)201(*)6.0*798()1pE 表示线路一的期望游客数量。在题目三中求得的人均住宿费用为 469.8，)1(pE 两者之间相差很小，故可认为不需要更改路线和预定住宿房间数量。 游客数量增加情形下三日游线路二的人均住宿费用为： =473.3)201(*)6.0*786()2(pE 表示线路

38、二的期望游客数量。在题目三中求得的人均住宿费用为 446.4，)2(pE 两者之间相差 26.9，对于游客基数比较的旅行社来说，是一个比较大的差价， 故可认为不需要更改路线和预定住宿房间数量。 通过计算得到不同日期下，在问题一二求出来的最优住宿地，人均住宿费用。 表 5.4.1 不同日期出发的旅行团人均住宿费用 星期一 星期二 星期三 星期四 星期五 星期六 星期天 线路一 469.8 469.8 469.8 475.9 489.0 489.0 495.9 线路二 446.4 446.4 446.4 456.1 472.0 472.0 486.1 线路三 818.1 818.1 818.1 8

39、38.6 838.6 855.1 855.1 线路四 835.5 835.5 835.5 867.5 867.5 910 910 绘制给路线最优住宿地人均住宿费用曲线： 图 5.4.1 绘制给路线最优住宿地人均住宿费用曲线 观察得到从星期五到周末人均住宿费用呈增长趋势。 5.4.3 对当前旅行社提出建议 三日游一线最优路线安排是： 由题意条件可知游览时间设为UBCECDAU 为17个小时，其中行程中坐车时间设为 为8个小时。其中 =2.1。1游T 1行T1Q行游T 由于住宿选择C点住宿其宾馆标准间的房价为350元。 三日游二线景点最优路线安排： 由题UIHIJK 意条件可知游览时间设为 为13

40、个小时，其中行程中坐车时间设为 为个2游T 2行 10.5小时。其中 =1.2。由于住宿选择I点住宿其宾馆标准间的房价为35012Q行 游 元。通过比较可知 且在三线一日游景点最优路线安排游览时间上 2 1游T ,在坐车行程时间上 。由于住宿点C和I上，景区房间宾馆标准间房2游T1行T行 价是一样的。即建议当前所有旅行路线的旅游景点安排上旅行时间应尽量大于 坐车行程时间，且通过比较发现在旅行住宿上应尽量考虑住宿便宜的标准间。 5.5 自助游线路线快速计算 六、模型的优缺点改进及误差分析 6.1 模型的优点 在第一题中，首先为了简化问题。综合实际中旅游路线的考虑，旅行社带 游客完全部景点后均要回

41、到出发地 U 且游览点不重复，因此可以看做是更多约 束的周游型旅游路线优化(TSP 问题)，用多目标 0-1 规划来建立模型。通过蚁群 算法和回溯思想求解模型，既取得了规划模型的优点，即目标函数与约束条件 的意义都十分清晰，从而使得每一个模型基本上都得到最优解。很快设计求得 三日游一线、三日游二线、五日游及七日游的旅行路线和住宿地点，使旅行社 住宿、行车和人工总成本尽可能节省。 在第二题中，我们结合第一题中的所建立的模型。参照一天中坐车时间和 参观景区的时间合理安排，且两者总和尽可能不要超过 10 个小时。求出时间安 排明细表见附录。 在第三题中，我们建立了动态模型，消除了一定的主观性。使确定

42、各住宿 点长期预订房间的数量。 在第四题中，我们创建动态模型在考虑的不同日期出发的旅游团的最优路 线是不相同的。解决了如果周五出发的三日游游客数比平时增加 20%，考虑调 整旅游路线的和长期客房预定数。研究了三日游一线和三日游二线景点的划分 的合理性，对当前的旅游景点提出游览时间必须尽量大于坐车行程时间且住宿 的费用尽量要合理的建议。 6.2 模型的不足 第一问中的模型均建立在速度、单位行程的费用等都为恒定的基础假设之 上，而实际上，对于不同的道路，时速以及费用都会略有波动，如果在模型中 能加入一些随机因素，应该可以更接近现实生活。 第二问中模型处理复杂问题的求解上，基本都采用了遗传算法。但是

43、，由 于遗传算法的进化是基于一定的概率，所以单纯的遗传算法有时并不能保证求 得最优解，或者虽然能求得最优解却要耗费相当多的时间，而这与我们的初衷 是相违背的。如果能将遗传算法与模拟退火算法、局部搜索等相结合，将会取 得更好的效果。 第三问中仅考虑了错开景点旅游高峰，即仅从理性的角度分析策划了旅游 线路，但没有考虑游客对各景点的偏好程度，即未加入感性的一些元素，而这 些对于现实问题还是很有影响的，因此，如果将游客的一些特定需要添加到模 型的约束中，将会更符合实际。 第四问中没有考虑到节省车辆、油耗及工人费用。没有考虑不同旅行路线 的游客在旅游前期合并出行的优化方案。没有比较不同日期出发的旅游团人

44、均 住宿费用以及游客构成及人数变化对人均住宿产生的影响。 七、参考文献 1Randall,A(1994).ADiffieultywiththeTraveleostMethod.LandEeonomies.7088-9. 2 楚义芳.关于旅游线路设计的初步研究,旅游学刊.1992 年第 2 期,11 页. 3 迪米特里斯.伯特西马斯著.数据、模型与决策一管理科学基础,中信出版社, 2002 年 5 月第 1 版. 4 关发兰.区域旅游系统网络结构分析与网络优化设计一以四川省为例,庞规荃 主编,旅游开发与旅游地理,旅游教育出版社,1992 年 5 月第一版,50 页. 5 杨林泉、郭山. 基于模糊

45、线性规划测度模型的旅游环境承载力实证分析J . 云南地理环境研究,2003 年第 3 期. 6 李士勇，蚁群算法及其应用，哈尔滨：哈尔滨工业大学出版社，2004 年. 附录 图 1 三日游一线景点及路线安排 图 2 三日游二线景点及路线安排 图 3 五日游景点及路线安排 图 4 七日游景点及路线安排 三日游一线景点及路线： 注： 即住宿安排UBCECDAU C 行程时间安排表： 表 1 第一天路线及行程安排： DA 第一天路线： 选择 处住宿A 7:00-7:30 早餐 7:40-9:40 由 U 出发坐车到 A 地 9:5011:50 参观 A 景点 12:0013:00 午餐时间 13:3

46、0-14:30 由 A 出发坐车到 D 景点 14:50-16:50 参观 D 景点 17:00-18：00 由 D 出发坐车到 C 地 18:2019:20 晚餐 表 2 第二天路线及行程安排： E 第二天路线： 选择 处住宿 CE 7:00-7:30 早餐 7:40-8:10 由 C 出发到景点 E 8:30-11:30 参观景点 E 12:00-13:00 午餐时间 13:30-16:30 继续参观景点 E 17:00-18：00 由 E 出发坐车到 C 地 18:2019:20 晚餐 表 3 第三天路线： UB 第三天路线： UBC 7:00-7:30 早餐 8:00-11:00 参观

47、 C 景点 11:20-12:20 午餐时间 12:30-13:30 由 C 出发到景点 B 13:40-15:40 参观景点 B 16:00-18:00 由 B 回到 U 三日游二线景点路线安排 UIHIJKU 行程及时间安排： 表 4 第一天路线： IJ 第一天路线： 住宿选择IJ 7:00-7:30 早餐 7:40-10:10 由 U 出发到达 K 景点 10:20-12:20 参观 K 景点 12:30-13:30 午餐时间 13:40-15:10 由 K 出发到达 J 景点 15:20-17:20 参观景点 J 17:30-18:00 由 J 到 I 18:20-19:20 晚餐时间

48、 表 5 第二天路线安排： H 第二天路线安排： 住宿选择 I IHI 7:00-7:30 早餐 7:40-8:40 由 I 出发到达 H 景点 8:50-11:50 参观 H 景点 12:00-13:00 午餐时间 13:30-16:30 参观 H 景点 16:40-17:40 由 H 景点到 I 18:00-19:00 晚餐时间 表 6 第三天路线安排： U 第三天路线安排： UI 7:00-7:30 早餐 8:00-11:00 参观 I 景点 11:20-12:20 午餐时间 13:00-17:00 由 I 回到 U 五日游景点及路线 UBCEWGVFDAU 行程时间安排： 表 7 第一天路线安排： VDAU 第一天路线安排： 选择 住宿VDAU 7:00-7:30 早餐 7:40-