帶二維裝箱約束的團隊定向問題模型及優化算法

彭 勇，宋其勤

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

帶二維裝箱約束的團隊定向問題模型及優化算法

彭 勇，宋其勤

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

研究了在車輛服務資源有限、貨物有特殊裝載要求和其他因素影響下，為了能獲得最大效益而采取特殊物流配送的問題——帶二維裝箱約束的團隊定向問題。在對該問題進行明確定義基礎上，建立了相應的數學模型；針對模型特點，設計了以遺傳算法為框架，利用基于BLF的算法確保二維裝箱約束的模型啟發式算法。數值算例驗證了算法的有效性。

交通運輸工程；團隊定向問題；二維裝箱約束；遺傳算法

0 引 言

團隊定向問題(team orienteering problem, TOP)是一類特殊的車輛配送路徑優化問題[1-2]，它尋求的是收益最大化。比如，在配送服務中，對每位服務客戶，企業將根據配送服務情況獲取一定收益(比如送貨費)，但由于客戶配送時間要求、車輛不足等各方面條件限制，企業無法為所有客戶提供服務，此時，企業面臨的決策將是如何充分利用自身能力，獲取更多收益的問題。

車輛路徑問題作為網絡優化問題中最基本的問題之一，一直受到學者的關注。彭勇等[3-4]在綜合考慮車輛行駛速度隨時間、路段不同而變化的特點，及車輛為多條路線上的客戶提供服務時對車輛路徑優化的影響后，分別運用粒子群算法以及Dijkstra-GA算法對路徑進行優化；李毅等[5]針對車輛路徑問題中單倉庫非滿載這一基本類型的具體特性，設計了一種混沌粒子群算法，較快得出最優路徑。在物流配送實踐中，不能只考慮路徑最優，部分貨物由于易損、易碎等原因，導致裝車貨物可能無法疊放。目前，有學者在對所有客戶均需要提供服務的車輛配送路徑優化中考慮該約束條件[6]。但對于團隊定向問題這類不需要對所有客戶提供服務的特殊車輛配送路徑優化問題，尚未發現有文獻考慮該約束條件。即，筆者將研究帶二維裝箱約束的TOP(TOP with two-dimensional loading constraints，2L-TOP)[7-9]。該問題中，由一定數量的車輛為一定數量客戶提供服務，每輛車在進行任務安排時必須滿足車輛裝載約束(二維裝箱約束、車輛最大載重約束)和車輛最大行駛距離約束。一旦某輛為某位客戶提供服務，企業將獲得相應收益，而其他車輛將不再為該客戶重復提供服務，優化目標為總收益最大化。由于團隊定向問題只服務部分客戶，目標為收益最大化的特點，其優化算法設計與一般車輛路徑問題有差異[10-13]，而筆者所提出的問題增加了二維裝箱約束，其優化算法需要結合問題特點重新設計。

1 2L-TOP數學描述

在數學描述中，令G=(V，E)；頂點集V={1,2,…,n}，其中：1,n為同一點(車輛從1出發，結束于n)表示車場，其余為客戶需求點；E={(i,j)|i,j∈V}為邊集；頂點間距離為Dij；每個客戶點i對應一個收益wi(當該客戶所有物品均由一輛車配送到時獲取該收益)；定義Ai為客戶點i所要求配送的mi個矩形物品集合；Ai中物品總重di。Ai中物品m(Iim)為底面投影為lim(物品水平方向長度)×wim(物品垂直方向長度)的矩形(在以下數學模型中會增加一下標k表示該物品放入對應車輛)。

令車廂俯視圖(車頭在下)左下角為坐標原點，水平向右、垂直向上為坐標軸。設物品Iim左下角坐標為(vim，him)(在以下數學模型中會增加一下標k表示該物品放入對應車輛)。令K={1,2,…,vh}為車輛集合；Qk為車輛k的最大載重量，k∈K；Dmax為單車的最大行駛距離。

式中：i=2,3，…, (n-1)；k∈K；

式中：i=1,2,…,n；j=1,2,…,n；k∈K。

2L-TOP數學描述如下：

(1)

(2)

(3)

(4)

(5)

(6)

0≤vimk≤W-wimk, ?i∈{2,3,…,n-1},m∈{1,2,…,mi},k∈K

(7)

0≤himk≤L-limk, ?i∈{2,3,…,n-1},m∈{1,2,…,mi},k∈K

