基于時(shí)間窗的出行旅游規(guī)劃問(wèn)題研究

楊曉芳 余婷

摘 要：針對(duì)帶時(shí)間窗旅游線路規(guī)劃問(wèn)題，以網(wǎng)絡(luò)優(yōu)化和數(shù)學(xué)規(guī)劃理論為基礎(chǔ)，建立相應(yīng)的數(shù)學(xué)模型，通過(guò)對(duì)游客旅游中的時(shí)間和費(fèi)用進(jìn)行分析，設(shè)計(jì)出了具體路線方案，以保證旅游體驗(yàn)最佳。仿真結(jié)果表明，利用蟻群算法求解能使出行時(shí)間最短、費(fèi)用最低、旅游體驗(yàn)最優(yōu)等問(wèn)題。

關(guān)鍵詞：線路規(guī)劃；時(shí)間窗；蟻群算法；仿真

中圖分類(lèi)號(hào)：F592.68 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： In view of the tourist route planning problem with time windows， on the basis of network optimization and mathematical programming theory， establish the corresponding mathematical model， the analysis of tourists travel time and the cost， designed the concrete route plan， to ensure the best travel experience. The simulation results show that using ant colony algorithm can make the shortest travel time， lowest cost， travel experience the most superior.

Key words： route planning； time windows； ant colony algorithm； simulation

0 引 言

傳統(tǒng)旅行商問(wèn)題（TSP）是指推銷(xiāo)人員要走訪多個(gè)地點(diǎn)時(shí)，如何找到在到達(dá)每個(gè)地點(diǎn)一次后再回到原點(diǎn)的最短路

徑[1-4]。TSP問(wèn)題描述起來(lái)簡(jiǎn)單，但解決卻很復(fù)雜，在實(shí)際問(wèn)題中，很多旅游路線并非完整的旅行商問(wèn)題，游客去多個(gè)景區(qū)游玩并不是組成一個(gè)完整的閉回路，而是每次出行均有時(shí)間限制，分幾次旅行，每次出行去計(jì)劃的某些景區(qū)之中的某幾個(gè)之后再回到原點(diǎn)，并且每個(gè)景區(qū)的開(kāi)放時(shí)間是固定的，此問(wèn)題即演變成了帶有時(shí)間窗車(chē)輛路徑問(wèn)題（VRP）[5-6]。如圖1所示，圖中正中間點(diǎn)表示車(chē)輛起始點(diǎn)（車(chē)場(chǎng)或配送中心），每個(gè)閉合圈內(nèi)的點(diǎn)表示需要到達(dá)的客戶(hù)點(diǎn)，兩點(diǎn)之間則表示路段，每條路線對(duì)應(yīng)著一個(gè)費(fèi)用，通常表示其距離或行駛時(shí)間。

為解決該類(lèi)旅游路線規(guī)劃問(wèn)題，為此類(lèi)游客提供更好的路徑體驗(yàn)，本文建立數(shù)學(xué)模型，并用蟻群算法求解模型，通過(guò)計(jì)算機(jī)編程仿真得到最優(yōu)旅游路線。

1 模型的建立

1.1 問(wèn)題描述

式（1）為目標(biāo)函數(shù)，及要求旅游時(shí)時(shí)間最短，約束式（2）、式（3）表示每個(gè)景區(qū)只游覽一次，約束式（4）旅游愛(ài)好者進(jìn)入景區(qū)i，也定會(huì)離開(kāi)景區(qū)i，約束式（5）表示每次旅行的最大限制時(shí)間，每次出游時(shí)間不能超過(guò)限制天數(shù)，約束式（6）為景區(qū)節(jié)點(diǎn)時(shí)間窗約束。

2 蟻群算法求解模型

