考慮時(shí)間窗限制的車位分配與叉車聯(lián)合調(diào)度優(yōu)化

徐黎明 鄧華 劉亮

摘? 要：倉(cāng)儲(chǔ)中心的叉車調(diào)度和車位分配是解決倉(cāng)儲(chǔ)中心工作效率低下的關(guān)鍵。通過(guò)貪婪遺傳算法，解決天津L綜合倉(cāng)儲(chǔ)中心的車輛的車位分配以及叉車作業(yè)優(yōu)化調(diào)度問(wèn)題。首先獲取車輛的偏好車位，在生成初始可行解的過(guò)程中，運(yùn)用貪婪算法將新到倉(cāng)儲(chǔ)中心的車輛分配到最先空閑的車位，減少車輛等待的時(shí)間，最后運(yùn)用遺傳算法的選擇、交叉和變異操作不斷產(chǎn)生適應(yīng)度較高的解，結(jié)合實(shí)際問(wèn)題，最終實(shí)現(xiàn)綜合倉(cāng)儲(chǔ)中心的運(yùn)輸車輛車位的分配以及叉車作業(yè)調(diào)度的聯(lián)合優(yōu)化。

關(guān)鍵詞：貪婪遺傳算法;車位分配;叉車調(diào)度;偏好車位

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? 引? 言

隨著經(jīng)濟(jì)的發(fā)展，我國(guó)的綜合倉(cāng)儲(chǔ)中心逐漸增多。但由于倉(cāng)儲(chǔ)中心管理水平的低下，貨物積壓、貨車停滯的現(xiàn)象不斷發(fā)生，導(dǎo)致倉(cāng)庫(kù)的工作效率降低，運(yùn)輸車輛的車位分配和叉車調(diào)度優(yōu)化是解決該問(wèn)題的核心。彭小利等[1]在智能倉(cāng)庫(kù)的環(huán)境下，結(jié)合RFID技術(shù)建立數(shù)學(xué)和叉車作業(yè)分配算法來(lái)提高倉(cāng)庫(kù)的工作效率;馬驪等[2]在不對(duì)現(xiàn)有的倉(cāng)儲(chǔ)空間進(jìn)行擴(kuò)大的條件下，提出倉(cāng)儲(chǔ)中心的主動(dòng)式倉(cāng)儲(chǔ)調(diào)度算法來(lái)降低阻塞時(shí)間;楊文強(qiáng)等[3]通過(guò)將完工時(shí)間最小視為目標(biāo)，提出一種改進(jìn)的布谷鳥智能算法來(lái)對(duì)倉(cāng)儲(chǔ)進(jìn)行調(diào)度;張曉磊[4]通過(guò)灰色多層次弱收斂序列系數(shù)擬合出最短線路，建立了飼料運(yùn)輸車輛的調(diào)度優(yōu)化方案。上述的研究多是以車輛?？寇囄坏淖钚r(shí)間為目標(biāo)進(jìn)行優(yōu)化，沒(méi)有考慮車輛?？寇囄粫r(shí)的偏好性以及時(shí)間窗的限制。本文建立了帶有車輛?？科眯缘臄?shù)學(xué)模型，并提出相應(yīng)的算法，得出使得車位分配和叉車聯(lián)合調(diào)度問(wèn)題最優(yōu)的分配結(jié)果。

1? 問(wèn)題描述

本文基于合作項(xiàng)目對(duì)位于天津的L綜合倉(cāng)儲(chǔ)中心進(jìn)行車位分配和叉車作業(yè)調(diào)度研究，L倉(cāng)儲(chǔ)中心主要用于儲(chǔ)存進(jìn)出口貿(mào)易的貨物以及生鮮等產(chǎn)品，進(jìn)出L倉(cāng)儲(chǔ)中心的車輛主要是進(jìn)行裝卸物資。由于L倉(cāng)儲(chǔ)中心的各個(gè)倉(cāng)庫(kù)的裝卸區(qū)域有限，所以會(huì)造成車輛有一定時(shí)間的延遲，本文定義c1來(lái)表示單位延遲成本，定義偏移偏好車位的成本為c2，定義每個(gè)叉車的單位服務(wù)成本為c3。本文綜合考慮車輛裝卸作業(yè)的緊迫程度（通過(guò)c1體現(xiàn)）、車位叉車配置數(shù)量經(jīng)濟(jì)性需求（通過(guò)c3體現(xiàn)）、車輛對(duì)倉(cāng)庫(kù)就近作業(yè)距離經(jīng)濟(jì)性需求（通過(guò)c2體現(xiàn)）。

2? 模型描述

2.1? 偏好車位的確定

