英文論文翻譯-關(guān)于集裝箱轉(zhuǎn)運(yùn)中心集卡的調(diào)度算法

1、關(guān)于集裝箱轉(zhuǎn)運(yùn)中心集卡的調(diào)度算法作者：Loo Hay Lee·Ek Peng Chew·Kok Choon Tan·Yuan Wang摘要：本文在考慮岸橋、場橋的作業(yè)能力情況下，解決了集裝箱轉(zhuǎn)運(yùn)中心集卡的調(diào)度問題.本文的目標(biāo)是使岸邊作業(yè)完成時(shí)間最小化.這個(gè)問題對于那些能夠通過信息技術(shù)充分利用數(shù)據(jù)做出科學(xué)決策的港口尤其重要.本文提出一個(gè)混合整數(shù)規(guī)劃模型來解決該問題.現(xiàn)有的解決方案不能在合理的時(shí)間內(nèi)解決混合整數(shù)規(guī)劃模型，因此，本文提出了兩個(gè)啟發(fā)式算法來解決該問題.第一個(gè)方法是基于鄰域搜索的網(wǎng)絡(luò)模型，第二個(gè)是基于遺傳算法和最小成本流的網(wǎng)絡(luò)模型.不像通常用任務(wù)序列代表染色

2、體的傳統(tǒng)遺傳算法，本文使用任務(wù)的開始時(shí)間代表染色體，最小成本流模型用于解碼染色體并且決定集卡的工作序列.本實(shí)驗(yàn)結(jié)果顯示了基于最小成本流的遺傳算法優(yōu)于鄰域搜索算法.關(guān)鍵詞：轉(zhuǎn)運(yùn)·集卡調(diào)度·完工時(shí)間·遺傳算法1介紹 海上運(yùn)輸一直是支持全球貿(mào)易的主心骨，因?yàn)?0%的國際貿(mào)易都是通過海上進(jìn)行運(yùn)輸.隨著世界貿(mào)易的不斷增長，主要港口之間的競爭也越來越激烈.因此，對港口操作者來說，選擇不同的決策工具和優(yōu)化算法來提高港口的效益和增加其競爭力是非常必要的. 典型的集裝箱港口主要資源有岸邊起重機(jī)（簡稱岸橋）、堆場起重機(jī)（簡稱場橋）、集裝箱卡車（簡稱集卡），為了提高碼頭的生產(chǎn)效率，在碼

3、頭內(nèi)協(xié)調(diào)分配給這些設(shè)備的任務(wù)，保證集裝箱流的無縫銜接是非常必要的. 當(dāng)船舶到達(dá)港口時(shí)，岸橋?qū)⑦M(jìn)口和轉(zhuǎn)運(yùn)的集裝箱從船上卸到集卡上，通過集卡將它們運(yùn)到堆場相應(yīng)的堆放位置.在堆場方面，場橋?qū)⑦@些集裝箱從集卡上卸下到指定的對方位置.從堆場向船上裝載進(jìn)口和轉(zhuǎn)運(yùn)集裝箱的過程與上述過程類似.碼頭前沿和堆場之間的運(yùn)輸對碼頭的生產(chǎn)效率起很決定性作用，因?yàn)楫?dāng)集卡沒有準(zhǔn)時(shí)到達(dá)或者到的太早引起交通擁擠，會(huì)導(dǎo)致岸橋或場橋操作延遲.實(shí)際上，因交通擁擠、交通延遲、設(shè)備故障和其他港口動(dòng)態(tài)不確定性導(dǎo)致各種設(shè)備之間在操作方面協(xié)調(diào)的復(fù)雜性，使得優(yōu)化這類調(diào)度問題變得充滿挑戰(zhàn)性.因此，需要一個(gè)信息技術(shù)平臺(tái)收集操作上的實(shí)時(shí)信息，然后決策

4、支持系統(tǒng)能夠充分利用這些信息，進(jìn)而提供快速、智能的方案來指導(dǎo)港口內(nèi)集卡的調(diào)度及路徑規(guī)劃.本文旨在通過為集卡調(diào)度設(shè)計(jì)算法來提高轉(zhuǎn)運(yùn)中心碼頭前沿港口操作效率，以此解決上述問題. 在過去，多數(shù)研究集中在改進(jìn)集卡的時(shí)間表.有許多文章研究自動(dòng)港口無人搬運(yùn)車（AGV）調(diào)度問題.Meersmans 和Wagelmans（2001a，b）對于AGV和起重機(jī)選址問題設(shè)計(jì)了定向搜索算法.Bose等人（2002）使用基于任務(wù)或基于集卡的方法找到初始解決方案，同時(shí)，利用進(jìn)化算法進(jìn)行改善.Van der Meer（2000）研究了集裝箱自動(dòng)碼頭中自動(dòng)搬運(yùn)車的控制.Hartmann（2004）為港口各類操作設(shè)備的調(diào)度和人