(8)

himk+limk≤hi′m′k, ?i,i′∈{2,3,…,n-1},m∈{1,2,…,mi},m′∈{1,2,…,mi′},k∈K,i≠i′

(9)

vimk+wimk≤vi′m′k, ?i,i′∈{2,3,…,n-1},m∈{1,2,…,mi},m′∈{1,2,…,mi′},k∈K,i≠i′

(10)

vimk≥vi′m′k, ?i,i′∈{2,3,…,n-1},m∈{1,2,…,mi},m′∈{1,2,…,mi′},k∈K,i≠i′

(11)

himk+limk≤hi′m′k, ?i,i′∈{2,3,…,n-1},m∈{1,2,…,mi},m′∈{1,2,…,mi′},k∈K,i≠i′

(12)

hi′m′k+li′m′k≤himk, ?i,i′∈{2,3,…,n-1},m∈{1,2,…,mi},m′∈{1,2,…,mi′},k∈K,i≠i′

(13)

(14)

上述整數線性規劃模型的含義如下：

式(1)給出模型優化目標為總收益最大化；式(2)、式(3)表示每一輛車均從1出發，止于n；式(4)表示每輛車到達某點次數等于離開其點次數；式(5)表示每點最多由一輛車提供一次服務；式(6)為車輛載重量限制；式(7)、式(8)表示每條路徑上物品以固定方向都能裝入車內；式(9)、式(10)表示物品不能相互疊放；式(11)～(13)保證裝箱物品能按序不受阻擋以物品裝入方向直線移進移出；式(14)為行駛距離限制。

2 2L-TOP算法設計

針對所給數學模型，筆者設計了以遺傳算法作為算法框架，利用基于BLF的算法確保二維裝箱約束的2L-TOP啟發式算法(BLF-GA算法)。

2.1 編 碼

采用隨機小數編碼形成個體[14]。比如：可能服務客戶10個，可提供的最大車輛數K為4輛，則個體長度為：N=10+4-1=13。假設某一個體為[0.51 0.23 0.67 0.59 0.47 0.56 0.58 0.92 0.73 0.32 0.49 0.08 0.70]，解碼時，首先根據個體各基因值大小升序排列形成對應基因位置序號的一個排列[6 2 10 9 4 7 8 13 12 3 5 1 11]。將大于10的數字以0替換，進一步解碼為[6 2 10 9 4 7 8 0 0 3 5 1 0]。然后，以0為路徑分割點，進一步解碼形成2條路徑(0代表車場)如下：0→3→5→1→0；0→6→2→10→9→4→7→8→0。

但以上形成的只是可能服務路徑，實際服務路徑還需滿足車輛裝箱約束(調用基于BLF的二維裝箱算法檢驗)、載重約束和行駛里程約束。從最后提供服務的客戶開始依次向前放棄不滿足車輛裝箱約束、載重約束及行駛里程約束的客戶，最終形成滿足約束條件的實際服務路徑。

2.2 初始種群

采用“隨機”的方法生成初始種群。

2.3 適應度評價

目標函數為適應度函數。

2.4 選擇操作

輪盤賭法和精英保留策略的結合。

2.5 交 叉

采用部分映射的方法，從種群中隨機抽取兩個個體形成一組。對每組個體，若隨機生成數不大于交叉概率pc，則隨機交叉互換；否則，該組個體不進行交叉操作。經過交叉操作或未經過交叉操作的個體構成新種群的個體。不斷重復此過程，直到該過程形成的個體數量達到群體規模一半為止。如下所示，個體a，b的[5，10]段互換。

個體a：[ 0.52 0.18 0.60 0.55 0.46 |0.50 0.77 0.90 0.71 0.31 | 0.49 0.17 ]

個體b：[ 0.31 0.05 0.26 0.58 0.43 |0.86 0.31 0.73 0.42 0.39 | 0.83 0.22 ]

↓↓

個體a′：[ 0.52 0.18 0.60 0.55 0.46 |0.86 0.31 0.73 0.42 0.39 | 0.49 0.17 ]

個體b′：[ 0.31 0.05 0.26 0.58 0.43 |0.50 0.77 0.90 0.71 0.31 | 0.83 0.22 ]

2.6 變 異

