基于圖論的自駕游路線設(shè)計(jì)的創(chuàng)新與實(shí)踐 

代超凱++夏靜

【摘要】隨著人們生活水平的提高，越來(lái)越多的家庭以自駕游的方式旅游.如何設(shè)計(jì)符合自身要求的路線是首先要考慮的問(wèn)題.為將旅游線路設(shè)計(jì)的普適性與個(gè)性化結(jié)合，設(shè)計(jì)出一種更加符合自駕游者自身?xiàng)l件的旅游路線，結(jié)合圖論、運(yùn)籌學(xué)方法建立了旅游路線設(shè)計(jì)單目標(biāo)優(yōu)化模型，并用lingo編程實(shí)現(xiàn).

【關(guān)鍵詞】圖論；單目標(biāo)優(yōu)化；旅游線路；lingo

【基金項(xiàng)目】2015年安徽省大學(xué)生創(chuàng)新訓(xùn)練項(xiàng)目：基于圖論的自駕游路線的設(shè)計(jì)與實(shí)踐（201510380025）.

隨著經(jīng)濟(jì)的發(fā)展，家庭汽車(chē)的普及，人們不滿(mǎn)足于傳統(tǒng)的旅游方式，自駕游出行成為人們出游的重要方式.隨之人們需要一個(gè)更加符合自身要求的旅游路線.因此，以人本主義為出發(fā)點(diǎn)，將旅游線路設(shè)計(jì)的普適性與個(gè)性化結(jié)合，設(shè)計(jì)出一種更加符合自駕游者自身?xiàng)l件的旅游路線，有著極大的市場(chǎng)需求，并且會(huì)促進(jìn)整個(gè)旅游業(yè)的健康發(fā)展.

通過(guò)我們的網(wǎng)絡(luò)調(diào)查問(wèn)卷，對(duì)收集到的問(wèn)卷進(jìn)行分析，結(jié)果表明自駕游愛(ài)好者主要是大學(xué)生及上班的工作人員，自駕游出行時(shí)間主要集中在假期，影響自駕游出行路線的主要因素有時(shí)間（自駕游車(chē)程所耗費(fèi)的時(shí)間）、費(fèi)用（自駕游車(chē)程所耗費(fèi)的費(fèi)用）、路程、到達(dá)目的地所轉(zhuǎn)折的道路節(jié)點(diǎn)數(shù)等.現(xiàn)選取6個(gè)旅游景點(diǎn)作為自駕游的目的地進(jìn)行相關(guān)的線路優(yōu)化設(shè)計(jì).

一、模型假設(shè)

1.在自駕過(guò)程中汽車(chē)平均以60 km/h的速度行駛，行程中無(wú)其他意外突發(fā)事件，以最短路徑作為行車(chē)路線.

2.每天的自駕時(shí)間和旅游時(shí)間為10小時(shí)，然后就找住宿的地方休息.

3.汽車(chē)在自駕過(guò)程中耗油為0.5元/km.（包括過(guò)橋、過(guò)路費(fèi)用）.

4.旅游外出時(shí)間主要是自駕時(shí)間和旅游景點(diǎn)游玩時(shí)間，其他時(shí)間不計(jì)入.

5.每個(gè)景點(diǎn)的游玩費(fèi)用固定不變，景點(diǎn)每天都按時(shí)間正常開(kāi)放.

6.自駕游愛(ài)好者在景點(diǎn)的食宿費(fèi)用為每個(gè)景點(diǎn)所在地一戶(hù)人家一天的平均消費(fèi)費(fèi)用.

二、模型的建立與求解

把游客要游覽的每個(gè)景點(diǎn)看作圖中的一個(gè)節(jié)點(diǎn)，各景點(diǎn)之間的距離、時(shí)間、費(fèi)用看作圖中對(duì)應(yīng)邊上的權(quán)，各景點(diǎn)的線路網(wǎng)就轉(zhuǎn)化成一個(gè)加權(quán)無(wú)向圖G.自駕游愛(ài)好者從某一節(jié)點(diǎn)出發(fā)，游遍圖中的每一個(gè)節(jié)點(diǎn)有且僅有一次，最終回到出發(fā)點(diǎn)使得總時(shí)間、總費(fèi)用或總路程最優(yōu)的自駕游路線，即旅行售貨員問(wèn)題，旅行售貨員問(wèn)題是一個(gè)完全NP問(wèn)題[1].對(duì)于單目標(biāo)優(yōu)化問(wèn)題，問(wèn)題可行解的優(yōu)劣可以通過(guò)比較解的大小來(lái)判斷優(yōu)劣，從而得出問(wèn)題的最優(yōu)解[2].我們將以蕪湖為出發(fā)地，其他地點(diǎn)作為自駕游的目的地.其中，將游覽景點(diǎn)的節(jié)點(diǎn)分別記為vi（i=1表示在出發(fā)地蕪湖，i=2，3，…，6分別代表游覽景點(diǎn)黃山、杭州、舟山、揚(yáng)州、南京），通過(guò)經(jīng)緯度換算等方式計(jì)算給出以下相關(guān)的數(shù)據(jù)，分別建立了以路程最短和費(fèi)用最少為目標(biāo)函數(shù)的路線模型.

（一）以距離最優(yōu)的自駕游線路設(shè)計(jì)求解

在自駕游中，有部分旅游者旅游偏好是更想走最近的路.不考慮其他因素，距離最優(yōu)設(shè)計(jì)方法為[3]：目標(biāo)函數(shù)：min=∑6i=1∑6j=1sijxij.