考慮平板車合作運(yùn)輸?shù)拇胺侄味褕?chǎng)間調(diào)度

李柏鶴, 蔣祖華， 陶寧蓉， 孟令通, 鄭 虹

(1. 上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院， 上海 200240； 2. 上海交通大學(xué) 高新船舶與 深海開發(fā)裝備協(xié)同創(chuàng)新中心， 上海 200240； 3. 上海海洋大學(xué) 工程學(xué)院， 上海 201306)

符號(hào)說明

h—工廠或堆場(chǎng)序號(hào)，h=1,2,…,k

i—運(yùn)輸任務(wù)編號(hào)，i=1,2,…,n

j—運(yùn)輸任務(wù)編號(hào),j=1,2,…,n

l—平板車編號(hào),l=1,2,…,p

mi—第i個(gè)任務(wù)分段的質(zhì)量

Q—無窮大的正數(shù)

tE—車場(chǎng)開放時(shí)間，即平板車最早可出發(fā)時(shí)間

tL—車場(chǎng)關(guān)閉時(shí)間，即平板車最晚回歸時(shí)間

xi—第i個(gè)任務(wù)是否是超重任務(wù)，即一個(gè)平板車無法運(yùn)輸，若為1表示是;若為0表示否

yil—第l輛平板車是否執(zhí)行第i個(gè)任務(wù)的0-1決策變量

zijl—第l輛平板車上第i，j個(gè)任務(wù)執(zhí)行順序的0-1決策變量，即如果第l輛平板車執(zhí)行完第i個(gè)任務(wù)后，接著執(zhí)行第j個(gè)任務(wù)，則zijl=1；否則zijl=0

zi0l—第l輛平板車執(zhí)行其最后1個(gè)任務(wù)的0-1決策變量

z0il—第l輛平板車執(zhí)行其第1個(gè)任務(wù)的0-1決策變量

α—平板車執(zhí)行所有任務(wù)的空載行駛時(shí)間權(quán)重

β—平板車執(zhí)行所有任務(wù)的等待時(shí)間權(quán)重

船舶制造是典型的拉式生產(chǎn)方式，船體建造工藝流程以中間產(chǎn)品“分段”作為組織生產(chǎn)的基本作業(yè)單元[1].分段在船塢之外的作業(yè)場(chǎng)或堆場(chǎng)進(jìn)行組立裝配、預(yù)舾裝、涂裝和舾裝等建造工藝，最后到船塢進(jìn)行總組搭載.船體分段質(zhì)量較大，一般為200～300 t，個(gè)別可達(dá)到500 t.因此，分段在作業(yè)場(chǎng)地和堆場(chǎng)之間的運(yùn)輸主要依靠重型平板車.

一般來說，船廠中的平板車資源都是有限的.目前，某大型船廠平板車的最大承重能力為425 t，將質(zhì)量超出現(xiàn)有平板車最大承重能力的單個(gè)分段，稱之為大型分段.大型分段需要采用多個(gè)平板車進(jìn)行合作運(yùn)輸.實(shí)際中，某大型船廠每天要完成約100個(gè)分段的運(yùn)輸.研究如何對(duì)船廠有限的運(yùn)輸資源進(jìn)行充分利用、如何運(yùn)輸大型分段、如何提高平板車的利用率以及如何在保證任務(wù)準(zhǔn)時(shí)進(jìn)行的情況下，降低無效作業(yè)的等待時(shí)間等問題，具有十分重要的現(xiàn)實(shí)應(yīng)用價(jià)值.

