王同慶 潘璐 張家敏 王靜

摘? ?要：文章針對環(huán)形穿梭車動態(tài)調(diào)度問題，基于任務(wù)完成時間最小化構(gòu)造解決環(huán)形穿梭車動態(tài)調(diào)度的基礎(chǔ)模型。首先，將任務(wù)完成時間最小化的目標(biāo)函數(shù)分解為穿梭車搬運(yùn)距離最短和系統(tǒng)擁塞次數(shù)最少。其次，提出了改進(jìn)的混合規(guī)則算法。最后，利用改進(jìn)的混合規(guī)則算法求解模型。

關(guān)鍵詞：穿梭車;混合規(guī)則;多指標(biāo)評價;動態(tài)調(diào)度

環(huán)形穿梭車系統(tǒng)的設(shè)計與調(diào)度，影響貨物運(yùn)送的效率。其中，貨物裝載的順序?qū)ψ罱K消耗的時間有關(guān)鍵性的作用。每輛穿梭車只能沿環(huán)形軌道進(jìn)行逆時針單向勻速運(yùn)行，該環(huán)形軌道可以同時運(yùn)行多臺穿梭車，從而改善了直線往復(fù)式穿梭車輸送能力有限的缺點(diǎn)。然而，由于系統(tǒng)采用封閉式軌道，在運(yùn)行過程中，不合理的調(diào)度會加劇軌道堵塞，降低運(yùn)行效率[1]。所以，探究車輛調(diào)度的裝卸順序?qū)?shí)際的調(diào)度有重要的意義。本文提出混合規(guī)則的環(huán)形穿梭車調(diào)度算法，模擬了穿梭車的調(diào)度過程。

1? ? 問題描述

穿梭車的運(yùn)行速度、車長以及數(shù)量對整個調(diào)度系統(tǒng)的效率有著重要的影響。其中，當(dāng)穿梭車的數(shù)量少于進(jìn)出貨物端口時，會導(dǎo)致在同一時刻處理順序的貨物，不能在同一個運(yùn)送周期內(nèi)得到處理，使得貨物運(yùn)送的效率降低，導(dǎo)致總時間變長。當(dāng)穿梭車數(shù)量多于進(jìn)出貨物端口時，雖然可以提高一個運(yùn)送周期內(nèi)貨物處理的數(shù)量，但是由于穿梭車數(shù)量增多，發(fā)生擁塞的次數(shù)也會隨之增加。因此，對穿梭車進(jìn)行合理的調(diào)度，可以減少軌道的堵塞，提高環(huán)形穿梭車系統(tǒng)的運(yùn)行效率[2]。

1.1? 相關(guān)假設(shè)

（1）環(huán)形穿梭車、出入貨端口在整個調(diào)度運(yùn)行周期中有故障發(fā)生時，系統(tǒng)停止運(yùn)行，對調(diào)度優(yōu)化過程不產(chǎn)生影響。

（2）環(huán)形穿梭車到達(dá)出入貨端口可立即完成出入貨，不考慮其他因素。

（3）本文中環(huán)形穿梭車和出入貨端口編號沿逆時針依次統(tǒng)一編號。

（4）在不考慮優(yōu)化算法執(zhí)行時間的情況下，即環(huán)形穿梭車系統(tǒng)調(diào)度是在理想情況下執(zhí)行的可以忽略系統(tǒng)執(zhí)行算法的時間。

2? ? 模型建立

在不考慮環(huán)形穿梭車的車長情況下，要使系統(tǒng)的工作效率盡可能高，則需要考慮所有作業(yè)任務(wù)完成時間最短。因此，環(huán)形穿梭車系統(tǒng)調(diào)度的優(yōu)化模型如式（1）所示。

其中，ti表示貨物i完成上貨下貨所需的時間，N_goods表示所有貨物的數(shù)量，包括系統(tǒng)A側(cè)和B側(cè)上貨端口需要完成的作業(yè)任務(wù)量Ni之和，如式（2）所示。

