基于蟻群算法的碼頭集裝箱卡車路徑優化研究

摘要：分析了集裝箱碼頭作業流程及其傳統作業工藝，提出了使用蟻群算法，以集裝箱卡車到達目的地的距離最短為目標，建立集裝箱卡車路徑優化模型，為碼頭集裝箱卡車尋求出發點與目的地之間的最短路徑。實驗表明，該方法能有效解決集卡最短路徑搜索問題。

關鍵詞：集裝箱卡車；蟻群算法；最短路徑

中圖分類號：U691文獻標識碼：A

文章編號：1002-3100(2008)12-0026-03

Abstract：In this paper， we analyze the process of container terminal operations and the traditional mode. Then， the routing optimization， which targets in the minimum route of container trucks is presented. The model is to seek the shortest route of container trucks which travels from the source to the destination. It is proved by the experiments that the problem for the container truck to search the shortest path can be solved with ant colony algorithm effectively.

Key words：container truck; ant colony algorithm; the shortest route

0引言

近年來，物流業迅猛發展，集裝箱運輸業面臨極大的挑戰，隨著港口貨運量的增長、船舶的大型化，碼頭為降低成本、增強競爭力，不斷研究新技術、加強對系統的管理，集裝箱卡車（簡稱集卡）的路徑對碼頭的生產效率有很大的影響，已成為國內外研究的熱點之一。如德國的Steenken等運用啟發式算法研究集卡在集裝箱碼頭的運輸路徑安排問題[1]；韓國的Byun等提出應用最短路徑算法，尋找集卡行走時間最短的路徑[2]；南開大學楊靜蕾[3]以集卡行走里程最短為目標，建立了集卡路徑優化模型，求解集卡最優行走路徑；大連理工大學張維英等[4]以集卡將碼頭堆場集裝箱送到岸邊橋式起重機（簡稱岸橋）所運行的距離最短為目標，建立配載模型并應用Hopfield 神經網絡模型進行計算機模擬。

目前，大部分港口采用傳統作業工藝，司機操作比較簡單，不容易出錯，便于管理與考核，但是隨著科學技術的進步、港口物流業的發展，這一模式的弊端逐漸暴露。首先，某條作業路上的集卡配置量是一個固定值，配置少了可能會出現岸橋等待集卡的現象，造成前方碼頭作業區的瓶頸；配置多了又容易產生資源浪費，使資源利用率低下，影響港口的生產效率。其次，傳統作業工藝中，集卡固定地為某一岸橋服務，僅局限于一條“作業路”，即集卡在完成一次作業如裝船、卸船或者轉堆后，必須空駛回到堆場或者碼頭，然后進行下一次作業，這樣造成集卡空載率較高，集卡利用率低下。最后，集卡分配給某一岸橋后，沿固定的路徑行駛，當碼頭上集卡數量過多時，集卡運輸可能發生交通堵塞，而且一旦發生堵塞，會對碼頭的生產效率帶來很大的影響。

要提高碼頭的吞吐量，就需要打破傳統作業工藝的束縛，為集卡選擇合理的行走路徑。本文基于蟻群算法為集卡建立路徑優化模型，使集卡選擇行走距離最短的路徑。

1集裝箱卡車路徑優化模型

1.1傳統作業工藝

港口集裝箱碼頭由岸邊橋式起重機、泊位、集裝箱龍門起重機（簡稱龍門吊）、集卡、堆場等組成。其中岸橋、集卡、龍門吊是港口最主要的機械設備，集裝箱裝卸作業需要這三種設備互相配合、協調，形成統一的整體，否則會出現岸橋、龍門吊等待集卡或者集卡等待岸橋、龍門吊等現象，影響碼頭的生產效率，而集卡是集裝箱裝貨、卸貨、轉堆過程中的運輸設備，在碼頭與堆場間作集裝箱水平運輸，銜接碼頭前沿岸橋和后方龍門吊的工作，是提高碼頭整體效率的關鍵設備。

目前，大部分港口采用傳統的集卡作業工藝，所謂的傳統作業工藝，也就是面向作業路的作業工藝，一般情況下，按照一定的比例為每臺岸邊橋式起重機分配集卡數量，例如，青島前灣港，按照碼頭的實際操作業務量，為每臺岸橋分配5~6輛集卡，分配的集卡與岸橋組成一條作業路，在調度過程中，集卡按照固定的路徑行走，配備的集卡始終為該岸橋服務直至泊位工作終止（見圖1）。

傳統作業工藝有其優點，也存在不足，本文在引言中分析了其優點與不足，本文打破打破傳統作業工藝的束縛，基于蟻群算法建立集卡路徑優化的模型，為集卡選擇合理的行走路徑，使其行走距離最短。

