彭 勇，馮 禹

(重慶交通大學(xué) 交通運(yùn)輸學(xué)院，重慶 400074)

?

帶指定點(diǎn)集的團(tuán)隊定向問題及算法研究

彭 勇，馮 禹

(重慶交通大學(xué) 交通運(yùn)輸學(xué)院，重慶 400074)

考慮現(xiàn)實(shí)世界配送問題中客戶性質(zhì)不同的特點(diǎn)，討論了一類帶指定點(diǎn)集的團(tuán)隊定向問題。建立了在時間限制條件下，帶指定點(diǎn)集的以利潤最大為目標(biāo)的團(tuán)隊定向問題模型。提出了帶2-opt的最大最小螞蟻系統(tǒng)的蟻群優(yōu)化算法，結(jié)合實(shí)際改進(jìn)啟發(fā)信息和信息素更新策略，采取2-opt對最優(yōu)解進(jìn)行優(yōu)化。數(shù)值算例驗(yàn)證了算法的有效性，表明了在團(tuán)隊定向問題中考慮指定點(diǎn)集的重要性。

交通運(yùn)輸工程；指定點(diǎn)集；團(tuán)隊定向問題；蟻群優(yōu)化算法

0 引 言

在物流配送路徑優(yōu)化問題中，有這樣一類問題，由有限數(shù)量的車輛在滿足一定約束條件下，為一組具有一定報酬的顧客提供服務(wù)，由于時間或旅行成本的限制(筆者研究有時間限制的情況)，每個位置至多被訪問一次，需要優(yōu)化這些車輛的配送路徑使得車隊總收益最大化。這實(shí)際上就是團(tuán)隊定向問題(TOP)[1-3]。

在實(shí)際應(yīng)用中，部分客戶是固定客戶、當(dāng)日有配送計劃的重要客戶或者是潛在的大客戶，在資源有限、收益較難量化的情況下，考慮帶指定點(diǎn)集的團(tuán)隊定向問題十分必要。近年來國內(nèi)外眾多研究學(xué)者廣泛關(guān)注著TOP，CTOP，SDTOP，TOPMT，CTOP-IS，SDCTOP-IS，TOPCT，MCTOPMTW，TOPID等團(tuán)隊定向問題，并運(yùn)用精確算法、啟發(fā)式算法、元啟發(fā)式算法求解TOP取得不少成果，但對于帶指定點(diǎn)集的團(tuán)隊定向問題關(guān)注甚少[4-7]。筆者首先建立帶指定點(diǎn)集的團(tuán)隊定向問題數(shù)學(xué)模型，設(shè)計帶2-opt的最大最小螞蟻系統(tǒng)(MMAS)的蟻群優(yōu)化算法[8]求解該問題，最后，通過數(shù)值算例驗(yàn)證算法的有效性，及在團(tuán)隊定向問題中考慮指定點(diǎn)集的重要性。

1 帶指定點(diǎn)集的團(tuán)隊定向問題數(shù)學(xué)模型

給定一個完全圖G=(V,E)，其中V=(1,2，…,n)是點(diǎn)集，1為起點(diǎn)，n為終點(diǎn)(若將1與n設(shè)在同一地理位置，即可表達(dá)車輛從配送中心出發(fā)提供配送服務(wù)然后回到配送中心的情況)；E={(i,j)︱i,j∈V}是邊集，每個點(diǎn)i服務(wù)時間為Ti，對應(yīng)一個收益ri，cij為經(jīng)過E中邊(i,j)所需要的時間。S?V為指定點(diǎn)集，即為必須服務(wù)的點(diǎn)的集合，其他非S的點(diǎn)不一定能被訪問。因此帶指定點(diǎn)集的團(tuán)隊定向問題即要找出m條從點(diǎn)1出發(fā)到點(diǎn)n終止的路徑，使得所經(jīng)過的點(diǎn)收益最大化，每個點(diǎn)至多能訪問一次。對于每條路徑訪問相應(yīng)點(diǎn)所用時間不能超過預(yù)先規(guī)定的時間限制Tmax。

模型的決策變量有：

其中：i,j=1,2,…,n,i!=j;k=1,2,…,m。

則帶指定點(diǎn)集團(tuán)隊定向問題的數(shù)學(xué)模型如下：

s.t：

(1)

(2)

k=1,…,m

(3)

(4)

(5)

(6)

xijk∈(0,1)，1≤i