國內(nèi)外船舶分段運(yùn)輸問題的研究相對(duì)較少.Joo等[2]以拖期時(shí)間和延遲時(shí)間的權(quán)重和作為目標(biāo)函數(shù)，設(shè)計(jì)了遺傳和啟發(fā)式進(jìn)化兩種算法對(duì)問題進(jìn)行求解.Wang等[3]以船舶分段運(yùn)輸過程中平板車的空駛時(shí)間、拖期時(shí)間和延遲時(shí)間的總和作為目標(biāo)函數(shù)，提出一種貪心啟發(fā)式算法對(duì)問題進(jìn)行求解.Salehi等[4]認(rèn)為運(yùn)輸過程中排放的氣體在溫室氣體排放中占較大的比例，因此提出一個(gè)雙目標(biāo)混合整數(shù)非線性規(guī)劃，目標(biāo)函數(shù)為總運(yùn)輸成本和總碳排放量，并提出一種構(gòu)造式啟發(fā)式算法用于求解問題.Hu等[5]考慮了多個(gè)單類型平板車運(yùn)輸一個(gè)大型分段的問題，建立了以最小化完工時(shí)間為優(yōu)化目標(biāo)的數(shù)學(xué)模型，為了提高求解方法的計(jì)算性能，用貪婪插入算法和遺傳算法生成初始解，設(shè)計(jì)順序插入法求解模型.張志英等[6]構(gòu)建了考慮堆場(chǎng)信息、分段進(jìn)出場(chǎng)次序等因素的最短場(chǎng)路模型并對(duì)其進(jìn)行優(yōu)化，以最小化臨時(shí)分段移動(dòng)量和平板車在堆場(chǎng)中的行駛距離為優(yōu)化目標(biāo)，確定分段在堆場(chǎng)中的最優(yōu)停放位置和進(jìn)出場(chǎng)路.王沖等[7]為解決船廠平板運(yùn)輸車搬運(yùn)船舶分段的日程計(jì)劃問題，建立了利用最少數(shù)量的平板車完成分段搬運(yùn)作業(yè)，以及所有分段搬運(yùn)作業(yè)完成時(shí)間最小化的兩階段優(yōu)化模型，提出了基于遺傳算法的兩種編碼方法以實(shí)現(xiàn)模型求解.

上述研究均沒有考慮當(dāng)單個(gè)分段的質(zhì)量超出平板車最大承重能力時(shí)，應(yīng)該如何調(diào)度多種類型的平板車.而本文的研究目的是解決該運(yùn)輸難點(diǎn)，采用多個(gè)平板車合作運(yùn)輸大型分段的策略，且設(shè)定有多種承重能力的平板車可供選擇.同時(shí)，為了保證生產(chǎn)的準(zhǔn)時(shí)性，引入任務(wù)時(shí)間窗緊約束作為約束條件，開展具體研究.

1 問題描述

研究的問題可描述為有n個(gè)待執(zhí)行的運(yùn)輸任務(wù)和p個(gè)運(yùn)輸平板車，每個(gè)運(yùn)輸任務(wù)包括：任務(wù)編號(hào)、分段編號(hào)、分段質(zhì)量、運(yùn)輸起點(diǎn)、運(yùn)輸終點(diǎn)、運(yùn)輸時(shí)間窗(任務(wù)最早可執(zhí)行時(shí)間以及任務(wù)最晚的執(zhí)行時(shí)間)；每個(gè)運(yùn)輸平板車包括：平板車編號(hào)、平板車承重能力.每個(gè)任務(wù)必須由滿足其分段承重需求的平板車在時(shí)間窗范圍內(nèi)開始從運(yùn)輸起點(diǎn)運(yùn)送至運(yùn)輸終點(diǎn).其中對(duì)于大型分段，一個(gè)平板車由于承重能力限制無法運(yùn)輸，此時(shí)就需要多個(gè)平板車合作運(yùn)輸.某船廠的道路路口情況、堆場(chǎng)位置以及平板車停放位置如圖1所示.其中：虛線為平板車空載行駛的路徑；實(shí)線為平板車負(fù)載行駛的路徑.假設(shè)平板車L1的任務(wù)序列為任務(wù)Oi和Oj，任務(wù)Oi為將目標(biāo)分段從平直中心運(yùn)輸?shù)酵垦b平臺(tái)；任務(wù)Oj為將目標(biāo)分段從9號(hào)平臺(tái)運(yùn)輸至曲面車間.則平板車的實(shí)際執(zhí)行流程為從平板車的停放位置出發(fā)，行駛至平直中心并提取分段，負(fù)載行駛至涂裝平臺(tái)后放下分段；然后，空駛運(yùn)行至9號(hào)平臺(tái)并提取分段，負(fù)載行駛至曲面車間后空駛至平板車停放位置，結(jié)束運(yùn)輸.