由于在實(shí)際運(yùn)算的過程中，貨物作業(yè)任務(wù)完成時間t無法直接計算，但貨物i在上貨下貨的過程中包括等待出入貨的時間tiwait和出入貨所用的時間tL/U，處理貨物的時間包括上貨和下貨的時間，如式（3）所示[3]。

而貨物i的等待時間包括上貨之前等待的時間tiwait_L和等待下貨tiwait_U的時間，如式（4）所示。

由于貨物等待調(diào)度的時間主要與上貨端口之前的貨物上貨時間有關(guān)，又由式（3）和式（4）可知貨物任務(wù)完成時間的主要因素是貨物等待下貨時間tiwait_U和貨物出入貨所用的時間tL/U，因此，可將上述優(yōu)化目標(biāo)分解為所有環(huán)形穿梭車搬運(yùn)距離之和最短及環(huán)形軌道堵塞造成停車次數(shù)最少兩個方面[4]，如式（5）所示。

其中，目標(biāo)函數(shù)式（1）表示使環(huán)形穿梭車運(yùn)送距離與等待時間的最小化。x=（x1，x2，x3，…，xn）是一組可行解，表示環(huán)形穿梭車調(diào)度貨物的序列;α，β分別為優(yōu)化函數(shù)f1，f2的權(quán)重;f1表示可行解x對應(yīng)的環(huán)形穿梭車運(yùn)送距離的標(biāo)準(zhǔn)差的優(yōu)化;f2表示環(huán)形軌道堵塞造成停車次數(shù)最少的。式（6）、式（7）給出了f1，f2的計算公式。

其中，N為穿梭車的數(shù)量，s是環(huán)形穿梭車的狀態(tài)量，Si表示第i輛穿梭車的狀態(tài)值，若Si=0表示穿梭車沒有被分配任務(wù);否則Si=1表示被分配任務(wù);l為環(huán)形穿梭車搬運(yùn)貨物的距離，li表示第i輛穿梭車沿著運(yùn)行方向到所承擔(dān)任務(wù)上貨端口的距離，若第i輛穿梭車未被分配任務(wù)，li=0;num（i，j）為第i輛穿梭車由于第j輛穿梭車而被堵塞。在本文中，由于環(huán)形穿梭車逆時針方向作業(yè)，因此i和j滿足式（8）所示。

環(huán)形穿梭車系統(tǒng)對式（5）所示模型存在以下約束條件：為了保證穿梭車能夠準(zhǔn)確地停到上貨端口，不會因?yàn)榫嚯x過短而使穿梭車駛過上貨端口。若lstop表示停車距離，則應(yīng)滿足：

在考慮車身長度的情況下，還應(yīng)該滿足相鄰兩輛穿梭車之間的安全距離，若lsafe表示兩輛車的安全距離，li，j表示第輛穿梭車和第j兩穿梭車之間的實(shí)際距離，則應(yīng)滿足：

在本文中，為了簡化問題，我們?nèi)绍嚨陌踩嚯x為穿梭車的車長。

3? ? 基于規(guī)則的調(diào)度算法

（1）規(guī)則1：最近站點(diǎn)優(yōu)先。取貨規(guī)則為：從穿梭車的隊(duì)尾開始，空閑穿梭車選擇最近的入貨端口裝載貨物;卸貨規(guī)則為：從車隊(duì)列的隊(duì)尾開始，裝載貨物的穿梭車選擇最近的出貨端口卸載貨物。

（2）規(guī)則2：最遠(yuǎn)站點(diǎn)優(yōu)先。取貨規(guī)則為：從穿梭車的隊(duì)頭開始，空閑穿梭車選擇最遠(yuǎn)的入貨端口裝載貨物;卸貨規(guī)則為：從車隊(duì)列的隊(duì)頭開始，裝載貨物的穿梭車選擇最遠(yuǎn)的出貨端口卸載貨物。

