帶指定點集的團隊定向問題及算法研究

彭 勇，馮 禹

(重慶交通大學 交通運輸學院，重慶 400074)

?

帶指定點集的團隊定向問題及算法研究

彭 勇，馮 禹

(重慶交通大學 交通運輸學院，重慶 400074)

考慮現實世界配送問題中客戶性質不同的特點，討論了一類帶指定點集的團隊定向問題。建立了在時間限制條件下，帶指定點集的以利潤最大為目標的團隊定向問題模型。提出了帶2-opt的最大最小螞蟻系統的蟻群優化算法，結合實際改進啟發信息和信息素更新策略，采取2-opt對最優解進行優化。數值算例驗證了算法的有效性，表明了在團隊定向問題中考慮指定點集的重要性。

交通運輸工程；指定點集；團隊定向問題；蟻群優化算法

0 引 言

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

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

1 帶指定點集的團隊定向問題數學模型

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

模型的決策變量有：

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

則帶指定點集團隊定向問題的數學模型如下：

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)

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

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

2.1 啟發信息的定義

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

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

(9)

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

2.2 信息素更新策略

τ(i,j)l+1=

(10)

2.3 限定信息素濃度策略

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

(11)

(12)

2.4 路徑構建策略

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

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

(13)

(14)

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

2.5 最優解優化策略

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

3 數值算例

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

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

表1 各客戶坐標、服務時間和收益值

(續表1)

No.XY服務時間收益值備注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二級代理商公司

配送關系分布見圖1，假設各客戶間的路上時間與各客戶間距離比率為1。

圖1 配送關系分布Fig.1 Scatter of customers

以下所示算例均在CPU2.53 GHz、內存2 GB的計算機上連續進行10次運算。

3.1 無指定點集約束

路徑數為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。

路徑數為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。

路徑數為4時，求出的最大收益值均為4 920，此時所有點均已遍歷。路徑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。

由上可知，無指定點約束，路徑數為2、3、4時形成的每條路徑用時均在規定的最長時間限制Tmax=100內。無指定點集約束，路徑數為2時的虛擬路徑如圖2，對應的最大收益值如圖3。

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

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

3.2 帶指定點集約束

路徑數為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，兩條路徑包含了指定點集S=[5,20]，同時兩條路徑耗時分別為t1= 95.060 0、t2=94.700 0。

路徑數為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條路徑包含了指定點集S=[5,20]，同時3條路徑耗時分別為t1=95.590 0、t2= 79.180 0、t3= 94.490 0。

路徑數為4時，求出的最大收益值均為4 920，此時所有點均已遍歷，相當于自身資源充足時不受指定點集的約束。路徑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。

由上可知，帶指定點約束，路徑數為2、3、4時形成的每條路徑用時均在規定的最長時間限制Tmax=100內。帶指定點集約束，路徑數為2時的虛擬路徑如圖4，對應的最大收益值如圖5。

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

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

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

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

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

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

4 結 語

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

進一步的工作可以考慮在算法的改進研究、參數的優化設置和增加約束條件等方面開展。

[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] 柯良軍,章鶴,尚可,等.一類求解帶時間窗的團隊定向問題的改進蟻群算法[J].計算機科學,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] 段海濱.蟻群算法原理及其運用[M].北京:科學出版社,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—)，男，重慶人，副教授，博士，主要從事交通運輸規劃與管理方面的研究。E-mail: pengyong@cquc.edu.cn。

U492.3+1

A

1674-0696(2015)02-128-05