圖1 道路及堆場(chǎng)布局圖Fig.1 Distribution of roads and yards

對(duì)于大型分段，兩個(gè)平板車之間的合作運(yùn)輸工作原理如圖2所示.其中：Ll為運(yùn)輸平板車序號(hào)；Bi為船舶分段；Sh為工作場(chǎng)或堆場(chǎng)序號(hào).以平板車L1和L2為例，平板車L1從車場(chǎng)出發(fā)，空駛至S1堆場(chǎng)，裝載分段B1后負(fù)載行駛至S3堆場(chǎng)，卸下分段；空駛至S5,由于分段B3是大型分段，需要L1和L2合作運(yùn)輸，所以等L1和L2均到達(dá)S5后，開始運(yùn)輸分段B3至S6.對(duì)于合作運(yùn)輸大型分段的平板車而言，若一輛平板車早到，一輛平板車晚到，將會(huì)導(dǎo)致早到的平板車只能原地等待，這在生產(chǎn)過程中是極度浪費(fèi)資源的，且等待時(shí)間也會(huì)造成生產(chǎn)進(jìn)程的滯后.因此，從平板車運(yùn)輸任務(wù)分段的全過程出發(fā)，以平板車執(zhí)行任務(wù)時(shí)的空載行駛時(shí)間和平板車由于早于時(shí)間窗到達(dá)產(chǎn)生的等待時(shí)間，或者平板車合作運(yùn)輸時(shí)產(chǎn)生的等待時(shí)間的權(quán)重和作為優(yōu)化目標(biāo)進(jìn)行研究，以期達(dá)到合作運(yùn)輸效率優(yōu)化的效果.

圖2 平板車合作運(yùn)輸示意圖Fig.2 Diagram of multi-flatcars cooperative transportation

考慮到堆場(chǎng)的實(shí)際情況以及便于堆場(chǎng)調(diào)度問題的研究，作出如下假設(shè)：① 平板車運(yùn)輸分段過程一旦開始執(zhí)行， 就不可被其他任務(wù)打斷；② 平板車在同一時(shí)刻最多只能運(yùn)輸一個(gè)分段；③ 不考慮道路因素 (道路上是否有平板車、道路寬度、道路上可以通行多少平板車)對(duì)平板車通行的影響；④ 為了方便說明， 假定大型分段的質(zhì)量不超過兩個(gè)平板車的承重能力之和；⑤ 合作運(yùn)輸?shù)钠桨遘嚳梢员３忠粯拥乃俣?

本研究要解決的問題有：① 運(yùn)輸任務(wù)的最優(yōu)序列；② 運(yùn)輸任務(wù)對(duì)應(yīng)哪些平板車執(zhí)行，大型任務(wù)由哪些平板車運(yùn)輸；③ 各個(gè)任務(wù)的開始執(zhí)行時(shí)間和完成時(shí)間.時(shí)間變量單位均為分鐘，以開始工作時(shí)間作為0點(diǎn)，其余時(shí)間均在此基礎(chǔ)上累加.

2 堆場(chǎng)間運(yùn)輸調(diào)度模型

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