1.2蟻群算法的基本原理

蟻群算法是由意大利學者Dorigo[5]等于1991年首先提出來的，是一種受自然界生物的行為啟發而產生的“自然”算法，在一系列困難的組合優化問題求解中取得了成效。研究表明，在一個復雜的環境中，螞蟻總是能夠有效地找到食物，并且能夠找到一條近似最優的路線把食物搬回家。這種最優路線具有靈活適應性，當稍稍更改食物位置的時候，螞蟻群體還是能夠隨環境的變化而變化，適應性地搜索新的路徑，產生新的選擇。研究發現，螞蟻在尋找食物時，能在其走過的路徑上分泌一種被稱為“信息素”的化學物質到環境中去，螞蟻個體正是通過這種信息素來進行信息傳遞。螞蟻可以嗅到這種信息素，而且可以根據信息素的濃度來指導自己對前進方向的選擇。而這種信息素的濃度，在自然環境下會隨著時間過去而慢慢揮發掉。由于走較短路徑的螞蟻很快能夠返回巢穴，并且它會馬上再按原來的路徑繼續搬運食物，所以這條路徑上的信息素就會得到較多的增強機會，因此，較短路徑上的信息素濃度比較長路徑的濃度更高，而強度大的信息素會吸引更多的螞蟻，從而形成一種正反饋。通過這種正反饋，螞蟻群體最終可以找到最短路徑。

1.3基于蟻群算法的集卡路徑優化模型

由此建立的目標函數為：

根據算法的步驟，得出算法流程圖如圖2所示：

2算例

本文以某港口為計算實例，根據船舶配載圖，到達港口的船舶A中的15個進口箱需要運輸到箱區12，其中船舶與箱區以及箱區間的位置關系如圖3所示，船舶與箱區間的距離如表1所示（用頂點代替船舶與箱區）。

3仿真結果

本文打破碼頭集卡行車路徑固定的束縛，使用蟻群算法為在船舶A與箱區12之間進行水平運輸的集卡選擇一條最短路徑，由圖2可知，本文是求解頂點1到頂點12的最短路徑。實驗中各參數的取值為：?琢=1，?茁=5，p=0.5，Q=100。運行程序，得到一條從船舶A到達箱區12的最短路徑：1-2-5-8-9-12，行駛距離為1 510.5米。而在傳統作業工藝中，集卡的行走路徑是固定的，船舶A與箱區12之間的固定路線為1-4-7-10-11-12，行走距離為1 704米，由比較得知，本文基于蟻群算法建立的模型，比傳統作業工藝中的集卡少行走193.5米。

圖4是螞蟻尋找路徑的過程圖，表示每次循環中得到的最短路徑與螞蟻在本次循環中實際走過的平均路徑隨循環次數的變化，其中橫坐標表示循環次數，縱坐標代表螞蟻的行走距離，最短路徑是指在本次循環中螞蟻找到的最短路徑，平均路徑是指本次循環中所有螞蟻找到的路徑長度的平均值。由圖可以看出，從第2次循環開始，出現螞蟻找到從起點到終點的最短路徑，并且在第86次循環之后，所有的螞蟻都能找到最短路徑。

4結論與展望

本文將蟻群算法應用于集裝箱碼頭，實驗結果表明，使用蟻群算法能夠較快地為集卡找到起點與終點之間的最短路徑。但還有一些問題尚待解決，如本文只考慮了集卡行走里程最短，未考慮天氣、路況、交通擁擠程度等對道路的影響，有待于進一步研究。

參考文獻：

[1] Steenken D， Henning A， Freigang S， et a1． Routing of straddle carriers at a container terminal with the special aspect of internal moves[J]. OR Spektrum，West Germany，1993，15(3):167-172.

[2] Byun Jae—Wook， Jo Kang—Hyun， Lee Young—Suk． Optimal supervisory control systems for automated unmanned container transporters in the automated container terminals[C]//Proceedings KORUS 2000， The 4th Korea—Russia International Symposium On Science and Technology． IEEE，Piseataway，NJ，USA，2000:206-211．

[3] 楊靜蕾. 集裝箱碼頭物流路徑優化研究[J]. 水運工程，2006，1(1):32-35.

[4] 張維英，林焰，紀卓尚. 基于拖車路徑優化的集裝箱船配載模型研究[J]. 大連理工大學報，2005，45(6):827-831.

[5] Dorigo M， Maniezzo V， Colomi A. The Ant System：Optimization by a Colony of Cooperating Agents[J]. IEEE Trans. System Man Cybernet，1996，26(1):29-42.