浅谈旅游线路的优化设计.doc

旅游线路的优化设计摘要在差不多假设和符号讲明的基础上,建立了最优线路Rm与时刻T、花费S的函数F(S,T).关于第一问本文以十一个都市的经纬度坐标算得都市之间的距离,构造成完备图,进而用TSP算法,,运用0—1变量来操纵住宿等不确定因素,,添加约束条件S≤2000元T≤120小时,使用排除法得到最终结果:第三问的最少费用为1998元,巡游都市8个,第四问的最短时刻为107小时,巡游都市7个;第五小问是第三和第四小问的有机整合,同时考虑时刻和花费的约束,联系实际情况,得到最终结果为;最少费用1848元,对应的最短时刻为103小时,巡游都市为5个。最后,给出模型的优点和缺点的讲明。关键字:完备图蚁群算法0—1规划约束条件一、问题重述江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后动身,到全国一些闻名景点旅游,最后回到徐州。由于跟团旅游会受到若干限制,他(她)打算自己作为背包客出游。他预选了十个省市旅游景点,如表所示:现假设:省市景点名称在景点的最短停留时刻江苏常州市恐龙园4小时山东青岛市崂山风景区6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时(A)城际交通出行能够乘火车(含高铁)、长途汽车或飞机(不同意包车或包机),同时车票或机票可预订到。(B)市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C)旅游费用以网上公布为准,具体包括交通费、住宿费、景点门票(第一门票)。晚上20:00至次日早晨7:00之间,假如在某地停留超过6小时,必须住宿,住宿费用不超过200元/天。吃饭等其它费用60元/天。(D)假设景点的开放时刻为8:00至18:00。依照以上要求,针对如下的几种情况,为该旅游爱好者设计详细的行程表,该行程表应包括具体的交通信息(车次、航班号、起止时刻、票价等)、宾馆地点和名称,门票费用,在景点的停留时刻等信息。(1)假如时刻不限,游客将十个景点全巡游完,至少需要多少旅游费用?请建立相关数学模型并设计旅游行程表。(2)假如旅游费用不限,游客将十个景点全巡游完,至少需要多少时刻?请建立相关数学模型并设计旅游行程表。(3)假如这位游客预备2000元旅游费用,想尽可能多巡游景点,请建立相关数学模型并设计旅游行程表。(4)假如这位游客只有5天的时刻,想尽可能多巡游景点,请建立相关数学模型并设计旅游行程表。(5)假如这位游客只有5天的时刻和2000元的旅游费用,想尽可能多巡游景点,请建立相关数学模型并设计旅游行程表。二、问题分析旅游最优路线问题已成为现今人们所感兴趣的话题之一。本题通过给定相关资料和数据,要求为旅游爱好者设计最优路线,建立具体优化模型,最后求解最优行程表。本题类似于旅行商问题(TSP问题),求解TSP问题的关键在于设计合适的优化算法【1】,要紧包括分支定界法、改良回路法、贪欲算法、MST算法、插入法,蚁群算法、遗传算法,在算法的选取上,应该讲求合适便捷的准则。基于本题的实际情况,能够按以下的求解过程实现:首先,建立以十一个都市为顶点的完全图。关于第一问,题目要求遍历所有都市使得话费最小,为了解题方便,我们能够选取都市之间的距离作为相应点与点之间的权重,最后通过合适的算法求解最优路线并设计出最优行程表;关于第二问,题目要求遍历所有都市使得时刻最小,通过改变第一问的权重(把距离改成完成这段距离的最短时刻)即可实现;然后,第三问和第四问分不是在第一问和第二问的基础上,通过添加约束条件,即费用和时刻的约束,即可求得最优线路,进而设计最优行程表;最后,第五问是建立在第三和第四小问基础上的有机组合,实现的方法是:在第三问所求得的结果的基础上,把第四问的约束条件添加到里面去,最后解得最优线路并设计最有行程表。三、模型假设1、不考虑班车和航班的推迟或取消,忽略天气阻碍或不可预测的事故;2、把经纬度看成是平面坐标的两簇相互垂直的平行线;3、旅馆处于非满客状态,即总可预订到房间;4、在时刻的认识上,把当天早上八点到次日的早上八点定义为一天;5、不考虑实际生活中出现的堵车等车等不可知现象。四、符号讲明都市i与都市j的图上距离旅游总费用第i个都市到第j个都市的交通费第i个都市到第j个都市是否需要通车第个都市到第个都市的时刻表示最优线路五、模型建立依照以上假设,把最优线路问题看成是时刻和花费的函数,而时刻和花费又是相互联系的,通过建立以下(0—1)变量,构造模型的目标函数、旅游费用函数。六、