蟻群算法（Ant Colony Optimization， ACO），是一種典型的仿生物算法，20世紀(jì)M. Dorigo等學(xué)者從螞蟻覓食行為的研究中受到啟發(fā)，進(jìn)而提出的一種優(yōu)化算法[7-8]。當(dāng)一只螞蟻發(fā)現(xiàn)一條通往食物所在地的路徑時(shí)即會(huì)釋放出一種“信息素”，并根據(jù)信息素濃度來(lái)決定下一刻的移動(dòng)方向，初始時(shí)刻各條路徑信息素濃度是一樣的；當(dāng)螞蟻沿著這條路到達(dá)終點(diǎn)后便會(huì)沿著原路返回；如此，短路徑上的螞蟻經(jīng)歷過(guò)的次數(shù)就越多，信息素濃度也就大，于是吸引更多螞蟻，信息素繼續(xù)升高，如此循環(huán)，最后找到最佳路徑。蟻群算法便捷準(zhǔn)確，可以利用該算法來(lái)求解各種復(fù)雜的VRP問(wèn)題。求解過(guò)程如下：

step1：設(shè)置初始參數(shù)；

step2：給第k只螞蟻隨機(jī)選擇起始點(diǎn)i，并把起始點(diǎn)i放入第k只螞蟻搜索禁忌表中，如果i為西安市，則將西安市刪去；

step3：求最大轉(zhuǎn)移概率maxp，得到下一個(gè)點(diǎn)j；

step4：考察和j連接后的線路上旅游次數(shù)sumg，若sumg≤Q（Q為游客每次出游最長(zhǎng)限制時(shí)間），則轉(zhuǎn)下一步，否則，轉(zhuǎn)step6；

step5：計(jì)算s，若s滿足時(shí)間窗要求，把點(diǎn)j放入tabu中，計(jì)算i點(diǎn)到j(luò)點(diǎn)路徑所用時(shí)間，轉(zhuǎn)step3，否則轉(zhuǎn)下一步；

step6：統(tǒng)計(jì)旅游次數(shù)，根據(jù)次數(shù)判斷allowed表，如果allowed表空，那么轉(zhuǎn)下一步；并轉(zhuǎn)step3，繼續(xù)搜索下一個(gè)點(diǎn)；

step7：重新計(jì)算各邊信息素以及信息素的增量；

step8：搜索k只螞蟻?zhàn)疃虝r(shí)間路徑，更新螞蟻每條路線信息素，若有k只螞蟻均巡游一遍，則更新k只螞蟻搜索過(guò)路徑的信息素，否則，更新該次循環(huán)最優(yōu)路徑；

step9：若算法循環(huán)NC_max后停止，則計(jì)算NC_max后最短路徑長(zhǎng)度和最短路徑，最少費(fèi)用和最少費(fèi)用路徑，否則轉(zhuǎn)step2。

從以上步驟可知，在整個(gè)循環(huán)中，螞蟻的起點(diǎn)不都是原點(diǎn)，而是隨機(jī)選擇的，這樣做更檢驗(yàn)算法的正確性，選擇不同的起始點(diǎn)更有利于找到更好解。當(dāng)該螞蟻不滿足以上約束條件，需要在剩余的點(diǎn)中尋找新的起點(diǎn)（用時(shí)最短的點(diǎn)），這樣在最大程度上提高了算法的效率。

3 仿真結(jié)果分析

假設(shè)該旅游愛(ài)好者每年外出旅游時(shí)間不超過(guò)30天，每年外出旅游次數(shù)不超過(guò)4次，每次旅游時(shí)間不超過(guò)15天；根據(jù)個(gè)人愛(ài)好確定了每個(gè)5A級(jí)景區(qū)最少的游覽時(shí)間。景區(qū)開(kāi)放時(shí)間統(tǒng)一規(guī)定為8：00至18：00。經(jīng)過(guò)建模求解仿真如圖2所示、詳細(xì)路徑如表1所示。

根據(jù)仿真結(jié)果求得最短時(shí)間為10.5年，即在本題目約束條件下，該旅游愛(ài)好者自駕游玩全國(guó)201個(gè)5A級(jí)風(fēng)景區(qū)