假設(shè)有30輛大型貨車分別在不同的時(shí)間段內(nèi)到達(dá)L倉(cāng)儲(chǔ)中心進(jìn)行裝卸載作業(yè)。其中15輛大型貨車進(jìn)行卸貨任務(wù)，另外15輛大型貨車進(jìn)行裝貨任務(wù)。對(duì)于裝貨的車輛，數(shù)據(jù)集中顯示了待裝貨物位置的具體倉(cāng)庫(kù)區(qū)號(hào)，因此當(dāng)這些車所?？康能囄痪嚯x這些倉(cāng)庫(kù)越近，顯然越有利于后續(xù)的車輛運(yùn)輸操作。因此在此通過(guò)計(jì)算這些倉(cāng)庫(kù)到各個(gè)車位的距離，然后取距離最小的車位作為裝貨車輛的偏好車位。具體如式（1）所示：

2.2? 參數(shù)設(shè)定

（1）假設(shè)單位延遲時(shí)間成本c1=5元;

（2）假設(shè)單位遠(yuǎn)離偏好車位的成本c2=100元;

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

（4）引入變量wi，來(lái)表示貨車i完成裝卸載任務(wù)所需的叉車總工時(shí)數(shù)。

2.3? 模型假設(shè)

（1）到庫(kù)車輛都必須且只能停一次，在裝卸過(guò)程中不考慮轉(zhuǎn)移倉(cāng)庫(kù)情況;

（2）每輛車均有一個(gè)偏好車位，當(dāng)車輛停泊在偏好車位時(shí)，集卡的運(yùn)輸距離最短;

（3）每輛車都有可分配叉車數(shù)的上限和下限，且在車輛裝卸過(guò)程中作業(yè)的叉車數(shù)不變;

（4）分配給車輛的叉車在裝卸任務(wù)開(kāi)始后直至裝卸任務(wù)結(jié)束不能中途停止;

（5）不考慮多個(gè)叉車同時(shí)作業(yè)時(shí)相互干擾對(duì)叉車工作效率的影響;

（6）所有車輛都能按照計(jì)劃時(shí)間準(zhǔn)時(shí)到達(dá)倉(cāng)庫(kù)，進(jìn)行停車裝載操作。

2.4? 模型與符號(hào)說(shuō)明

2.4.1? 參數(shù)說(shuō)明

V：計(jì)劃周期內(nèi)到倉(cāng)儲(chǔ)中心車輛的數(shù)量;

B：倉(cāng)儲(chǔ)中心可用車位數(shù);

M：極大的正數(shù);

Q：總岸橋數(shù);

ai：車輛i的計(jì)劃到倉(cāng)儲(chǔ)中心時(shí)間;

bi：車輛i的計(jì)劃離散時(shí)間;

pi：車輛i的偏好車位;

2.4.2? 決策變量

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

qi：分配給車輛i的叉車數(shù)。

2.4.3? 從屬變量

Ei：車輛i的進(jìn)入倉(cāng)儲(chǔ)中心時(shí)刻;

Di：車輛i的離開(kāi)倉(cāng)儲(chǔ)中心時(shí)刻;

Uit：若車輛i在t時(shí)刻被服務(wù)則取值為1，否則取值為0。

2.4.4? 數(shù)學(xué)模型

根據(jù)上述的定義結(jié)合車位分配和叉車調(diào)度問(wèn)題，建立的數(shù)學(xué)模型具體如式（2）至（15）所示：

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

3? 貪婪遺傳算法

對(duì)于小規(guī)模的車位與叉車調(diào)度問(wèn)題，傳統(tǒng)的商業(yè)軟件Lingo、CPLEX軟件等能夠進(jìn)行求解。但隨著車輛數(shù)量的增加，問(wèn)題的規(guī)模呈指數(shù)型增長(zhǎng)，具有全局尋優(yōu)能力的遺傳算法可以更好地求解這一問(wèn)題。

3.1? 個(gè)體編碼及種群初始化

本文遵循先到先服務(wù)原則為到倉(cāng)儲(chǔ)中心車輛競(jìng)爭(zhēng)分配車位，因此車輛的安排順序是確定的。在本次遺傳算法的求解過(guò)程中，每個(gè)種群個(gè)體用（4×30）的數(shù)組進(jìn)行，如表1所示。

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

式（17）車輛被嚴(yán)重延遲，車輛實(shí)際被服務(wù)時(shí)間都晚于計(jì)劃離港時(shí)間，因增加叉車數(shù)qj已經(jīng)失效，需要同時(shí)增加同一車位處上一輛車的qi和qj來(lái)縮短服務(wù)時(shí)間，使得Ej和Dj都落入時(shí)間窗內(nèi)。在本文中，針對(duì)式（16）的情況，主要先通過(guò)增加qj來(lái)實(shí)現(xiàn)，如果qj= 仍無(wú)法實(shí)現(xiàn)使Ej和Dj都落入時(shí)間窗內(nèi)，在考慮增加同一車位處，上一輛車qi;對(duì)于式（17）情況，直接令qj= ，然后通過(guò)增加同一車位處上一輛車qi，使得Ej和Dj都落入時(shí)間窗內(nèi)。

3.2? 遺傳算子