建立平板車在堆場(chǎng)間的運(yùn)輸調(diào)度模型，優(yōu)化目標(biāo)在調(diào)度過程中的時(shí)間因素.首先，平板車執(zhí)行任務(wù)所消耗的時(shí)間是確定的，但平板車執(zhí)行任務(wù)之間的空載行駛時(shí)間是不確定的，其會(huì)隨著平板車上任務(wù)序列的改變而改變；其次，平板車早到堆場(chǎng)或工作場(chǎng)時(shí)，由于時(shí)間窗緊約束的原因，會(huì)使平板車產(chǎn)生等待時(shí)間；再次，由于考慮的是平板車合作運(yùn)輸?shù)拇笮头侄?，合作運(yùn)輸?shù)钠桨遘嚾绻竭_(dá)堆場(chǎng)或者工作場(chǎng)的時(shí)間不同，也會(huì)使早到的平板車產(chǎn)生等待時(shí)間.而等待時(shí)間會(huì)產(chǎn)生附加成本，即資源的浪費(fèi)，進(jìn)而影響生產(chǎn)進(jìn)程.因此，模型以平板車執(zhí)行任務(wù)的空載行駛時(shí)間與等待時(shí)間的權(quán)重和作為目標(biāo)函數(shù)，優(yōu)化運(yùn)輸成本.現(xiàn)有研究文獻(xiàn)中，以最小化任務(wù)完工時(shí)間作為目標(biāo)函數(shù)的也較多，本文模型中由于考慮了時(shí)間窗緊約束，嚴(yán)格控制每個(gè)任務(wù)的執(zhí)行時(shí)間，所以不需要優(yōu)化任務(wù)完工時(shí)間.

(1) 平板車完成所有任務(wù)的任務(wù)間空駛時(shí)間:

(2) 平板車從車場(chǎng)出發(fā)空駛到其第1個(gè)任務(wù)起點(diǎn)的時(shí)間，以及平板車執(zhí)行完任務(wù)空駛返回車場(chǎng)的時(shí)間:

(3) 平板車早于時(shí)間窗到達(dá)或者由于協(xié)同運(yùn)輸而產(chǎn)生的等待時(shí)間:

目標(biāo)函數(shù)以上述三者的權(quán)重和作為優(yōu)化目標(biāo)，使其最小化.

minf=α(f1+f2)+βf3

2.2 約束條件

(1) 非大型分段由1個(gè)且只由1個(gè)平板車進(jìn)行運(yùn)輸，大型分段由2個(gè)平板車進(jìn)行運(yùn)輸：

(2) 每個(gè)平板車上的第1個(gè)任務(wù)只有1個(gè)：

(3) 每個(gè)平板車上的最后1個(gè)任務(wù)只有1個(gè)：

(4) 平板車上執(zhí)行的相鄰2個(gè)任務(wù)之間的時(shí)間存在約束：

(5) 任務(wù)時(shí)間窗約束：

(6) 車場(chǎng)時(shí)間窗約束：

(7) 平板車承重能力與任務(wù)分段質(zhì)量約束：

(8) 對(duì)于大型分段任務(wù)來說，執(zhí)行任務(wù)的平板車必須都到任務(wù)始點(diǎn)地，任務(wù)才能開始執(zhí)行：

(9) 保證平板車上執(zhí)行完一個(gè)任務(wù)后接下來的任務(wù)要滿足在解中的出現(xiàn)次數(shù)約束：

(10) 保證平板車上執(zhí)行的任務(wù)要滿足在解中的出現(xiàn)次數(shù)約束：

(11) 決策變量的取值范圍約束：

3 基于禁忌搜索的模型求解

船舶分段堆場(chǎng)間的運(yùn)輸調(diào)度模型為混合整數(shù)線性規(guī)劃問題.對(duì)于小規(guī)模問題，可以采用商業(yè)求解器，如CPLEX求出最優(yōu)解.但在實(shí)際應(yīng)用中，需要搬運(yùn)的分段數(shù)量較大，現(xiàn)有求解器很難在有限時(shí)間內(nèi)求出高效解.禁忌搜索算法在組合優(yōu)化問題中具有較好的效果，廣泛應(yīng)用于旅行商問題以及車輛路徑問題.禁忌搜索算法依靠禁忌表的存在，可以在搜索中跳出局部最優(yōu)，不同的構(gòu)造鄰域方法也增加了鄰域空間的多樣性，具有較好的求解效果.因此，設(shè)計(jì)禁忌搜索算法在分鐘級(jí)別的時(shí)間內(nèi)高效求解模型，具有較高的實(shí)際應(yīng)用價(jià)值.