（3）規(guī)則3：考慮到當(dāng)穿梭車數(shù)量比較多時，大于入貨端口數(shù)量，如果一起出發(fā)，勢必發(fā)生大面積堵車現(xiàn)象。于是每次一趟車輛循環(huán)分解為兩次小循環(huán)，第一組為與出貨口數(shù)接近的車的數(shù)量，第二組為剩下的輛車，為防止擁塞現(xiàn)象，第二組的所有車輛都延遲一定的出發(fā)時間。

規(guī)則1避免了穿梭車隊(duì)列后面的穿梭車選擇較遠(yuǎn)的出貨端口，此次運(yùn)送距離變大，運(yùn)送時間變長。規(guī)則2避免了穿梭車隊(duì)列的前面的穿梭車選擇較近的出貨端口，在卸載貨物過程中堵塞后面的穿梭車，整個系統(tǒng)的效率降低。規(guī)則3避免了因穿梭車數(shù)量較多導(dǎo)致?lián)矶卢F(xiàn)象的頻發(fā)。

4? ? 算例分析

本文采用穿梭車軌道長L=100 m，穿梭車數(shù)量分別為3—9，出貨口數(shù)量為7，入貨口數(shù)量為6進(jìn)行實(shí)驗(yàn)?zāi)M。求得不同數(shù)量下穿梭車調(diào)度系統(tǒng)的吞吐量（見圖1）、以及穿梭車?yán)寐首兓ㄒ妶D2）。

由圖1可知，系統(tǒng)吞吐量隨著穿梭車數(shù)量的增加而逐漸上升。在系統(tǒng)中少于7輛穿梭車時，系統(tǒng)中每增加一輛穿梭車，系統(tǒng)吞吐量約增加0.5個。而在系統(tǒng)中多余7輛穿梭車時，系統(tǒng)中每增加一輛穿梭車，系統(tǒng)吞吐量約增加0.1個。由圖2可知，穿梭車?yán)寐孰S著穿梭車數(shù)量的增加整體呈下降趨勢。穿梭車數(shù)量在4～7個、8～9個區(qū)間內(nèi)呈下降趨勢;穿梭車數(shù)量在3～4個、7～8個區(qū)間內(nèi)呈上升趨勢。

5? ? 結(jié)語

本文構(gòu)建了基于混合規(guī)則的算法模型，對不同環(huán)形穿梭車數(shù)量進(jìn)行了分析，得到了這些參數(shù)對系統(tǒng)吞吐量變換的影響。本文構(gòu)建的模型高效、穩(wěn)定，可以用于工廠倉庫的中環(huán)形穿梭車系統(tǒng)的構(gòu)建，從而提高貨物分揀的效率，縮短貨物總完工時間，對工廠的發(fā)展有著重要的意義。

[參考文獻(xiàn)]

[1]江唯，何非，童一飛，等.基于混合算法的環(huán)形軌道RGV系統(tǒng)調(diào)度優(yōu)化研究[J].計算機(jī)工程與應(yīng)用唯一官方網(wǎng)站，2016（22）：242-247.

[2]YASSIR B，MOHAMMED D，MOHAMMED B，et al.Optimal preventive remanufacturing planning of production equipment under operational and imperfect maintenance constraints：a hybrid genetic algorithm based approach[J].Reliability Engineering & System Safety，2018（9）：1.

[3]EKREN B Y，HERAGU S S，KRISHNAMURTHY A，et al.An approximate solution for semi-open queueing network model of an autonomous vehicle storage and retrieval system[J].IEEE Transactions on Automation Science & Engineering，2013（1）：205-215.

[4]胡建偉，李東波，何非，等.環(huán)形穿梭車調(diào)度系統(tǒng)設(shè)計與開發(fā)[J].物流技術(shù)，2015（9）：266-268.

Abstract：In this paper， based on the dynamic scheduling problem of the ring shuttle， the basic model of the dynamic scheduling of the ring shuttle is solved based on the task completion time minimization structure. First， the objective function that minimizes the task completion time is decomposed into the shortest shuttle handling distance and the least system congestion. Then， an improved hybrid rule algorithm is proposed. Finally， the improved hybrid rule algorithm is used to solve the model.

Key words：shuttle; hybrid rules; multi-index evaluation; dynamic scheduling