對種群每一個體，若隨機生成數不大于變異概率pm，則隨機對個體某一位置的數值重新隨機生成，形成新個體；否則，不進行變異操作。如下所示，假設個體a隨機選取位置為5，對應0.45，隨機變異為0.86，形成新個體a′。

個體a：[ 0.31 0.27 0.65 0.56 0.450.58 0.77 0.84 0.73 0.33 0.85 0.72 ]

↓↓

個體a′：[ 0.31 0.27 0.65 0.56 0.860.58 0.77 0.84 0.73 0.33 0.85 0.72 ]

算法流程如下：①參數初始化；②隨機產生初始種群；③若滿足迭代次數等于最大迭代次數，轉到⑨，否則轉到④；④對種群個體解碼，計算種群個體適應值；⑤輪盤賭生成新種群；⑥交叉、變異操作；⑦采用精英保留策略，得到子代種群；⑧迭代次數增加一次，轉到③；⑨取種群最優的適應值即為最優收益，對應個體解碼后形成最優方案。

3 基于BLF的二維裝箱算法設計

針對文中模型裝箱約束條件，設計了基于BLF[9-10]的二維裝箱算法。

假設某幾位客戶配送物品形成某個裝入序列，已裝入4件物品，如圖1。首先確定這4件物品左下點(某品左下點是由該物品矩形上線段上的左下點和右線段上的左下點組成)，方法如下：

1)物品上線段上的左下點為物品的上線段以右點為原點向左延伸與該物品的左邊物體第一次相交的點或與車廂左側廂壁相交的點；若該點在某物體的下線段上，則該物品在上線段上沒有左下點(物品3的上線段在物品4的下線段上，因此，物品3的上線段無左下點)，如圖1。

圖1 物品上線段上的左下點Fig.1 Left lower point on the line segment of items

2)物品右線段上的左下點為物品右線段向下延伸與其下方物品第一次相交的點；若該點在其他物品的左線段上，則該物品在右線段上沒有左下點(物品1的右線段向下延伸交點在物品2的左線段上，物品2的右線段向下延伸交點在物品3的左線段上，因此，物品1、2右線段都無左下點)，如圖2。

圖2 物品右線段上的左下點Fig.2 Left lower point on the right line segment of items

把所有左下點按照左下點靠近車頭距離升序排序，如圖3。在放下一個物品時，首先選擇升序排列的第一個左下點放，若能放下，就將該物品放在此處，若不能，依次選擇升序排列的下一個左下點放，直到找到能放下該物品的左下點。判斷在某左下點能否放下該物品的依據是比較該左下點對應的區間長度與該物品的長度，若前者大，則能放下該物品，否則就不能。

圖3 左下點排序Fig.3 Sorting of left lower points

計算某物品左下點對應的區間長度方法：以該物品左下點為原點，向右做一條平行靠近車頭車廂壁的射線，當該射線與其他物品的左線段相交時或與車廂右壁相交時，則之間的距離為該物品左下點對應的區間長度，如圖4中的左下點1，2，3，4，5。

圖4 物品左下點對應的區間長度Fig.4 Corresponding interval lengths of left lower points of items

按以上方法裝貨時，可能不滿足模型約束。如圖5，物品4下方形成一空隙。當放置下一個物品5時，按以上放置方法，物品5可能被放入物品4下方空隙。但實際裝車過程中，物品5可能由于物品4旁邊空間不夠，受到阻擋，無法放入；或者需要向下然后左移才能放入。兩種情況均不滿足模型約束。

圖5 物品4不覆蓋物品3Fig.5 Item 3 not covered by item 4

筆者在算法中采用覆蓋方法避免發生此種情況，算法中每放入車廂一件物品后，均會首先采取如圖6和圖7的覆蓋操作，形成已放入車廂新的虛擬物品；然后再采取同樣方法尋找已放入車廂物品左下點，繼續按序放入物品。

圖6 物品4完全覆蓋物品3Fig.6 Item 3 completely covered by item 4

圖7 物品4部分覆蓋物品3Fig.7 Item 3 partly covered by item 4

圖6中，物品4完全覆蓋物品3，則把物品4和3合成，作為物品4，屬于物品3的信息都變成0。圖7中，物品4部分覆蓋物品3，則把覆蓋的部分合成到物品4里面，物品3則減少覆蓋的部分。