3.1 解的編碼方式

模型解的編碼與解碼方式如圖3所示.編碼方式為3個(gè)一維數(shù)組串行，表示平板車運(yùn)輸?shù)姆侄渭捌溥\(yùn)輸順序.如圖3(a)中，第1行表示任務(wù)序列編號(hào)，第2行和第3行表示任務(wù)被執(zhí)行的平板車編號(hào).若第2行和第3行的平板車編號(hào)相同，則表示該任務(wù)是由同一個(gè)平板車執(zhí)行的；若第2行和第3行平板車編號(hào)不相同， 則表示該任務(wù)是由兩個(gè)平板車合作運(yùn)輸?shù)?解碼后的運(yùn)輸方案如圖3(b)所示，即平板車1執(zhí)行第3、6、1、2個(gè)任務(wù)；平板車2執(zhí)行第4、6、5個(gè)任務(wù)；平板車3執(zhí)行第9、7、10、8個(gè)任務(wù).其中任務(wù)6為大型任務(wù)，由平板車1和平板車2合作運(yùn)輸.同理，如果考慮3個(gè)平板車合作運(yùn)輸，則用4個(gè)一維數(shù)組串行表示平板車運(yùn)輸?shù)姆侄渭斑\(yùn)輸順序.

圖3 編碼與解碼圖Fig.3 Coding and decoding

3.2 構(gòu)造初始種群

采用隨機(jī)構(gòu)造初始種群的方式，先隨機(jī)生成任務(wù)序列，再根據(jù)承重約束為每個(gè)任務(wù)分配平板車，對(duì)于大型任務(wù)則隨機(jī)產(chǎn)生兩個(gè)符合其承重約束的平板車.由于模型中存在時(shí)間窗約束，很可能構(gòu)造的個(gè)體是不可行的，但對(duì)于不可行解，在計(jì)算適應(yīng)度時(shí)會(huì)給予懲罰，所以在迭代中，不可行解會(huì)被逐漸取代.

3.3 個(gè)體適應(yīng)度評(píng)估

個(gè)體代表模型的解，個(gè)體適應(yīng)度函數(shù)就是模型需要優(yōu)化的目標(biāo)函數(shù)，對(duì)于所提模型的適應(yīng)度越低，代表個(gè)體越好.個(gè)體解碼后，可以獲得每個(gè)車的運(yùn)輸方案、計(jì)算平板車從車場(chǎng)出發(fā)至執(zhí)行第1個(gè)任務(wù)的空載行駛時(shí)間，以及執(zhí)行后續(xù)任務(wù)的空載行駛時(shí)間與執(zhí)行完所有任務(wù)后回到車場(chǎng)的空載行駛時(shí)間.在計(jì)算平板車等待時(shí)間時(shí)，首先需要注意大型任務(wù)要等到執(zhí)行大型任務(wù)的所有平板車均到達(dá)其起始點(diǎn)才可以開始執(zhí)行.大型分段的時(shí)間更新示意圖如圖4所示.由圖4可知，第1輛平板車上任務(wù)6的執(zhí)行時(shí)間要后移，因?yàn)榈?輛平板車還未到達(dá).其次，需要調(diào)整每個(gè)平板車上第1個(gè)任務(wù)的開始執(zhí)行時(shí)間，以最小化等待時(shí)間.由于任務(wù)6是大型任務(wù)，任務(wù)6的開始時(shí)間被延后，導(dǎo)致L1在執(zhí)行完任務(wù)3后存在一段等待時(shí)間，此時(shí)需要對(duì)任務(wù)6之前的任務(wù)開始執(zhí)行時(shí)間進(jìn)行調(diào)整.將任務(wù)3的開始時(shí)間延后，此時(shí)等待時(shí)間就消除了(見圖4右框).同理，第3輛平板車也需要對(duì)任務(wù)9的開始時(shí)間進(jìn)行調(diào)整，這樣可以減少平板車的等待時(shí)間.在算法求解過程中可以出現(xiàn)不可行解，但一定要對(duì)其適應(yīng)度加上一定的懲罰，且根據(jù)不可行解的出現(xiàn)情況，動(dòng)態(tài)改變懲罰系數(shù).

