軟時(shí)間窗與隨機(jī)航行時(shí)間的不定期船舶航線規(guī)劃

丁 一， 仲 穎， 林國(guó)龍， 溫 馨

(上海海事大學(xué) 科學(xué)研究院， 上海 201306)

?

丁 一*， 仲 穎， 林國(guó)龍， 溫 馨

(上海海事大學(xué) 科學(xué)研究院， 上海 201306)

為優(yōu)化航線設(shè)計(jì)，降低船舶企業(yè)運(yùn)營(yíng)成本，在研究VRP(Vehicle Routing Problem)的基礎(chǔ)上，將其方法擴(kuò)展應(yīng)用到不定期船舶調(diào)度問題，船舶運(yùn)輸需要在路徑優(yōu)化時(shí)同時(shí)考慮不確定航行時(shí)間及需求時(shí)間窗，用線性近似的方法來消除不確定航行時(shí)間的影響，通過懲罰函數(shù)的引入表示需求時(shí)間窗，建立充分考慮時(shí)間因素的數(shù)學(xué)模型，以總成本最小為目標(biāo).運(yùn)用掃描法和禁忌搜索算法，將問題分為二個(gè)階段，第一階段，通過掃描法將VRP轉(zhuǎn)化為TSP(Traveling Salesman Problem)，然后用禁忌搜索算法解決TSP，通過算例證明了提出算法的有效性，為實(shí)際不定期船舶的航線規(guī)劃提供了參考.

時(shí)間窗； 隨機(jī)航行時(shí)間； 航線規(guī)劃； 掃描法； 禁忌搜索算法

一般將船舶運(yùn)輸模式分為3類，分別為工業(yè)船運(yùn)、不定期船運(yùn)和班輪船運(yùn)[1].不定期船運(yùn)輸是指無固定航線、固定掛靠港口和班期的一種船舶營(yíng)運(yùn)方式，在整個(gè)水路運(yùn)輸中占有相當(dāng)高的比重.

對(duì)于帶時(shí)間窗的VRP的研究， Archetti[2]等提出了第一個(gè)求解SDVRPTW (Vehicle Routing Problems with Split Deliveries and Time Windows)的精確算法，他們運(yùn)用禁忌搜索算法和新的有效不等式對(duì)子問題分別求解，一種新的啟發(fā)式算法則被用于尋找最優(yōu)拆分點(diǎn).

對(duì)于VRPST(Vehicle Routing Problem with Stochastic Travel Time)的研究，Zheng和Liu[3]運(yùn)用一種混合智能算法求解車輛模糊旅行時(shí)間問題.

綜上所述，國(guó)內(nèi)外關(guān)于運(yùn)輸路徑優(yōu)化的問題，重點(diǎn)在于研究車輛路徑問題，但是在國(guó)際貿(mào)易中，海上運(yùn)輸擔(dān)負(fù)著將近90%的海上貨運(yùn)量，船舶航線規(guī)劃問題與車輛路徑問題相比較，有其自己的特性.首先，船舶單次的行程比較長(zhǎng)，時(shí)間也更久，航行時(shí)間較容易受天氣等多種因素的影響[4]，因此其隨機(jī)性較大；其次，碼頭的設(shè)備數(shù)量和規(guī)模有所限制，船舶特別是大型船舶卸貨時(shí)間也較長(zhǎng)，因此時(shí)間窗是不容忽視的；此外，船舶載貨量大，一般是單次行程服務(wù)于多個(gè)需求點(diǎn)，再回到配送中心的.本文是在研究VRP問題[5-7]的基礎(chǔ)上，將其方法擴(kuò)展應(yīng)用到不定期船舶調(diào)度問題，船舶運(yùn)輸需要在路徑優(yōu)化時(shí)同時(shí)考慮不確定航行時(shí)間及需求時(shí)間窗，這兩個(gè)因素的引入都會(huì)使得原本就是NP-Hard的TSP問題更加復(fù)雜，用線性近似的方法來消除不確定航行時(shí)間的影響[8]，通過懲罰函數(shù)的引入表示需求時(shí)間窗.運(yùn)用掃描法[9]和禁忌搜索算法，將問題分為二個(gè)階段，第一階段，通過掃描法將VRP轉(zhuǎn)化為TSP，然后用禁忌搜索算法[10]解決TSP.

1 問題描述和符號(hào)表示

1)物流配送中心的位置為已知且唯一，設(shè)置配送中心為0；

2)需求點(diǎn)的位置及需求量已知；

3)需求點(diǎn)與需求點(diǎn)的線路與距離為已知且確定；

4)船舶經(jīng)過需求點(diǎn)時(shí)只有卸貨而無裝貨，貨物配送完畢后以空船返回配送中心；

5)船舶的最大載重量相同.

表1 各需求點(diǎn)的需求量和坐標(biāo)

