動態(tài)需求下跨碼頭集卡調(diào)度問題研究

18-1-動態(tài)需求下跨碼頭集卡調(diào)度問題研究1引言隨著國際集裝箱運輸業(yè)的迅猛發(fā)展，現(xiàn)代港口集裝箱碼頭向大型化、信息化、自動化和智能化方向發(fā)展。同時，港口所面臨的經(jīng)營與競爭壓力越來越大，降低碼頭的裝卸成本，提高集裝箱的裝卸效率，是各個港口碼頭關(guān)注的重要領(lǐng)域。特別是當裝卸工藝基本確定后，裝卸設(shè)備的配置不均衡性是港口集成化運營面臨的主要難題。集裝箱卡車(簡稱集卡)運輸是集裝箱碼頭作業(yè)系統(tǒng)中的重要環(huán)節(jié)，銜接前沿岸橋和后方龍門吊的工作。目前國內(nèi)很多港務(wù)集團下港口都設(shè)有多個碼頭，各自采用內(nèi)集卡作為水平運輸資源。港口大部分集卡調(diào)度系統(tǒng)普遍采用某碼頭單管一定數(shù)量的集卡的傳統(tǒng)調(diào)度規(guī)則。傳統(tǒng)集卡分配模式是根據(jù)本碼頭的實際操作業(yè)務(wù)量，對每個碼頭配備50～60輛集卡,配備的集卡就始終為該碼頭服務(wù)直至泊位工作終止。而集裝箱碼頭的裝卸任務(wù)量在不同時段往往有較大的差別，集卡的空閑程度也不同，此種調(diào)度規(guī)則下集卡在作業(yè)量較少時會產(chǎn)生空置的情況。這種模式便于管理集卡但不利于進一步提高集裝箱碼頭機械設(shè)備的利用率，難以適應(yīng)多泊位現(xiàn)代化集裝箱碼頭生產(chǎn)管理的發(fā)展需求。因此采用集約化方式對集卡進行統(tǒng)一的跨碼頭調(diào)度是目前研究的熱點。2跨碼頭集卡調(diào)度問題描述跨碼頭集卡動態(tài)調(diào)度是根據(jù)某時刻碼頭申請的集卡需求動態(tài)地調(diào)度集卡。設(shè)立一個集卡總調(diào)度中心集約化管理港口所有的集卡,使各個碼頭共享所有的集卡。各碼頭可根據(jù)當日碼頭作業(yè)計劃向總調(diào)度中心提前預定一定數(shù)量的集卡，當某碼頭集卡無法滿足碼頭作業(yè)要求時可提出申請額外的集卡，而當碼頭有空閑集卡即可申請退訂。總調(diào)度中心可根據(jù)申請合理地就近從其他碼頭調(diào)度空置的集卡，各碼頭其余空置集卡則調(diào)回總調(diào)度中心。靈活地滿足各碼頭對集卡的不同需求，從而在保證碼頭作業(yè)效率的基礎(chǔ)上大幅度減少集卡數(shù)量并提高資源的利用率。圖1集約管理港口集卡圖2業(yè)務(wù)概述跨碼頭集卡調(diào)度的主要決策內(nèi)容是：對于任一正常作業(yè)狀態(tài)的集卡，是否將其調(diào)運至其他碼頭或總調(diào)度中心，從而滿足租用方（碼頭）的申請及退訂要求。集卡資源的分配必須遵循一定的規(guī)則，主要有以下幾點：（1）按需分配原則。需求量是各碼頭根據(jù)其實際作業(yè)情況向總調(diào)度中心申請的集卡數(shù)量。當碼頭業(yè)務(wù)較繁忙而集卡無法滿足碼頭作業(yè)需求時，需要向總調(diào)度中心額外申請的需要集卡。總調(diào)度中心分配給該碼頭的集卡數(shù)量應(yīng)不大于該碼頭的申請量，并盡量滿足碼頭的申請需求。（2）調(diào)回原則。調(diào)回原則指的是對于某碼頭申請退訂的集卡，必須調(diào)離該碼頭，即就近調(diào)度至需要的碼頭，或者調(diào)度回總調(diào)度中心。（3）就近調(diào)度原則。集卡跨碼頭調(diào)度需考慮碼頭與碼頭之間的調(diào)運成本，該成本和碼頭之間的距離有關(guān)。例如碼頭A申請退訂集卡而碼頭C申請需求額外的集卡的情況。若將集卡從碼頭A直接調(diào)運至碼頭C的距離要大于集卡從碼頭A先調(diào)運至總調(diào)度中心再從總調(diào)度中心調(diào)運至碼頭C的距離，此時則選擇后一種調(diào)運方案。圖3就近調(diào)度原則（4）工時平均原則集卡的有效工時指的是集卡調(diào)入總調(diào)度中心的時間減去上一次調(diào)出總調(diào)度中心的時間的差。為盡量均衡個集卡之間的作業(yè)強度，優(yōu)先調(diào)度有效工時少的集卡至其他碼頭作業(yè)。若將碼頭退訂的空置集卡調(diào)回總調(diào)度中心，優(yōu)先調(diào)度有效工時相對較多的集卡回調(diào)度中心。圖4工時平均原則（5）等級需求。對于難度較高的裝卸作業(yè)任務(wù)，某些碼頭可以對集卡司機的經(jīng)驗等級提出要求。例如在處理危險品貨物的情況下，可申請經(jīng)驗較為豐富的司機操作作業(yè)。3集卡跨碼頭調(diào)度模型構(gòu)建3.1符號定義（1）維度（實體）的表示符號t，表示第t輛待調(diào)度的集卡。i/j，表示第i/j個碼頭，模型中將總調(diào)度中心設(shè)置為一個虛擬碼頭。l，表示集卡對應(yīng)的司機經(jīng)驗等級，從高到低依次可分為甲、乙、丙、丁四個等級。（2）已知參數(shù)的表示符號，binary，用于描述第t輛集卡是否處于第j個碼頭。1表示第t輛集卡當前時刻處于第j個碼頭，0則相反。，用于描述第j個碼頭的集卡需求量。由各碼頭根據(jù)當前作業(yè)情況提出申請。，用于描述碼頭j的特殊等級需求。表示碼頭j對司機等級為l的集卡的需求量。它與裝卸貨物的特征有關(guān)。，binary，表示碼頭j是否有特殊等級需求。1表示碼頭j有水平等級l的需求，0則相反。，用于描述碼頭i申請的司機水平等級為l的集卡退訂數(shù)量。，用于描述集卡從第i個碼頭調(diào)度到第j個碼頭的調(diào)運成本。它和碼頭i的碼頭j之間的距離有關(guān)。，binary，表示第t輛集卡對應(yīng)的司機經(jīng)驗等級。1表示集卡t對應(yīng)的司機經(jīng)驗等級為等級l，0則相反。，用于描述集卡t的有效工時。，binary，1表示碼頭i是總調(diào)度中心，0則相反。，表示碼頭j分配集卡資源的優(yōu)先系數(shù)。描述碼頭對于需要集卡調(diào)度的重要程度。（3）決策變量的表示符號，模型的決策變量，binary，用于計算是否將集卡t調(diào)運至碼頭j。3.2模型約束條件構(gòu)建（1）按需分配限制根據(jù)各碼頭向總調(diào)度中心提出的申請，可獲得當前時刻碼頭集卡的空閑狀態(tài)。當碼頭業(yè)務(wù)較繁忙而集卡無法滿足碼頭作業(yè)需求時，就反饋所另需的集卡數(shù)量至總調(diào)度中心，即可得實時集卡需求量。在盡量滿足各碼頭需求的前提下，總調(diào)度中心安排實際調(diào)度出的集卡數(shù)量應(yīng)不超過統(tǒng)計的需求量，以免造成資源浪費以及增加調(diào)度成本。圖5按需分配原則模型中該約束方程表示如下：不等式的左邊，為關(guān)于t，j的二維01矩陣，對t求和后得到調(diào)度至碼頭j的集卡數(shù)量。不等式的右邊是實時統(tǒng)計的碼頭j的集卡需求量。為滿足資源需求限制，使得左邊小于等于右邊。（2）調(diào)回約束當碼頭的作業(yè)任務(wù)所需的集卡數(shù)量小于原先預定的集卡數(shù)量時，就會造成部分集卡處于空置的狀態(tài)，空置集卡的數(shù)量即可為該碼頭申請的集卡退訂量。對于某碼頭申請退訂的集卡，必須調(diào)離該碼頭。因此，實際調(diào)出的l等級集卡應(yīng)等于申請的退訂量。圖6調(diào)回原則模型中該約束方程表示如下：等式的左邊，二維01矩陣、和相乘可得關(guān)于t，j，i，l的四維01矩陣，其中1表示從碼頭i調(diào)出且對應(yīng)司機等級為l的集卡被調(diào)度至了碼頭j，0則表示該集卡t未被調(diào)度至了碼頭j。對j，t求和，可得到從碼頭i調(diào)出且對應(yīng)司機等級為l的集卡數(shù)量。等式的右邊，變量表示碼頭i申請的司機等級為l的集卡退訂數(shù)量。等式兩邊乘以，表示碼頭i為總調(diào)度中心時，該約束不起作用。令左邊等于右邊，對集卡調(diào)回量進行約束。（3）等級需求約束。在某些特殊情況下，各碼頭需要根據(jù)業(yè)務(wù)的情況申請一定數(shù)量的特定等級的集卡。例如在處理危險品貨物的情況下，需要經(jīng)驗等級為甲級的司機操作作業(yè)。在集卡調(diào)度時應(yīng)盡量滿足碼頭對集卡司機經(jīng)驗等級的要求，同時實際調(diào)出的該等級的集卡應(yīng)不超過需求量。圖7等級需求原則模型中該約束方程表示如下：不等式的左邊，二維01矩陣和二維01矩陣相乘可表示得關(guān)于t，j，l的三維01矩陣，其中1表示對應(yīng)司機等級為l的集卡t被調(diào)度至了碼頭j，0則表示該集卡t未被調(diào)度至了碼頭j。對t求和，可得到調(diào)度至碼頭j且對應(yīng)司機等級為l的集卡數(shù)量。不等式的右邊，變量表示碼頭j對司機等級為l的集卡的需求數(shù)量。令左邊右邊，對調(diào)度至各碼頭且為各特定等級的集卡數(shù)進行約束。（4）唯一性約束該約束保證一輛空置集卡只能分配給一個碼頭。集卡t指派給碼頭i后，就不能再將其指派給碼頭j。圖8唯一性約束模型中該約束方程表示如下：3.3模型的目標函數(shù)構(gòu)建（1）目標1——最大化集卡調(diào)運數(shù)量最大化集卡調(diào)運數(shù)量指的是在不超過碼頭所申請的集卡需求量的前提下，盡量滿足該碼頭的需求，即分配量最大。滿足該限制原則的目標函數(shù)可表示如下：表示集卡調(diào)度至各碼頭應(yīng)考慮優(yōu)先系數(shù)?？紤]到在實際調(diào)運中，集卡t應(yīng)優(yōu)先調(diào)度至其他碼頭j，不考慮分配給作為一虛擬碼頭的總調(diào)度中心。因此，為保證集卡可被調(diào)運至需要的碼頭，對于，總調(diào)度中心的優(yōu)先系數(shù)應(yīng)遠小于其他碼頭。表示調(diào)度至碼頭j的集卡數(shù)量，使其最大化，即盡量滿足碼頭的需求。（2）目標2——最小化調(diào)運成本集卡跨碼頭調(diào)度需考慮碼頭與碼頭之間的調(diào)運成本，即和碼頭之間的距離有關(guān)。若將集卡調(diào)運至碼頭i，應(yīng)從與其距離最短的碼頭j調(diào)運。集卡調(diào)運的總成本可表示如下：表示集卡t從碼頭i調(diào)運至碼頭j的調(diào)運距離，對其求和可得所有被調(diào)度的集卡的總調(diào)運距離。使最小化，即可實現(xiàn)該子目標。（3）目標3——優(yōu)先調(diào)回工時較長的集卡為滿足工時平均化原則，將碼頭退訂的空置集卡調(diào)回總調(diào)度中心時，應(yīng)優(yōu)先調(diào)度有效工時相對較多的集卡回調(diào)度中心。即對于調(diào)回總調(diào)度中心的所有集卡，其有效工時之和應(yīng)最大化。該目標函數(shù)可表示如下：表示調(diào)回總調(diào)度中心的集卡t的有效工時，對其求和可得調(diào)回總調(diào)度中心的所有集卡的有效工時之和。使其最大化，可實現(xiàn)該子目標。（4）目標4——優(yōu)先調(diào)派工時較短的集卡如從總調(diào)度中心調(diào)出集卡，則優(yōu)先調(diào)度有效工時少的集卡至其他碼頭作業(yè)。即從總調(diào)度中心調(diào)出的所有集卡的有效工時最小。該目標函數(shù)可表示如下：表示從總調(diào)度中心調(diào)出的集卡t的有效工時，對其求和可得從總調(diào)度中心調(diào)出的所有集卡的有效工時之和。使最小化，可實現(xiàn)該子目標。（5）目標5——盡量滿足對集卡等級的特殊需求碼頭在處理特殊貨物時，對集卡對應(yīng)司機的經(jīng)驗等級有特殊的需求。最大等級需求分配指的是對于某個特定的司機經(jīng)驗等級，在不超過碼頭申請的集卡需求量的前提下，盡量滿足該碼頭的等級需求，即是該等級分配量最大。表示對應(yīng)司機等級為l的集卡調(diào)度至了碼頭j，乘以二維01矩陣后，使得該目標只對有特殊等級需求的碼頭有效。則表示調(diào)度至碼頭j且對應(yīng)司機等級為l的集卡數(shù)量，使其最大化，即盡量滿足碼頭的等級需求。（6）總目標函數(shù)本模型是一個多目標規(guī)劃問題，總的目標函數(shù)可表達如下：a、b、c、d為目標函數(shù)的優(yōu)先因子。子目標5是子目標1的特例，因此兩目標之間優(yōu)先滿足目標5，而子目標1的重要級又高于其余子目標，因此本目標函數(shù)的優(yōu)先級取即可。4模型求解及算例分析4.1模型求解4.2算例分析某港口設(shè)有四個碼頭進行生產(chǎn)作業(yè)，分別為碼頭A、碼頭B、碼頭C及碼頭D。假設(shè)總調(diào)度中心配置有30輛集卡，分別為T01、T02、T03……T30，碼頭可根據(jù)需求提前預定。而集卡對應(yīng)的司機經(jīng)驗等級，從高到低依次可分為甲、乙、丙、丁四個等級。4.2.1已知參數(shù)數(shù)據(jù)（1）集卡信息總調(diào)度中心配置有30輛集卡，其中12輛甲等級集卡，7輛乙等級集卡，5輛丙等級集卡及6輛丁等級集卡。具體集卡對應(yīng)的司機經(jīng)驗等級的矩陣可表示為下表：表1由上矩陣可知，矩陣元素為1的則表示該集卡對應(yīng)某特定司機等級，例如集卡T01對應(yīng)的司機等級為甲等級，集卡T21對應(yīng)的司機等級為丙等級。（2）集卡位置信息根據(jù)當天計劃，碼頭A提前預定9輛集卡，其中5輛甲等級集卡和4輛乙等級集卡。碼頭B預定5輛集卡，其中3輛丙等級和2輛丁等級。碼頭C預定7輛集卡，其中4輛甲等級集卡、2輛乙等級集卡和1輛丙等級集卡。碼頭D預定4輛集卡，其中3輛丁等級集卡和1輛甲等級集卡。而總調(diào)度中心剩余5輛集卡，其中2輛甲等級集卡、1輛丁等級集卡、1輛丙等級集卡和1輛乙等級集卡。集卡具體情況可見下矩陣：表2由上矩陣可知，集卡T01、T02…T09分配給碼頭A，集卡T10、T11…T14分配給碼頭B，集卡T15、T16…T21分配給碼頭C，集卡T22、T23…T25分配給碼頭D，而剩余的集卡T26、T27…T30由總調(diào)度中心管理。（3）碼頭需求數(shù)據(jù)碼頭需求可分為對集卡數(shù)量的需求以及對特定等級的需求，碼頭集卡需求量包含特殊等級的集卡需求數(shù)。碼頭A需求3輛集卡，其中甲等級集卡3輛。碼頭B需求2輛集卡，其中乙等級集卡2輛。碼頭C不需要集卡。碼頭D需求3輛集卡，無經(jīng)驗等級的特殊需求。具體需求情況見下矩陣：表3申請需求甲乙丙丁總需求碼頭A33碼頭B22碼頭C碼頭D3（4）特殊等級退訂數(shù)據(jù)根據(jù)當前的作業(yè)情況，碼頭A處理危險品貨物的裝卸，需要經(jīng)驗豐富的司機進行操作作業(yè)，因此將不滿足條件的4輛乙等級集卡退訂，并需求3輛甲等級的集卡。碼頭C退訂1輛甲等級集卡，碼頭B、碼頭D則無特定等級退訂量。其矩陣可如下所示：表4退訂需求甲乙丙丁碼頭A4碼頭B碼頭C1碼頭D（5）調(diào)運成本集卡的調(diào)運成本與碼頭之間的距離有關(guān)。該港口四個碼頭的位置如圖1所示，根據(jù)碼頭之間距離的相對比例，調(diào)運成本可用如下矩陣表示。表5調(diào)運成本總調(diào)度中心碼頭A碼頭B碼頭C碼頭D總調(diào)度中心15151723碼頭A15102245碼頭B15101236碼頭C17221220碼頭D23453620（6）有效工時集卡的有效工時指的是集卡調(diào)入總調(diào)度中心的時間減去上一次調(diào)出總調(diào)度中心的時間的差。該港口在調(diào)運集卡時考慮集卡的工作時間。集卡具體情況如下表所示。表6集卡有效工時集卡有效工時集卡有效工時T018T114T213T024T126T222T035T137T234T043T142T241T057T158T256T069T164T263T073T177T275T082T185T284T095T197T297T104T207T3054.2.2結(jié)果分析決策結(jié)果如下表所示。表7調(diào)運方案碼頭A碼頭B碼頭DT061T071T081T091T151T261T271T281圖9決策結(jié)果最優(yōu)調(diào)運方案為：將集卡T06、T08從碼頭A調(diào)運至碼頭B，集卡T07、T09從碼頭A調(diào)運至碼頭D，集卡T15從碼頭C調(diào)運至碼頭A，集卡T26、T27從總調(diào)度中心調(diào)運至碼頭A，集卡T28從總調(diào)度中心調(diào)運至碼頭D。（1）滿足按需分配原則。根據(jù)申請需求，總調(diào)度中心分配給碼頭A的集卡數(shù)量應(yīng)不超過3輛，分配給碼頭B的集卡數(shù)量應(yīng)不超過2輛，分配給碼頭D的集卡數(shù)量應(yīng)不超過3輛，并盡量滿足碼頭的申請需求。總調(diào)度中心將為T15、T26、T27的3輛集卡分配給碼頭A，將為T06、T08的2輛集卡分配給碼頭B，將為T07、T08、T28的3輛集卡分配給碼頭D，均滿足按需分配原則。（2）滿足調(diào)回原則。碼頭A申請退訂的4輛集卡，2輛被調(diào)運至碼頭B，2輛被調(diào)度至碼頭D。碼頭C申請退訂的1輛集卡，被調(diào)度至碼頭A。滿足某碼頭申請退訂的集卡，必須調(diào)離該碼頭的原則。（3）滿足最大等級需求分配。根據(jù)申請?zhí)厥獾燃壭枨螅傉{(diào)度中心分配給碼頭A的甲等級集卡數(shù)量應(yīng)不超過3輛，分配給碼頭B的乙等級集卡數(shù)量應(yīng)不超過2輛?？傉{(diào)度中心分配給碼頭A為T15、T26、T27的3輛集卡均為甲等級，分配給碼頭B為T06、T08的2輛集卡均為乙等級。在不超過碼頭申請的集卡需求量的前提下，盡量滿足該碼頭的等級需求。（4）滿足最小調(diào)運成本。碼頭A申請需求3輛甲等級集卡，碼頭B申請需求2輛乙等級集卡，碼頭C申請需求3輛集卡?？紤]各碼頭之間的距離，將碼頭C退訂的1輛甲等級集卡以及總調(diào)度中心的2輛甲等級車調(diào)運至碼頭A，將碼頭A退訂的2輛乙等級集卡調(diào)運至碼頭B，將碼頭A退訂的另2輛集卡以及總調(diào)度中心的1輛集卡調(diào)運至碼頭D。在滿足特殊需求的情況下，此時的調(diào)運距離最短，調(diào)運成本最小為237。由于從碼頭A至碼頭D的距離比至其他碼頭距離長，兩碼頭間的集卡調(diào)運數(shù)量增加，調(diào)運成本增加的幅度也會提高。若將碼頭A退訂的1輛集卡調(diào)運至碼頭B，另3輛集卡調(diào)運至碼頭D，此時總調(diào)運成本增加至238。（5）滿足工時平均原則。根據(jù)具體情況，需要從總調(diào)度中心調(diào)1輛集卡至碼頭D。總調(diào)度中心的集卡T26已分配給碼頭A，剩余的4輛集卡T27、T28、T29、T30的有效工時分別為5、4、7、5。選擇調(diào)運有效工時最少的集卡T28，滿足優(yōu)先調(diào)度有效工時少的集卡至其他碼頭作業(yè)的原則。而退訂的集卡無調(diào)回總調(diào)度中心的情況，因此優(yōu)先調(diào)度有效工時相對較多的集卡回調(diào)度中心的原則不作考慮。（6）滿足唯一性約束。進行調(diào)度的集卡T06、T07、T08、T09、T15、T26、T27、T28，都只分配給一個碼頭，滿足唯一性約束。4.3求解效率分析通過進行大量的算例分析及系統(tǒng)測試，可證明此決策系統(tǒng)性能良好，在實際進行決策的過程中能保持高效率的運行計算。不同的算例所需計算時間及占用內(nèi)存對比情況如下表所示。此決策系統(tǒng)在變量數(shù)較多的情況下仍能保證所需的計算時間較短，且占用內(nèi)存較小，運行性能良好，求解效率較高，可運用于實際的問題求解。算例碼頭數(shù)集卡數(shù)變量數(shù)SolvingTimePeakMem算例1210200.02sec1.1Mb算例2220400.02sec1.2Mb算例3320600.03sec1.3Mb算例43401200.05sec1.8Mb算例54301200.04sec1.6Mb算例64401200.05sec1.8Mb算例75241200.04sec1.7Mb算例85402000.07sec2.1Mb算例96503000.09sec2.7Mb算例106603600.09sec2.8Mb下圖表為各算例計算時間的對比情況，變量個數(shù)為20~120的算例，所需計算時間呈遞增趨勢且增勢平緩；而變量個數(shù)為200~360的算例，所需計算時間呈遞增趨勢且增幅較之前略大。下圖表為各算例占用內(nèi)存的對比情況，變量個數(shù)為20~120的算例，占用內(nèi)存的大小呈遞增趨勢且增勢平緩；而變量個數(shù)為2