圖4 大型分段的時(shí)間更新示意圖Fig.4 Diagram of time update of large-blocks

3.4 鄰域結(jié)構(gòu)

如何從當(dāng)前解出發(fā)，構(gòu)造高效的鄰域解是禁忌搜索算法的核心所在.設(shè)計(jì)5種鄰域結(jié)構(gòu)，具體操作過程如下.

(1) M1.讓1個(gè)任務(wù)從1輛平板車遷移到另外1輛平板車.

步驟1在解的任務(wù)序列上隨機(jī)地選擇1個(gè)任務(wù).

步驟2若該任務(wù)是大型任務(wù)，則在滿足大型任務(wù)的承重約束下生成新的平板車賦值給解的第3行序列；若該任務(wù)不是大型任務(wù)，則在滿足任務(wù)承重約束下生成新的平板車，并賦值給解的第2行和第3行序列.

M1的具體領(lǐng)域結(jié)構(gòu)圖如圖5所示.

圖5 M1的鄰域結(jié)構(gòu)Fig.5 Neighborhood structure of M1

(2) M2.讓1輛平板車上的2個(gè)任務(wù)的執(zhí)行順序發(fā)生改變.

步驟1在解的平板車序列中隨機(jī)選擇1個(gè)平板車.

步驟2在該平板車上選擇2個(gè)任務(wù)， 交換其位置及平板車號(hào).

M2的具體領(lǐng)域結(jié)構(gòu)圖如圖6所示.

圖6 M2的鄰域結(jié)構(gòu)Fig.6 Neighborhood structure of M2

(3) M3.讓兩個(gè)車之間交換任務(wù)片段，這樣更有利于保護(hù)時(shí)間窗的約束[8].

步驟1在解的平板車序列中選擇2個(gè)平板車.

步驟2選擇平板車上除了開始和末尾的1個(gè)任務(wù)序列片段，即2個(gè)連續(xù)的任務(wù)，與另外1個(gè)平板車上的任務(wù)序列片段進(jìn)行交換.

步驟3檢查新的解是否滿足大型任務(wù)的承重約束，若不滿足，則返回步驟 1；若滿足則結(jié)束.

M3的具體領(lǐng)域結(jié)構(gòu)圖如圖7所示.

圖7 M3的鄰域結(jié)構(gòu)Fig.7 Neighborhood structure of M3

(4) M4.讓1輛車的上1個(gè)任務(wù)遷移到該車上的另1個(gè)任務(wù)的前面，以增加任務(wù)序列的多樣性.

步驟1在解的平板車序列中選擇1輛平板車.

步驟2選擇平板車上的1個(gè)任務(wù)，再選擇另外1個(gè)任務(wù).

步驟3將選擇的第1個(gè)任務(wù)遷移到選擇的第2個(gè)任務(wù)位置前.

M4的具體鄰域結(jié)構(gòu)圖如圖8所示.

圖8 M4的鄰域結(jié)構(gòu)Fig.8 Neighborhood structure of M4

(5) M5.讓1輛車的上1個(gè)任務(wù)遷移到該車上的另1個(gè)任務(wù)之后，以增加任務(wù)序列的多樣性.

步驟1在解的平板車序列中選擇1輛平板車.

步驟2選擇平板車上的1個(gè)任務(wù)，再選擇另1個(gè)任務(wù).

