考慮時間窗限制的車位分配與叉車聯合調度優化

徐黎明 鄧華 劉亮

摘? 要：倉儲中心的叉車調度和車位分配是解決倉儲中心工作效率低下的關鍵。通過貪婪遺傳算法，解決天津L綜合倉儲中心的車輛的車位分配以及叉車作業優化調度問題。首先獲取車輛的偏好車位，在生成初始可行解的過程中，運用貪婪算法將新到倉儲中心的車輛分配到最先空閑的車位，減少車輛等待的時間，最后運用遺傳算法的選擇、交叉和變異操作不斷產生適應度較高的解，結合實際問題，最終實現綜合倉儲中心的運輸車輛車位的分配以及叉車作業調度的聯合優化。

關鍵詞：貪婪遺傳算法;車位分配;叉車調度;偏好車位

Abstract：Forklift scheduling and parking space allocation are the key to solve the low efficiency of storage center. The greedy genetic algorithm is used to solve the problem of vehicle space allocation and forklift operation optimization scheduling in Tianjin L comprehensive storage center. In the process of generating the initial feasible solution，the greedy algorithm is used to allocate the new vehicles to the first idle parking space，so as to reduce the waiting time，finally，the selection，crossover and mutation operations of genetic algorithm are used to produce solutions with high adaptability. Combined with practical problems，the allocation of transportation vehicle parking space in the comprehensive storage center and the joint optimization of forklift operation scheduling are finally realized.

Keywords：greedy genetic algorithm;berth allocation;shore bridge scheduling;preference berth

0? 引? 言

隨著經濟的發展，我國的綜合倉儲中心逐漸增多。但由于倉儲中心管理水平的低下，貨物積壓、貨車停滯的現象不斷發生，導致倉庫的工作效率降低，運輸車輛的車位分配和叉車調度優化是解決該問題的核心。彭小利等[1]在智能倉庫的環境下，結合RFID技術建立數學和叉車作業分配算法來提高倉庫的工作效率;馬驪等[2]在不對現有的倉儲空間進行擴大的條件下，提出倉儲中心的主動式倉儲調度算法來降低阻塞時間;楊文強等[3]通過將完工時間最小視為目標，提出一種改進的布谷鳥智能算法來對倉儲進行調度;張曉磊[4]通過灰色多層次弱收斂序列系數擬合出最短線路，建立了飼料運輸車輛的調度優化方案。上述的研究多是以車輛停靠車位的最小時間為目標進行優化，沒有考慮車輛停靠車位時的偏好性以及時間窗的限制。本文建立了帶有車輛停靠偏好性的數學模型，并提出相應的算法，得出使得車位分配和叉車聯合調度問題最優的分配結果。

1? 問題描述

本文基于合作項目對位于天津的L綜合倉儲中心進行車位分配和叉車作業調度研究，L倉儲中心主要用于儲存進出口貿易的貨物以及生鮮等產品，進出L倉儲中心的車輛主要是進行裝卸物資。由于L倉儲中心的各個倉庫的裝卸區域有限，所以會造成車輛有一定時間的延遲，本文定義c1來表示單位延遲成本，定義偏移偏好車位的成本為c2，定義每個叉車的單位服務成本為c3。本文綜合考慮車輛裝卸作業的緊迫程度（通過c1體現）、車位叉車配置數量經濟性需求（通過c3體現）、車輛對倉庫就近作業距離經濟性需求（通過c2體現）。

2? 模型描述

2.1? 偏好車位的確定

假設有30輛大型貨車分別在不同的時間段內到達L倉儲中心進行裝卸載作業。其中15輛大型貨車進行卸貨任務，另外15輛大型貨車進行裝貨任務。對于裝貨的車輛，數據集中顯示了待裝貨物位置的具體倉庫區號，因此當這些車所停靠的車位距離這些倉庫越近，顯然越有利于后續的車輛運輸操作。因此在此通過計算這些倉庫到各個車位的距離，然后取距離最小的車位作為裝貨車輛的偏好車位。具體如式（1）所示：

2.2? 參數設定