5、力資源設(shè)計(jì)了遺傳算法.Grunow等（2004）研究了多負(fù)載自動(dòng)搬運(yùn)車調(diào)度問題，為在線物流控制系統(tǒng)設(shè)計(jì)了靈活性優(yōu)先的方法，利用混合整數(shù)線性規(guī)劃模型對在線策略進(jìn)行評估，并且分多種情況對優(yōu)先規(guī)則的績效和混合整數(shù)線性規(guī)劃模型進(jìn)行分析.Grunow等（2006）對集裝箱自動(dòng)碼頭的自動(dòng)搬運(yùn)車調(diào)度策略進(jìn)行仿真研究，并用可擴(kuò)展仿真模型對提出的仿真策略進(jìn)行評估.Kim和Bae（2004）利用Kim和Bae（1999）提出的混合整數(shù)模型給自動(dòng)搬運(yùn)車調(diào)度設(shè)計(jì)了拓展算法，該算法與本文研究類似，該文章討論了在有未來任務(wù)位置和時(shí)間的退出信息情況下，如何調(diào)度自動(dòng)搬運(yùn)車使得岸橋總等待時(shí)間和總移動(dòng)時(shí)間最小化的問題.這篇文章還

6、考慮了多岸橋和自動(dòng)搬運(yùn)車雙循環(huán)操作的聯(lián)合調(diào)度策略.Nguyen和Kim（2009）進(jìn)一步研究了Kim和Bae（2004）發(fā)表文章的主要思想，設(shè)計(jì)了解決自己能從地面上起升集裝箱的自動(dòng)起升車調(diào)度問題的啟發(fā)式算法. 集卡調(diào)度也被考慮在傳統(tǒng)卡車和拖車系統(tǒng)中.Bish等（2001）研究了集卡調(diào)度的NP-hard問題，根據(jù)最小化完工時(shí)間給每一個(gè)卸載集裝箱分配了堆場位置.Bish（2003）提出了一個(gè)啟發(fā)式算法以解決集卡的調(diào)度問題，當(dāng)編制岸橋裝卸時(shí)間表的時(shí)候，確定每一集裝箱卸往堆場儲(chǔ)存位置.Bish等（2005）是Bish（2003）問題的延伸，兩者都解決該問題提出了簡單的可實(shí)施的啟發(fā)式算法，并且算出了所提

7、出算法最壞情況絕對性能比和漸進(jìn)性能比.Nishimura等（2005）研究了動(dòng)態(tài)拖車路徑問題，在該篇文章中，拖車分配給制定岸橋，并且車輛可能是單拖車或是雙拖車.Zhang等（2005）提出了三個(gè)關(guān)于集裝箱碼頭集卡調(diào)度問題的混合整數(shù)規(guī)劃模型，任務(wù)的開始時(shí)間和集卡的工作序列需要確定，這些模型只考慮了一個(gè)泊位一條船舶的卸載階段，并且只有一臺(tái)特定的岸橋服務(wù)船舶.Ng和Mak（2004）設(shè)計(jì)了一個(gè)算法給運(yùn)輸出口集裝箱的卡車進(jìn)入工作車道順序進(jìn)行排序.Ng等（2007）使用遺傳算法研究了集裝箱碼頭一隊(duì)集卡執(zhí)行一系列運(yùn)輸任務(wù)的時(shí)間表問題，他們集中研究完工時(shí)間最小化的情況下卡車任務(wù)順序的時(shí)間表.Chen等（20

8、07）將調(diào)度問題轉(zhuǎn)換為一個(gè)帶有優(yōu)先約束和阻塞限制的混合流水車間調(diào)度問題，并運(yùn)用基于禁忌搜索的算法來解決該問題，結(jié)果顯示擁有一個(gè)較優(yōu)初始方案很重要. 上述許多研究除了Chen等（2007）都沒有考慮堆場的延遲情況，它們都在必要的時(shí)候假設(shè)場橋數(shù)量總是足夠的，當(dāng)場橋不存在擁擠情況或是場橋數(shù)量足夠的時(shí)候這個(gè)，該假設(shè)是合理的，但是事實(shí)并不總是如此，尤其是當(dāng)交通量很大的時(shí)候.另外，大多數(shù)文章局限于任務(wù)為出口集裝箱或進(jìn)口集裝箱港口. 本文將考慮堆場處的延遲，并同時(shí)考慮集裝箱的裝卸過程，這是在集裝箱轉(zhuǎn)運(yùn)港口最常見的情況.另外，集卡可服務(wù)于任何岸橋，而不是指定給某一特定岸橋.我們尋求在考慮所有設(shè)備的情況下，完成