(7)

y1k=ynk,yik∈(0,1)，i=2,…,n-1;k=1,…,m

(8)

目標(biāo)函數(shù)表示總收益最大。約束條件(1)、(2)表示從起點(diǎn)1出發(fā)在n點(diǎn)結(jié)束；約束條件(3)表示路徑到達(dá)點(diǎn)j，也必須從點(diǎn)j離開，保證了路徑的連通性；約束條件(4)保證了除點(diǎn)1和n點(diǎn)的其他點(diǎn)至多被訪問一次；約束條件(5)保證了最大時間限制；約束條件(6)保證了指定點(diǎn)集必須包含在路徑中，其中q表示指定點(diǎn)的數(shù)量，約束條件(7)、(8)表示變量取值連續(xù)非負(fù)。

2 帶2-opt的最大最小螞蟻算法

2.1 啟發(fā)信息的定義

假設(shè)第k條(未完成)路徑當(dāng)前頂點(diǎn)i,A包含所有的候選可行頂點(diǎn)。假設(shè)該路徑的已用時間為Lki，對于點(diǎn)j∈A，如果該點(diǎn)不滿足約束條件(5)，則該點(diǎn)不可行。不失一般性，假設(shè)j點(diǎn)可行。為了能經(jīng)過邊(i,j)，所用時間為t(i,j)=cij+Tj。

對于帶指定點(diǎn)集的團(tuán)隊定向問題就是在包含指定點(diǎn)集的情況下，在規(guī)定的時間內(nèi)獲得最大的收益，具有較高收益時間比率的點(diǎn)對于螞蟻的吸引力更大，因此，筆者將啟發(fā)信息定義為：

(9)

式中：rj表j點(diǎn)的收益；p是指定點(diǎn)權(quán)重增長值，通過提高p的值可以增加選中指定點(diǎn)的概率。

2.2 信息素更新策略

τ(i,j)l+1=

(10)

2.3 限定信息素濃度策略

式(11)、式(12)表示信息素濃度最大最小值的計算公式，其中F(sbs)是全局最優(yōu)對應(yīng)的收益時間比，n是客戶數(shù)量，avg是每只螞蟻在構(gòu)建解的每一步中面臨的不同選擇的平均數(shù)，文中取avg=n/2，Pbest為螞蟻一次搜索到最優(yōu)解的概率參數(shù)。

(11)

(12)

2.4 路徑構(gòu)建策略

串行法利用候選鏈表以串行的方式構(gòu)造m條路徑。令起點(diǎn)終點(diǎn)固定，為了探索更多路徑，每只螞蟻的第1步隨機(jī)選擇頂點(diǎn)，再按照偽隨機(jī)比例規(guī)則〔式(11)、式(12)〕計算的概率依次選擇下一個頂點(diǎn)，直到?jīng)]有可行點(diǎn)就直接達(dá)到終點(diǎn)。

偽隨機(jī)比例規(guī)則體現(xiàn)了蟻群算法是帶有正反饋的隨機(jī)搜索算法。隨機(jī)性體現(xiàn)在位于城市i的螞蟻選擇下一個將要到達(dá)的城市j時，取q∈[0,1]的隨機(jī)數(shù)，如果q≤q0則利用先驗(yàn)知識式(13)選擇最優(yōu)的邊，否則按式(14)計算的概率選擇最優(yōu)邊。參數(shù)q0表示利用先驗(yàn)知識與探索新路徑之間的相對重要程度，取q0=0.2。

(13)

(14)

式(14)體現(xiàn)了蟻群算法的正反饋性，假設(shè)第j步時可行點(diǎn)集為Fj，依概率從Fj中選擇一個頂點(diǎn)vj+1，其中α和β是參數(shù)，用來控制信息素和啟發(fā)因子的相對重要程度。

2.5 最優(yōu)解優(yōu)化策略

筆者采取2-opt對最優(yōu)解進(jìn)行進(jìn)一步優(yōu)化，2-opt屬于局部搜索算法，對問題進(jìn)行求解時將任意兩元素位置對調(diào)，每一步對調(diào)兩元素就獲得一個新的可行解，將可行解代入目標(biāo)函數(shù)所得解與最優(yōu)解進(jìn)行比較，取較優(yōu)者為新的最優(yōu)解，如此反復(fù)得到最終最優(yōu)解。

3 數(shù)值算例

