丁 一， 仲 穎， 林國龍， 溫 馨

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

?

丁 一*， 仲 穎， 林國龍， 溫 馨

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

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

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

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

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

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

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

1 問題描述和符號表示

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

2)需求點的位置及需求量已知；

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

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

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

表1 各需求點的需求量和坐標

表2 各港口之間的隨機航行時間分布情況、卸貨時間以及時間窗

符號表示：a：單位航行成本；b：每使用一艘船的固定成本；c：船舶早于時間窗到達的懲罰成本；d：船舶晚于時間窗到達的懲罰成本；Q：船舶最大載貨量；wi：船舶k為了滿足港口i的時間窗約束，在港口外的等待時間;dij：港口i到港口j的距離;qi：港口i的需求量;qik:港口i由船舶k運輸?shù)牧?

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

2 數(shù)學模型

目標函數(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)保證每個節(jié)點的運輸需求均被滿足；(3)保證每艘船舶都是始于母港，訪問客戶節(jié)點后，最后又回到母港；(4)和(5)保證每艘船最多訪問每個客戶節(jié)點1 次，且訪問后必須離開；(7)表示每個節(jié)點至少被訪問一次.

3 算法研究

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

3.1 不確定性航行時間的近似處理

圖1 隨機航行時間的線性近似圖Fig.1 The approximate linear figure of random sailing time

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

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

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

3.3 求解所用的方法

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

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

4 求解過程

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

4.1 構(gòu)造初始解

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

4.2 禁忌搜索

禁忌搜索的步驟如下：

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

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

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

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

表3 需求點之間的距離

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

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

4.4 求解結(jié)果

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

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

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

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

5 結(jié)束語

航行時間為隨機時候的總成本是1 000.6，比航行時間是確定值的時候的998.8多了1.8，這說明隨著航行時間不確定性的引入，帶來了時間窗懲罰成本的上升.海上運輸擔負著將近90%的海上貨運量，國內(nèi)外對公路運輸?shù)难芯课墨I很多，相比之下，對船舶航線，特別是不定期班輪航線的研究不多，由于不定期船舶運輸沒有固定的船期、固定的航線、以及固定的掛靠港，因此對于不定期船經(jīng)營公司來說，如何規(guī)劃船舶航線是十分重要的問題.本文根據(jù)船舶運輸?shù)奶攸c，將其抽象為隨機航行時間且?guī)в行枨髸r間窗的多重旅行商模型.運用掃描法和禁忌搜索算法，將問題分為二個階段，第一階段，通過掃描法將VRP轉(zhuǎn)化為TSP，然后用禁忌搜索算法解決TSP，并通過算例證明了算法的有效性，本文中所用到的算法，為實際不定期船舶的航線規(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] 靳鵬歡，隨機因素影響下的不定期船航次優(yōu)化研究[D]. 大連：大連海事大學， 2012: 1-11．

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

[6] 謝秉磊， 郭耀煌， 郭 強. 動態(tài)車輛路徑問題：現(xiàn)狀與展望[J]. 系統(tǒ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] 戴 韜， 楊稀麟. 考慮時間窗與隨機航行時間的船舶航線規(guī)劃[J]. 計算機工程與應用，2012， 48(25)：234-238．

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

[10] 郎茂祥， 胡思繼. 車輛路徑問題的禁忌搜索算法研究[J]. 管理工程學報，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.

國家自然科學基金項目(71301101)；上海教育委員會科研創(chuàng)新重點項目(11ZS1145)；上海市教委重點學科資助(J50704)．

1000-1190(2015)03-0387-05

U697.1

A

*E-mail: yingzhongbs1@163.com．