9、給定數(shù)量的集裝箱任務(wù)使碼頭前沿完工時(shí)間最短的一種有效率集卡調(diào)度方法.我們將這個(gè)作為目標(biāo)的原因是我們想要加速船舶的周轉(zhuǎn)時(shí)間，其他的目標(biāo)，像岸橋等待時(shí)間、船舶周轉(zhuǎn)時(shí)間我們的模型中也考慮到了. 我們?yōu)榻鉀Q該問題，提出了一個(gè)混合整數(shù)規(guī)劃模型，數(shù)值試驗(yàn)表明現(xiàn)有的解器不能直接求解該混合整數(shù)規(guī)劃問題，因此，我們提出了兩個(gè)啟發(fā)式算法來解決這個(gè)問題.第一個(gè)方法是領(lǐng)域搜索法，對于第二種方法我們將最小成本流網(wǎng)絡(luò)模型與遺傳算法結(jié)合在一起，在遺傳算法此方法中，我們根據(jù)任務(wù)的開始時(shí)間編碼染色體，而不是直接用集卡任務(wù)序列.這種方法是創(chuàng)新的，并且能夠利用遺傳算法和最小成本流的優(yōu)點(diǎn).在給定的開始時(shí)間下，最小成本流旨在找到能使最

10、小成本流模型目標(biāo)最小的集卡時(shí)間表.本文證明了最小成本流能夠?qū)⑷旧w解碼，并得出最優(yōu)集卡工作時(shí)間表.當(dāng)染色體編碼擁有良好的領(lǐng)域結(jié)構(gòu)，遺傳算法在設(shè)計(jì)空間上進(jìn)行局部和整體的搜索都具有優(yōu)勢.在這種情況下，我們能發(fā)現(xiàn)由于交叉算子執(zhí)行時(shí)，開始時(shí)間的領(lǐng)域結(jié)構(gòu)被保存，用開始時(shí)間對染色體進(jìn)行編碼會(huì)比用工作序列更好. 我們考慮了堆場的延遲即增加了問題難度的一個(gè)維度，所以研究內(nèi)容與現(xiàn)有的大多數(shù)研究不同.Chen等（2007）解決了類似的問題，但是我們同時(shí)考了了轉(zhuǎn)運(yùn)中心的裝卸過程，另外，我們使用的是遺傳算法和最小成本流，而他們使用的是禁忌搜索法.本文其他部分結(jié)構(gòu)如下所示：第二部分提出了混合整數(shù)規(guī)劃模型，第三部分描述了

11、解決該問題的兩種啟發(fā)式算法，第四部分展示了數(shù)值試驗(yàn)的結(jié)果，最后，第五部分我們給出了結(jié)論還有未來研究方向.2數(shù)學(xué)模型 本文研究的是幾條船舶在一給定時(shí)間段內(nèi)同時(shí)進(jìn)行裝卸，每一個(gè)集裝箱的堆場位置對集卡來說是已知的，主要的操作決策就是確定集卡的任務(wù)順序.實(shí)際上，大多數(shù)港口都直接將一定數(shù)量的集卡通過啟發(fā)式算法分配給制定的某一岸橋，例如，最近的任務(wù)優(yōu)先.當(dāng)這種貪婪方法很容易實(shí)施時(shí)，可能會(huì)給出較差的解決方法.因此，設(shè)計(jì)一個(gè)同時(shí)考慮所有的設(shè)備的模型是很重要的.在這個(gè)部分，我們將為這個(gè)集卡調(diào)度問題提出一個(gè)混合整數(shù)規(guī)劃模型.假設(shè)如下所示：1.每一個(gè)岸橋的任務(wù)序列、任務(wù)類型都已知，并且岸橋必須嚴(yán)格按照岸橋序列清單上

12、執(zhí)行；2.每一任務(wù)的堆場位置已知；3.兩個(gè)處理地點(diǎn)之間的位置已知；4.集卡服務(wù)于所有岸橋；5.集裝箱任務(wù)、岸橋、場橋、集卡的數(shù)量已知；6.集卡一次只能運(yùn)載一個(gè)集裝箱；7.場橋的行駛時(shí)間計(jì)入操作時(shí)間；8.不考慮集卡的交通擁擠；符號(hào)參數(shù)K岸橋的集合M集卡的集合R場橋的集合Nk岸橋k工作列表的工作數(shù)量L裝箱任務(wù)的集合D卸箱任務(wù)的集合H所有任務(wù)的集合，H=LDN集裝箱任務(wù)的總數(shù)，包括裝卸任務(wù)，N= = ;（i，）任務(wù)索引，任務(wù)（i，）表示岸橋工作列表中的第i個(gè)任務(wù)；（S，D）虛擬開始任務(wù)；（E，D）虛擬結(jié)束任務(wù)；集裝箱任務(wù)的集合，包括虛擬開始任務(wù)和虛擬結(jié)束任務(wù)，；包括虛擬開始任務(wù)的所有集裝箱任務(wù)，；包