表2 各港口之間的隨機(jī)航行時(shí)間分布情況、卸貨時(shí)間以及時(shí)間窗

符號(hào)表示：a：?jiǎn)挝缓叫谐杀?；b：每使用一艘船的固定成本；c：船舶早于時(shí)間窗到達(dá)的懲罰成本；d：船舶晚于時(shí)間窗到達(dá)的懲罰成本；Q：船舶最大載貨量；wi：船舶k為了滿足港口i的時(shí)間窗約束，在港口外的等待時(shí)間;dij：港口i到港口j的距離;qi：港口i的需求量;qik:港口i由船舶k運(yùn)輸?shù)牧?

opi：港口i的卸貨時(shí)間；[ei，li]：港口i的時(shí)間窗.

2 數(shù)學(xué)模型

目標(biāo)函數(shù)：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

qij≥0,wi≥0,

(9)

yik=0或1 ?ixijk=0或1 ?i，?j.

(10)

式(1)表示確保船舶不超過最大載重量；(2)保證每個(gè)節(jié)點(diǎn)的運(yùn)輸需求均被滿足；(3)保證每艘船舶都是始于母港，訪問客戶節(jié)點(diǎn)后，最后又回到母港；(4)和(5)保證每艘船最多訪問每個(gè)客戶節(jié)點(diǎn)1 次，且訪問后必須離開；(7)表示每個(gè)節(jié)點(diǎn)至少被訪問一次.

3 算法研究

算法的思想：以確定的航行時(shí)間求得初始解，再構(gòu)造虛擬時(shí)間窗，以虛擬時(shí)間窗的懲罰函數(shù)代替初始的懲罰函數(shù)，進(jìn)行兩次求解，最后獲得修正解.

3.1 不確定性航行時(shí)間的近似處理

圖1 隨機(jī)航行時(shí)間的線性近似圖Fig.1 The approximate linear figure of random sailing time

3.2 虛擬時(shí)間窗的構(gòu)造

軟時(shí)間窗下懲罰函數(shù)：

虛擬時(shí)間窗下的懲罰函數(shù)：

3.3 求解所用的方法

3.3.1 掃描法 Gillett和Miller于1974年所提出的求解車輛路線問題的方法，此方法屬于先分群再排路線的方式.該方法采用極坐標(biāo)來表示各需求點(diǎn)的區(qū)位，然后任取一需求點(diǎn)為起始點(diǎn)，定其角度為零度，以順時(shí)鐘或逆時(shí)鐘方向，以車容量為限制條件進(jìn)行服務(wù)區(qū)域之分割，進(jìn)行車輛配送的分組作業(yè)，由此實(shí)現(xiàn)將VRP轉(zhuǎn)化為TSP.3.3.2禁忌搜索法 禁忌搜索算法最早是由

Glover 提出的，它是一種“局部搜索”的修正方法，從一些初始解開始，試圖找到更好的解，然后從這個(gè)新的解開始，繼續(xù)尋找好的解，這一過程不斷重復(fù)，直到找到的解不再改善為止.

4 求解過程

采用“先分組再排線路”的二階段求解方法，進(jìn)行配送線路的安排.

4.1 構(gòu)造初始解

以掃描法為基礎(chǔ)，修改其演算方法進(jìn)行初始解的構(gòu)造，此算法可以達(dá)到先分組的目標(biāo)，而且此方法在選擇配送點(diǎn)進(jìn)行求解時(shí)，可以將臨近的點(diǎn)選入同一群組中，滿足初始解的基本需求.而在船舶路線規(guī)劃方面，在構(gòu)造初始路線時(shí)，加入“船舶載重限制”的條件，使得初始解的每一群組均能滿足此限制.

4.2 禁忌搜索

禁忌搜索的步驟如下：

1)輸入需求點(diǎn)的數(shù)據(jù)；

2)設(shè)定參數(shù)，禁忌名單長(zhǎng)度設(shè)為4，最大重復(fù)搜尋次數(shù)設(shè)為100；

3)目標(biāo)函數(shù)和移步.

在計(jì)算目標(biāo)函數(shù)值之前，首先建立一個(gè)對(duì)稱矩陣，存放兩兩需求點(diǎn)之間的距離.計(jì)算目標(biāo)函數(shù)值時(shí)，使用點(diǎn)對(duì)交換(Pair Swap)的節(jié)點(diǎn)交換法作為禁忌搜索法的移步方法，來達(dá)到臨近搜尋的目的.

表3 需求點(diǎn)之間的距離

4.3 最優(yōu)解的改善

建立初始解所使用的掃描法，被納入組中的需求點(diǎn)就無法在不同的路線中跳動(dòng)，得到較差的初始解結(jié)果.此處使用兩種不同線路中交換節(jié)點(diǎn)的方法來彌補(bǔ)這個(gè)缺陷，期望能在需求點(diǎn)盡量相鄰的條件下，找出更好的路線規(guī)劃.

