基于0-1規(guī)劃模型旅游團(tuán)路線的設(shè)計

董飛

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

關(guān)鍵詞：0-1規(guī)劃 旅游團(tuán) 最短路

一、引言

隨著中國經(jīng)濟(jì)的快速發(fā)展，旅游產(chǎn)業(yè)在以更迅猛的速度前進(jìn)。當(dāng)下越來越多的人選擇空閑的時間去旅游，而報團(tuán)旅游成為多數(shù)人的一個選擇。對于旅游團(tuán)組織者來說設(shè)計一個合理的旅游線路，使旅游者能夠以最短的時間獲得最大的觀賞效果尤為重要。筆者以徐州潘安湖風(fēng)景區(qū)為例，以最短路模型設(shè)計最優(yōu)的旅游線路。

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

二、問題分析

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

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

三、模型建立與求解

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

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

則目標(biāo)函數(shù)為：

約束條件（設(shè)為①式）：

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

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

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

約束條件：

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

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

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

四、結(jié)語

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

參考文獻(xiàn)：

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

[2] 韓中庚.數(shù)學(xué)建模方法及其應(yīng)用（第二版）[M].北京：高等教育出版社，2009.

基金項(xiàng)目：浙江機(jī)電職業(yè)技術(shù)學(xué)院教育教學(xué)改革重點(diǎn)培育項(xiàng)目“高職高等數(shù)學(xué)趣味化教學(xué)探究”（編號：A015218314）。

（作者單位：浙江機(jī)電職業(yè)技術(shù)學(xué)院）