基于時間窗的出行旅游規劃問題研究

楊曉芳 余婷

摘 要：針對帶時間窗旅游線路規劃問題，以網絡優化和數學規劃理論為基礎，建立相應的數學模型，通過對游客旅游中的時間和費用進行分析，設計出了具體路線方案，以保證旅游體驗最佳。仿真結果表明，利用蟻群算法求解能使出行時間最短、費用最低、旅游體驗最優等問題。

關鍵詞：線路規劃；時間窗；蟻群算法；仿真

中圖分類號：F592.68 文獻標識碼：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 引 言

傳統旅行商問題（TSP）是指推銷人員要走訪多個地點時，如何找到在到達每個地點一次后再回到原點的最短路

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

為解決該類旅游路線規劃問題，為此類游客提供更好的路徑體驗，本文建立數學模型，并用蟻群算法求解模型，通過計算機編程仿真得到最優旅游路線。

1 模型的建立

1.1 問題描述

式（1）為目標函數，及要求旅游時時間最短，約束式（2）、式（3）表示每個景區只游覽一次，約束式（4）旅游愛好者進入景區i，也定會離開景區i，約束式（5）表示每次旅行的最大限制時間，每次出游時間不能超過限制天數，約束式（6）為景區節點時間窗約束。

2 蟻群算法求解模型

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

step1：設置初始參數；

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

step3：求最大轉移概率maxp，得到下一個點j；

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

step5：計算s，若s滿足時間窗要求，把點j放入tabu中，計算i點到j點路徑所用時間，轉step3，否則轉下一步；

step6：統計旅游次數，根據次數判斷allowed表，如果allowed表空，那么轉下一步；并轉step3，繼續搜索下一個點；

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

step8：搜索k只螞蟻最短時間路徑，更新螞蟻每條路線信息素，若有k只螞蟻均巡游一遍，則更新k只螞蟻搜索過路徑的信息素，否則，更新該次循環最優路徑；

step9：若算法循環NC_max后停止，則計算NC_max后最短路徑長度和最短路徑，最少費用和最少費用路徑，否則轉step2。

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

3 仿真結果分析

假設該旅游愛好者每年外出旅游時間不超過30天，每年外出旅游次數不超過4次，每次旅游時間不超過15天；根據個人愛好確定了每個5A級景區最少的游覽時間。景區開放時間統一規定為8：00至18：00。經過建模求解仿真如圖2所示、詳細路徑如表1所示。

根據仿真結果求得最短時間為10.5年，即在本題目約束條件下，該旅游愛好者自駕游玩全國201個5A級風景區