旅游景點最短路徑設(shè)計

-.z.景點旅游規(guī)劃摘要

旅游路線的設(shè)計問題屬于優(yōu)化問題，是通過排列組合，離散程度比擬等知識求最短路徑的問題。旅游路線設(shè)計的是否合理直接關(guān)系游客的旅游體驗和景區(qū)的經(jīng)濟效益，所以我們需要通過數(shù)學(xué)建?？茖W(xué)的研究旅游路線的設(shè)計問題。

在本問題中景區(qū)共10個景點，其中1、3、6、9、10

五個景點為景區(qū)特色景點。要求每個旅游套餐要有

4個景點，其中至少包括

2個特色景點。又因景點1、6和景點9、10分別是同類景點，游覽內(nèi)容很相近，所以旅游套餐中的特色景點不能只是同類景點。景區(qū)特色景點的客流容納人數(shù)是其他景點的兩倍。

針于問題一，找出4個景點〔其中包含至少兩個且不全只是同類的特色景點〕，將這

4個景點之間相連的路徑長度求和即為這個旅游套餐的路徑長度。我們可用排列組合算出有多種景點組合，由于游覽順序取總行程最短的順序，所以不存在因游覽順序不同而導(dǎo)致路徑不同的情況。通過鄰接矩陣，用Matble編寫程序計算出各種組合的路徑，經(jīng)過E*cel排序篩選出6種符合題意且路徑最短的

套餐。

針對問題二，在問題一的根底上，可以用0-1規(guī)劃以及

6個旅游套餐中所有景點的客流量的離散程度來刻畫景點客流量的離散程度，離散程度是描述數(shù)據(jù)離散程度的量，離散程度越小各景點的客流量越均衡。要使離散程度盡量小，首先

