基于圖論的鐵路集裝箱貨場龍門起重機配置的研究

摘要：鐵路集裝箱貨場龍門起重機的配置問題，就是在堆場中配置一定數量的龍門起重機，配合集卡為進場的貨車提供裝卸服務。目前鐵路集裝箱貨場的龍門起重機配置大都根據經驗進行配置，缺乏定量模型和方法。針對鐵路集裝箱貨場裝卸過程中龍門起重機配置問題，依據圖論的有關知識，給出貨場裝卸作業中確定龍門起重機配置的定量化模型及其算法。

關鍵詞：鐵路集裝箱貨場；龍門起重機；圖論；Ford-Fulkerson算法

中圖分類號：U169.6文獻標識碼：A文章編號：1002-3100(2008)08-0047-04

Abstract: The problems of collocation of gantry cranes in railway container freight yard， is to collocate cantry cranes in the freight yard， for the handling services with the container trucks. At present the cantry cranes in railway container freight yard configured mostly based on experience， and lack the quantitative models and methods. Aiming at the problem how to determine the collocation of gantry cranes in railway container freight yard， it gives the quantitative model and algorithm of gantry cranes in the freight yard handling process based on Graph Theory.

Key words: railway container freight yard; gantry crane; Graph Theory; Ford-Fulkerson algorithm

0引言

鐵路集裝箱貨場的裝卸機械是完成鐵路裝卸作業的重要手段。裝卸作業機械化對于提高裝卸效率、節約勞動力、減輕工人的勞動強度、縮短裝卸作業時間、加速貨位運送等都是十分有利的[1]。龍門起重機便是裝卸作業中最重要機械之一。在鐵路集裝箱貨場裝卸過程中，在貨場集卡配置好之后，便需要配置龍門起重機，以和集卡配合，使貨場運作順利的進行。龍門起重機是用于集裝箱裝卸、搬運和堆碼的專用機械，可以在堆場的不同箱區和同箱區的不同貨位之間移動[2-3]。

同時，龍門起重機的作業過程是一個復雜過程，其中往往存在一些隨機因素，例如其提放箱時間具有隨機性，與集卡的行走時間也具有隨機性。尤其是在采用面向作業面和裝卸同時進行的新工藝后，一種設備的隨機性會被放大，甚至波及到整個作業流程。因此，單純的采用解析計算方法或按照經驗進行設備配置在實際應用中可能會有一定的偏差，有必要采用更為科學的方法進行資源配置、修正。

鑒于堆場龍門起重機的合理優化配置對鐵路集裝箱貨場的高效運轉具有極其重要作用的原因，本文建立了一個基于圖論的網絡圖模型，給出了貨場裝卸作業中確定龍門起重機配置的定量化模型及其算法，以求得整個鐵路集裝箱貨場裝卸工作的最優化。

1問題描述

在鐵路集裝箱貨場卸箱作業過程中，首先是由龍門起重機將進口集裝箱從貨車上提起放至堆場，再由集卡裝載，而后集卡返回。而在裝箱作業過程中，首先由集卡將貨物在堆場裝箱，再由龍門起重機將出口集裝箱從堆場上提起放至出運貨車，集卡返回。所謂龍門起重機的配置問題是指在配置好集卡后還需要配置一定數量的龍門起重機來配合集卡工作，以實現鐵路集裝箱貨場的流暢作業，從而提高貨場的作業效率。因此龍門起重機配置過程的目標是以最少的龍門起重機最大程度的按計劃完成作業。本文所建立的龍門起重機配置模型基于以下幾點假設：（1）在計劃期內整個堆場共N項任務（集裝箱）需要龍門起重機完成，這些任務可以分為出口箱和進口箱兩類，并且每項任務的發生時刻和發生位置已知；（2）龍門起重機必須能夠及時地在任務發生時刻提供服務，以保證整個計劃的順利執行；（3）龍門起重機每次只能提取一個集裝箱。

2龍門起重機配置模型

因此龍門起重機的配置問題就是在有向圖G中尋找一個能夠滿足邊的流量約束并且經過各個節點僅一次的s到t的最小流量f，也即尋找最少的f條不重復且流量為1的路以覆蓋G中的所有節點，該最小流量f即為龍門起重機的配置數量。從s到t的每一條路的流量都是1，并且分別代表一臺龍門起重機的工作順序。下面本文給出該問題的最小流算法。

3最小流算法

下面以圖1所示的龍門起重機配置問題為例，說明最小流算法[4]的實現過程：

（2）最小流算法的有效性

5實例分析

5.1已知條件

6結束語

本文討論了鐵路集裝箱貨場裝卸中的龍門起重機配置問題，給出了確定龍門起重機配置數量的網絡流模型，給出了模型的最小流算法，并用數學方法證明算法的正確性和有效性，最后通過一個算例證明該模型和算法是正確有效的。因此，本文對于鐵路集裝箱貨場龍門起重機配置，提高作業效率具有一定的指導意義。

參考文獻：

[1] 尹啟泰，陳占芬. 鐵路貨運組織[M]. 成都：西南交通大學出版社，1993.

[2] 何華武. 中國鐵路集裝箱運輸發展戰略[J]. 集裝箱化，2005(1):35-37.

[3]Lai K K， Lam K. A study of container yard equipment alloca-tion strategy in Hongkong[J]. International Journal of Mod-eling and Simulation， 1994，14(3):134-138.

[4]Vis I F A， de Koster R， Roodbergen K J， Peeters L W P. Determination of the number of automated guided vehicles required at a semi-automated container terminal[J]. Journal of the operation research society， 2001(52):409-417.

[5]《運籌學》教材編寫組. 運籌學[M]. 2版. 北京：清華大學出版社，1997.

[6] 謝政，李建平. 網絡算法與復雜性理論[M]. 湖南：國防科技大學出版社，1995.

[7] 嚴蔚敏，吳偉民. 數據結構[M]. 北京：清華大學出版社，1999.