某二級代理商給客戶配送貨物需從一級代理商處(表1中1點(diǎn)，圖1中正方形)提貨出發(fā)，貨物配送完成后再回到自己公司(表1中32點(diǎn)，圖1中菱形)。由于配送時間有限，客戶只能部分配送，剩余的將在下個時間段接著配送。30個客戶的坐標(biāo)值、服務(wù)時間及收益值明細(xì)見表1，所有客戶收益和R=4 920。其中客戶5、客戶20雖然耗時較長、收益也較少，無指定點(diǎn)約束時可能訪問不到，但客戶5與該二級代理商有長期合作關(guān)系是重要客戶，客戶20是潛在客戶，配送時必須配送，因此指定點(diǎn)集S=[5,20](圖1中圓包星)。

本文算法基于MATLAB實(shí)現(xiàn)。在實(shí)驗(yàn)中算法各參數(shù)設(shè)置如下：螞蟻數(shù)量m=20，最大循環(huán)次數(shù)NC_max=200，最長時間限制Tmax=100，指定點(diǎn)權(quán)重參數(shù)增長值p=0.005，螞蟻一次搜索到最優(yōu)解的概率Pbest=0.05，信息素重要程度α=1，啟發(fā)因子重要程度β=1，信息素?fù)]發(fā)率ρ=0.2。筆者對比討論無指定點(diǎn)約束和帶指定點(diǎn)集約束時配送車輛數(shù)為2、3、4輛時的求解情況。

表1 各客戶坐標(biāo)、服務(wù)時間和收益值

(續(xù)表1)

No.XY服務(wù)時間收益值備注520600.450客戶620450.5200客戶718250.5200客戶815250.5400客戶915600.380客戶1010350.260客戶1114400.270客戶128100.380客戶138450.4200客戶1450400.4100客戶1555450.4100客戶1622400.3200客戶1710200.2150客戶1810450.480客戶1940100.3300客戶2045100.570客戶2142350.4100客戶2240150.3200客戶2330150.360客戶2435350.3300客戶2530250.2200客戶2660170.3100客戶2735420.3180客戶2824200.2250客戶2916300.2260客戶3040400.4190客戶3125320.5210客戶32322800二級代理商公司

配送關(guān)系分布見圖1，假設(shè)各客戶間的路上時間與各客戶間距離比率為1。

圖1 配送關(guān)系分布Fig.1 Scatter of customers

以下所示算例均在CPU2.53 GHz、內(nèi)存2 GB的計算機(jī)上連續(xù)進(jìn)行10次運(yùn)算。

3.1 無指定點(diǎn)集約束

路徑數(shù)為2時，求出的最大收益值均為3 530。路徑1為：1→2→16→11→13→10→29→8→7→ 25→32；路徑2為：1→27→30→24→22→19→23→ 28→31→32。兩條路徑耗時分別為t1=95.730 0、t2=86.540 0。

路徑數(shù)為3時，求出的最大收益值均為4 480。路徑1為： 1→21→24→25→28→17→8→7→29→ 31→32；路徑2為：1→27→30→15→14→22→19→ 23→32；路徑3為：1→16→6→4→3→2→18→13→ 11→32。3條路徑耗時分別為t1=87.830 0、t2=94.070 0、t3=94.920 0。

路徑數(shù)為4時，求出的最大收益值均為4 920，此時所有點(diǎn)均已遍歷。路徑1為：1→6→16→29→ 7→8→17→12→28→25→32；路徑2為：1→27→ 24→30→21→20→19→22→23→32；路徑3為：1→ 4→3→2→5→9→13→18→11→10→31→32；路徑4為：1→15→14→26→32。4條路徑耗時分別為t1=93.650 0、t2=87.270 0、t3=95.980 0、t4=78.050 0。

由上可知，無指定點(diǎn)約束，路徑數(shù)為2、3、4時形成的每條路徑用時均在規(guī)定的最長時間限制Tmax=100內(nèi)。無指定點(diǎn)集約束，路徑數(shù)為2時的虛擬路徑如圖2，對應(yīng)的最大收益值如圖3。

圖2 無指定點(diǎn)集約束，路徑數(shù)為2時虛擬路徑 Fig.2 Virtual paths when there are 2 paths without specified point set

圖3 無指定點(diǎn)集約束，路徑數(shù)為2時最大收益值變化情況Fig.3 Maximum profit when there are 2 paths without specified point set

