基于貪心策略的環(huán)形穿梭車調(diào)度算法設(shè)計(jì)

◆鄒佰翰 夏 鑫 張吉懿

（1.天津工業(yè)大學(xué) 天津 300387；2.華北水利水電大學(xué) 河南 450000；3.鄭州航空工業(yè)管理學(xué)院 河南 450046）

1 環(huán)形穿梭車系統(tǒng)概述

最經(jīng)典的環(huán)形穿梭車系統(tǒng)，由環(huán)形軌道、N 輛穿梭車、m 個(gè)進(jìn)貨口構(gòu)成。A 側(cè)進(jìn)出貨口是出貨口在一起，進(jìn)貨口在一起；B側(cè)進(jìn)出貨口交替排列。小車的起點(diǎn)都位于A 側(cè)直軌道的正中間，即有如下示意圖1：

圖1 環(huán)形穿梭車示意圖

系統(tǒng)需求即需要確定使系統(tǒng)效率最高的環(huán)形穿梭車的數(shù)量和調(diào)度方法。

2 問題分析

在此將在同一時(shí)間區(qū)間內(nèi)處于同一直軌道上的穿梭車集合視作一個(gè)隊(duì)列。以貪心策略建立模型，選取評(píng)估參數(shù)，使用數(shù)據(jù)包絡(luò)分析法（DEA）輸出最優(yōu)目標(biāo)值。

3 模型的建立與求解

3.1 環(huán)形穿梭車運(yùn)動(dòng)基本模型的建立

貪心策略是基于貪心選擇的算法，指在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最優(yōu)選擇每做一次貪心選擇就將所求問題簡(jiǎn)化為一個(gè)規(guī)模更小的子問題。

對(duì)于穿梭車在相鄰的兩個(gè)裝/卸貨口之間的運(yùn)行時(shí)間t，有如下公式：

（1）對(duì)于任意穿梭車s 的裝卸路線，可總結(jié)以下方法：當(dāng)穿梭車前面的車數(shù)為0，即穿梭車位于隊(duì)首，需前往最遠(yuǎn)的貨口。

（2）如果距離d大于相鄰兩裝/卸貨口之間的距離，則需要依據(jù)如下具體情況判斷：

在A 側(cè)：若對(duì)幾個(gè)裝/卸口均分穿梭車，則相鄰兩裝卸口之間的距離無法容納相應(yīng)數(shù)量的穿梭車。此時(shí)穿梭車應(yīng)當(dāng)停留在最近的貨口。

在B 側(cè)：當(dāng)相鄰兩穿梭車裝載任務(wù)相同，且都是空車或都滿載的情況下，不能繼續(xù)前進(jìn)。此時(shí)穿梭車必須停留等待，此時(shí)前往最近的貨口。

為使總完工時(shí)間最小，提出如下目標(biāo)函數(shù)：

3.1.1 當(dāng)穿梭車s 位于隊(duì)首

在當(dāng)前直軌道上，假設(shè)穿梭車s 前面的車的數(shù)量Pns=0。若穿梭車s 后面的車數(shù)Pbs＞0，即穿梭車的后面還有其他車：

① 若此時(shí)穿梭車從B 向A 運(yùn)載，且滿足如下條件：

此時(shí)，穿梭車s 可以就近停在距離它最近的裝貨口。

②若穿梭車同樣是從B 向A 運(yùn)載，但滿足如下條件：

此時(shí)與①中情況相反，穿梭車s 應(yīng)前往距離它最遠(yuǎn)的貨口。

3.1.2 穿梭車s 位于隊(duì)列中間或隊(duì)尾

假設(shè)前面的車數(shù)Pns＞0，考慮穿梭車在隊(duì)列中間或者隊(duì)尾的情況：

（1）當(dāng)穿梭車從B 側(cè)向A 側(cè)運(yùn)載時(shí)，根據(jù)排隊(duì)論，對(duì)于每個(gè)裝/卸貨口，按順序分配n′

輛穿梭車。從而可得到穿梭車s 的運(yùn)動(dòng)規(guī)劃：

（2）當(dāng)穿梭車從A 側(cè)向B 側(cè)運(yùn)載時(shí)：

①若載貨的穿梭車到達(dá)指定的卸載口，則所需時(shí)間滿足遞歸公式：

②若穿梭車空車到達(dá)裝載口，且其后面的穿梭車s-1 的任務(wù)是卸貨，則穿梭車只需就近裝載。這一過程可用流程圖表示如圖2：

圖2 去往B 側(cè)的示意圖

3.2 對(duì)系統(tǒng)效率的評(píng)估

為確定系統(tǒng)工作效率，在此運(yùn)用數(shù)據(jù)包絡(luò)分析法對(duì)系統(tǒng)效率做出評(píng)價(jià)。各項(xiàng)評(píng)估指標(biāo)如下：

（1）擁堵時(shí)間：按所有穿梭車擁堵的時(shí)間總和來計(jì)算。設(shè)穿梭車s 在第j個(gè)貨口附近消耗的擁堵時(shí)間為Tsj，則總擁堵時(shí)間Tsum為：

（2）穿梭車數(shù)量：穿梭車隊(duì)列的總長(zhǎng)度不能超過環(huán)形軌道的周長(zhǎng)。即應(yīng)當(dāng)做如下約束：

將數(shù)據(jù)導(dǎo)入Lingo 得到效率指數(shù)如表1：

表1 效率指數(shù)表

5 2 分21 秒 3 時(shí)31 分56 秒 0.7801 6 3 分24 秒 3 時(shí)00 分50 秒 1.0000 7 4 分12 秒 2 時(shí)36 分26 秒 0.7409 8 4 分34 秒 2 時(shí)18 分53 秒 0.5600

從表中可以看到在穿梭車數(shù)量區(qū)間[2，6]內(nèi)，效率指數(shù)經(jīng)歷了穩(wěn)定上升的過程。當(dāng)小車數(shù)量超過6 時(shí)，在[6，8]區(qū)間內(nèi)，系統(tǒng)的效率指數(shù)開始變得不再穩(wěn)定。

綜上，我們認(rèn)為系統(tǒng)整體的運(yùn)行效率較高，系統(tǒng)中的小車數(shù)量在6 輛左右時(shí)效率較高，但出于安全性和穩(wěn)定性的考慮，小車數(shù)量不能高于8 輛。