旅行社旅行路线安排问题

旅行社旅行路线安排问题

摘要

本文从旅游系统理论、行为地理学和旅游经济学的角度对旅行社旅游线路定制问题进行了研究, 提出了旅行社旅游线路定制决策模型; 结合景点及游览时间表、景区公路交通图、景区宾馆标准间房价及旅游游客的部分表, 把景点定制下旅行社旅游行程线路问题转化为一个游憩中心的选址问题, 建立模型进行了研究。

针对问题1：根据题目建立成本最低的旅游路线即是在满足旅游要求的情况下，使旅游的路线最短，住宿费用最少，综合实际中旅游路线设计情况，旅行社带游客旅游完全部景点后要回到出发地U且游览的地点不重复，因此可以看作是更多约束的周游型旅游路线优化(TSP问题)，用多目标0—1规划来建立模型。本题模型以规划为基础，以蚁群算法求解。基于此，本文将该题定义为旅游企业对旅游者旅游活动内容的时间和时空安排。

针对问题2：由问题一中所建立的模型，充分考虑到游客舒适度的要求，即：一天中坐车时间和参观景区的时间合理安排，两者总和尽可能不要超过10小时，跟所给的条件，早餐时间安排在7:00-7:30，午餐和晚餐时间各一个小时，且当前季节应该在18:00之前结束游览活动。因此同样可以看作TSP问题，用多目标0—1规划来建立模型。

针对问题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问题0—1规划

一、问题的重述

面对蓬勃发展的巨大市场,旅游企业推出了大量丰富多彩的旅游线路以满足旅游者的需求。为了设计更好的旅游线路,为了优化现有的线路设计,旅行社和旅游景区进行了大量的实践探索。本文试图在总结前人研究成果的基础上,把旅游线路问题的层次结构梳理清楚,并讨论运筹学和图论理论在旅游线路优化中的应用。

在分析了上述基本问题之后,本文应用运筹学和图论的理论分别讨论了旅行社线路优化问题和旅游景区线路优化问题。具体的,讨论了最短路问题、旅行商问题和排程问题在旅行社线路优化中的应用;讨论了最小支撑树问题、覆盖问题和最大流问题在旅游景区线路优化中的运用,并在附录中给出了详细的电子表格解法。总之,本文是一种应用运筹学、图论理论讨论旅游企业科学管理的分析;本文是一种既考虑旅行社线路问题又考虑的旅游景区线路问题的微观层面的。本文是一种在既定约束条件下实现最优目标的规范性分析;本文是一种既考虑管理者的要求又结合数学模型的定性分析与定量分析相结合的分析。就旅游者而言,对旅游线路的期望是最大化地满足其消费需要并使成本最小、日程安排最方便;对旅行社来说,他们则希望在满足旅游者需求的前提下,降低成本、提高效益,并可面

对突发事件及时调整线路;旅游景区在规划设计时就要考虑景区内线路空间布局的合理性、科学性,在管理中也要考虑如何合理分流、控制游客数量的问题。显然,不管从哪个角度来说,旅游线路问题都是十分重要并值得深入研究的问题。

本文拟解决以下问题：

(1)分别设计三日游一线、三日游二线、五日游及七日游的旅行和住宿点，使旅行社住宿、行车和人工总成本尽可能节省。

(2)考虑到游客的舒适度要求，即一天中坐车的时间和参观景区的时间总和不超过10个小时，针对此问题制定各条旅行路线的行程安排表。

(3)分析人均住宿费用关于长期预订客房数变化的波动情况，制定各住宿点长期预订的房间的数量。

(4)不同日期出发的旅游客数不同，考虑最优路线是否需要调整旅游线路和长期客房预订数。为了节省车辆、油耗及人工费用，讨论是否存在不同旅行线路的游客在旅行前期合并出行的优化方案。研究三日游一线和三日游二线的景点划分的合理性，对当前所有旅行线路的旅游景点安排提出建议。

(5)分析上述最优旅行线路的设计方法是否可以推广到15天以上行程的自助游行线路快速计算。

二、问题的分析

2.1问题一

本题要求设计三日游一线、三日游二线、五日游三线及七日游的路线和住宿点，使得旅行社住宿行车和人工总成本尽可能节省。根据题目建立成本最低的旅游路线即是在满足旅游要求的情况下，使旅游的路线最短，住宿费用最少，综合实际中旅游路线设计情况，旅行社带游客旅游完全部景点后要回到出发地U 且游览的地点不重复，因此可以看作是更多约束的周游型旅游路线优化(TSP 问题)，用多目标0-1规划来建立模型。

2.2 问题二