13、括虛擬開始任務(wù)的所有集裝箱任務(wù)，；使用場橋的任務(wù)；一個(gè)很大額常熟岸橋處理任務(wù)（裝或卸）的操作時(shí)間；場橋處理任務(wù)（裝或卸）的操作時(shí)間；集卡從任務(wù)起始地到其預(yù)設(shè)目的地的運(yùn)輸時(shí)間；集卡從任務(wù)結(jié)束地到其下一任務(wù)起始地的空載時(shí)間；變量，當(dāng)集卡結(jié)束任務(wù)后駛向下一任務(wù)的起始位置；否則.，當(dāng)場橋結(jié)束任務(wù)后開始下一任務(wù)的起始位置；否則.岸橋處理任務(wù)的開始時(shí)刻；相應(yīng)場橋處理任務(wù)的開始時(shí)刻；所有任務(wù)都為裝載任務(wù)或卸載任務(wù)，因此，為了方便建立模型，我們有必要對這兩種任務(wù)的活動(dòng)時(shí)間進(jìn)行分析.·卸載任務(wù)的活動(dòng)時(shí)間軸（圖一）下面的卸載任務(wù)活動(dòng)時(shí)間軸描述了集卡完成裝卸任務(wù)所需時(shí)間，深色區(qū)域表示每一個(gè)集卡在碼頭前沿或

14、堆場的可能等待時(shí)間.對卸載任務(wù)來說，表示岸橋?qū)⑺牡趇個(gè)集裝箱卸載到集卡的開始時(shí)刻；表示岸橋卸載集裝箱到集卡上的操作時(shí)間.圖1.卸載任務(wù)的活動(dòng)時(shí)間軸圖.卸載任務(wù)活動(dòng)時(shí)間軸圖.裝載任務(wù)活動(dòng)時(shí)間軸圖2.卸載任務(wù)的活動(dòng)時(shí)間軸目標(biāo)函數(shù)：約束條件：·資源約束·給定任務(wù)的時(shí)間約束·不同資源的順序依賴時(shí)間岸橋：由同一岸橋處理的兩個(gè)集裝箱任務(wù)必須要隔至少一個(gè)操作時(shí)間.集卡：由同一集卡處理的兩個(gè)集裝箱任務(wù)必須要隔至少一個(gè)操作時(shí)間.場橋：由同一場橋處理的兩個(gè)集裝箱任務(wù)必須要隔至少一個(gè)操作時(shí)間. 目標(biāo)函數(shù)（1）表示碼頭前沿基于當(dāng)前設(shè)備配置情況，完成給定的一系列任務(wù)的完工時(shí)間最小. 約束

15、條件（2-10）為資源約束，在這些約束條件總，（2-6）是關(guān)于碼頭前沿的，其余的是關(guān)于堆場的. 約束條件（2）和（3）表示集合H內(nèi)每一個(gè)集裝箱任務(wù)都有前序任務(wù)和后續(xù)任務(wù)，并且只有一輛集卡完成，約束條件（4）保證了每一輛集卡路徑的連續(xù)性.約束條件（5）、（6）定義了集卡序列的虛擬起始點(diǎn)和虛擬結(jié)束點(diǎn)，關(guān)于堆場的約束條件（7-10）幾乎與碼頭前沿的一致. 約束條件（11、12）是時(shí)間約束，限定了岸橋和場橋來時(shí)任務(wù)時(shí)刻必須由集卡在岸橋和場橋之間的移動(dòng)時(shí)間和操作時(shí)間. 約束條件（13-18）是不同資源的順序依賴時(shí)間約束與具有優(yōu)先限制的多旅行商問題和平行機(jī)排程問題相類似，表示了由同一岸橋/場橋/集卡所執(zhí)行

16、的兩個(gè)任務(wù)之間必須隔至少一個(gè)操作時(shí)間.約束（14-17）表示集卡的順序依賴時(shí)間限制取決于兩個(gè)任務(wù)的類型，如卸卸，裝裝，裝卸，卸裝.約束（19-21）為非負(fù)和整數(shù)約束.3提出的啟發(fā)式算法 分提出的調(diào)度模型將決定集卡和場橋的工作順序，我們以2臺(tái)岸橋，3臺(tái)場橋，2輛集卡為例進(jìn)行數(shù)值試驗(yàn)，對該模型的效率進(jìn)行檢測，該模型利用CPLEX進(jìn)行求解，并由程序執(zhí)行.我們發(fā)現(xiàn)當(dāng)任務(wù)數(shù)量從增加到時(shí)，求解該混合整數(shù)規(guī)劃模型的運(yùn)行時(shí)間更長.圖.求解混合指數(shù)規(guī)劃模型用時(shí) 由于解決小規(guī)模問題所需時(shí)間過長（如圖），因此該混合整數(shù)規(guī)劃模型不適合解決實(shí)際碼頭的問題，我們提出了一個(gè)如圖所示的解決方案框架來解決這類問題，該框架的主要

