基于混合規則的環形穿梭車動態調度系統研究

王同慶 潘璐 張家敏 王靜

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

關鍵詞：穿梭車;混合規則;多指標評價;動態調度

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

1? ? 問題描述

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

1.1? 相關假設

（1）環形穿梭車、出入貨端口在整個調度運行周期中有故障發生時，系統停止運行，對調度優化過程不產生影響。

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

（3）本文中環形穿梭車和出入貨端口編號沿逆時針依次統一編號。

（4）在不考慮優化算法執行時間的情況下，即環形穿梭車系統調度是在理想情況下執行的可以忽略系統執行算法的時間。

2? ? 模型建立

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

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

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

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

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

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

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

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

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

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

3? ? 基于規則的調度算法

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

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

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

規則1避免了穿梭車隊列后面的穿梭車選擇較遠的出貨端口，此次運送距離變大，運送時間變長。規則2避免了穿梭車隊列的前面的穿梭車選擇較近的出貨端口，在卸載貨物過程中堵塞后面的穿梭車，整個系統的效率降低。規則3避免了因穿梭車數量較多導致擁堵現象的頻發。

4? ? 算例分析

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

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

5? ? 結語

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

[參考文獻]

[1]江唯，何非，童一飛，等.基于混合算法的環形軌道RGV系統調度優化研究[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]胡建偉，李東波，何非，等.環形穿梭車調度系統設計與開發[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