任務(wù)可選的自動(dòng)化集裝箱碼頭AGV配對(duì)調(diào)度優(yōu)化

包曉瓊，鹿飛燕，胡志華

(1.上海海事大學(xué) 物流研究中心，上海 201306；2.上海海事大學(xué) 電工電子實(shí)驗(yàn)中心，上海 201306)

自動(dòng)化集裝箱碼頭中最主要的3類(lèi)作業(yè)設(shè)備為自動(dòng)化岸橋、自動(dòng)化堆垛機(jī)、自動(dòng)化導(dǎo)引車(chē)(automatic guided vehicle，AGV)。通常，一臺(tái)40 ft的AGV可以運(yùn)輸兩個(gè)20 ft的集裝箱或一個(gè)40 ft的集裝箱，而這種配置在運(yùn)輸單個(gè)20 ft的集裝箱時(shí)裝載率為50%，意味著資源浪費(fèi)。因此，采用20 ft的AGV獨(dú)立運(yùn)輸20 ft的集裝箱和配對(duì)運(yùn)輸40 ft的集裝箱是自動(dòng)化集裝箱碼頭的一種新工藝，然而這種新工藝對(duì)配對(duì)調(diào)度提出了更高的要求[1-2]。

AGV是自動(dòng)化集裝箱碼頭中最常見(jiàn)的水平運(yùn)輸設(shè)備[3]。目前AGV調(diào)度[4-5]與路徑優(yōu)化[6]的研究較多，其他也包括AGV配置問(wèn)題[7]和充電問(wèn)題[8]。HU等[9-10]從船舶分段運(yùn)輸和大件物流運(yùn)輸模式中得到啟發(fā)，提出多輛車(chē)運(yùn)輸一個(gè)貨物的多車(chē)輛單任務(wù)問(wèn)題(multi-vehicle and one-cargo transportation，MVOC)，建立混合整數(shù)規(guī)劃模型并設(shè)計(jì)貪婪算法和改進(jìn)遺傳算法求解。AGV配對(duì)調(diào)度就是一個(gè)MVOC問(wèn)題。

筆者采用20 ft AGV獨(dú)立運(yùn)輸20 ft集裝箱和配對(duì)運(yùn)輸40 ft集裝箱的新工藝，考慮任務(wù)可選模式下，按照對(duì)入選的任務(wù)進(jìn)行獎(jiǎng)勵(lì)、對(duì)延后執(zhí)行的任務(wù)進(jìn)行懲罰的策略，研究AGV配對(duì)調(diào)度問(wèn)題。將搬運(yùn)成本和懲罰成本作為約束條件，以運(yùn)輸成本、完成時(shí)間和空載時(shí)間最小化為目標(biāo)，建立混合整數(shù)規(guī)模模型。設(shè)計(jì)算例并對(duì)AGV數(shù)量、運(yùn)輸時(shí)間和操作時(shí)間3個(gè)參數(shù)進(jìn)行敏感性分析，以驗(yàn)證模型的有效性。

1 問(wèn)題描述

車(chē)輛資源有限且集裝箱裝卸搬運(yùn)作業(yè)密集是自動(dòng)化集裝箱碼頭建設(shè)進(jìn)程中的常見(jiàn)問(wèn)題。在計(jì)劃期內(nèi)考慮任務(wù)可選，入選的任務(wù)有搬運(yùn)成本，而被延后執(zhí)行的任務(wù)會(huì)產(chǎn)生懲罰成本。由20 ft AGV獨(dú)立運(yùn)輸20 ft集裝箱和配對(duì)運(yùn)輸40 ft集裝箱優(yōu)先任務(wù)的關(guān)鍵點(diǎn)是配對(duì)調(diào)度。配對(duì)調(diào)度分為3個(gè)步驟：①選擇配對(duì)，令選中的AGVs行駛至任務(wù)裝載點(diǎn)，配對(duì)成具有相應(yīng)荷載能力的搬運(yùn)車(chē)。②搬運(yùn)，配對(duì)AGVs將集裝箱從裝載點(diǎn)搬運(yùn)到卸載點(diǎn)。③分離，卸載結(jié)束后，配對(duì)AGVs自動(dòng)分離，等待后續(xù)作業(yè)命令。