17、構(gòu)思就是搜索集卡序列，得到給定集卡序列后評價(jià)模型再給出場橋序列，最后，我們希望該框架能找到較優(yōu)的集卡序列.初始集卡序列方案集卡方案群評價(jià)模型搜索方法圖.所提算法的框架 現(xiàn)在，我們討論框架的概念，首先，我們產(chǎn)生一個(gè)初始集卡序列，這個(gè)序列既可以為隨機(jī)給出的，也可以通過基于像最小成本流網(wǎng)絡(luò)模型的啟發(fā)式算法得出，基于該序列，我們創(chuàng)造一群新序列，并通過考慮不同場橋序列對這些集卡序列進(jìn)行評估，為了提高解的質(zhì)量，將運(yùn)用一些搜索方法來產(chǎn)生新序列群，重復(fù)該過程直至達(dá)到停止標(biāo)準(zhǔn). 對于該評估模塊，我們需要在考慮碼頭前沿和堆場的延遲情況下，計(jì)算對于一給定集卡序列，完成碼頭前沿活動(dòng)的完工時(shí)間，我們提出兩種方法，第一個(gè)

18、是基于簡化的混合整數(shù)規(guī)劃模型，第二個(gè)是基于先到先服務(wù)的仿真方法，該簡化混合整數(shù)規(guī)劃模型實(shí)質(zhì)上就是第部分所提出的，不同的是，此處集卡序列是給定的，這意味著所有的值是固定的，因?yàn)榛旌险麛?shù)規(guī)劃模型的規(guī)模已經(jīng)大大減小了，所以該簡化混合整數(shù)規(guī)劃模型解決這類小規(guī)模問題效率很高，但是因?yàn)樗允且粋€(gè)混合整數(shù)規(guī)劃模型，所以當(dāng)任務(wù)數(shù)量變大了之后，運(yùn)行情況就變得不好了. 對于基于先到先服務(wù)的仿真模型，我們假設(shè)場橋根據(jù)集卡到達(dá)場橋時(shí)間，按先到先服務(wù)規(guī)則進(jìn)行作業(yè).集卡序列已知，通過先到先服務(wù)規(guī)則，可以使用集散事件調(diào)度方法確定集卡在碼頭前沿和堆場完成活動(dòng)的時(shí)間，因?yàn)椴恍枰蠼馊蝿?wù)優(yōu)化模型，相比簡化混合整數(shù)規(guī)劃模型，該方法

19、計(jì)算速度更快，在數(shù)值試驗(yàn)中，我們得知仿真方案和簡化混合整數(shù)規(guī)劃模型的效果差不多，由于仿真方法計(jì)算的效率高，我們使用它來解決規(guī)模大的問題. 對于搜索方法，我們采用兩種不同的方法來產(chǎn)生新的集卡任務(wù)序列：一個(gè)是可變鄰域搜索法，另一個(gè)是基于遺傳算法和最小成本流的網(wǎng)絡(luò)模型方法. 在接下來的部分，我們將詳細(xì)得討論最小成本流、可變鄰域搜索法和基于遺傳算法和最小成本流的網(wǎng)絡(luò)模型.3.最小成本流模型 Cheng等（2005）文章中提到最小成本流模型的目標(biāo)是找到一個(gè)使延遲最小、集卡利用率最大的集卡序列.而在我們的研究中，打算運(yùn)用最小成本流作為產(chǎn)生集卡序列的一種方法.Vis等（2001,2005）和potvin等（

20、1992,1993）的研究中有關(guān)于最小成本流網(wǎng)絡(luò)模型的詳細(xì)介紹. 本文用到的最小成本流模型中，我們假設(shè)任務(wù)的開始時(shí)間已知，并且由集卡的順序無關(guān)，場橋充足即在堆場不存在等待時(shí)間. 該模型尋求與任務(wù)開始時(shí)間最小差值最小的集卡序列，不考慮延遲、設(shè)備之間的干擾、工作序列，我們提出的最小成本流模型中使用的開始時(shí)間不是實(shí)際操作的開始時(shí)間，換言之，這些開始時(shí)間可以看成是虛擬開始時(shí)間，通過確定這些時(shí)間可以幫助找到集卡序列. 在后續(xù)的討論中，我們將用符號(hào)i,j表示集裝箱任務(wù)，S,D分別表示虛擬開始任務(wù)、虛擬結(jié)束任務(wù)，我們的模型可以看做的有向圖，表示點(diǎn)的集合，表示弧的集合，集合中所有集裝箱任務(wù)都為中的點(diǎn)，用有向的