覆蓋處理的作用可從圖8、圖9看出。當采取覆蓋處理后，物品1放置位置從圖8所示位置變為圖9所示位置。在裝卸物品1時可沿裝車方向直接移進移出，從而在裝卸中減少物品發生碰撞可能及裝卸時間與裝卸成本。

圖8 物品1處于物品2，3左側空隙Fig.8 Item 1 is on the left side of space of item 2, 3

圖9 覆蓋保證物品1不會放入物品2，3左側空隙Fig.9 Coverage ensuring that item 1 will not be put on the left side of space of item 2, 3

4 數值算例

算法采用MATLAB實現。所有計算在操作系統Windows7、配置為Inter Core i3-2330 M、2.20 GHz、4.00 GB內存電腦上完成。

由于尚未發現2L-TOP研究文獻，難以直接驗證本文算法有效性。筆者采用調整參數的方式將問題變為已有研究文獻的TOP或2L-CVRP，間接驗證本文算法有效性。TOP選取Benchmark算例p1.2，p1.3，p1.4，2L-CVRP選取Iori提出的Benchmark算例E016-03m.dat，E021-04m.dat測試算法有效性。

在Chao測試算例p1.2，p1.3，p1.4中，為能應用本文算法，增加車長40和寬20，載重為90，物品長寬均為1，物品重量為1。由于所有物品為標準正方形且面積相對車廂面積極小，相當于無裝箱約束，同樣道理，物品重量遠小于車輛最大載重量，相當于無裝載重量約束。因此，在增加參數后，其問題與Chao測試算例無區別，計算結果可比較。利用本文算法，每個類別各計算10次，選取最好結果如表1。

表1 文中算法在Chao測試算例的結果

Chao所有測試算例給出的已有TOP算法計算用時約為20～40 s，筆者所給算法計算用時約為40～55 s，文中算法用時略高；文中計算結果與Chao測試算例所給結果基本相同(圖10)。文中算法增加了物品屬性(長、寬、重量)，算法中嵌入了裝箱算法，算法運行時間增加應在預料之中。

圖10 p1.2.b配送路徑方案和算法優化過程Fig.10 Scheme of distribution route and process of algorithm optimization for p1.2.b

綜合來看，文中算法在最優結果和效率上可以接受，說明文中算法是有效的。

在Iori測試算例中，單車行駛最大距離設置成無限大，使用筆者提出的算法，得到最優路徑，然后得到這條路徑的總長度，再與算例結果進行對比，如表2。表2中數據是2L-CVRP算例E021-04m.dat(NO.3)和E016-03m.dat(NO.1) 中的CLASS1。由于行駛距離無限制，所有客戶均會被服務，總收益也自然達到最大值(所有客戶收益總和)。因此，需要對本文算法適應函數調整為總路徑長度的倒數，即優化目標調整為最小化總路徑長度。

表2 文中算法在Iori測試算例的驗算結果

注：δ1=(文中算法優化路徑長度-測試算例所給優化路徑長度)/測試算例所給優化路徑長度。

文中算法計算結果較為接近算例所給結果。不一致主要是由于文中算法是針對文中模型設計，相對于專門針對2L-CVRP設計的算法用于2L-CVRP，文中算法計算結果有一定差異應在預料之中。但計算結果較為接近，說明文中算法是有效的。

利用算例E016-03m.dat(NO.1)數據，增加點的收益，形成2L-TOP。隨機生成15個點的收益為：V=[10 22 10 12 18 20 11 18 15 14 35 18 23 16 20]。令單車最大行駛距離=5，每個類別各計算10次，結果如表3(表中數據來自2L-CVRP算例的中的E016-03m.dat(NO.1)，包含5種類別)。圖11為使用文中算法計算10次的結果。

表3 文算法在Iori測試算例的結果

注：裝載率1=最優路徑中客戶物品的面積/(車輛數×車輛面積)；裝載率2=所有客戶物品的面積/(車輛數×車輛面積)；δ2=(裝載率2-裝載率1)/裝載率2。

從表3可見，計算時間隨物品增多成線性增長。從圖11可見，裝載率高，收益不一定高，可能的原因是個別客戶的物品占車輛較多空間或重量太重，但其支出的服務費用(服務收益)卻比較少。

5 結 語

考慮物流配送實踐，筆者提出了帶二維裝箱約束的團隊定向問題，建立了該問題的數學模型。根據所建立數學模型特點，設計了BLF-GA算法，利用Iori和Chao數據間接驗證了算法有效性。最后，給出了算法數值算例。

