最佳旅游線路的數(shù)學(xué)模型

【摘要】本文通過對自駕游云南的幾個旅游景點，求出了最正確旅游線路的數(shù)學(xué)模型，為旅游者設(shè)計旅游線路提供有一定價值的參考。首先，本文對所求問題做出合理假設(shè)，然后運用“分枝定界法”建立并尋找最正確旅游線路的圖論模型使問題簡單明了，并充分利用線性規(guī)劃建立模型，得出了最優(yōu)的線路設(shè)計，最后提出該模型的算法及求解過程。【關(guān)鍵字】分枝定界法Floyd〔弗勞德〕算法哈密頓圈旅游線路一、問題重述云南是我國的旅游大省，擁有豐富的旅游資源，吸引了大批的省外游客，旅游業(yè)正在成為云南的支柱產(chǎn)業(yè)。隨著越來越多的人選擇到云南旅游，旅行社也推出了各種不同類型的旅行路線，使得公眾的面臨多條線路的選擇問題。某一個從沒有到過云南的人準備在假期帶家人到云南旅游，預(yù)計從昆明出發(fā)，并最終返回昆明，且旅行者采取自駕游的旅行方式。二、符號說明1、，：加權(quán)圖的頂點即云南各旅游景點；2、：各景點間的距離構(gòu)成的矩陣；3、：各景點間的距離構(gòu)成的矩陣中每一行減去該行的最小的元素及每一列減去該列的最小元素后所構(gòu)成的矩陣；4、：加權(quán)圖的邊，即權(quán)，表示兩景點間的距離；5、：為任意兩頂點與頂點在圖中最短路徑長度。三、模型假設(shè)1、假設(shè)旅游者在各景點的逗留時間、花費等都相同；2、旅游者最終要返回昆明，假設(shè)昆明是旅游者要去的一個旅游景點；3、假設(shè)旅游者所經(jīng)過的公路是同一等級公路，在汽車恒速及單位路程所耗油量相同的條件下，各景點的路程與時間及耗油量成正比，即在較短時間及較低耗油量內(nèi)，旅游較多景點，為此我們制定一條路線使得路程最短，這樣就能使旅游者花費時間最短而耗油量又最低得情況下旅游相同的景點。四、模型建立與求解1、根據(jù)旅游者采取的是自駕游的旅行方式，我們可以得到云南省局部旅游景點的交通路線中〔自駕游可以自選路線，每兩個旅游景點間都有可行路程〕每兩景點間的路程，任意兩旅游景點間的路程如下表所示〔單位：公里〕：昆明大理麗江石林西雙版納瀘沽湖香格里拉昆明031950285542567629大理3190183397854448314麗江50218305811037260178石林853975810603654707西雙版納5428541037603012261164瀘沽湖56744826065412260434香格里拉62931417870711644340表1各旅游景點間的路程表下列圖是云南省旅游景點地圖：圖1云南省旅游景點圖由上面的地圖可畫出所給旅游景點的路線圖如下：香格里拉麗江大理香格里拉麗江大理瀘沽湖昆明石林西雙版納由表1和圖1可得到加權(quán)無向圖圖2如下：71712345662931954256785314397854448183581103717826060370765412261164434502注：1.昆明2.大理3.麗江4.石林5.西雙版納6.瀘沽湖7.香格里拉2、“分枝定界法”模型：用階矩陣中的各個元素來表示各個景點之間的距離，且各個景點之間的距離是沒有方向的，那么階矩陣是對稱型矩陣,中的所有元素減去該行的最小非零元素，得到新的矩陣，再抽取矩陣每列的最小非零元素，并令矩陣各列的所有元素減去該列的最小非零元素，得到新的矩陣，這樣得到矩陣是每行每列都至少有一個零元素存在。然后，選擇起點與某景點之間距離為零的元素，把這個元素所在的行和列從矩陣中劃去，得到新的矩陣，同時，把起點與某景點組成一條路。對矩陣重復(fù)矩陣變化到矩陣的步驟操作，得到新的景點參加到最近路的末頂點的后面，使其成為一條新路。直到得到的最后矩陣是，且這條路包含所有的景點，所有的景點在這條路上只能出現(xiàn)一次，這樣操作才算停止，否那么重復(fù)上面的步驟。3、“分枝定界法”模型求解，用“分枝定界法”尋找近似最正確旅游線路的算法如下：步驟1：用Floyd算法求任意兩景點之間的距離，構(gòu)建一個加權(quán)無向圖，每條邊的權(quán)叫為頂點與頂點在圖中最短路徑長度。步驟2：隨機搜索加權(quán)無向圖中已指定的起點的假設(shè)干個哈密頓圈，或者找出它的任意一個初始的哈密頓圈。步驟3：用二邊逐次修改法對步驟2中的哈密頓圈進行優(yōu)化，從而得到近似最正確的哈密頓圈。步驟4：比擬上述哈密頓圈，找出權(quán)值最小的一個，即為所要找的最正確哈密頓的近似解。4、“分枝定界法”模型求解的具體過程：123456712345671234567由“分枝定界法”的模型建立和矩陣算法，選擇一條路，并令再把矩陣的第一行，第四列劃去，得到矩陣:123567123567123567從矩陣中，可以選擇頂點5添加在路中，那么有路，將第一行，第四列劃去，令得：123671236712367從矩陣中，選擇將頂點2添加到路，即得到路，將第一行，第二列劃去，令得1367將頂點3添加到路上得路，將第一行，第二列劃去并令得：167將頂點7添加到路上得路，將第一行第三列劃去，并令得：16最后將頂點6添加得，從而可得總權(quán)數(shù)最小的哈密頓圈，即總權(quán)數(shù)為2904。所以最正確的旅游路線是：昆明石林西雙版納大理麗江香格里拉瀘沽湖昆明。五、模型推廣在模型求解過程中，我們可以應(yīng)用“最鄰近插入法”，0-1變量等方法尋找近似的最正確旅游線路，對景點較少而言，具體操作過程簡單，但對有較多的景點時，具體操作過程比擬復(fù)雜，因此用這種方法尋找近似最正確的旅游線路存在一定的缺陷。而用“分枝定界法”尋找近似的最正確旅游線路，能在有限的時間內(nèi)根據(jù)個人條件盡可能游覽較多的景點，是游客所關(guān)心的問題。該模型能尋找出較多景點的最正確旅游線路，并用Floyd〔弗勞德〕算法更簡單快捷的求解問題。六、模型評價為了尋找最正確旅游路線的問題，在“最鄰近插入法”，0-1變量法和“分枝定界法”中，0-1變量法是用代數(shù)的方法轉(zhuǎn)化為lindo或lingo中求解，“最鄰近插入法”和“分枝定界法”均是將其轉(zhuǎn)化為在給定加權(quán)無向圖中尋找總權(quán)數(shù)最小的哈密頓圈。但由于求解的模型和算法不同，“最鄰近插入法”的求解過程更為直觀、便于理解，而“分枝定界法”在景點較多的情況下，可通過計算機編程求解。所以，在實踐中運用“分枝定界法”來尋找近似的最正確旅游線路更有優(yōu)勢。一般來說，一個整數(shù)規(guī)劃問題的可行解或是無限或是有限的。對于有限的可行解來說，我們自然想到列舉法〔或稱枚舉法〕，把所有可能的整數(shù)可行解組合列出來，然后得到目標函數(shù)的最優(yōu)值和最優(yōu)解。但是如果斷策變量很多或整數(shù)可行解組合多得驚人時，列舉法就沒有實用價值了。因此，就要尋求一種可行方法，使之僅檢查局部整數(shù)可行解組合，從而得出最優(yōu)的整數(shù)解。分枝定界法〔branchandboundmethod〕就是其中一種，它靈活且便于用計算機求解，是解整數(shù)規(guī)劃的重要方法。七、參考文獻[1]周溪召主編.運籌學(xué)及應(yīng)用.——北京：化學(xué)工業(yè)出版社，2009.1[2]王文平等編著.運籌學(xué).——北京：科學(xué)出版社，2007[3]栗雪娟，崔尚森，張柯．最正確旅游路線選擇的神經(jīng)網(wǎng)絡(luò)方法[J]．交通與計算機，2006[4]張杰，周碩主編；邢麗娟等編寫.運籌學(xué)模型與實驗.——北京：中國電力出版社，2007