3.2.1? 算子的選擇

本文在選擇算子方面使用的是傳統(tǒng)的輪盤賭算法，由于目標(biāo)是求取極小化問(wèn)題，因此對(duì)每個(gè)染色體的所對(duì)應(yīng)的函數(shù)值取倒數(shù)轉(zhuǎn)化為適應(yīng)度。適應(yīng)度越大的個(gè)體被挑選到的概率越大。

3.2.2? 算子的交叉和變異

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

4? 算例分析

4.1? 算例背景

本文針對(duì)天津L綜合倉(cāng)儲(chǔ)中心的車位與叉車調(diào)度進(jìn)行研究，該綜合倉(cāng)儲(chǔ)中心的日常基本工作流程為：裝有貨物的車輛到達(dá)指定車位，由車位處的叉車卸貨物到倉(cāng)庫(kù)，然后叉車返回車位或者到下一個(gè)倉(cāng)庫(kù)區(qū)取貨。該倉(cāng)儲(chǔ)中心遵循先到先服務(wù)原則為車輛競(jìng)爭(zhēng)分配車位，同一車位在同一時(shí)間只能接收一輛車，且車輛采用連續(xù)裝卸貨方式，一旦進(jìn)入車位立即開(kāi)始作業(yè)，完成裝載任務(wù)后立即離開(kāi)車位，不考慮車輛移泊情況。由于該倉(cāng)庫(kù)有足夠多的叉車，但考慮成本問(wèn)題，需要制定出一個(gè)綜合的車輛停泊計(jì)劃與叉車分配計(jì)劃。

4.2? 運(yùn)行結(jié)果

運(yùn)用MATLAB軟件進(jìn)行編程求解上述問(wèn)題。貪婪遺傳算法的具體參數(shù)說(shuō)明如表3所示。

圖3為運(yùn)行的車位?？糠植紙D，圖鐘橫軸表示?？康能囄痪幪?hào)，縱軸表示?？繒r(shí)間，如圖中1（2）表示編號(hào)為1的車輛停靠在車位2上，安排的叉車個(gè)數(shù)為2個(gè)，其中高度表示在倉(cāng)儲(chǔ)中心的停留的時(shí)間。

5? 結(jié)? 論

本文提出了一種時(shí)間窗限制條件下的倉(cāng)庫(kù)車位與叉車聯(lián)合調(diào)度問(wèn)題，通過(guò)對(duì)該問(wèn)題建立模型，計(jì)算獲取車輛的偏好車位，生成初始可行解，運(yùn)用貪婪算法將新到倉(cāng)儲(chǔ)中心的車輛分配到最先空閑的車位，從而減少車輛等待的時(shí)間，最后運(yùn)用傳統(tǒng)遺傳算法的選擇、交叉和變異操作不斷產(chǎn)生適應(yīng)度較高的解，最終實(shí)現(xiàn)L綜合倉(cāng)儲(chǔ)中心的作業(yè)優(yōu)化調(diào)度問(wèn)題的求解。不足之處在于本文未考慮倉(cāng)庫(kù)牽引車作業(yè)的時(shí)間等因素，下一步的研究可以和牽引車作業(yè)結(jié)合，對(duì)車輛裝卸貨所用到的所有資源進(jìn)行整合優(yōu)化。

參考文獻(xiàn)：

[1] 彭小利，廖婷.制造物聯(lián)環(huán)境下智能倉(cāng)庫(kù)叉車作業(yè)分配算法研究 [J].電子設(shè)計(jì)工程，2018，26（14）：6-9.

[2] 馬驪，王銀珠，張敏，等.大型物流配送中心的主動(dòng)式倉(cāng)儲(chǔ)調(diào)度策略及其性能分析 [J].西安財(cái)經(jīng)學(xué)院學(xué)報(bào)，2018，31（1）：63-68.

[3] 楊文強(qiáng)，郭昊，李勇峰.布谷鳥算法求解組裝車間倉(cāng)儲(chǔ)調(diào)度優(yōu)化問(wèn)題 [J].電子測(cè)量與儀器學(xué)報(bào)，2016，30（10）：1506-1511.

[4] 張曉磊.依賴灰色多層次弱收斂序列系數(shù)的農(nóng)村飼料物流車輛調(diào)度優(yōu)化 [J].物流科技，2020，43（1）：6-8+25.

作者簡(jiǎn)介：徐黎明（1993—），男，漢族，安徽太和人，碩士，研究方向：復(fù)雜系統(tǒng)仿真與優(yōu)化;鄧華（1977—），男，漢族，四川綿陽(yáng)人，系主任，副教授，博士，研究方向：質(zhì)量工程、運(yùn)營(yíng)與供應(yīng)鏈管理;劉亮（1979—），男，漢族，山東德州人，副教授，博士，研究方向：復(fù)雜系統(tǒng)仿真與優(yōu)化、工業(yè)工程與精益管理創(chuàng)新。