在任務(wù)可選模式下，采用獎(jiǎng)懲策略，并以搬運(yùn)成本和懲罰成本為約束條件，建立混合整數(shù)規(guī)劃模型，為優(yōu)先任務(wù)匹配AGV配對(duì)調(diào)度方案。假設(shè)總?cè)蝿?wù)集合中有6個(gè)搬運(yùn)任務(wù)，每個(gè)搬運(yùn)任務(wù)對(duì)應(yīng)一個(gè)集裝箱，集裝箱尺寸Si、相應(yīng)的裝載點(diǎn)Pi和卸載點(diǎn)Di均已知。由于集裝箱尺寸、裝卸載點(diǎn)位置和起重機(jī)操作時(shí)間的差異，各任務(wù)運(yùn)輸成本不同，運(yùn)輸成本包括擱置成本和搬運(yùn)成本。以最小化運(yùn)輸成本為目標(biāo)，從6個(gè)搬運(yùn)任務(wù)中選中3個(gè)優(yōu)先任務(wù)，分別為1、3、5。引入2個(gè)虛擬任務(wù)：起點(diǎn)任務(wù)S和終點(diǎn)任務(wù)T，則優(yōu)先任務(wù)共5個(gè)。任務(wù)1中集裝箱尺寸為40 ft，需要2輛AGV配對(duì)搬運(yùn)；任務(wù)3和任務(wù)5中集裝箱尺寸為20 ft，由1輛AGV可完成搬運(yùn)，配對(duì)調(diào)度示意圖如圖1所示。

圖1 AGV配對(duì)調(diào)度示意圖

為便于建模，提出以下假設(shè)：①搬運(yùn)任務(wù)尺寸及裝卸載位置信息確定。②AGV數(shù)量、位置信息及可調(diào)度時(shí)間確定。③AGV配對(duì)和分離時(shí)間忽略不計(jì)，在裝載操作開(kāi)始之前，AGV需完成配對(duì)并等候；卸載操作結(jié)束之后，配對(duì)的AGV方可分離。④排除搬運(yùn)過(guò)程中交通堵塞、電量不足等不確定因素。⑤AGV全程無(wú)故障，勻速行駛且忽略啟動(dòng)時(shí)間。

2 任務(wù)可選的配對(duì)調(diào)度模型

(3)決策變量。yi∈{0,1}，1表示任務(wù)i為優(yōu)先任務(wù)，產(chǎn)生搬運(yùn)成本，0表示任務(wù)i為擱置任務(wù)，產(chǎn)生擱置成本；xijv∈{0,1}，1表示第v輛AGV優(yōu)先搬運(yùn)任務(wù)i后緊接著搬運(yùn)任務(wù)j，否則為0，v∈V；yiv∈{0,1},1表示第v輛AGV有參與搬運(yùn)任務(wù)i；zi表示任務(wù)i的可操作時(shí)刻。