21、弧鏈接被同一集卡執(zhí)行的兩個(gè)任務(wù)，當(dāng)輛集卡執(zhí)行集合中任務(wù)是，需要確定從到的條路徑，弧的值表示與開始時(shí)間的差值，目標(biāo)是全網(wǎng)絡(luò)成本最低. 讓為決策變量，當(dāng)同一集卡在結(jié)束任務(wù)后立即執(zhí)行任務(wù)時(shí)取，為集卡結(jié)束任務(wù)后執(zhí)行任務(wù)開始時(shí)間差值的成本參數(shù).模型如下：最小成本流模型 等式（）表示目標(biāo)函數(shù)為整個(gè)成本流最小化.約束條件（）是對個(gè)集卡流的守恒.約束條件（）和（）保證了從點(diǎn)到點(diǎn)集合中的嗎條路徑要執(zhí)行集合中任務(wù)，約束條件（）和（）規(guī)定每個(gè)任務(wù)只能有一條路徑服務(wù)（即一輛集卡）.約束條件（）限制了流量小于. 該模型提供二進(jìn)制的解決方案，因此問題能有有效率地解決，接下來我們將討論如何計(jì)算.從虛擬節(jié)點(diǎn)到所有集裝箱任務(wù)節(jié)

22、點(diǎn)的弧、所有集裝箱任務(wù)節(jié)點(diǎn)到虛擬節(jié)點(diǎn)的弧都為成本.為了計(jì)算兩個(gè)集裝箱任務(wù)節(jié)點(diǎn)間的弧，我們需要知道兩任務(wù)在各自岸橋處的開始時(shí)間、行程時(shí)間和操作時(shí)間.讓為岸橋卸載或裝載集裝箱任務(wù)的開始時(shí)間.表示當(dāng)集卡在岸橋處開始任務(wù)與在集卡處結(jié)束任務(wù)之間的間隔時(shí)間，因此，為集卡到達(dá)操作任務(wù)的岸橋處的時(shí)間，在結(jié)束任務(wù)后開始任務(wù)的時(shí)間差值，如下所示：是大于的常數(shù).是在過早或過早的一個(gè)相關(guān)權(quán)重參數(shù)，過晚的話會(huì)導(dǎo)致岸橋過早的等待，不僅使集卡等待而且會(huì)產(chǎn)生由岸橋序列混亂導(dǎo)致的不可行性.當(dāng)數(shù)值試驗(yàn)運(yùn)行時(shí)，我們需要調(diào)整參數(shù).的計(jì)算取決于任務(wù)對的類型，如卸卸，裝裝，裝卸，卸裝（見圖）.對于卸裝任務(wù)，包括任務(wù)i的岸橋操作時(shí)間，從岸

23、橋到場橋的行駛時(shí)間，場橋的操作時(shí)間，從任務(wù)i場橋目的地到任務(wù)j場橋起始地的行駛時(shí)間，場橋操作任務(wù)j的時(shí)間，從場橋到岸橋的行駛時(shí)間，因此，對iD，jL有：同樣，我們可以得出其他幾種情況下的定義：圖.四種情況下的組成 當(dāng)所有任務(wù)的開始時(shí)間已知，任務(wù)之間的已知時(shí)，該模型的優(yōu)點(diǎn)是能高效率地解決調(diào)度問題，而缺點(diǎn)是假設(shè)場橋是充足的，也就是說不考慮堆場的等待時(shí)間，另外，通過確定開始時(shí)間，我們直接假設(shè)集卡總是能在開始時(shí)間在岸橋處開始任務(wù)，忽略岸橋和集卡的等待時(shí)間. 最小成本流模型不排斥任務(wù)的子方案，由于某些開始時(shí)間可能會(huì)給出不可行的集卡序列，所以，選擇合適的開始時(shí)間是很重要的，幸運(yùn)的是，由于成本系數(shù)的定義，我

24、們模型中的子方案都是劣解，為了得帶更好的解，按照到達(dá)的順序，任務(wù)的開始時(shí)間都是給遞減的，這樣選擇的所有都是小的，然而，如果解中存在子方案，意味著由于違背非遞減性，至少存在一個(gè)較大，存在能提供好的甚至是最優(yōu)集卡序列的開始時(shí)間.定理1表示存在一系列可得到最優(yōu)集卡序列的開始時(shí)間. 表示使碼頭前沿完工時(shí)間最小的集卡序列，MCF（t）表示在給定開始時(shí)間t的情況下，t為表示所有任務(wù)開始時(shí)間的矢量，通過求解最小成本流模型得到的最優(yōu)集卡序列.定理1 對所有任務(wù)最優(yōu)開始時(shí)間，存在=MCF（）證明 已知中一個(gè)最優(yōu)集卡序列，將第一個(gè)任務(wù)的開始時(shí)間設(shè)為0，用下面公式對序列任務(wù)按順序進(jìn)行設(shè)置準(zhǔn)備時(shí)間，在最優(yōu)集卡序列中，

