基于0-1規劃模型旅游團路線的設計

董飛

摘要：基于0-1規劃模型設定目標函數與約束條件，并通過LINGO軟件求解，給出了游覽潘安湖7個景點，每個景點至少游覽一次的最短路徑安排。景點在有游覽時間和開放時間的限制下，通過增加約束條件，給出了三個旅游團景點游覽最大時長的路線安排。

關鍵詞：0-1規劃 旅游團 最短路

一、引言

隨著中國經濟的快速發展，旅游產業在以更迅猛的速度前進。當下越來越多的人選擇空閑的時間去旅游，而報團旅游成為多數人的一個選擇。對于旅游團組織者來說設計一個合理的旅游線路，使旅游者能夠以最短的時間獲得最大的觀賞效果尤為重要。筆者以徐州潘安湖風景區為例，以最短路模型設計最優的旅游線路。

潘安湖景區有游客服務中心、陽光草坪等7個景點，景點之間最短步行距離如表1所示。現有兩個問題：問題1游客從V0景石出發，步行游覽V1游客服務中心，V2陽光草坪，V3森林小劇場，V4兒童科普體驗區，V5兒童戲水場，V6濕地博物館，V7濕地商業街，找出一條以V0景石為起點，以V7濕地商業街為終點的最短路線，并且要求V1-V7每個景點至少經過一次;問題2現在有三個旅游團同時到潘安湖景區旅游，V1-V6每個景點在同一時間只能接待一個旅游團，即在某一景點后到的旅游團需等前面的旅游團游覽完才能游覽，三個旅游團步行的速度是一定的，同時V3森林小劇場，只有整點或半點才能開放，若三個旅游團第一個參觀的景點為V3則必然有等待時間，旅游團在每個景點的游覽時間在一定時間范圍內可調節，為使在景點的游覽時間最長，給出三個旅游團的瀏覽路線。

二、問題分析

對于問題1，已知任意兩個景點之間的最短步行距離，尋找從景石到濕地商業街的最短路線，且中間要經過V1-V6至少一次，景點游覽的順序不同，路線的長短也會不同。此問題看似和最短路問題相似，但不是最短路問題，最短路問題是求起點到終點的最短路，給出的中間點可以不全部通過，但此問題設定的是V1-V6至少要通過一次，所有的點通過一次，這類問題又和哈密爾頓圈問題相似，但哈密爾頓圈問題是經過所有的點最終要回到原點，這里我們所有的點不回到原點。因此，我們需要對哈密爾頓圈問題進行適當的改進以此來解決此問題。這里采用0-1規劃模型[1-2]，以所有的點連接距離最短為目標函數，添加相應的等式作為約束條件，用LINGO軟件求解此問題。

對于問題2，三個旅游團在其中游覽，為使三個旅游團在景點總的游覽時間達到最長，應該使在景點間走路的時間最短，同時應盡量錯開旅游團在同一景點同一時間的游覽，以避免等待時間。目標函數依舊為游覽所有的景點距離最短，以此來使景點間走路時間最短，同時約束條件應增加限制，錯開各旅游團的路線，利用可在某個景點游覽時間的長短，錯開兩個旅游團在同一個景區的等待時間，使游覽時間達到最長。

三、模型建立與求解

（一）問題1模型的建立與求解

用表示景點i與景點j之間的距離，引入0—1變量，表示從景點i到景點j的路線在最短路徑上，表示該路線不在最短路徑上。

則目標函數為：

約束條件（設為①式）：

對于約束條件表示從第1個點即起點出發，只有一條路連接到其他點;對于表示路中間的點只能一條路進，一條路出;對于表示第8個點即終點，只有一條路進入。通過LINGO軟件求解，得到0-1變量為1的為，旅游最短路線為V0→V3→V5→V1→V2→V4→V6→V7，最短總步行距離為1820（米）及游覽景點間具體距離如表2所示。

（二）問題2模型的建立與求解

若想增大旅游團在景點的游覽時間，必須要縮短在景點間的步行時間。游客步行速度是一定的，因此為游客設計最大的景點游覽時間線路，就是設計從景石出發到濕地商業街的最短路徑。問題1給出了從景石出發到濕地商業街的最短路徑，現在有三個旅游團對景點進行游覽，并且森林小劇場只有整點或者半點開放。問題1最短旅游路線從景石出發第一個旅游點為森林小劇場，由于森林小劇場是半點或整點開放，若第一個游覽點為森林小劇場必然會等待，因此旅行團第一個點不應該經過森林小劇場，為此應增加約束，在①式基礎上增加x14=0這個約束，于是第一個旅游團目標函數：

約束條件：

通過LINGO軟件求解，可得變量x13，x27，x35，x46，x54，x62，x78為1，所以第一個旅游團的行走線路為V0景石V2陽光草坪V4兒童科普體驗區V3森林小劇場V5兒童戲水場V1旅游服務中心V6濕地博物館V7濕地商業街。

對于第二旅游團來說，第一個游覽的點不能為森林小劇場，同時為了不等待第一個旅游團第一個游覽的點，因此第二旅游團第一個不能瀏覽的點也就是陽光草坪，因此約束條件在①式基礎上增加約束：x14=0，x13=0。通過LINGO軟件求解，可得變量x12，x26，x35，x43，x57，x64，x78為1，在第二個旅游團第一個點不游覽森林小劇場和陽光草坪的條件下，最短旅游路線為：V0景石V1旅游服務中心V5兒童戲水館V3森林小劇場V2陽光草坪V4兒童科普體驗區V6濕地博物館V7濕地商業街。

對于第三個旅游團，和第二個旅游團類似，第一個游覽的點不能為森林小劇場，同時也不能為第一個旅游團第一個游覽的點與第二個旅游團第一個游覽的點，即不能為陽光草坪與旅游服務中心，因此約束條件在①式基礎上增加約束：x14=0，x13=0，x12=0。 通過LINGO軟件求解，可得變量x16，x27，x43，x52，x64，x78為1，即第三個旅游團的最短旅游路線為：V0景石V5兒童戲水場V3森林小劇場V2陽光草坪V4兒童科普體驗區V1游客服務中心V6濕地博物館V7濕地商業街。

四、結語

旅游團安排路線是一個較為復雜的問題，本文基于0-1規劃模型給出將所有的景點都至少經過一次的最短路徑，并給出了三個旅游團旅游的時間安排。本模型還可以推廣到n個景點的最短路設計，以及m個旅游團的游覽安排。此模型利用LINGO軟件求解方便準確，以此安排旅游路線，提高了游客的游玩效率，便于旅游團旅行安排。

參考文獻：

[1] 謝金星，薛毅.優化建模與LINDO/LINGO軟件[M].北京：清華大學出版社，2005.

[2] 韓中庚.數學建模方法及其應用（第二版）[M].北京：高等教育出版社，2009.

基金項目：浙江機電職業技術學院教育教學改革重點培育項目“高職高等數學趣味化教學探究”（編號：A015218314）。

（作者單位：浙江機電職業技術學院）