（1）假設單位延遲時間成本c1=5元;

（2）假設單位遠離偏好車位的成本c2=100元;

（3）假設每個叉車參與工作的成本c3=100元;

（4）引入變量wi，來表示貨車i完成裝卸載任務所需的叉車總工時數。

2.3? 模型假設

（1）到庫車輛都必須且只能停一次，在裝卸過程中不考慮轉移倉庫情況;

（2）每輛車均有一個偏好車位，當車輛停泊在偏好車位時，集卡的運輸距離最短;

（3）每輛車都有可分配叉車數的上限和下限，且在車輛裝卸過程中作業的叉車數不變;

（4）分配給車輛的叉車在裝卸任務開始后直至裝卸任務結束不能中途停止;

（5）不考慮多個叉車同時作業時相互干擾對叉車工作效率的影響;

（6）所有車輛都能按照計劃時間準時到達倉庫，進行停車裝載操作。

2.4? 模型與符號說明

2.4.1? 參數說明

V：計劃周期內到倉儲中心車輛的數量;

B：倉儲中心可用車位數;

M：極大的正數;

Q：總岸橋數;

ai：車輛i的計劃到倉儲中心時間;

bi：車輛i的計劃離散時間;

pi：車輛i的偏好車位;

2.4.2? 決策變量

Uijk：若車輛i在j車位按次序k被服務則取值為1，否則為0;

qi：分配給車輛i的叉車數。

2.4.3? 從屬變量

Ei：車輛i的進入倉儲中心時刻;

Di：車輛i的離開倉儲中心時刻;

Uit：若車輛i在t時刻被服務則取值為1，否則取值為0。

2.4.4? 數學模型

根據上述的定義結合車位分配和叉車調度問題，建立的數學模型具體如式（2）至（15）所示：

式（2）是最小化三大成本：延遲成本+偏離偏好車位成本+叉車服務成本。式（3）和（4）保證任何車輛在各自的時間窗口內都進行裝卸載工作。式（5）使得單輛車只停靠倉庫的機會有且僅有一次。式（6）規定了單個車位在服務的時候僅能接收一輛車。式（7）規定了車輛進出倉儲中心時的服務順序。式（8）可以避免車輛在同一個車位被服務的時候產生時間沖突問題。式（9）可以保證在任意的一個時刻的叉車的數量不會比倉庫中現有的叉車數目要多。式（10）必須滿足每輛車所需的叉車臺數，即每輛車工作完才能離開。式（11）限制了分配給每個車位的叉車數。式（12）保證了工作時間上的連續，以及在時間窗內必須完成所有工作。式（13）（14）（15）定義了決策變量和從屬變量的取值范圍。

3? 貪婪遺傳算法

對于小規模的車位與叉車調度問題，傳統的商業軟件Lingo、CPLEX軟件等能夠進行求解。但隨著車輛數量的增加，問題的規模呈指數型增長，具有全局尋優能力的遺傳算法可以更好地求解這一問題。

3.1? 個體編碼及種群初始化

本文遵循先到先服務原則為到倉儲中心車輛競爭分配車位，因此車輛的安排順序是確定的。在本次遺傳算法的求解過程中，每個種群個體用（4×30）的數組進行，如表1所示。

鑒于模型約束較多，在算法設計中將約束條件嵌入算法結構，從而降低模型求解難度。結合具體問題，在設計染色體編碼方面做出如下改進：對于每一個染色體的前面9列，分別在第一行填入1～9的全排列，考慮到1、2、8三輛車具有偏好車位，讓它們停靠在各自的偏好車位上，改進后的個體編碼如表2所示。

式（17）車輛被嚴重延遲，車輛實際被服務時間都晚于計劃離港時間，因增加叉車數qj已經失效，需要同時增加同一車位處上一輛車的qi和qj來縮短服務時間，使得Ej和Dj都落入時間窗內。在本文中，針對式（16）的情況，主要先通過增加qj來實現，如果qj= 仍無法實現使Ej和Dj都落入時間窗內，在考慮增加同一車位處，上一輛車qi;對于式（17）情況，直接令qj= ，然后通過增加同一車位處上一輛車qi，使得Ej和Dj都落入時間窗內。

