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

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