4.4 求解結(jié)果

以0點(diǎn)為原點(diǎn)，任意做一條射線，逆時(shí)針方向掃描，得到7種初始解，如表4所示.

表4 掃描法求解結(jié)果

表5 最終求解結(jié)果

圖2 航線規(guī)劃最終結(jié)果Fig.2 The end results of route planning

5 結(jié)束語(yǔ)

航行時(shí)間為隨機(jī)時(shí)候的總成本是1 000.6，比航行時(shí)間是確定值的時(shí)候的998.8多了1.8，這說明隨著航行時(shí)間不確定性的引入，帶來了時(shí)間窗懲罰成本的上升.海上運(yùn)輸擔(dān)負(fù)著將近90%的海上貨運(yùn)量，國(guó)內(nèi)外對(duì)公路運(yùn)輸?shù)难芯课墨I(xiàn)很多，相比之下，對(duì)船舶航線，特別是不定期班輪航線的研究不多，由于不定期船舶運(yùn)輸沒有固定的船期、固定的航線、以及固定的掛靠港，因此對(duì)于不定期船經(jīng)營(yíng)公司來說，如何規(guī)劃船舶航線是十分重要的問題.本文根據(jù)船舶運(yùn)輸?shù)奶攸c(diǎn)，將其抽象為隨機(jī)航行時(shí)間且?guī)в行枨髸r(shí)間窗的多重旅行商模型.運(yùn)用掃描法和禁忌搜索算法，將問題分為二個(gè)階段，第一階段，通過掃描法將VRP轉(zhuǎn)化為TSP，然后用禁忌搜索算法解決TSP，并通過算例證明了算法的有效性，本文中所用到的算法，為實(shí)際不定期船舶的航線規(guī)劃提供了參考.

[1] Meng Q， Wang S， Henrik A，et al. Containership routing and scheduling in liner shipping: Overview and future research directions[J]. Transportation Science， 2013， 0461:1-16.

[2] Archetti C， Bouchard M， Desaulniers G. Enhanced branch and price and cut for vehicle routing with Split deliveries and time windows[J].Transportation Science， 2011， 45(3)： 285-298.

[3] Zheng Y， Liu B. Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm[J]. Applied Mathematics and Computation， 2005， 176(2)：673-683．

[4] 靳鵬歡，隨機(jī)因素影響下的不定期船航次優(yōu)化研究[D]. 大連：大連海事大學(xué)， 2012: 1-11．

[5] 李 娜. VRP在支線船舶調(diào)度中的擴(kuò)展應(yīng)用研究[D].大連：大連海事大學(xué)， 2006; 1-41．

[6] 謝秉磊， 郭耀煌， 郭 強(qiáng). 動(dòng)態(tài)車輛路徑問題：現(xiàn)狀與展望[J]. 系統(tǒng)工程理論方法應(yīng)用， 2002， 11(2): 116-120．

[7] Archetti C， Feillet D， Gendreau M， et al. Complexity of the VRP and SDVRP[J]. Transportation Research Part C， 2011， 19: 741-750.

[8] 戴 韜， 楊稀麟. 考慮時(shí)間窗與隨機(jī)航行時(shí)間的船舶航線規(guī)劃[J]. 計(jì)算機(jī)工程與應(yīng)用，2012， 48(25)：234-238．

[9] 邱愛華. 掃描法和遺傳算法在物流配送車輛優(yōu)化調(diào)度中的應(yīng)用研究[D]. 北京：北京交通大學(xué)，2008: 1-42．

[10] 郎茂祥， 胡思繼. 車輛路徑問題的禁忌搜索算法研究[J]. 管理工程學(xué)報(bào)，2004， 18(1)：81-84．

Tramp ship routing plan with soft time window and random sailing time

DING Yi， ZHONG Ying， LIN Guolong， WEN Xin

(Institute of Science， Shanghai Maritime University， Shanghai 201306)

This paper is based on the study of VRP problems， and the method is extended to tramp scheduling problem， using a linear approximation method to eliminate the uncertain effect of the time of sailing and introducing a penalty function to deal with the time window. Using the scanning method and the tabu search algorithm， which divided the problem into two stages， the scanning method converted the VRP into TSP. Then the tabu search algorithm was utilized to solve the TSP with an example to prove the performance of the proposed algorithm. which provided a reference for the tramp ship when making route plan．

time window; stochastic travel time; ship route planning; scanning method; tabu search algorithm

2014-12-24.

國(guó)家自然科學(xué)基金項(xiàng)目(71301101)；上海教育委員會(huì)科研創(chuàng)新重點(diǎn)項(xiàng)目(11ZS1145)；上海市教委重點(diǎn)學(xué)科資助(J50704)．

1000-1190(2015)03-0387-05

U697.1

A

*E-mail: yingzhongbs1@163.com．