步驟3將選擇的第1個(gè)任務(wù)遷移到選擇的第2個(gè)任務(wù)位置后.

M5的具體鄰域結(jié)構(gòu)圖如圖9所示.

圖9 M5的鄰域結(jié)構(gòu)Fig.9 Neighborhood structure of M5

3.5 懲罰系數(shù)的更新

由于模型的約束較多，很難一直在可行解空間搜索模型的解，且對(duì)于上述5種鄰域構(gòu)造方法均不保證時(shí)間窗約束的成立，所以對(duì)于不滿足時(shí)間窗約束的個(gè)體，在計(jì)算個(gè)體適應(yīng)度時(shí)需加上額外的懲罰.文獻(xiàn)[9]通過研究證明，動(dòng)態(tài)系數(shù)的方式效果更好，即如果本次迭代中最好的解不是可行解，則懲罰系數(shù)應(yīng)變大，以減少不可行解的存在；如果本次迭代中最好的解是可行解，則懲罰系數(shù)應(yīng)變小，以增大不可行解的存在.

3.6 禁忌表及特赦規(guī)則

由于上述設(shè)定的5種鄰域結(jié)構(gòu)是不同的，所以針對(duì)每個(gè)鄰域結(jié)構(gòu)分別建立禁忌表，以防止每種策略產(chǎn)生重復(fù)的鄰域解.特赦規(guī)則為如果由禁忌表中的操作產(chǎn)生的解優(yōu)于當(dāng)前最優(yōu)解，則觸發(fā)特赦規(guī)則.對(duì)于第1種鄰域結(jié)構(gòu),用(i,l1,l2)表示任務(wù)i由Ll1車遷移到Ll2車，則用(i,l2,l1)作為禁忌元素加入到禁忌表中以防止最優(yōu)解的操作重復(fù)出現(xiàn)；同理，第2種鄰域結(jié)構(gòu)用(i,j,l)表示車Ll上任務(wù)i和任務(wù)j交換，則禁忌元素為(j,i,l)和(i,j,l)；第3種鄰域結(jié)構(gòu)用(i1,j1,l1;i2,j2,l2)表示Ll1車上(i1,j1)任務(wù)片段與Ll2車上(i2,j2)任務(wù)片段交換，則禁忌元素為(i1,j1,l2;i2,j2,l1)；第4種鄰域結(jié)構(gòu)用(i,j,l)表示Ll車上任務(wù)i遷移到任務(wù)j前面；第5種鄰域結(jié)構(gòu)用(i,j,l)表示Ll車上任務(wù)i遷移到任務(wù)j后面.禁忌長(zhǎng)度與鄰域空間有關(guān)，一般為10lgn.

4 數(shù)值試驗(yàn)

4.1 實(shí)例驗(yàn)證

表1 運(yùn)輸任務(wù)和時(shí)間窗信息表Tab.1 List of transportation tasks and time windows

表2 平板車信息Tab.2 Flatcar informations

獲得的調(diào)度結(jié)果如表3所示.由表3可知，平板車與執(zhí)行任務(wù)之間滿足承重約束；任務(wù)開始執(zhí)行時(shí)間滿足時(shí)間窗約束；第9、18、28、38號(hào)任務(wù)為大型任務(wù)，由兩輛平板車協(xié)同運(yùn)輸.實(shí)例結(jié)果驗(yàn)證了所提算法的有效性.然而，調(diào)度結(jié)果中出現(xiàn)了承重能力為425、380 t的平板車運(yùn)輸質(zhì)量為200 t分段的情況，這主要是由于調(diào)度結(jié)果是從整個(gè)調(diào)度周期的總目標(biāo)函數(shù)考慮而導(dǎo)致的.如果質(zhì)量為200 t的分段都由承重能力為250 t或270 t的平板車運(yùn)輸，很有可能造成250、270 t的平板車之后的運(yùn)輸任務(wù)不滿足時(shí)間窗約束或者運(yùn)輸成本較高，所以算法在求解時(shí)舍棄了成本較高的解.