25、集卡完成任務(wù)i后立即開始任務(wù)j，任務(wù)i的開始時(shí)間為，則任務(wù)j的開始時(shí)間=+，用這種方法設(shè)置開始時(shí)間會(huì)使得接下來最優(yōu)序列中的任務(wù)對的=0.因此，當(dāng)開始時(shí)間為時(shí)，在最小成本流模型中的目標(biāo)函數(shù)值為0.定理1表明當(dāng)我們在開始時(shí)間的設(shè)計(jì)空間內(nèi)搜索時(shí)不會(huì)丟失最優(yōu)解，我們所設(shè)計(jì)的啟發(fā)式算法中，以兩種不同方法用到了最小成本流模型：第一種是在所有任務(wù)初始開始時(shí)間已知情況下，產(chǎn)生初始集卡序列，第二種是作為以開始時(shí)間編碼染色體的遺傳算法的解碼器.3.2可變鄰域搜索法 Mladenovic and Hansen（1997）提到可變鄰域搜索法（VNS）是用于求解足額和和全局最優(yōu)問題的一種啟發(fā)式算法，是使鄰域有一個(gè)系統(tǒng)改

26、變的簡單有效的搜索方法.Garcia-Lopez等（2002）講解了其基本步驟，首先找到一個(gè)初始解，兩個(gè)嵌套的圈，中心的圈通過稱為“環(huán)裂”、“局部搜索”的兩個(gè)主要功能改變、探索.當(dāng)內(nèi)圈進(jìn)行主要的局部搜索時(shí)，外圈反復(fù)更新內(nèi)圈，只要解有所改進(jìn)便進(jìn)行迭代，直到滿足停止標(biāo)準(zhǔn)，環(huán)裂功能使解變得多樣化. 在該遺傳算法中，VNS用于更新由MCF方法得到的初始解，該更新步驟已知重復(fù)直至滿足停止標(biāo)準(zhǔn)，VNS的偽代碼如圖6所示，體現(xiàn)了我們整數(shù)調(diào)度問題的VNS法解決方法.圖6.VNS解決方法 由得到的初始解，我們令，通過環(huán)裂程序產(chǎn)生從中大小為的鄰域內(nèi)得帶隨機(jī)解，通過局部搜索技術(shù)，從該隨機(jī)解找到一個(gè)新解，為了強(qiáng)化該隨

27、機(jī)解的鄰域搜索，局部搜索重復(fù)次.若所得解優(yōu)于當(dāng)前解，則采納新解，并將鄰域大小設(shè)為.若在次嘗試后，當(dāng)前解未得到改進(jìn)，將鄰域大小增加，當(dāng)超過的最大限度時(shí)停止算法. 基于交換片段方式的兩集卡任務(wù)序列的局部優(yōu)化（如圖所示）.下面討論基于啟發(fā)式算法的步驟.步驟：（） 初始化：找到初試方案，令.進(jìn)行評估是否交換？交換兩條片段隨機(jī)選兩條集卡路徑在第一條路徑中隨機(jī)選一片段在第二條路徑中隨機(jī)選一片段可行？在該集卡序列隊(duì)停止？停止選擇集卡序列隊(duì)？停止搜索圖.法的局部搜索步驟（2）環(huán)裂過程：從中大小為的鄰域內(nèi)隨機(jī)選出.（3）局部搜索：從解中隨機(jī)選出兩個(gè)集卡序列片段.（）從第一個(gè)序列中連續(xù)任務(wù)命令任意基數(shù)的片段是隨機(jī)

28、選取的； 連續(xù)命令的片段長度可以任意地為1、2、3，為了不破壞原始序列，將片段的基數(shù)小于3.（）從第二個(gè)序列中連續(xù)任務(wù)命令任意基數(shù)的片段是隨機(jī)選取的； （）交換兩條選取的片段（如圖所示）. 其中一個(gè)集卡序列片段插入另外一集卡序列片段移出的位置. （）可行性檢驗(yàn)：檢測在給定岸橋序列下，兩個(gè)新的集卡序列是否可行. 在交換后，應(yīng)該檢測兩個(gè)集卡序列的可行性，以任務(wù)、為例，假設(shè)任務(wù)、都在同一岸橋的工作清單內(nèi)，工作順序?yàn)橄热蝿?wù)后任務(wù)，則在集卡序列中，任務(wù)不能出現(xiàn)在任務(wù)之前，否則，該交換不可行.若兩個(gè)新集卡序列可行，進(jìn)入評估步驟.交換之后的兩條隨機(jī)選擇片段交換之前的兩條隨機(jī)選擇片段 圖8.兩條片段的交換形式