本题要求考虑游客的适度要求：一天坐车时间和参观景区的时间要合理安排，两者总和尽可能不要超过10个小时。针对上述问题考虑原则上一天行程20:00之前结束，景点接待游客时间每天早上6:30到下午18:30。结合模型一考虑。综合实际中旅游路线设计，因此可以看作是更多约束的周游型旅游路线优化(TSP 问题)，用多目标0-1规划来建立模型。

2.3问题三

假设旅行社针对不同线路预定不同住宿地房间数)10...2,1;4,3,2,1(==j i R ij ，当预定房间数目大于需要客房数目时，就不需要考虑增加新客房，当需要客房数目大于预定房间数目，针对不同的时间段，需要考虑不同住宿地点酒店的优惠政策。为了节省旅行社住宿消费，应尽量考虑适合的房间预定数量，保证得到尽量多的优惠政策，然而不造成过高空房闲置。

2.4问题四

本题要求考虑首先不同日期宾馆的住宿费用变化，而问题一中考虑到的住宿价格是不变的。针对此情况我们考虑住宿成本以每天人均住宿费用描述。从而可以根据问题一所建立的模型求解出发的旅游团队的最优路线是否相同。在考虑周五出发客数比平时增加20%的情况下，通过观察可以求出三日游两条路线的最优住宿点人均住宿费用，如果人均费用在增加游客数20%的时候并没有大幅度增

加，可认为旅行路线住宿点不需要调整。且对预订房间的数量不需要增加。在研究三日游一线和三日游二线的景点划分的合理性上，本文通过比较旅游景点游览时间与坐车行程时间的比较，以及住宿费用的比较提出尽可能选择景区游览时间大于坐车时间，住宿宾馆应尽量选择价格合理的标准间旅馆。

三、问题基本假设

(1)假设出行旅游时天气均是良好；

(2)假设单一景点逗留型旅游，对本次旅行路线的设定没有影响；

(3)假设每一位旅客都服从导游及旅行社的安排，不擅自停留耽误行程；

(4)假设如五一、十一黄金周不会出现超大的旅客流量。不会影响交通；

(5)假设每个景点只游览一次，当考虑住宿时，该地点可重复经过。

(6)假设旅行社带游客旅游完全部景点后要回到出发地U。

(7)假设中晚餐不再车上吃，且晚餐在一天的旅行结束后吃。

(8)假设旅游人数都住在一个住宿点

(9)假设每次出游的人数随机且相互独立

四、符号说明

五、模型假设及求解

根据题目建立成本最低的旅游路线即是在满足旅游要求的情况下，使旅游的路线最短，住宿费用最少，综合实际中旅游路线设计情况，旅行社带游客旅游完全部景点后要回到出发地U 且游览的地点不重复，因此可以看作是更多约束的周游型旅游路线优化(TSP 问题)，用多目标0-1规划来建立模型。

5.1.1 0-1规划基本模型

当整数规划问题中的决策变量i x 仅限于0或1两个数值，则该问题称为0-1整数规划，简称0-1规划，其一般模型为

?????===≥=≤=∑∑==.),2,1(10),2,1(),(..,

max(min)1

1n j x m i b x a t s x c z j

i n j j ij n

j j j 或，(5.1.1) 5.1.2 周游型旅游路线优化模型

周游型旅游路线问题是由出发地出发,途中刚好不重复的遍游所有的景点,最后回到出发地,形成一个闭合的环型路线的问题。该类问题至今也没有完美解决，是个NPC 类问题，可由TSP 问题建模，模型如下： 目标函数：∑∑==?a i a

j ij ij w x 11

)(21min((5.1.2) 约束条件1：所有决策变量ij x 为二分变量，即10或=ij x

约束条件2：总边数 a x a i a

j ij =∑∑==11

)(21(5.1.3) 约束条件3：横行和

21=∑=a j ij x (5.1.4) 约束条件4：纵列和 21=∑=a i ij

x

(5.1.4) 约束条件5：横对称 );(11∑∑+=+===

=a

b j ij m a b i ij b b b x C x R C R (5.1.5) 其中，ij x 表示各边对应的决策变量，ij w 表示各边对应的长度，a 为表示节点的数量。

5.1.3 0-1规划成本最小的旅游路线优化模型

根据上一节TSP 问题模型的设计原理，结合本题的要求建立模型。根据题意旅游路线设计中要考虑住宿的问题，对于住宿点不能区分是经过该点还是住在该点，因此为了更方便建模和求解将住宿点用两个符号分别表示，其一表示住宿点，其二表示经过该点，例如点B ，在该地既可以游览又可以住宿，则将B 表示为游览点，而B '来表示住宿点，而两点之间的距离则为0。为了更好的表示各个地点，本文将游览点和住宿点统一放到数组D 中，用[]index D 表示相应的点，其中D 表示为