【文章內容簡介】 卡具有更高的優(yōu)先考慮級別，也就是在集卡分配過程中，可以出現(xiàn)集卡等待岸橋，但不允許出現(xiàn)岸橋等待集卡。在現(xiàn)實情況下，岸橋的購置成本要遠遠高于集卡的購置成本，因此在港口作業(yè)過程中應該充分利用岸橋，通過調節(jié)集卡來適應岸橋的需求，而不能本末倒置。(4)在集卡的工作中，集卡的某些作業(yè)需要堆場機械的配合。模型假定場橋總是能夠及時服務于集卡，保證集卡及時服務于岸橋。如果堆場計劃員將堆場計劃做的較好時，就不會出現(xiàn)集卡等待場橋的情況，同時可以通過調整場橋的配置來實現(xiàn)，所以這種假設存在著一定的合理性[5]。(5)不考慮堆場中的交通擁擠、堵塞情況。 符號定義在對集裝箱碼頭的集卡調度優(yōu)化時，除了考慮集卡本身的作業(yè)因素外，還必須考慮岸橋的作業(yè)因素，例如岸橋何時需要集卡的服務，而此時是否有空閑的集卡，空閑的集卡離岸橋的距離多遠，與此同時，堆場中也有集裝箱需要作業(yè)，這時有沒有空閑的集卡可以作業(yè)，空閑集卡是去服務岸橋還是去服務堆場的集裝箱等等。本文中為了方便模型的描述，將集卡把一個集裝箱從岸邊(或堆場)運輸?shù)蕉褕?或岸邊)的過程定義為一個調度任務。這個調度任務的起始點為岸邊(或堆場)，終點為堆場(或岸邊)。船舶作業(yè)之前，岸橋的裝卸作業(yè)已經(jīng)由配載計劃做好，所以每臺岸橋的裝卸量以及作業(yè)的集裝箱順序都是已知的，同時己知岸橋的平均裝卸效率，即岸橋處理一個集裝箱的平均時間是多少。這樣針對這臺岸橋的每一個集裝箱，我們都知道該集裝箱的開始作業(yè)的時間、開始作業(yè)的地點、完成作業(yè)的時間以及完成作業(yè)的終點(岸區(qū)或是堆場中)。每兩個調度任務之間的距離也是已知的。為了打破集卡固定服務一個岸橋的模式，將所有岸橋作業(yè)的集裝箱綜合起來考慮，并按照它們作業(yè)的開始時間排序。運用這樣的思想岸橋的作業(yè)因素轉變?yōu)闀r間因素，約束到集卡作業(yè)中，便于建立集卡的調度優(yōu)化模型。建立集卡的調度優(yōu)化模型時首先定義如下符號：p：調度的集卡，假設計劃周期內所需集卡的總數(shù)為N，p=1，2，…，N；M：計劃周期內所有調度任務的總和；：調度任務i的開始時間，；：集卡完成調度任務i所需要的時間，；：集卡從調度任務i釋放集卡到調度任務j開始占用集卡所需要的時間，即集卡的無效作業(yè)時間。本文引入如下決策變量：，當=1時表示調度任務i和調度任務j由同一輛集卡相繼完成；，當=1時表示集卡p首先從調度任務i開始執(zhí)行；，當=1時表示集卡p在完成調度任務后結束工作。 模型建立基于以上所定義的符號以及決策變量，建立如下的集卡調度優(yōu)化模型：. min (). () () () () () () () ()其中，()為模型的目標函數(shù)，追求所有集卡的無效作業(yè)里程最短；()~()為模型的約束條件：()保證所有的集卡開始作業(yè)一次且僅一次；()保證所有的集卡結束作業(yè)一次且僅一次；()保證所有的調度任務開始一次且僅一次；()保證所有的調度任務結束一次且僅一次；()是兩個調度任務能成為相繼作業(yè)，在時間上所需滿足的條件，該約束條件來源于前述的岸橋作業(yè)因素。()~()保證變量為01變量。通過對集卡調度優(yōu)化模型的求解，可以得到集卡調度的優(yōu)化方案，從而使得所有集卡的無效作業(yè)里程最短。第4章 蟻群算法求解集卡調度數(shù)學模型通常，對集卡動態(tài)調度模型的求解是建立在指定集卡數(shù)量的前提下進行的，如《集裝箱碼頭調度問題研究》[15]在給定集卡數(shù)量的情況下進行優(yōu)化，而未考慮集卡數(shù)量的優(yōu)化。而《集裝箱碼頭堆場拖車動態(tài)調度問題研究》[13]將這一問題分解為數(shù)量配置模型和動態(tài)調度模型分別求解；對動態(tài)調度模型采用遺傳算法求解，并利用數(shù)量配置模型得到的車輛數(shù)作為條件之一。本文借鑒蟻群算法在VRP問題中的應用，求解集卡調度模型，在獲得最優(yōu)路徑的同時兼顧集卡數(shù)量最小這一目標。 蟻群算法簡介蟻群優(yōu)化(ACO，Ant Colony Optimization )算法是由意大利學者Colomi A、Dorigo M和Maniezzv于1991年提出來的[6]，是一種新型的模擬進化算法。蟻群算法是通過對自然界螞蟻在覓食過程中的尋路方式進行模仿而得出的一種優(yōu)化算法。自然界中的螞蟻在覓食的過程中會在自身爬行過的路徑上留下“信息素”來記錄路徑，同時在選擇路徑的時候也是根據(jù)之前螞蟻在該路徑留下的“信息素”濃度來判斷，濃度越高，則選擇的可能性越大。從蟻巢到食物的所有路徑中，路徑越短，則相同時間內通過的螞蟻也就更多，這樣在該路徑上所留下的信息素濃度也就更高，螞蟻選擇這條路徑的可能性就越大，這就形成了一種信息的正向反饋機制，如圖所示： 蟻群算法蟻群算法是基于螞蟻覓食的過程建立的。(a)中，一群螞蟻從一個未經(jīng)歷過的分岔口開始出發(fā)，最初所有螞蟻隨機選擇路徑行進。假設兩條路徑各被一半的螞蟻選中。每只螞蟻在行進過程中會在路徑上留下外激素以提示后到的螞蟻如何選擇路徑，途中的虛線表示螞蟻留下的外激素數(shù)量。(b)，由于路徑一比路徑二短，所以同一時間內，走過路徑一的螞蟻比走過路徑二的螞蟻多，因此路徑一上留下的外激素也就多。由于外激素數(shù)量對螞蟻選擇路徑的影響，經(jīng)過很短的時間，外激素數(shù)量的差異就大的足以影響新來的螞蟻的決策。(c)，由于這樣的正反饋，選擇路徑一的螞蟻越來越多。最終所有的螞蟻都會選擇路徑一。人工蟻群算法依此原理，在一組節(jié)點中尋找出一條代價最小的路徑。每只人工螞蟻根據(jù)狀態(tài)轉換規(guī)則反復地選擇為訪問過的城市，通過這種方式來完成一次完整的旅程。一旦所有的螞蟻都完成了旅程，系統(tǒng)就會使用一種全局的外激素更新規(guī)則，根據(jù)路徑被選擇的情況更新所其上的外激素數(shù)量。算法不斷迭代直至達到終止條件搜索到最優(yōu)解。 蟻群算法基本原理由于蟻群算法的思想是模仿螞蟻尋找最短路的機制，因此該算法最早是應用在了旅行商(TSP)問題上，而TSP問題又具有廣泛的代表意義和應用前景，許多現(xiàn)實問題，均可抽象為TSP問題進行求解[7]。接下來就以蟻群算法如何解決TSP問題介紹算法的基本原理。在解決TSP問題時所設置的人工螞蟻具有一些特點：(1)選擇路徑時，偏向于選擇信息素濃度高的路徑；(2)一般的，某條路徑越短，則該路徑上信息素增加得就越快；(3)螞蟻是通過遺留在路徑上的信息素來相互影響的。以上三個特點是人工螞蟻模仿自然界中真實螞蟻的性質而得來的，在解決實際問題中，人工螞蟻往往根據(jù)問題設置一些特有的性質。解決TSP問題的人工螞蟻還具有以下特性：(4)螞蟻能識別要遍歷的所有節(jié)點之間的距離；(5)所有的螞蟻都能記住先前所走過的節(jié)點(這種記憶在每次新的循環(huán)開始都清空)。設表示t時刻位于元素i的螞蟻數(shù)目，表示t時刻路徑(ij)上的信息量，n表示TSP規(guī)模，m為蟻群中螞蟻的總書目，則。初始時刻，各條路徑上的信息量相等，并設。螞蟻k(k=1,2,……,m)來記錄螞蟻k當前所走過的城市，集合隨著進化過程動態(tài)調整。在搜索過程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來計算狀態(tài)轉移概率: （）上式中，等式左邊表示t時刻，螞蟻k由位置i轉移到位置j的概率，為啟發(fā)函數(shù)，在TSP問題中，其表達式如下： （）式中，表示相鄰連個城市之間的距離。對于螞蟻k而言，越小，則越大，也就越大。顯然，該啟發(fā)函數(shù)表示螞蟻從元素(城市)i轉移到(城市)j的期望程度。為信息啟發(fā)式因子，表示軌跡的相對重要性，反映了螞蟻在運動過程中所積累的信息在螞蟻運動是所起的作用，其值越大，則該螞蟻越傾向于選擇其他螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作越強；為期望啟發(fā)式因子，表示能見度的相對重要性，反映了螞蟻在運動過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態(tài)轉移概率越接近貪心法則。為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻走完一步或者完成對雖有n個城市的遍歷(也即一個循環(huán)結束)后，要對殘留信息進行更新處理。這種更新策略模仿了人腦記憶的特點，在新信息不斷存入大腦的同時，存儲在大腦中的舊信息隨著時間的推移逐漸淡化，甚至忘記。由此t + n時刻在路徑(i，j)上的信息量可按如下規(guī)則進行更新： （） （）式中，ρ表示信息素揮發(fā)系數(shù)，則1ρ表示信息素殘留因子，為了防止信息的無限積累，ρ的取值范圍為：；表示本次循環(huán)中路徑(i,j)上的信息素增量，初始時刻，表示第k只螞蟻在本次循環(huán)中留在路徑(i,j)上的信息量。根據(jù)信息素更新策略的不同，Dorigo M提出了三種不同的基本蟻群算法模型，分別稱之為AntCycle模型、AntQuantity模型及AntDensity模型，其差別在于求法的不同。在AntCycle模型中 （）式中，Q表示信息素強度，它在一定程度上影響算法的收斂速度；表示第k只螞蟻在本次循環(huán)中所走路徑的總長度。在AntQuantity模型中 （）在AntDensity模型中 （）區(qū)別：式（）和式（）中利用的是局部信息，即螞蟻完成一部后更新路徑是上的信息素；而式（）中利用的是整體信息，即螞蟻的完成一個循環(huán)后更新所有路徑上的信息素，在求解TSP時性能更好，因此通常采用式1作為蟻群算法的基本模型。具體算法步驟如下：(1)參數(shù)初始化。令時間t=0和循環(huán)次數(shù)Nc=0，設置最大循環(huán)次數(shù)Ncmax，將m螞蟻置于n個元素(城市)上，令有向圖上每條邊(i，j)的初始化信息量，其中const表示常數(shù)，且初始時刻。(2)循環(huán)次數(shù)Nc←Nc+1。(3)螞蟻的禁忌表索引號k=1。(4)螞蟻數(shù)目k←k+1。(5)螞蟻個體根據(jù)狀態(tài)轉移概率公式計算的概率選擇元素(城市)j并前進，j∈{Ctabuk}。(6)修改禁忌表指針，即選擇好之后將螞蟻移動到新的元素(城市)，并把該元素(城市)移動到該螞蟻個體的禁忌表中。(7)若存在螞蟻沒有完成遍歷，即km，則跳轉至第(4)步，否則執(zhí)行第(8)步。(8)根據(jù)更新法則對每條路徑上的信息量進行更新。(9)若滿足結束條件，即如果循環(huán)次數(shù)Nc≥Ncmax，則循環(huán)結束并輸出程序技術結果，否則清空禁忌表并跳轉到第(2)步。 集卡調度模型算法設計本文所建立的集卡調度模型是面向“作業(yè)面”裝卸工藝的，集卡在作業(yè)過程中是動態(tài)分配的，并不固定的為某一個岸橋服務。同時本文假設在集卡作業(yè)期間，有裝卸要求的船舶的數(shù)量、位置及需求箱量是固定不變的，而堆場內的集裝箱的位置也是固定不變的，各堆場之間及堆場與岸區(qū)之間的距