29、 否則，返回（）在每一個(gè)集卡序列中選一片斷，最多取次，若在次之后， 沒找到可行解，為了避免不必要的搜索返回（）環(huán)裂，選擇另一對集卡序列.（4）評估：用簡化模型或基于仿真的方法對新解進(jìn)行評估，得到目標(biāo)值，若更優(yōu)，接受新解，令，.否則保留當(dāng)前解，返回，進(jìn)行次局部搜索，令，返回（）選擇另外一個(gè)解，直到達(dá)到的限制.3.3基于最小成本流網(wǎng)絡(luò)模型的遺傳算法 遺傳算法是常見的元啟發(fā)式算法，源于生物的自然進(jìn)化，能夠同時(shí)運(yùn)算一群解.本文選擇遺傳算法原因如下：首先，遺傳算法是常見的元啟發(fā)式算法，并且它的求解效率已被許多問題所證實(shí).第二相比較于領(lǐng)域搜索算法，我們需要一個(gè)像遺傳算法一樣的基于種群的方法以便更好地搜索解

30、空間.遺傳算法的步驟如圖9所示，相比較于其他傳統(tǒng)遺傳算法的設(shè)置，本文使用開始時(shí)間對染色體進(jìn)行編碼，求解最小成本流模型來得到集卡序列.3.3.1染色體編碼 我們用開始時(shí)間對染色體進(jìn)行編碼，相比于用集卡序列編碼的好處在于交叉操作后，鄰域結(jié)構(gòu)更容易被保留，而且，岸橋的序列也易得出.此外，本文在定理1處通過謹(jǐn)慎選擇開始時(shí)間，能夠得到最優(yōu)集卡序列. 本文用個(gè)指定岸橋序列中各任務(wù)開始時(shí)間來編碼染色體，而不是直接用開始時(shí)間，為任務(wù)i在岸橋處的開始時(shí)間，為岸橋下一個(gè)任務(wù)的開始時(shí)間，. 染色體根據(jù)進(jìn)行編碼，用這種編碼可以保證任務(wù)的開始時(shí)間遵循岸橋序列，遺傳算法對進(jìn)行搜索，很容易得到.3.3.2父代的選擇 父代的

31、選擇策略意味著如何在能產(chǎn)生下一代的當(dāng)前群體中選擇染色體，通常來說，當(dāng)前群體中解越優(yōu)被選為生成子代的父代概論越大，這種方法是更好的.因此本文使用二元競標(biāo)賽選擇法，二元競標(biāo)賽選擇法隨機(jī)選出兩個(gè)個(gè)體，贏的一方成為父代，在交叉操作中，將會(huì)重復(fù)該過程直到選出父代，為了保證最優(yōu)個(gè)體能夠存活到下一代，本文使用精英策略使最優(yōu)解一直留在群體中.3.3.3交叉本文使用算術(shù)交叉算子來探索解空間，新的子代與父代成線性關(guān)系.為0.5到1之間的任意數(shù).3.3.4突變 突變算子的主要任務(wù)是在子代中維持種群的多樣性并探索解空間.對每一個(gè)體，先選0到1之間認(rèn)得任意數(shù)與突變概論相比較，因?yàn)橥蛔儼l(fā)生的概論實(shí)在太?。ㄍǔ?0.001

32、），若該數(shù)小于（概論相當(dāng)?shù)停?，則對該個(gè)體執(zhí)行突變.突變步驟為交換兩條任意選中基因的值.3.3.5子代的選擇 采用擬貪婪策略的形式接受由遺傳算子產(chǎn)生的子代，在該策略中，如果子代的適應(yīng)度小于它父輩的平均值，則作為新一代接受.3.3.6停止標(biāo)準(zhǔn) 為了減少計(jì)算時(shí)間，我們采用兩個(gè)標(biāo)準(zhǔn)作為停止規(guī)則：（1）生成子代數(shù)達(dá)到最大值，（2）當(dāng)前種群染色體適應(yīng)度的標(biāo)準(zhǔn)差小于某個(gè)很小的值.4試驗(yàn) 為了檢測算法的求解效率和所得解的質(zhì)量，我們進(jìn)行試驗(yàn)，所有試驗(yàn)都2GB RAM的2.4GHZ PC執(zhí)行，啟發(fā)式算法由C+運(yùn)行，MIP模型由線性求解器進(jìn)行求解.每一個(gè)算例都由鄰域搜索法和遺傳算法求解次，并記錄完工時(shí)間（目標(biāo)值）.通過兩組