6個套餐應(yīng)覆蓋盡量多的景點，再由每種套餐的比例來約束離散程度，使得離散程度盡量小。要說明的是，由于特色景點的客容量是普通景點的兩倍，所以這里的離散程度在表達式上要進展簡單處理，具體見模型建立。關(guān)鍵詞：排列組合鄰接矩陣0-1規(guī)劃離散程度matlab一、問題重述*景區(qū)有10個景點，各景點的交通示意圖如圖1。其中1，3，6，9，10五個景點為景區(qū)特色景點。景區(qū)特色景點的客流容納人數(shù)是其他景點的兩倍。在特色景點中，1和6都是海濱景點，9和10都是山區(qū)景點。圖1為了合理規(guī)劃景區(qū)的旅游，景區(qū)旅游經(jīng)營者方案推出6種不同的旅游套餐，每種旅游套餐包括4個景點，其中至少2個特色景點。由于景點1、6和景點9、10分別是同類景點，游覽內(nèi)容相近，景區(qū)規(guī)定，旅游套餐中的特色景點不能只是同類景點。問題一：按照上述旅游套餐選擇的要求，找出6種路程最短的套餐。問題二：設(shè)計出6種不同旅游套餐，并計算出各種套餐的人數(shù)比例，使得景點的客流量根本均衡，且總行程盡可能短。二．問題的分析針對問題一：找出6種路徑最短的方案，每種方案都是四個景點，其中至少兩個不重復(fù)的特色景點。由于四個景點的順序不影響游客的欣賞情況，且路徑的長短一樣，所以把不同次序的四個一樣景點的情況看做一種方案。采用排列組合的方法算出約束條件不完全的情況，因為方案較少，采用列舉法算出所有的可能，通過matlab軟件計算出每種方案的路程，再比擬路徑的長短，求解出路徑最短的六種方案。針對問題二：在第一問求解的所有符合要求的方案中，找出六種人數(shù)比例均衡且路徑盡可能短的六種方案?？梢杂昧鶄€旅游方案中所有景點的客流量的離散程度來刻畫景點客流量的均衡程度，離散程度越小，各景點的客流量越均衡。由于特色景點的客容量是普通景點的兩倍，所以在計算離散程度時，表達式上要進展簡單處理，具體見模型建立。為使離散程度方盡量小，要六個方案應(yīng)覆蓋盡量多的景點，再由每種方案的比例來約束離散程度，最終得出六個最優(yōu)方案。三．模型假設(shè)與符號說明模型假設(shè)假設(shè)一：所有旅客都按照設(shè)計的旅游方案進展游玩，且每經(jīng)過一個景點都進入，不存在到而不玩的情況。假設(shè)二：每個景點接待游客的數(shù)目是很大的，可以同時接納所有方案同時到達的旅客。假設(shè)三：不同次序的但景點一樣的方案視為一個方案。且按路程最短的道路計算。符號說明，i=1～10：表示第i個景點，j=1～10：表示第j個景點，i=1～10，j=1～10，〔i≠j〕：第i個景點到第j個景點的距離:表示每種方案的總路程:表示客流量總?cè)藬?shù)，k=a,b,c,d,e,f:表示第k種方案占總?cè)藬?shù)的比例，i=1～10：第i個景點的客流量：景點客流量的離散程度:每個景點平均客流量四．模型的建立與求解問題一要求每種旅游套餐包括4個景點，其中至少2個特色景點，由于景點1、6和景點9、10分別是同類景點，游覽內(nèi)容相近，景區(qū)規(guī)定，旅游套餐中的特色景點不能只是同類景點。一共有10個景點，特色景點為5個。在不考慮每個景點是否有通路時：所有的方案有：=135(種)計算結(jié)果為135種，但由于不是每個景點都可以直接到達另外一個景點，所以可行的方案應(yīng)小于135種。根據(jù)圖片給的道路信息，通過列舉法計算所有可行的方案。以經(jīng)過1景點的可行方案為例。列舉法如圖：從每一個景點出發(fā)，計算所有的情況如下表：景點一二三四景點一二三四34562389324667896523543105679310846481079839764781032381052310678106431034674389384624310345143219846310891089774310387683213479123103251根據(jù)給出的旅游景點路線圖可以得到各景點之間的鄰接矩陣，由于一些景點不能直接到達，假設(shè)為距離無限遠，為了在進展矩陣運算時便以計算，把無限遠距離用1000代替。鄰接矩陣如下圖：031.510001000191000100010001000100031.507.512.7171000100010001000100010007.5014.510001000100017.6100024.6100012.714.506.810.816.811.210001000191710006.807.8100010001000100010001000100010.87.8012.810001000100010001000100016.8100012.8012.611.810001000100017.611.21000100012.6018.611.610001000100010001000100011.818.6010001000100024.6100010001000100011.610000把方案與鄰接矩陣代入matlab軟件中運行出每種方案的路程，并從中得出六個最短路程的方案。所有的方案路程345629.1324631652332.3567932.46481033.6976435.42381036.76781037346738.1384639.6345140.3984640.61089742387643347943.1325143.5238943.76789445431045.93108447.47983487810348.85231049.16431049.9438950.72431051.8432153.53108954.87431055.9832156.61231063.6有上圖可以確定如下六中方案路程最短：序號旅游套餐總路程13→4→5→629.123→2→4→63136→5→2→332.345→6→7→932.456→4→8→1033.669→7→6→435.4問題二我們?yōu)榱耸垢骶包c游客量均衡，通過不同的6種旅游線路按比例組合，模型如下：目標函數(shù)：條件或每個景點接待游客的人數(shù)：因為總游客數(shù)是k,每個游客要游覽四個景點，所以每個景點平均接待游客量：為使所有景點客流量較均衡，所選的6個套餐及其比例應(yīng)使所有景點接待游客量的離散程度盡量小，且考慮到特色景點游客的容納量是普通景點的兩倍：通過軟件計算出結(jié)果，選擇最短的六條路徑，得到最優(yōu)的六種方案。方案如圖：套餐景點路程套餐人數(shù)比例5→6→7→932.439→7→8→103626→7→8→103721→5→4→340.346→4→8→940.631→2→3→1063.64五．模型結(jié)果的分析問題一中，通過排列組合以及matlab軟件的應(yīng)用，計算出符合要求的多種方案的路程長短，通過排序，找出了六條最短的路徑，符合要求。問題二中，通過計算每個景點人流量的離散程度的方法，來保證客流量根本均衡，在客流量根本均衡的情況下，又選擇了路徑最短的方案，找出來最優(yōu)的六個方案，滿足題目的要求。六．模型的推廣與改良方向此題在解決實際的問題中，計算最短路徑設(shè)計方案，以及通過每個景點的游客量的離散程度來估計景點的人流量平衡問題，都有很強的移植性，可以應(yīng)用在不同的優(yōu)化問題中，對實際問題有較強的解決能力。七．模型的優(yōu)缺點在此題的方案設(shè)計以及計算的過程中，運用了嚴謹?shù)臄?shù)學(xué)知識和一些數(shù)學(xué)方法，建立了簡單的模型，對實際生活中的方案選擇問題找出了比擬合理的方案，對實際的問題有較大的參考意義。但是，在問題一的計算中，只考慮了兩個景點之間的路程長短，沒有考慮現(xiàn)實生活中的其他因素，比方危險路段，河流等，都會影響路程的選擇；在第二個問題中，沒有考慮每個人游玩各個景點的時間是否一樣等問題，使模型不夠全面，所有要想選出更加合理的可行性方案，需要考慮更加的因素，再對方案作出合理的改良。八.參考文獻[1]姜啟源.數(shù)學(xué)模型〔第三版〕[M].：高等教育，1999.[2]韓中庚.數(shù)學(xué)建模方法及其應(yīng)用〔第二版〕[M].：高等教育，2021[3]韓中庚，數(shù)學(xué)建模競賽——獲獎?wù)撐木x與點評，：科學(xué)，[4]卓金武.MATLAB在數(shù)學(xué)建模中的應(yīng)用〔第一版〕.航空航天大學(xué).2021.[5]趙靜但琦.數(shù)學(xué)與數(shù)學(xué)實驗〔第三版〕.高等教育.2021.[6]胡守信李伯年.基于MATLAB的數(shù)學(xué)實驗.科學(xué).2004.附錄計算各方案路程長度：functionf=f1(A,B)[m,n]=size(B);fora=1:md(a)=A(B(a,1),B(a,2))+A(B(a,2),B(a,3))+A(B(a,3),B(a,4));B=[B;d(a)];EndB運行結(jié)果：345629.1324631652332.3567932.46481033.6976435.42381036.76781037346738.1384639.6345140.3984640.61089742387643347943.1325143.5238943.76789445431045.93108447.47983487810348.85231049.16431049.9438950.72431051.8432153.53108954.87431055.9832156.61231063.6for(inti=0;i<10;i++){chisu[i]=0;}//六種套餐的人數(shù)chisu[a.i]+=(double)aRadio/1000.0*(double)PersonMun;chisu[a.j]+=(double)aRadio/1000.0*(double)PersonMun;chisu[a.k]+=(double)aRadio/1000.0*(double)PersonMun;chisu[a.l]+=(double)aRadio/1000.0*(double)PersonMun;chisu[b.i]+=(double)bRadio/1000.0*(double)PersonMun;chisu[b.j]+=(double)bRadio/1000.0*(double)PersonMun;chisu[b.k]+=(double)bRadio/1000.0*(double)PersonMun;chisu[b.l]+=(double)bRadio/1000.0*(double)PersonMun;chisu[c.i]+=(double)cRadio/1000.0*(double)PersonMun;chisu[c.j]+=(double)cRadio/1000.0*(double)PersonMun;chisu[c.k]+=(double)cRadio/1000.0*(double)PersonMun;chisu[c.l]+=(double)cRadio/1000.0*(double)PersonMun;;chisu[d.i]+=(double)dRadio/1000.0*(double)PersonMun;chisu[d.j]+=(double)dRadio/1000.0*(double)PersonMun;chisu[d.k]+=(double)dRadio/1000.0*(double)PersonMun;chisu[d.l]+=(double)dRadio/1000.0*(double)PersonMun;chisu[e.i]+=(double)eRadio/1000.0*(double)PersonMun;chisu[e.j]+=(double)eRadio/1000.0*(double)PersonMun;chisu[e.k]+=(double)eRadio/1000.0*(double)PersonMun;chisu[e.l]+=(double)eRadio/1000.0*(double)PersonMun;chisu[f.i]+=(double)dRadio/1000.0*(double)PersonMun;chisu[f.j]+=(double)dRadio/1000.0*(double)PersonMun;chisu[f