最佳旅游路線設(shè)計(jì)論文

-.z.最正確旅游路線設(shè)計(jì)摘要本文主要研究的是如何選擇最正確線路的問題。對(duì)于線路的選擇，我們主要考慮旅行中的費(fèi)用及旅行時(shí)間。我們首先通過網(wǎng)絡(luò)查找得到各景點(diǎn)〔包括景區(qū)〕之間的距離，門票費(fèi)用以及最正確逗留時(shí)間，據(jù)此將景點(diǎn)圖簡(jiǎn)化成賦權(quán)無向圖。然后利用floyd算法得到每2個(gè)景點(diǎn)間的最短路徑。據(jù)此，根據(jù)題目要求分別建立0-1線性規(guī)劃模型。問題一給定了時(shí)間約束，要求花最少的錢游盡可能多的地方。據(jù)此，我們以花費(fèi)最少為目標(biāo)，以時(shí)間限制及線路要求為約束，建立0-1規(guī)劃模型，利用lingo軟件對(duì)模型求解。對(duì)結(jié)果進(jìn)展綜合分析，最后我們向王先生夫婦推薦景點(diǎn)數(shù)為16的路線：烏魯木齊-達(dá)坂城-哈密-庫(kù)爾勒-樓蘭-阿克-千佛洞-天鵝湖-伊犁-博樂-石河子-克拉瑪依-阿勒泰-昌吉-天山天池-烏魯木齊。平均每個(gè)景點(diǎn)花費(fèi)為73.4元，除了吃飯以外，這對(duì)夫婦總共花費(fèi)估計(jì)為4102元。問題二要提出2條路線游完所有景點(diǎn)，據(jù)此，我們首先將所有景點(diǎn)按南北疆分為2組。這兩條路線要求交通費(fèi)用最少，即總路程最少，我們以總行駛路程為目標(biāo)，以相應(yīng)的條件為約束，建立0-1線性規(guī)劃模型。利用lingo求解得到每組路線所需最短時(shí)間，并求得其均衡度。然后對(duì)其進(jìn)展調(diào)整，找到均衡度最好的一種分組。我們?yōu)橥跸壬驄D推薦的第一個(gè)月的路線為：烏魯木齊-昌吉-博樂-石河子-克拉瑪依-阿勒泰-額爾齊斯河-喀納斯湖-天山天池-哈密-吐魯番-達(dá)坂城-烏魯木齊，交通費(fèi)用為740元。第二個(gè)月的路線為烏魯木齊--庫(kù)爾勒--樓蘭--尼雅遺址--和田--喀什--阿克--千佛寺--伊犁--天鵝湖--烏魯木齊，交通費(fèi)用為820元。問題四中，由于參加每條路線的人數(shù)與該線路上效勞能力成正比，我們認(rèn)為每個(gè)景點(diǎn)只在一條線路上。據(jù)此，我們根據(jù)假期時(shí)間限制以及游遍所有景點(diǎn)所需時(shí)間最少，求得至少要提供4條旅游路線才能滿足題意。根據(jù)分析，我們發(fā)現(xiàn)無法找到這樣4條路線均滿足要求，因此，我們將所有景點(diǎn)分為5組，通過屢次求解調(diào)整，最終我們?yōu)槁眯猩缣峁┝?種路線。具體結(jié)果在正文中給出。問題三與問題二相似，我們根據(jù)各景點(diǎn)之間的最短路徑畫出以烏魯木齊為樹根的樹形圖，然后按分類原那么分為三組。將模型二中的目標(biāo)函數(shù)換為考察時(shí)間最小得到模型三，分別用lingo求解得到每組最正確路線及時(shí)間。求其均衡度，然后對(duì)其進(jìn)展調(diào)整。最后，我們對(duì)該考察團(tuán)設(shè)計(jì)了三條考察路線。路線一：烏魯木齊-博樂-伊犁-昌吉-天山天池-吐魯番-達(dá)坂城-烏魯木齊，考察時(shí)間為47天。路線二：烏魯木齊-石河子-克拉瑪依-天鵝湖-千佛洞-阿克-尼亞遺址-和田-喀什-烏魯木齊，考察時(shí)間為51天。路線三：烏魯木齊-喀納斯湖-阿勒泰-額爾齊斯河-庫(kù)爾勒-樓蘭-哈密-烏魯木齊，考察時(shí)間為48天。最后，本文對(duì)模型進(jìn)展了分析與評(píng)價(jià)。一、問題的重述王先生夫婦是華東某高校的年輕教師，打算暑假中到XX旅游。受文學(xué)作品的影響，天池、達(dá)坂城、吐魯番、樓蘭古城、伊犁都是他們十分向往的地方，XX的其他地方對(duì)他們也有很大的吸引力。1．請(qǐng)你們?yōu)樗麄冊(cè)O(shè)計(jì)適宜的旅游路線，使他們?cè)诮衲晔罴僖粋€(gè)月的時(shí)間里花最少的錢游盡可能多的地方，并估算除吃飯之外的費(fèi)用。2．如果他們打算今、明兩年暑假完成對(duì)XX的旅游，請(qǐng)你們?yōu)樗麄冊(cè)O(shè)計(jì)適宜的旅游路線，使在XX境的交通費(fèi)用盡量地節(jié)省。3．如果華東某高校的少數(shù)民族研究所組織對(duì)XX文化考察，考察分三組進(jìn)展，用于交通的時(shí)間和前兩種情況一樣，但考察時(shí)間是旅游觀光時(shí)間的四倍，請(qǐng)你們?yōu)樗麄冊(cè)O(shè)計(jì)適宜的考察路線，以便盡早完成考察任務(wù)。4．XX自治區(qū)旅游部門為迎接"五一旅游黃金周〞〔考慮到遠(yuǎn)途旅游，自治區(qū)游程延長(zhǎng)為十二天〕準(zhǔn)備為自治區(qū)外的游客組織多條旅游路線以分散游客，提高接待的質(zhì)量。在假設(shè)參加你們?cè)O(shè)計(jì)的各條路線的游客人數(shù)與整條路線的接待能力成比例的條件下，請(qǐng)你們?yōu)閄X自治區(qū)旅游部門設(shè)計(jì)適宜的、準(zhǔn)備向游客推介的全部旅游路線。下列圖是XX主要景點(diǎn)分布圖，各旅游點(diǎn)之間的路程、每個(gè)景點(diǎn)的最正確逗留時(shí)間等信息可以登陸XX旅游網(wǎng)對(duì)題。你也可以目做進(jìn)一步的完善。二、問題的分析分析題意可知，此題的目標(biāo)是尋找最正確旅游線路。便于分析，我們首先將景點(diǎn)進(jìn)展編號(hào)，把實(shí)際地圖簡(jiǎn)化為賦權(quán)無向圖，即轉(zhuǎn)化為圖論問題。再考慮旅行中的花費(fèi)，除吃飯和住宿外，主要考慮交通費(fèi)用和景點(diǎn)的門票費(fèi)。因此我們需收集各景點(diǎn)之間的路程、最正確逗留時(shí)間以及門票費(fèi)用。問題一要找出一條最正確旅游路線，使得夫婦在一個(gè)月的時(shí)間花最少的錢游盡可能多的地方，這是一個(gè)最正確旅行商問題。對(duì)此，首先運(yùn)用floyd算法求得各景點(diǎn)間的最短路徑，然后我們以平均每個(gè)景點(diǎn)的消費(fèi)額最低為目標(biāo)，以時(shí)間和景點(diǎn)以及線路要求為約束，建立一個(gè)0-1線性規(guī)劃模型。用lingo求解，便可得到最正確旅游路線以及其他各項(xiàng)信息。問題二實(shí)際上就是要求找到2條路線，均從同一頂點(diǎn)出發(fā)再回到此點(diǎn)。這兩條線路所包括的點(diǎn)不能重復(fù)且它們的并集應(yīng)是所有景點(diǎn)。分組中，應(yīng)盡量保證每組旅游時(shí)間控制在一個(gè)月且均衡。據(jù)此，我們可以將所有景點(diǎn)按南北疆分為兩類，然后進(jìn)展調(diào)整。選定景點(diǎn)后，同樣利用0-1線性規(guī)劃求解得到最正確路線及所需時(shí)間，分別計(jì)算幾種分組的時(shí)間均衡度，選取最好的一組即可。問題三是多旅行商問題。同問題二，我們依據(jù)考察隊(duì)的組數(shù)將所有景點(diǎn)分為3類，盡量使各組的考察時(shí)間相等。由問題一中得到的各景點(diǎn)間的最短路徑，畫出以烏魯木齊為起點(diǎn)的樹形圖，然后按照分類的原那么，將景點(diǎn)分為三類，再進(jìn)展調(diào)整即可。確定景點(diǎn)后，建立0-1線性規(guī)劃模型求解。問題四與問題三相似，我們首先利用問題一中的模型求得游玩所有景點(diǎn)所需最少時(shí)間，再根據(jù)五一黃金周時(shí)間限制，確定游玩路線至少應(yīng)分為幾條，才可以以分散游客。然后按時(shí)間均衡度和花費(fèi)均衡度都盡可能好的原那么將景點(diǎn)進(jìn)展分類，再按照問題二中的模型求解，即可得所需旅游路線。三、模型的假設(shè)假設(shè)一：王先生夫婦旅游期間，所有的景點(diǎn)均正常開放。假設(shè)二：每晚的住宿費(fèi)用為100元，大巴的車費(fèi)為0.15元/km。假設(shè)三：每天的旅游時(shí)間加上行車時(shí)間不超過10個(gè)小時(shí)。假設(shè)四：在行駛過程中，所有的道路路況一樣，汽車的速度保持在75km/h。假設(shè)五：每個(gè)景點(diǎn)所花的錢只考慮景點(diǎn)門票費(fèi)用。假設(shè)六：每一種旅游路線均從烏魯木齊出發(fā)然后回到烏魯木齊。假設(shè)七：考察團(tuán)將所有景點(diǎn)均要考察到四、符號(hào)的說明總交通費(fèi)用加門票費(fèi)用M除吃飯外的所有消費(fèi)〔包括住宿費(fèi)〕總的交通費(fèi)用總的門票費(fèi)用第i個(gè)景點(diǎn)的門票費(fèi)用每條路線總的行駛路程假設(shè)=1，那么表示從i景點(diǎn)去j景點(diǎn)，否那么=0表示i景點(diǎn)與j景點(diǎn)之間的距離表示從i景點(diǎn)到j(luò)景點(diǎn)多需的時(shí)間表示游客在i景點(diǎn)的最正確逗留時(shí)間五、模型的建立與求解問題一基于分析，我們首先在網(wǎng)上收集各旅游景點(diǎn)之間的路程、門票、最正確逗留時(shí)間、汽車的行駛速度以及住宿費(fèi)用，具體數(shù)據(jù)見表1，并據(jù)此對(duì)地圖進(jìn)展了簡(jiǎn)化，如下列圖所示:我們加上了王先生夫婦特別向往的景點(diǎn)天池和達(dá)坂城。對(duì)于很靠近旅游景區(qū)的景點(diǎn)，我們把它劃分到一個(gè)景區(qū)，只考慮各景點(diǎn)的最正確逗留時(shí)間的和。表1：各景點(diǎn)最正確逗留時(shí)間及門票費(fèi)用-.z.景點(diǎn)編號(hào)景點(diǎn)名稱逗留時(shí)間門票費(fèi)用〔元〕1烏魯木齊0天02天山天池1天1003達(dá)坂城1天04吐魯番2天1965哈密〔回王陵〕1天206阿勒泰1天07額爾齊斯河2天08喀納斯湖2天1309克拉瑪依1天010石河子1天011庫(kù)爾勒〔博斯湖〕2天3012樓蘭〔羅布泊〕2天013和田1天014尼亞遺址1天5015喀什3天8016阿克1天017千佛洞。庫(kù)車大寺2天5518天鵝湖1天3019伊犁〔乾隆格登碑〕4天3020博樂〔怪石溝，博爾塔拉〕2天021昌吉1天0大巴平均行駛速度：75km/h，車費(fèi)為0.15/km住宿費(fèi)用：100元/晚依題意，要找出一條最正確路線，使王先生夫婦在一個(gè)月花最少的錢游盡可能多的地方，這是一個(gè)優(yōu)化問題。由以上加權(quán)網(wǎng)絡(luò)圖，我們可以通過floyd算法求得任意兩景點(diǎn)間的距離，據(jù)此畫出一個(gè)完備圖?；诖耍覀兛梢越⒁粋€(gè)0-1線性規(guī)劃模型來求解，其中包含兩個(gè)相矛盾的目標(biāo)，花最少的錢與游盡可能多的地方。對(duì)此，我們的做法是先給定游玩的景點(diǎn)數(shù)，代入模型求得此景點(diǎn)數(shù)下最少需要花費(fèi)的錢和時(shí)間，選取不同的景點(diǎn)數(shù)便可得到不同的花費(fèi)，然后經(jīng)過綜合比擬，選取景點(diǎn)數(shù)較多且花費(fèi)較少的路線作為最正確路線。旅途中總的消費(fèi)除吃飯外主要考慮交通費(fèi)用m1和門票費(fèi)用m2，而，，那么得到目標(biāo)函數(shù)：再考慮約束條件：約束一：時(shí)間約束，游玩所有景點(diǎn)最正確路線的時(shí)間不能超過一個(gè)月，即300個(gè)小時(shí)。此時(shí)間包括路上交通所消耗的時(shí)間和景點(diǎn)逗留時(shí)間，路上消耗的時(shí)間為，景點(diǎn)逗留的總時(shí)間為，由此可得約束二：我們假設(shè)王先生夫婦游玩的景點(diǎn)數(shù)為n，一共有21個(gè)景點(diǎn)，為保證數(shù)量，我們規(guī)定n=12，13。。。21，由假設(shè)可知，所選路線為1個(gè)環(huán)形，因此約束三：我們把所有景點(diǎn)連成一個(gè)圈，每個(gè)景點(diǎn)是圈上的一點(diǎn)。那么，對(duì)于每個(gè)景點(diǎn)，最多只有一條邊進(jìn)入，同樣只允許最多一條邊出來。并且只要有一條邊進(jìn)去就有一條邊出來，因此約束五：考慮到實(shí)際情況，所有的線路出發(fā)點(diǎn)均為烏魯木齊，即，所有的線路的終點(diǎn)也為烏魯木齊，即。約束六：除了烏魯木齊外，其余的景點(diǎn)游客至多只會(huì)游玩一次，即當(dāng)時(shí)，不會(huì)出現(xiàn)，因此我們可得約束：綜上所述，我們可以建立如下0-1線性規(guī)劃：分別令n=12,13….21，求解，得到如下結(jié)果N每個(gè)景點(diǎn)的平均消費(fèi)額總時(shí)間總費(fèi)用具體路線1259.123天709.61-21-10-9-20-19-18-16-17-11-12-3-11363.525天825.71-3-11-12-16-17-18-19-20-10-9-6-21-11468.426天958.71-3-11-12-16-17-18-19-20-10-9-6-2-21-11573.428.5天1101.71-3-5-11-12-16-17-18-19-20-10-9-6-21-2-11683.930天1343.11-2-3-4-5-11-17-16-18-19-20-10-9-8-6-21-1分析上表，一個(gè)月可參觀的景點(diǎn)數(shù)最多為16個(gè)，但其平均消費(fèi)額也最大為83.9，比景點(diǎn)數(shù)為15時(shí)的平均消費(fèi)額高10.5，綜合考慮，我們向王先生夫婦推薦景點(diǎn)數(shù)為15的旅游路線：1-3-5-11-12-16-17-18-19-20-10-9-6-21-2-1當(dāng)n=12時(shí)，王先生除吃飯外花費(fèi)的錢為=交通費(fèi)用+門票費(fèi)用+住宿費(fèi)=709.6+3000=3709.6元問題二：據(jù)分析，我們需將所有景點(diǎn)分為2組，保證游完每條線路的時(shí)間不超過一個(gè)月，且每組的時(shí)間盡量相等，即均衡度盡量小。按照實(shí)際地理情況，我們將所有景點(diǎn)按南北疆分為如下2組：第一種分組：按南北疆分第一組8，6，7，9，2，1，21，3，4，5，10，20第二組19，18，11，17，16，12，15，14，13以每條線路上所消耗的時(shí)間最少為目標(biāo)，約束條件與問題一相似，建立0-1線性規(guī)劃模型如下：分別將上述分組代入模型，運(yùn)用lingo軟件求解，得到如下結(jié)果交通費(fèi)用具體路線740元1-12-11-10-9-6-7-8-2-5-4-3-1820元1-2-3-5-4-6-7-8-10-9-1計(jì)算上述分組的均衡度：對(duì)上述分組如下調(diào)整第二種分法：左調(diào)整第一組8，6，7，9，2，1，21，3，4，5，10第二組19，18，11，17，16，12，15，14，13，20用上述模型及方法求解，得：交通費(fèi)用具體路線651元1-6-8-7-9-10-21-5-4-3-2-1823元1-20-19-18-17-16-15-14-13-12-11-1均衡度為再進(jìn)展如下調(diào)整：第三種分法：右調(diào)整第一組8，6，7，9，2，1，21，3，4，5，10，20，19第二組18，11，17，16，12，15，14，13求解得交通費(fèi)用具體路線807元1-2-5-4-3-13-19-21-10-9-8-6-7-1727元1-18-17-16-15-14-13-12-11-1均衡度比擬三種分組的均衡度，按第一種分法均衡度最好，因此選擇此種分組。得到王先生夫婦2次的最正確旅游線路為:第一個(gè)月：烏魯木齊--昌吉--博樂--石河子--克拉瑪依--阿勒泰--額爾齊斯河--喀納斯湖--天山天池--哈密--吐魯番--達(dá)坂城--烏魯木齊，交通費(fèi)用為740元。第二個(gè)月：烏魯木齊--庫(kù)爾勒--樓蘭--尼雅遺址--和田--喀什--阿克--千佛寺--伊犁--天鵝湖--烏魯木齊，交通費(fèi)用為820元。問題三：據(jù)分析，首先根據(jù)問題一中求得的各景點(diǎn)間的最短路徑，畫出以烏魯木齊為起點(diǎn)的樹狀圖如下由題意考察團(tuán)分三組進(jìn)展，且考察對(duì)象為所有景點(diǎn)，即所有景點(diǎn)都必需包括在，那么要把所有景點(diǎn)分成3組。分組過程中需盡量遵守以下三個(gè)原那么：原那么一：盡量使同一干支上的點(diǎn)分在同一組。原那么二：應(yīng)將相鄰的干枝上的點(diǎn)分在同一組。原那么三：盡量將長(zhǎng)的干枝與短的干枝分在同一組。原那么四：盡量使各組的停留時(shí)間相等。第一種分法：按以上三個(gè)原那么，可將所有景點(diǎn)按如下所示分為6個(gè)區(qū)分組情況如下所示：第一種分組〔嚴(yán)格按分組原那么分〕第一組〔①③〕1，9，10，14，13，15，16，17，18，21第二組〔④⑥〕12，11，4，5，6，7，8，1第三組〔②⑤〕19，20，1，2，3將上述分組，按照模型二的求解方法求解，得到如下結(jié)果：組別考察時(shí)間具體路線第一組55天1-16-15-14-13-17-18-9-10-21-1第二組56天1-6-8-7-4-12-11-5-1第三組23天1-20-19-2-3-1該種分法的均衡度為：該分法的均衡度較差，因此我們對(duì)分組進(jìn)展調(diào)整，將將⑥中的4景點(diǎn)調(diào)整到第三組中，將③中的21調(diào)整到第三組，分組如下：第一組1，9，10，13，14，15，16，17，18第二組1，6，7，8，11，12，5第三組1，2，3，19，20，21，4仍用上述方法求解，得到如下結(jié)果：考察時(shí)間具體路線第一組47天1-20-19-21-2-4-3-1第二組51天1-10-9-18-17-16-14-13-15-1第三組48天1-8-6-7-11-12-5-1該種分法的均衡度為：顯然這種分法的均衡性要好一些，因此選用該種方法。即該考察團(tuán)的考察路線為：第一組：烏魯木齊-博樂-伊犁-昌吉-天山天池-吐魯番-達(dá)坂城-烏魯木齊，考察時(shí)間為47天。第二組：烏魯木齊-石河子-克拉瑪依-天鵝湖-千佛洞-阿克-尼亞遺址-和田-喀什-烏魯木齊，考察時(shí)間為51天。第三組：烏魯木齊-喀納斯湖-阿勒泰-額爾齊斯河-庫(kù)爾勒-樓蘭-哈密-烏魯木齊，考察時(shí)間為48天。問題四：此問題實(shí)質(zhì)是對(duì)景點(diǎn)的分組問題。由第一問我們求出了行遍所有景點(diǎn)的最短路為9317公里，花在路上的時(shí)間為9317/〔10*75〕=12.42天，要行遍所有景點(diǎn)的總逗留時(shí)間為32天，計(jì)算出總共花費(fèi)的時(shí)間44.42天，44.42/123.68，那么至少要分出4組路線。當(dāng)分成4組路線時(shí)，各組停留時(shí)間大約為32/4=8天，各組花在路途上的時(shí)間為12-8=4天。由第三問我們