3.2 帶指定點(diǎn)集約束

路徑數(shù)為2時，求出的最大收益值均為3 370。路徑1為：1→2→5→3→4→6→16→24→27→ 30→21→25→32；路徑2為：1→20→19→22→28→ 8→7→32，兩條路徑包含了指定點(diǎn)集S=[5,20]，同時兩條路徑耗時分別為t1= 95.060 0、t2=94.700 0。

路徑數(shù)為3時，求出的最大收益值均為4 420。路徑1為：1→14→21→20→19→22→28→31→32；路徑2為：1→30→27→24→29→8→17→7→25→ 32；路徑3為：1→2→5→3→4→6→10→13→11→ 16→32，3條路徑包含了指定點(diǎn)集S=[5,20]，同時3條路徑耗時分別為t1=95.590 0、t2= 79.180 0、t3= 94.490 0。

路徑數(shù)為4時，求出的最大收益值均為4 920，此時所有點(diǎn)均已遍歷，相當(dāng)于自身資源充足時不受指定點(diǎn)集的約束。路徑1為：1→6→18→13→10→ 17→12→32；路徑2為：1→27→16→11→29→ 8→ 7→28→23→25→31→32；路徑3為：1→30→14→ 15→26→20→19→22→32；路徑4為：1→2→5→ 9→3→4→24→21→32。4條路徑耗時分別為t1=98.000 0、t2= 91.210 0、t3=97.350 0、t4=82.390 0。

由上可知，帶指定點(diǎn)約束，路徑數(shù)為2、3、4時形成的每條路徑用時均在規(guī)定的最長時間限制Tmax=100內(nèi)。帶指定點(diǎn)集約束，路徑數(shù)為2時的虛擬路徑如圖4，對應(yīng)的最大收益值如圖5。

圖4 路徑數(shù)為2，帶指定點(diǎn)集約束時虛擬路徑Fig.4 Virtual paths when there are 2 paths with the specified point set

圖5 路徑數(shù)為2，帶指定點(diǎn)集約束時最大收益值變化情況Fig.5 Maximum profit when there are 2 paths with specified point set

與無指定點(diǎn)集約束問題比較，通常帶指定點(diǎn)集優(yōu)化路徑總收益比無指定點(diǎn)集約束問題優(yōu)化路徑總收益少，但無指定點(diǎn)集約束問題優(yōu)化路徑可能未包含重要客戶(文中帶指定點(diǎn)集路徑總收益比無指定點(diǎn)集約束問題路徑總收益少，但無指定點(diǎn)集約束問題優(yōu)化路徑未包含重要客戶5與潛在客戶20，而帶指定點(diǎn)集問題優(yōu)化路徑包含客戶5與客戶20)。這說明在無指定點(diǎn)集約束情況下優(yōu)化路徑有可能未包含企業(yè)希望服務(wù)的客戶，而指定點(diǎn)集提供了這一保障。這表明了研究帶指定點(diǎn)集問題的必要性。

圖6為各種情況下連續(xù)計算10次計算用時圖，其中無指定點(diǎn)約束路徑數(shù)為2時用“2無”簡稱，帶指定點(diǎn)約束路徑數(shù)為2時用 “2帶”簡稱，以此類推。

圖6 各種情況下連續(xù)10次計算用時Fig.6 Spending time of 10 consecutive computation in every condition

從不同路徑情況下計算結(jié)果來看，不同路徑數(shù)下算法10次計算優(yōu)化結(jié)果相同，說明算法具有很高的計算穩(wěn)定性；而從計算用時來看(圖6)，算法10次計算時間差在2 s左右，表明算法計算時間的穩(wěn)定性，而圖3、圖5最大收益值變化過程圖也表明最大收益值隨算法尋優(yōu)過程得到了很好的增加。從不同路徑數(shù)下無指定點(diǎn)集約束與帶指定點(diǎn)集優(yōu)化結(jié)果來看，無指定點(diǎn)集約束問題優(yōu)化收益通常不小于帶指定點(diǎn)集問題優(yōu)化收益，但在不能保證為所有客戶提供服務(wù)的情況下，無指定點(diǎn)集約束問題優(yōu)化結(jié)果可能未包含企業(yè)希望服務(wù)的客戶，而帶指定點(diǎn)集問題優(yōu)化結(jié)果避免此種情況的出現(xiàn)。這實(shí)際上可以理解為企業(yè)指定了一些必需服務(wù)到的客戶后進(jìn)行路徑優(yōu)化可能會以收益損失為代價。但這也表明企業(yè)在考慮長期利益等情況下形成的帶指定點(diǎn)集問題研究的重要意義。在路徑數(shù)為4時，無指定點(diǎn)集約束與帶指定點(diǎn)集問題優(yōu)化收益相同，這實(shí)際上是必然，因?yàn)楫?dāng)所有客戶都能被服務(wù)情況下，指定必需服務(wù)的客戶必然被包含其中。