(4)目標(biāo)函數(shù)及約束條件。在20 ft自動(dòng)化導(dǎo)引車(chē)(AGV)獨(dú)立搬運(yùn)20 ft集裝箱和配對(duì)搬運(yùn)40 ft集裝箱的自動(dòng)化集裝箱碼頭新工藝背景下，以最小化優(yōu)先任務(wù)的運(yùn)輸成本、完成時(shí)間和空載時(shí)間為目標(biāo)(如式(1)～式(4)所示)，建立任務(wù)可選配對(duì)調(diào)度的混合整數(shù)規(guī)劃模型。式(5)和式(6)表示任務(wù)i的完成時(shí)間應(yīng)晚于準(zhǔn)備時(shí)間且非負(fù)；式(7)規(guī)定了AGV服務(wù)的首個(gè)任務(wù)i的完成時(shí)間；式(8)表示AGV合理分配任務(wù)并明確其服務(wù)順序；式(9)～式(11)表示為優(yōu)先任務(wù)分配的AGV數(shù)量應(yīng)與集裝箱尺寸相一致，否則任務(wù)不能被處理，一直處于等待狀態(tài)；式(12)為作業(yè)流約束，即入度與出度相等；式(13)和式(14)表示虛擬起點(diǎn)和虛擬終點(diǎn)是AGV服務(wù)的初始任務(wù)和末任務(wù)。

minf=(fCost,fMakespan,fEmpty)

(1)

(3)

fMakespan≥zi,?i

(4)

f≥0,zi≥0,?i

(5)

zi≥Ai,?i

(6)

zi≥Rv+TLv,Pi+Ti,?i,v

(7)

zj+(1-xijv)M≥zi+Tj+TDi,Pj,?i≠j,v

(8)

(9)

(10)

(11)

xijv+xjiv≤1,?v

(12)

(13)

(14)

3 算例分析

表1 搬運(yùn)任務(wù)參數(shù)值

表2 AGV參數(shù)設(shè)置

采用GUROBI求解器,使用PYTHON語(yǔ)言編譯求解模型，得到3個(gè)算例的最優(yōu)作業(yè)序列及運(yùn)輸成本、完成時(shí)間和空載時(shí)間。算例1的AGV配對(duì)時(shí)序圖如圖2所示，其中矩形區(qū)域中的數(shù)字表示AGV正在完成的任務(wù)序列，矩形的長(zhǎng)度表示時(shí)間的長(zhǎng)短。算例2和算例3的AGV作業(yè)銜接序列如表3和表4所示。

圖2 算例1的AGV配對(duì)時(shí)序圖

算例1從20個(gè)總?cè)蝿?wù)集合中選中13個(gè)優(yōu)先任務(wù)(包含2個(gè)虛擬任務(wù))，其中20 ft集裝箱共4個(gè)(任務(wù)編號(hào)為1、5、8、17)，40 ft集裝箱共7個(gè)(任務(wù)編號(hào)為3、6、7、10、13、15、16)，由8輛AGV搬運(yùn)優(yōu)先任務(wù)的完成時(shí)間為37 206，運(yùn)輸成本為61 188。例如7# AGV的搬運(yùn)任務(wù)有4個(gè)，即獨(dú)立運(yùn)輸任務(wù)1，分別與2#、3#和5# AGV配對(duì)搬運(yùn)優(yōu)先任務(wù)13、15和6。

算例2由9輛AGV 配對(duì)完成23個(gè)優(yōu)先任務(wù)，包括8個(gè)20 ft集裝箱和15個(gè)40 ft集裝箱，完成時(shí)間為45 292，運(yùn)輸成本為108 719。

表3 算例2 的AGV作業(yè)銜接序列

表4 算例3的AGV作業(yè)銜接序列

算例3從40個(gè)總?cè)蝿?wù)集合中選中28個(gè)優(yōu)先任務(wù)，包括13個(gè)20 ft集裝箱和15個(gè)40 ft集裝箱，并由13輛AGV 配對(duì)搬運(yùn)，完成時(shí)間為26 784，運(yùn)輸成本為106 881。

4 實(shí)驗(yàn)驗(yàn)證

在算例3(40個(gè)搬運(yùn)任務(wù)20輛AGV)的基礎(chǔ)上設(shè)計(jì)3組實(shí)驗(yàn)場(chǎng)景，以研究AGV數(shù)量、運(yùn)輸時(shí)間和操作時(shí)間的敏感性并分析模型的特征。場(chǎng)景描述及參數(shù)調(diào)整如表5所示。

