帶二維裝箱約束的團(tuán)隊(duì)定向問題模型及優(yōu)化算法

彭 勇，宋其勤

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

帶二維裝箱約束的團(tuán)隊(duì)定向問題模型及優(yōu)化算法

彭 勇，宋其勤

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

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

交通運(yùn)輸工程；團(tuán)隊(duì)定向問題；二維裝箱約束；遺傳算法

0 引 言

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

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

1 2L-TOP數(shù)學(xué)描述

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

令車廂俯視圖(車頭在下)左下角為坐標(biāo)原點(diǎn)，水平向右、垂直向上為坐標(biāo)軸。設(shè)物品Iim左下角坐標(biāo)為(vim，him)(在以下數(shù)學(xué)模型中會(huì)增加一下標(biāo)k表示該物品放入對應(yīng)車輛)。令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數(shù)學(xué)描述如下：

(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)

上述整數(shù)線性規(guī)劃模型的含義如下：

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

2 2L-TOP算法設(shè)計(jì)

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

2.1 編 碼

采用隨機(jī)小數(shù)編碼形成個(gè)體[14]。比如：可能服務(wù)客戶10個(gè)，可提供的最大車輛數(shù)K為4輛，則個(gè)體長度為：N=10+4-1=13。假設(shè)某一個(gè)體為[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]，解碼時(shí)，首先根據(jù)個(gè)體各基因值大小升序排列形成對應(yīng)基因位置序號(hào)的一個(gè)排列[6 2 10 9 4 7 8 13 12 3 5 1 11]。將大于10的數(shù)字以0替換，進(jìn)一步解碼為[6 2 10 9 4 7 8 0 0 3 5 1 0]。然后，以0為路徑分割點(diǎn)，進(jìn)一步解碼形成2條路徑(0代表車場)如下：0→3→5→1→0；0→6→2→10→9→4→7→8→0。

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

2.2 初始種群

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

2.3 適應(yīng)度評價(jià)

目標(biāo)函數(shù)為適應(yīng)度函數(shù)。

2.4 選擇操作

輪盤賭法和精英保留策略的結(jié)合。

2.5 交 叉

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

個(gè)體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 ]

個(gè)體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 ]

↓↓

個(gè)體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 ]

個(gè)體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 變 異

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

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

↓↓

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

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

3 基于BLF的二維裝箱算法設(shè)計(jì)

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

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

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

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

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

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

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

圖3 左下點(diǎn)排序Fig.3 Sorting of left lower points

計(jì)算某物品左下點(diǎn)對應(yīng)的區(qū)間長度方法：以該物品左下點(diǎn)為原點(diǎn)，向右做一條平行靠近車頭車廂壁的射線，當(dāng)該射線與其他物品的左線段相交時(shí)或與車廂右壁相交時(shí)，則之間的距離為該物品左下點(diǎn)對應(yīng)的區(qū)間長度，如圖4中的左下點(diǎn)1，2，3，4，5。

圖4 物品左下點(diǎn)對應(yīng)的區(qū)間長度Fig.4 Corresponding interval lengths of left lower points of items

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

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

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

圖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看出。當(dāng)采取覆蓋處理后，物品1放置位置從圖8所示位置變?yōu)閳D9所示位置。在裝卸物品1時(shí)可沿裝車方向直接移進(jìn)移出，從而在裝卸中減少物品發(fā)生碰撞可能及裝卸時(shí)間與裝卸成本。

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

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

4 數(shù)值算例

算法采用MATLAB實(shí)現(xiàn)。所有計(jì)算在操作系統(tǒng)Windows7、配置為Inter Core i3-2330 M、2.20 GHz、4.00 GB內(nèi)存電腦上完成。

由于尚未發(fā)現(xiàn)2L-TOP研究文獻(xiàn)，難以直接驗(yàn)證本文算法有效性。筆者采用調(diào)整參數(shù)的方式將問題變?yōu)橐延醒芯课墨I(xiàn)的TOP或2L-CVRP，間接驗(yàn)證本文算法有效性。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中，為能應(yīng)用本文算法，增加車長40和寬20，載重為90，物品長寬均為1，物品重量為1。由于所有物品為標(biāo)準(zhǔn)正方形且面積相對車廂面積極小，相當(dāng)于無裝箱約束，同樣道理，物品重量遠(yuǎn)小于車輛最大載重量，相當(dāng)于無裝載重量約束。因此，在增加參數(shù)后，其問題與Chao測試算例無區(qū)別，計(jì)算結(jié)果可比較。利用本文算法，每個(gè)類別各計(jì)算10次，選取最好結(jié)果如表1。

表1 文中算法在Chao測試算例的結(jié)果

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

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

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

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

表2 文中算法在Iori測試算例的驗(yàn)算結(jié)果

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

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

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

表3 文算法在Iori測試算例的結(jié)果

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

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

5 結(jié) 語

考慮物流配送實(shí)踐，筆者提出了帶二維裝箱約束的團(tuán)隊(duì)定向問題，建立了該問題的數(shù)學(xué)模型。根據(jù)所建立數(shù)學(xué)模型特點(diǎn)，設(shè)計(jì)了BLF-GA算法，利用Iori和Chao數(shù)據(jù)間接驗(yàn)證了算法有效性。最后，給出了算法數(shù)值算例。

[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] 彭勇,謝祿江,劉松.時(shí)變單車路徑問題建模及算法設(shè)計(jì)[J].重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版),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] 彭勇,何俊生.實(shí)時(shí)路網(wǎng)單車多任務(wù)物流配送路徑優(yōu)化[J].重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版),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]. 重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版),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].系統(tǒng)工程理論與實(shí)踐,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] 武曉今,朱仲英.二維裝箱問題的一種實(shí)現(xiàn)方法[J].微型電腦應(yīng)用,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—)，男，重慶人，教授，博士，主要從事交通運(yùn)輸規(guī)劃與管理方面的研究。E-mail:pengyong@cqjtu.edu.cn。

U492.3+1

A

1674-0696(2016)03-141-06