3.2? 遺傳算子

3.2.1? 算子的選擇

本文在選擇算子方面使用的是傳統的輪盤賭算法，由于目標是求取極小化問題，因此對每個染色體的所對應的函數值取倒數轉化為適應度。適應度越大的個體被挑選到的概率越大。

3.2.2? 算子的交叉和變異

通過對模型的具體分析可知將編號為10的車輛安排到某一車位的關鍵因素在于安排給前九的車輛在各自車位上離泊時間的長短。若第i輛車由于貨物量少或安排的叉車數很多，最早離開該車位，那么第10輛車就會安排到該車位，應該叉車數的多少會對后續的結果產生影響。因此交叉操作本文主要對叉車數進行操作，交叉操作如圖1所示;在染色體突變方面，由于本問題的染色體較長，因此設計兩個突變點進行變異，變異的部分仍然是叉車數，如圖2所示。對于變異的點，隨機生成一個[，]的隨機數，插入到原染色體中，如圖2的虛線框所示，這樣就完成了染色體的變異操作。

4? 算例分析

4.1? 算例背景

本文針對天津L綜合倉儲中心的車位與叉車調度進行研究，該綜合倉儲中心的日常基本工作流程為：裝有貨物的車輛到達指定車位，由車位處的叉車卸貨物到倉庫，然后叉車返回車位或者到下一個倉庫區取貨。該倉儲中心遵循先到先服務原則為車輛競爭分配車位，同一車位在同一時間只能接收一輛車，且車輛采用連續裝卸貨方式，一旦進入車位立即開始作業，完成裝載任務后立即離開車位，不考慮車輛移泊情況。由于該倉庫有足夠多的叉車，但考慮成本問題，需要制定出一個綜合的車輛停泊計劃與叉車分配計劃。

4.2? 運行結果

運用MATLAB軟件進行編程求解上述問題。貪婪遺傳算法的具體參數說明如表3所示。

圖3為運行的車位停靠分布圖，圖鐘橫軸表示停靠的車位編號，縱軸表示停靠時間，如圖中1（2）表示編號為1的車輛停靠在車位2上，安排的叉車個數為2個，其中高度表示在倉儲中心的停留的時間。

5? 結? 論

本文提出了一種時間窗限制條件下的倉庫車位與叉車聯合調度問題，通過對該問題建立模型，計算獲取車輛的偏好車位，生成初始可行解，運用貪婪算法將新到倉儲中心的車輛分配到最先空閑的車位，從而減少車輛等待的時間，最后運用傳統遺傳算法的選擇、交叉和變異操作不斷產生適應度較高的解，最終實現L綜合倉儲中心的作業優化調度問題的求解。不足之處在于本文未考慮倉庫牽引車作業的時間等因素，下一步的研究可以和牽引車作業結合，對車輛裝卸貨所用到的所有資源進行整合優化。

參考文獻：

[1] 彭小利，廖婷.制造物聯環境下智能倉庫叉車作業分配算法研究 [J].電子設計工程，2018，26（14）：6-9.

[2] 馬驪，王銀珠，張敏，等.大型物流配送中心的主動式倉儲調度策略及其性能分析 [J].西安財經學院學報，2018，31（1）：63-68.

[3] 楊文強，郭昊，李勇峰.布谷鳥算法求解組裝車間倉儲調度優化問題 [J].電子測量與儀器學報，2016，30（10）：1506-1511.

[4] 張曉磊.依賴灰色多層次弱收斂序列系數的農村飼料物流車輛調度優化 [J].物流科技，2020，43（1）：6-8+25.

作者簡介：徐黎明（1993—），男，漢族，安徽太和人，碩士，研究方向：復雜系統仿真與優化;鄧華（1977—），男，漢族，四川綿陽人，系主任，副教授，博士，研究方向：質量工程、運營與供應鏈管理;劉亮（1979—），男，漢族，山東德州人，副教授，博士，研究方向：復雜系統仿真與優化、工業工程與精益管理創新。