[發(fā)明專利]一種基于蟻群算法的智能旅游行程規(guī)劃方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201711207377.4
• 申請(qǐng)日: 2017-11-27
• 公開（公告）號(hào): CN107832894A
• 公開（公告）日: 2018-03-23
• 發(fā)明（設(shè)計(jì)）人: 宋夫華
• 申請(qǐng)（專利權(quán)）人: 浙江卓銳科技股份有限公司
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q30/06;G06Q50/14;G06N3/00
• 代理公司: 浙江永鼎律師事務(wù)所33233
• 代理人: 郭小麗

1.一種基于蟻群算法的智能旅游行程規(guī)劃方法，其特征在于，包括以下步驟：

(1)輸入游客需求信息；

(2)參數(shù)初始化：初始化系統(tǒng)運(yùn)行參數(shù)；

(3)迭代步數(shù)超限判斷：判斷迭代步數(shù)是否超限，如果超限調(diào)轉(zhuǎn)到步驟(11)步，否則繼續(xù)運(yùn)行以下步驟；

(4)基本要素約束計(jì)算

定義時(shí)間、費(fèi)用、距離三個(gè)基本要素的旅游行程規(guī)劃啟發(fā)式信息計(jì)算規(guī)則：

σij(t)=φ1α1Tout(i,j)+α2Tin(i,j);]]>

ρij(t)=φ2β1Mout(i,j)+β2Min(i,j);]]>

πij(t)=φ3γ1Dout(i,j)+γ2Din(i,j);]]>

式中φ₁、φ₂、φ₃分別為時(shí)間、費(fèi)用、距離的重要程度參數(shù)；

T_out(i,j)、T_in(i,j)分別表示行程節(jié)點(diǎn)間遷移時(shí)間和行程節(jié)點(diǎn)內(nèi)游覽時(shí)間；

M_out(i,j)、M_in(i,j)分別表示行程節(jié)點(diǎn)間花費(fèi)和行程節(jié)點(diǎn)內(nèi)花費(fèi)；

D_out(i,j)、D_in(i,j)分別表示行程節(jié)點(diǎn)間距離和行程節(jié)點(diǎn)內(nèi)距離；

α₁、α₂、β₁、β₂、γ₁、λ₂均為權(quán)值參數(shù)；

(5)時(shí)間、費(fèi)用和距離以外的其他游客偏好約束計(jì)算

在計(jì)算螞蟻個(gè)體選擇下一個(gè)可能景點(diǎn)的概率時(shí)，計(jì)算時(shí)間、費(fèi)用和距離以外的其他游客偏好約束γ_ij(t)，γ_ij(t)的表達(dá)式為：

γij(t)=Σk=1m(wt,kIt,k)(wj,kIj,k)Σk=1m(wt,kIt,k)2Σk=1m(wj,kIj,k)2]]>

其中I_j,k∈{1,2,3,4,5},k＝1,2,...,m為景點(diǎn)j的m維固有特性，I_t,k∈{1,2,3,4,5},k＝1,2,...,m為游客t的m維需求信息；w_j,k∈[0,1],k＝1,2,...,m為景點(diǎn)j的各個(gè)特性權(quán)重；w_t,k∈[0,1],k＝1,2,...,m為游客的各個(gè)需求權(quán)重；

(6)動(dòng)態(tài)控制參數(shù)計(jì)算

根據(jù)算法迭代過程，算法控制參數(shù)q₀的動(dòng)態(tài)調(diào)整公式，如下式所示：

q0=0.1+8·tT,t∈[0,T10]0.9,t∈[0.9T,T]]]>

其中t是算法當(dāng)前迭代次數(shù)，T是最大迭代次數(shù)；

(7)螞蟻個(gè)體狀態(tài)轉(zhuǎn)移概率計(jì)算

pij(t)=λijα(t)σijβ(t)ρijϵ(t)πijδ(t)γijϵ(t)Σk∈Niλikα(t)σikβ(t)ρikϵ(t)πikδ(t)γikϵ(t),j∈Ni0,j∉Ni]]>

其中，λ_ij(t)表示路徑(i，j)上的信息素強(qiáng)度；σ_ij(t)表示時(shí)間啟發(fā)式信息，ρ_ij^ε(t)表示花費(fèi)啟發(fā)式信息，π_ij(t)表示距離啟發(fā)式信息，γ_ij(t)表示游客偏好的約束；α、β、ε、δ、ε分別表示信息素濃度、啟發(fā)式信息和游客偏好約束的相對(duì)重要性；初始迭代時(shí)，路徑上的信息素被初始化為一個(gè)常數(shù)；

首先根據(jù)螞蟻個(gè)體狀態(tài)轉(zhuǎn)移概率求得各個(gè)景點(diǎn)的選擇概率，然后產(chǎn)生一個(gè)[0，1]內(nèi)均勻分布的隨機(jī)變量q，與控制參數(shù)q₀(q₀∈[0,1])進(jìn)行比較，如果q≤q₀，螞蟻個(gè)體按照已知的信息素、啟發(fā)式信息和游客偏好約束來確定下一目的景點(diǎn)j，具體確定方式為：j＝arg(max{λ_ij^α(t),σ_ij^β(t),ρ_ij^ε(t),π_ij^δ(t),γ_ij^ε(t)})；如果q＞q₀，下一目的景點(diǎn)j根據(jù)螞蟻個(gè)體狀態(tài)轉(zhuǎn)移概率公式p_ij(t)確定；

(8)局部信息素更新

螞蟻個(gè)體一邊進(jìn)行路線選擇，一邊對(duì)經(jīng)過的局部路徑進(jìn)行信息素更新，局部更新規(guī)則為：λ_ij(t)＝(1-μ)λ_ij(t)+μλ₀，其中μ是0到1之間的一個(gè)隨機(jī)變量，λ₀是初始信息素濃度；

(9)全局信息素更新

螞蟻群體構(gòu)建完成行程后，并不對(duì)所有螞蟻?zhàn)哌^的路線進(jìn)行信息素更新，而是僅對(duì)螞蟻群體中表現(xiàn)優(yōu)秀的螞蟻個(gè)體所有規(guī)劃的行程進(jìn)行全局信息度更新，全局更新規(guī)則為：

λ_ij(t)＝(1-ρ)λ_ij(t)+ρΔ_τij

其中ρ(0≤ρ≤1)表示路徑信息素的衰減度；

R_best(t)表示本次迭代所有經(jīng)過路徑(i,j)螞蟻的移動(dòng)距離之和；

(10)局部行程規(guī)劃

輸出本次迭代的局部行程規(guī)劃；

(11)規(guī)劃行程輸出

輸出規(guī)劃的旅游行程。