4 結(jié) 語

筆者從TOP問題入手，討論了一類有服務(wù)時間限制的帶指定點(diǎn)集的團(tuán)隊定向問題，建立了有時間限制的帶指定點(diǎn)集的團(tuán)隊定向問題的模型，設(shè)計了帶2-opt的最大最小螞蟻系統(tǒng)的蟻群優(yōu)化算法。算例表明了本文提出的算法計算結(jié)果穩(wěn)定性好，對于解決帶指定點(diǎn)集的團(tuán)隊定向問題可以給出滿意的優(yōu)化解，驗(yàn)證了算法的有效性。通過對比相同路徑數(shù)時帶指定點(diǎn)約束和無指定點(diǎn)約束的求解，表明了實(shí)際應(yīng)用中，解決團(tuán)隊定向問題時考慮帶指定點(diǎn)集具有重要現(xiàn)實(shí)意義。

進(jìn)一步的工作可以考慮在算法的改進(jìn)研究、參數(shù)的優(yōu)化設(shè)置和增加約束條件等方面開展。

[1] Chao I,Golden B,Wasil E.Theory and methodology——the team orienteering problem[J].European Journal of Operational Research,1996,88:464-474.

[2] Vansteenwegen P,Souffriau W,Oudheusden D V.The orienteering problem:a survey[J].European Journal of Operational Research,2011,209(1):1-10.

[3] 柯良軍,章鶴,尚可,等.一類求解帶時間窗的團(tuán)隊定向問題的改進(jìn)蟻群算法[J].計算機(jī)科學(xué),2012,39 (4):214-216. Ke Liangjun,Zhang He,Shang Ke,et al.Improved ant colony optimization approach for the team orienteering problem with time windows[J].Computer Science,2012,39 (4):214-216.

[4] Lin S W,Yu V F.A simulated annealing heuristic for the team orienteering problem with time windows[J].European Journal of Operational Research,2012,217(1):94-107.

[5] Lin S W.Solving the team orienteering problem using effective multi-start simulated annealing [J].Applied Soft Computing,2013,13(2):1064-1073.

[6] Nacima L,Renata M,Jan M,et al.The team orienteering problem with time windows:an LP-based granular variable neighborhood search[J].European Journal of Operational Research,2012,220(1):15-27.

[7] Souffriau W,Vansteenwegen P,Berghe G V,et al.A path relinking approach for the team orienteering problem[J].Computers & Operations Research,2010,37(11):1853-1859.

[8] 段海濱.蟻群算法原理及其運(yùn)用[M].北京:科學(xué)出版社,2005:33-38. Duan Haibin.Ant Colony Algorithms:Theory and Applications[M].Beijing:Science Press,2005:33-38.

[9] Dorigo M,Stützle T.Ant Colony Optimization[M].Cambridge,MA:MIT Press,2004:70-75.

Team Orienteering Problem with Specified Point Set

Peng Yong, Feng Yu

(School of Traffic & Transportation, Chongqing Jiaotong University, Chongqing 400074, China)

The team orienteering problem with the specified point set was discussed based on the nature of customers. A mathematic team orienteering problem model with the specified point set which targets the maximized profits was established under the time constrained condition. A MMAS algorithm with 2-opt was developed to solve this problem. It improved stimulating factor and update pheromones strategy. And optimal solution was optimized with 2-opt. The numerical examples demonstrate the algorithm is available, and it is important to take the specified point set into account to solve team orienteering problem.

traffic transportation engineering; specified point set; team orienteering problem(TOP); ant colony optimization

10.3969/j.issn.1674-0696.2015.02.27

2013-08-22；

2013-11-04

彭 勇(1973—)，男，重慶人，副教授，博士，主要從事交通運(yùn)輸規(guī)劃與管理方面的研究。E-mail: pengyong@cquc.edu.cn。

U492.3+1

A

1674-0696(2015)02-128-05