表3 調(diào)度結(jié)果Tab.3 Scheduling results

(續(xù)表)

4.2 數(shù)值實(shí)驗(yàn)分析

4.2.1實(shí)驗(yàn)條件 為了驗(yàn)證所提禁忌搜索算法求解模型的性能，以多組船廠的實(shí)際數(shù)據(jù)進(jìn)行實(shí)驗(yàn).任務(wù)數(shù)量分別為6、8、10、12、20、30、40、50；大型任務(wù)數(shù)分別為1、1、1、1、2、3、4、5；平板車數(shù)量為2、3、4、5、6、7、8.以任務(wù)執(zhí)行時(shí)間、各任務(wù)之間的行駛時(shí)間作為輸入量.時(shí)間窗根據(jù)實(shí)際背景進(jìn)行調(diào)整.選用IBM ILOG CPLEX優(yōu)化求解器求解模型，禁忌搜索基于Java語言編寫.考慮到實(shí)際應(yīng)用及便于對(duì)比等因素，設(shè)定CPLEX求解器的求解時(shí)間為 3 600 s.

表4 小規(guī)模任務(wù)的CPLEX與禁忌搜索求解對(duì)比

由表4可知，隨著任務(wù)數(shù)和平板車數(shù)量的增加，CPLEX的求解時(shí)間急劇增加.禁忌搜索算法在任務(wù)數(shù)為6、8、10時(shí)能夠求出最優(yōu)解，在未求出最優(yōu)解的測(cè)試用例上求出近最優(yōu)解，GAP小于0.02，同時(shí)求解時(shí)間并沒有急劇增加，證明禁忌搜索算法是有效且可行的.由表5可知，當(dāng)任務(wù)數(shù)為20、平板車數(shù)為4時(shí)，CPLEX已經(jīng)在 3 600 s內(nèi)無法求出最優(yōu)解.針對(duì)較大規(guī)模的任務(wù)數(shù)和平板車數(shù)時(shí)，禁忌搜索算法均可以在80s內(nèi)求得結(jié)果，且在任務(wù)數(shù)為30、40、50時(shí)求得的結(jié)果明顯優(yōu)于CPLEX.其他任務(wù)數(shù)和平板車數(shù)上GAP均小于0.04，驗(yàn)證了禁忌搜索算法在實(shí)際應(yīng)用中具有較好的效果.

表5 中等規(guī)模任務(wù)的CPLEX與禁忌搜索求解對(duì)比

由于模型目標(biāo)函數(shù)考慮了等待時(shí)間，所以需要考慮所有任務(wù)的開始執(zhí)行時(shí)間，但是禁忌搜索算法卻不能遍歷所有任務(wù)的開始時(shí)間，只能根據(jù)時(shí)間窗和任務(wù)序列的時(shí)間連貫性進(jìn)行微調(diào)整，這就導(dǎo)致了大規(guī)模任務(wù)時(shí)禁忌搜索求解結(jié)果與最優(yōu)解在等待時(shí)間上會(huì)有一定的差距.

5 結(jié)語

考慮平板車合作運(yùn)輸?shù)拇胺侄味褕?chǎng)間的運(yùn)輸調(diào)度模型，通過平板車合作運(yùn)輸解決大型分段的運(yùn)輸難點(diǎn)，提出通過調(diào)整任務(wù)的開始時(shí)間以減小平板車的等待時(shí)間.從數(shù)值結(jié)果可以看出，所提算法在規(guī)模較大的情況下依然可以快速求得質(zhì)量較高的解，驗(yàn)證了所設(shè)計(jì)的禁忌搜索算法具有較好的效果，可用于實(shí)際生產(chǎn).但如何提高大規(guī)模問題解的精度、如何使算法求解穩(wěn)定、如何設(shè)計(jì)策略優(yōu)化平板車的等待時(shí)間等問題仍需進(jìn)一步的研究.