[1] CHAO I M, GOLDEN B L, WASIL E A. The team orienteering problem[J].EuropeanJournalofOperationalResearch, 1996, 88(3): 464-474.

[2] VANSTEENWEGEN P, SOURLAU W, OUDHEUSDEN D. The orienteering problem: a survey[J].EuropeanJournalofOperationalResearch, 2011, 209(1): 1-10.

[3] 彭勇,謝祿江,劉松.時變單車路徑問題建模及算法設計[J].重慶交通大學學報(自然科學版),2013,32(2):263-266. PENG Yong, XIE Lujiang, LIU Song. Route modeling and algorithm designing of time-dependent single vehicle[J].JournalofChongqingJiaotongUniversity(NaturalScience), 2013,32(2):263-266.

[4] 彭勇,何俊生.實時路網單車多任務物流配送路徑優化[J].重慶交通大學學報(自然科學版),2014,33(2):123-125. PENG Yong, HE Junsheng. Route optimization of multi-trip single vehicle based on real time road network[J].JournalofChongqingJiaotongUniversity(NaturalScience), 2014,33(2):123-125.

[5] 李毅,陸百川,劉春旭.車輛路徑問題的混沌粒子群算法研究[J]. 重慶交通大學學報(自然科學版),2012,31(4):842-845. LI Yi, LU Baichuan, LIU Chunxu. Research on chaos particle swarm optimization algorithm for vehicle routing problem[J].JournalofChongqingJiaotongUniversity(NaturalScience),2012,31(4):842- 845.

[6] 王征,胡祥培,王旭坪.帶二維裝箱約束的物流配送車輛路徑問題[J].系統工程理論與實踐,2011,31(12):2328-2341. WANG Zheng, HU Xiangpei, WANG Xuping. Vehicle routing problem in distribution with two-dimensional loading constraint [J].SystemsEngineeringTheory&Practice, 2011, 31(12): 2328-2341.

[7] BAKER B S, COFFMAN J E G, RIVEST R L. Orthogonal packing in two dimensions[J].SIAMJournalonComputing,1980,9(4): 846-855.

[8] BROWN D J. An improved BL lower bound[J].InformationProcessingLetters,1980,11(1):37-39.

[9] 武曉今,朱仲英.二維裝箱問題的一種實現方法[J].微型電腦應用,2003,19(4):20-23. WU Xiaojin, ZHU Zhongying. A method to solve two-dimensional loading problem[J].MicrocomputerApplications,2003,19(4):20-23.

[10] DANG Duc-cuong, GUIBADJ R N, Moukrim A. A PSO-based memetic algorithm for the team orienteering problem[J].ApplicationsofEvolutionaryComputation,2008,4974:649-658.

[11] BOULY H, DANG Duc-cuong, MOUKRIM A. A memetic algorithm for the team orienteering problem[J].ApplicationsofEvolutionaryComputation,2008,4974:49-70.

[12] DANG D C, GUIBADJ R N, MOUKRIM A. An effective PSO-inspired algorithm for the team orienteering problem[J].EuropeanJournalofOperationalResearch,2013,229(2):332-344

[13] KIM B I, LI Hong, ANDREW L J. An augmented large neighborhood search method for solving the team orienreering problem[J].ExpertSystemswithApplications,2013,40(8):3065- 3072

[14] BEAN J C. Genetic algorithms and random keys for sequencing and optimization[J].ORSAJournalonComputing,1994,6(2):154-160.

Model of Team Orienteering Problem with Two-Dimensional Loading Constraint and Its Optimization Algorithm

PENG Yong, SONG Qiqin

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

Taking the limited vehicle service resources, special goods loading requirements and other factors into account, a special logistic problem to maximize the profit — a team orienteering problem with two-dimensional loading constraint was studied. On the base of clear definition of the above problem, a corresponding mathematic model was established. Aiming at the model characteristics, a heuristic algorithm was designed, which took the genetic algorithm as a framework and made use of BLF algorithm to ensure two-dimensional loading constraint model. Numerical studies verify the effectiveness of the proposed algorithm.

traffic and transportation engineering; team orienteering problem; two-dimensional loading constraint; GA

10.3969/j.issn.1674-0696.2016.03.29

2014-10-09；

2015-01-04

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

U492.3+1

A

1674-0696(2016)03-141-06