基于自適應量子遺傳算法的環形穿梭車調度系統研究

張雪玉 徐紅博 李赫 肖愛梅

摘 要 環形穿梭車是一種智能的搬運設備，它有著很高的靈活性，而環形穿梭車系統已成為現如今工業生產中最重要的貨物運輸調度方式之一。如何合理設計系統的算法，為工業生產節省更多的時間成為人們需要解決的問題。本文運用排隊論相關知識，結合C++編程，使用量子遺傳算法自適應的確定個體交叉變異概率，為穿梭車系統的設計與調度過程進行了最優化的模擬。通過動態模擬穿梭車調度過程，對環形穿梭車系統進行了多角度的分析，建立了穿梭車動態調度模型，并給出了該系統最優化的貨物處理方案，在實際應用中有較大的參考價值。

關鍵詞 排隊論;動態調度;環形穿梭車;量子遺傳算法

1問題背景

近年來，隨著物流行業的高速發展與廣泛應用，因全球經濟飛速發展等原因，物流運輸對物流作業能力、勞動生產率、物流作業差錯、利潤等方面的要求越來越高。物流運輸已逐漸趨于自動化。環形穿梭車系統是一種智能的搬運設備。以其自動化控制、高速運輸、線路控制、合理作業等特點而獲得廣大用戶的認可和支持，現普遍應用于日用百貨、煙草、機電、醫藥等領域，已成為工業生產中最重要的貨物運輸調度方式之一。如何合理的設計系統的算法，為工業生產節省更多的時間成為人們需要解決的問題。對于環形穿梭車系統的研究和開發，不僅意義重大，而且具有實際運用價值。

2問題描述

環形穿梭車系統[1]由兩側的進出貨口、若干輛穿梭車以及一個環形軌道組成。它的工作流程如下：①穿梭車行至相應進貨口。②若穿梭車前面有車，則等待裝貨;若無，則立即裝載貨物。③穿梭車行至相應出貨口。④若穿梭車前面有車，則等待;若無，則立即卸載貨物⑤循環過程1-4直至所有貨物全部裝卸完畢。

假設環形穿梭車在工作過程中不會出現故障，并且能夠完整地跑完整個過程。環形穿梭車在到達進貨口裝載貨物的時候，能夠立即開始裝貨，即保證進貨口能夠及時供貨側進貨口裝載的貨物只能運送到B指定的出貨口，B側進貨口裝載的貨物可以運送到A側任意出貨口。每個進出貨口都遵循先來先服務的原則，且A側某個進貨口運輸到B側的出貨口的序號不是固定的。在不考慮穿梭車長度的情況下，目標為總完工時間最小[2]。整體流程示意圖如圖1所示。

3模型構建

排隊論[3-4]是研究解決排隊問題的一門學科，因為該系統中穿梭車的調度過程中不允許發生超車，即會出現排隊的情況。在排隊模型中，我們可以把穿梭車看成顧客，把服務機構看成貨物口，排隊服從于先來先服務的規則，當裝卸完畢之后視為服務結束。

由此建立N輛穿梭車的貨物調度模型，計算總完工時間，其可以描述為：

其中代表穿梭車處理第i個貨物所需要的總時間，我們把某個任務的完成時間分為了三部分，空載運行的時間、裝貨運行的時間以及排隊等待的時間，則的計算方式如下：

其中貨物的等待時間為前面需要處理裝卸貨物的穿梭車的個數乘上裝卸貨所需要的時間，即

在穿梭車接收到指令到到達貨物口的這段過程中，穿梭車處于空載狀態，我們設這段距離所需要的時間為：

穿梭車裝載貨物完成后到達目的出貨口的過程，所需要花費的時間為：

為了評定模型效率，建立評價模型，我們從以下三個方面來分析系統的花費時間。

系統完成整個任務的總過程中，穿梭車的空閑時間為：

（n 是需要處理的貨物總數）

不考慮小車長度穿梭車總的擁堵時間：

系統 100 秒內的最大貨物吞吐量：

β為在時間段中完成的貨物個數。根據實際生活中的具體情況，我們對每個影響參數進行加權平均，獲得系統總的效率評價模型：

其中為影響每個參數的權重因子。通過改變穿梭車數目，運行程序100次，測得α1，α2，α3的平均值為 0.1，0.3，0.6。因此采用此比例作為最終的評價權重因子。

4實驗仿真

在系統中，由于穿梭車速度的原因，導致穿梭車裝卸貨物的時間內，后面的穿梭車只能處于等待狀態而浪費了大量時間。因此我們利用問題模型結合遺傳算法，對小車的運行速度進行了優化。

根據本問題的實際需求，本文使用自適應量子遺傳算法[5-7]來對3穿梭車情況下的最優速度問題進行求解，受篇幅所限，自適應量子遺傳算法原理在此不再贅述。算法在2.03s就跑出了結果，其進化代數與相應的調度總時間如圖2所示。可以看出，算法的迭代次數和收斂效果都非常的不錯。

圖2 自適應量子遺傳算法進化代數效果圖

其中算法得到的最終結果與相應時間如圖3所示。

從運行結果可以看出，小車速度并不是越快越好，由于會發生堵塞等原因，3 穿梭車在速度為 5.0m/s 時，總調度時間最短為13126s。

5結束語

本文給出了環形穿梭車的動態調度模型和時間最優化算法。為了能夠實現動態調度最優化，首先把問題分解為多個子問題：環形車的物料運輸問題、環形車的排隊問題，環形車的分配派遣問題，根據不同的子問題建立總的的動態規劃模型。并且將擁堵時間與理想時間的比值、單位時間貨物的最大處理量作為評價依據，建立評價模型。利用自適應量子遺傳算法，對環形穿梭車系統的穿梭車速度參數進行改進，得到了良好的實驗效果。

圖3 自適應量子遺傳算法效果圖

參考文獻

[1] 鄒佰翰，夏鑫，張吉懿.基于貪心策略的環形穿梭車調度算法設計[J].網絡安全技術與應用，2020（4）：52-53.

[2] 向旺，吳雙，張可義，等.基于排隊論的環形穿梭車系統運行參數分析[J].制造業自動化，2018，40（6）：151-153.

[3] 楊少華，張家毅，趙立.基于排隊論的環軌多車數量與能力分析[J].制造業自動化，2011，33（16）：102-104.

[4] 胡建偉，李東波，何非，童一飛.環形穿梭車調度系統設計與開發[J].物流技術，2015，34（9）：266-268.

[5] 余建坤，張文彬，陸玉昌. 遺傳算法及其應用[J]. 云南民族學院學報（自然科學版），2002（4）：193-197.

[6] 曲志堅，張先偉，曹雁鋒，等. 基于自適應機制的遺傳算法研究[J]. 計算機應用研究，2015（11）：3222-3225.

[7] WangY，Feng XY，HuangYX，et al. Anovel quantumswarm evolutionary algorithm and its applications[J].Neurocomputing，2007，70（4-6）：633-640.

作者簡介

張雪玉（1998-），女，山東省煙臺市人;現就讀學校：山東理工大學計算機科學與技術學院，本科在讀，研究方向：智能優化算法。

徐紅博（1998-），男，山東省聊城市人;現就讀學校：山東理工大學計算機科學與技術學院，本科，研究方向：遺傳算法與機器學習。

李赫（1997-），男，山東省濟南市人;現就讀學校：山東理工大學計算機科學與技術學院，本科，研究方向：計算機軟件與應用。

肖愛梅（1973-），女，山東省膠州市;學歷：碩士，職稱：副教授，現就職單位：山東理工大學計算機科學與技術學院，研究方向：計算機軟件與應用。