表5 實(shí)驗(yàn)場(chǎng)景和參數(shù)調(diào)整

圖3 AGV數(shù)量變化對(duì)結(jié)果的影響

圖4 運(yùn)輸時(shí)間Tij變化對(duì)結(jié)果的影響

圖5 操作時(shí)間Ti變化對(duì)結(jié)果的影響

(1)AGV數(shù)量變化對(duì)結(jié)果的影響。由圖3可知，運(yùn)輸成本和完成時(shí)間呈波動(dòng)逆向變化，即運(yùn)輸成本增加時(shí)，完成時(shí)間相應(yīng)減少。當(dāng)AGV數(shù)量處于12～20輛時(shí)，運(yùn)輸成本和完成時(shí)間之和波動(dòng)下降。當(dāng)AGV配置數(shù)量達(dá)到20輛時(shí)，運(yùn)輸成本和完成時(shí)間之和最??；當(dāng)AGV數(shù)量在12～16輛之間時(shí)，空載時(shí)間變化較小，之后波動(dòng)下滑，但當(dāng)AGV數(shù)量達(dá)到26輛時(shí)，空載時(shí)間顯著增加。根據(jù)以上分析，以運(yùn)輸成本、完成時(shí)間和空載時(shí)間為指標(biāo)，以搬運(yùn)成本和擱置成本為約束，可為搬運(yùn)任務(wù)匹配合理的AGV數(shù)量。

(2)運(yùn)輸時(shí)間變化對(duì)結(jié)果的影響。由圖4可知，隨著運(yùn)輸時(shí)間的增加，運(yùn)輸成本逐步增加，完成時(shí)間和空載時(shí)間呈波動(dòng)增加，在運(yùn)輸時(shí)間為初始值時(shí)空載時(shí)間略有下降。完成時(shí)間對(duì)運(yùn)輸時(shí)間變化的敏感性較低，可知在搬運(yùn)成本和擱置成本約束條件下，該算法可以最優(yōu)的匹配方式調(diào)度AGV搬運(yùn)待完成任務(wù)。

(3)操作時(shí)間變化對(duì)結(jié)果的影響。由圖5可知，隨著操作時(shí)間的增加，運(yùn)輸成本、完成時(shí)間和空載時(shí)間均波動(dòng)上升。相較于實(shí)驗(yàn)場(chǎng)景2，運(yùn)輸成本和空載時(shí)間對(duì)操作時(shí)間變化的敏感性均增強(qiáng)。

5 結(jié)論

采用由20 ft的AGV獨(dú)立運(yùn)輸20 ft集裝箱和配對(duì)運(yùn)輸40 ft集裝箱的新工藝，在車(chē)輛資源有限且集裝箱裝卸搬運(yùn)作業(yè)密集的環(huán)境中，考慮計(jì)劃期內(nèi)選擇部分任務(wù)優(yōu)先完成，并對(duì)延后的任務(wù)進(jìn)行懲罰。以搬運(yùn)成本和擱置成本為主要約束條件，以運(yùn)輸成本、完成時(shí)間和空載時(shí)間最小化為目標(biāo)建立混合整數(shù)規(guī)劃模型。設(shè)計(jì)自動(dòng)化集裝箱碼頭算例和數(shù)據(jù)集，研究AGV數(shù)量、運(yùn)輸時(shí)間和操作時(shí)間的敏感性，結(jié)果表明運(yùn)輸成本對(duì)操作時(shí)間和運(yùn)輸時(shí)間敏感性較低，而完成時(shí)間和空載時(shí)間對(duì)這兩個(gè)參數(shù)敏感度較高，且空載時(shí)間對(duì)兩個(gè)參數(shù)的敏感性比完成時(shí)間高。以上實(shí)驗(yàn)驗(yàn)證了模型的有效性，并可獲得合理的配對(duì)調(diào)度方案，具有良好的可行性，對(duì)降低成本、提高碼頭效益也具有實(shí)際意義。