基于混合規(guī)則的環(huán)形穿梭車動態(tài)調度系統(tǒng)研究

王同慶 潘璐 張家敏 王靜

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

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

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

1? ? 問題描述

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

1.1? 相關假設

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

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

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

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

2? ? 模型建立

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

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

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

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

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

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

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

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

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

在本文中，為了簡化問題，我們取兩車的安全距離為穿梭車的車長。

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

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

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

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

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

4? ? 算例分析

本文采用穿梭車軌道長L=100 m，穿梭車數量分別為3—9，出貨口數量為7，入貨口數量為6進行實驗模擬。求得不同數量下穿梭車調度系統(tǒng)的吞吐量（見圖1）、以及穿梭車利用率變化（見圖2）。

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

5? ? 結語

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

[參考文獻]

[1]江唯，何非，童一飛，等.基于混合算法的環(huán)形軌道RGV系統(tǒng)調度優(yōu)化研究[J].計算機工程與應用唯一官方網站，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)形穿梭車調度系統(tǒng)設計與開發(fā)[J].物流技術，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