【正文】 且晚餐在一天的旅行結(jié)束后吃。(8)假設(shè)旅游人數(shù)都住在一個住宿點(diǎn)(9)假設(shè)每次出游的人數(shù)隨機(jī)且相互獨(dú)立四、符號說明表示各邊對應(yīng)的決策變量表示各邊對應(yīng)的長度表示節(jié)點(diǎn)數(shù)量表示D中第i個位置上的點(diǎn)到第j個位置上的點(diǎn)的時間表示第i天是否選擇從第ｊ個位置到第k個位置參觀旅游或住宿表示D中第k位置的住宿費(fèi)用信息啟發(fā)式因子 期望啟發(fā)式因子信息素?fù)]發(fā)系數(shù)表示標(biāo)準(zhǔn)間市場價客房數(shù)目N新增客房數(shù)目五、模型假設(shè)及求解根據(jù)題目建立成本最低的旅游路線即是在滿足旅游要求的情況下，使旅游的路線最短，住宿費(fèi)用最少，綜合實(shí)際中旅游路線設(shè)計(jì)情況，旅行社帶游客旅游完全部景點(diǎn)后要回到出發(fā)地U且游覽的地點(diǎn)不重復(fù)，因此可以看作是更多約束的周游型旅游路線優(yōu)化(TSP問題)，用多目標(biāo)01規(guī)劃來建立模型。 01規(guī)劃基本模型當(dāng)整數(shù)規(guī)劃問題中的決策變量僅限于0或1兩個數(shù)值，則該問題稱為01整數(shù)規(guī)劃，簡稱01規(guī)劃，其一般模型為 () 周游型旅游路線優(yōu)化模型周游型旅游路線問題是由出發(fā)地出發(fā),途中剛好不重復(fù)的遍游所有的景點(diǎn),最后回到出發(fā)地,形成一個閉合的環(huán)型路線的問題。該類問題至今也沒有完美解決，是個NPC類問題，可由TSP問題建模，模型如下：目標(biāo)函數(shù)： () 約束條件1：所有決策變量為二分變量，即約束條件2：總邊數(shù) ()約束條件3：橫行和 ()約束條件4：縱列和 ()約束條件5：橫對稱 () 其中，表示各邊對應(yīng)的決策變量，表示各邊對應(yīng)的長度，為表示節(jié)點(diǎn)的數(shù)量。 01規(guī)劃成本最小的旅游路線優(yōu)化模型根據(jù)上一節(jié)TSP問題模型的設(shè)計(jì)原理，結(jié)合本題的要求建立模型。根據(jù)題意旅游路線設(shè)計(jì)中要考慮住宿的問題，對于住宿點(diǎn)不能區(qū)分是經(jīng)過該點(diǎn)還是住在該點(diǎn)，因此為了更方便建模和求解將住宿點(diǎn)用兩個符號分別表示，其一表示住宿點(diǎn)，其二表示經(jīng)過該點(diǎn)，例如點(diǎn)B，在該地既可以游覽又可以住宿，則將B表示為游覽點(diǎn)，而B39。來表示住宿點(diǎn)，而兩點(diǎn)之間的距離則為0。為了更好的表示各個地點(diǎn)，本文將游覽點(diǎn)和住宿點(diǎn)統(tǒng)一放到數(shù)組中，用表示相應(yīng)的點(diǎn)，其中表示為則可以將圖轉(zhuǎn)換為以中各點(diǎn)的排序下的鄰接矩陣， ()其中，表示中第個位置上的點(diǎn)到第個位置上的點(diǎn)的時間。假設(shè)01變量表示第天是否選擇從第個位置到第個位置去旅游或住宿，即旅游的天數(shù)為，景點(diǎn)數(shù)為(算上出發(fā)點(diǎn))，住宿點(diǎn)個數(shù)為個，不是景點(diǎn)的住宿點(diǎn)個數(shù)為個，則建立目標(biāo)函數(shù)：?行車總時間最短： ()?住宿費(fèi)用最少： ()其中，表示中第個位置的住宿費(fèi)用，當(dāng)該位置不是住宿點(diǎn)時將其設(shè)為0，即對于目標(biāo)函數(shù)進(jìn)行約束：(1)旅游路線起始點(diǎn)的約束：?對于整條旅游路線來說起始點(diǎn)為U，則第一天必從U出發(fā)到某個點(diǎn)，而最后一天必從某點(diǎn)回到U，即 () ()?對于每天的旅游路線，除最后一天外，每天都必須有住宿的地方，即 ()(2)旅游路線連續(xù)性的約束：?對于每天來說，旅游路線都必須是連續(xù)的，也就是每個點(diǎn)的出入度是一樣的，即 ()?對于所有天來說，整個旅游路線必須是連續(xù)的，即 () ()(3)游覽點(diǎn)的約束：對于游覽點(diǎn)，旅行社設(shè)計(jì)路線時必須經(jīng)過且次數(shù)只能是一次，即 ()(4)旅游時間的約束：一天旅行從7:00開始，18:00結(jié)束，而一天的行程最遲可以在20:00的時候結(jié)束，即 () ()其中，為景點(diǎn)游覽時間矩陣，其元素排列順序與一一對應(yīng)。由于路線的選擇和住宿的選擇之間相互關(guān)聯(lián)，同時考慮兩者的情況下，求解過程十分復(fù)雜且變量過多導(dǎo)致求解效率很低?？紤]在游覽時間固定的情況下，實(shí)際中一般都先確定好游覽路線，再來確定住宿的位置。另外，住宿點(diǎn)的選擇對路線有很大的依賴關(guān)系，并且行程的時間主要受路線的影響，且本題中住宿費(fèi)用變化較為平緩。因此，為了簡化求解過程，本文通過先確定所有景點(diǎn)的游覽順序，再根據(jù)該順序?qū)ふ易顑?yōu)的住宿點(diǎn)來近似求解。確定所有景點(diǎn)的游覽順序?qū)嵸|(zhì)就是周游型旅游路線優(yōu)化， 其中，為景點(diǎn)之間的鄰接矩陣。為各景點(diǎn)間的順序表示。由于問題中所用點(diǎn)數(shù)量數(shù)量不多，則本文采用基本蟻群算法來求解。其步驟如下：(1) 初始化各路徑上的信息量，且，設(shè)置信息啟發(fā)式因子，期望啟發(fā)式因子，信息素?fù)]發(fā)系數(shù)，啟發(fā)函數(shù)和。(2) 將q個螞蟻分布到m個景點(diǎn)中。(3) 每個螞蟻計(jì)算該時刻下景點(diǎn)到景點(diǎn)的狀態(tài)轉(zhuǎn)移概率， 并以輪盤賭博的方式選擇下一個景點(diǎn)，并前進(jìn)。判斷是否已遍歷完所有景點(diǎn)，是則繼續(xù)執(zhí)行,否則跳到下一步。(4) 根據(jù)更新每條路徑上的信息量。 (5) 如果滿足結(jié)束條件，即循環(huán)次數(shù)大于或等于最大迭代次數(shù)，算法結(jié)束否則，否則返回(2)繼續(xù)執(zhí)行。根據(jù)以上步驟求得景點(diǎn)游覽順序矩陣S。接著根據(jù)該順序?qū)ふ易∷撄c(diǎn)使住宿費(fèi)和增加的行程時間最小。本文用回溯的思想來尋找住宿點(diǎn)，在尋找住宿點(diǎn)前應(yīng)先將行程時間和住宿費(fèi)用作歸一化處理，而住宿費(fèi)以300以50的間隔到450，兩者之間的數(shù)據(jù)個數(shù)相差很大，因此，先將住宿費(fèi)補(bǔ)齊后再進(jìn)行歸一化處理，本文采用離差標(biāo)準(zhǔn)化法進(jìn)行歸一化，即得到歸一化后的數(shù)據(jù)，見表(),() 時間歸一化對照表原123456歸01 住宿費(fèi)歸一化對照表原數(shù)據(jù)300350400450歸一化后0數(shù)據(jù)歸一化后，用回溯法尋找住宿點(diǎn)，其步驟如下：(1) 初始化行程時間；(2) 從中按順序取出景點(diǎn)，求，如果則執(zhí)行下一步，否則繼續(xù)步驟(2)。(3) ，如果找不到，則跳到步驟(5)。(4) 分別計(jì)算增加各個住宿點(diǎn)后所增加的時間，比較與，如果前者大于后者，則選擇為住宿點(diǎn)，否則選擇為住宿點(diǎn)。所有住宿點(diǎn)選好返回步驟(1)，沒有則跳到步驟(6)。(5) 修改昨天的住宿點(diǎn)，選擇在那天另外可住的點(diǎn)，如果沒有則修改前