基于自適應(yīng)量子遺傳算法的環(huán)形穿梭車調(diào)度系統(tǒng)研究

張雪玉 徐紅博 李赫 肖愛梅

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

關(guān)鍵詞 排隊(duì)論;動(dòng)態(tài)調(diào)度;環(huán)形穿梭車;量子遺傳算法

1問題背景

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

2問題描述

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

假設(shè)環(huán)形穿梭車在工作過程中不會(huì)出現(xiàn)故障，并且能夠完整地跑完整個(gè)過程。環(huán)形穿梭車在到達(dá)進(jìn)貨口裝載貨物的時(shí)候，能夠立即開始裝貨，即保證進(jìn)貨口能夠及時(shí)供貨側(cè)進(jìn)貨口裝載的貨物只能運(yùn)送到B指定的出貨口，B側(cè)進(jìn)貨口裝載的貨物可以運(yùn)送到A側(cè)任意出貨口。每個(gè)進(jìn)出貨口都遵循先來先服務(wù)的原則，且A側(cè)某個(gè)進(jìn)貨口運(yùn)輸?shù)紹側(cè)的出貨口的序號(hào)不是固定的。在不考慮穿梭車長(zhǎng)度的情況下，目標(biāo)為總完工時(shí)間最小[2]。整體流程示意圖如圖1所示。

3模型構(gòu)建

排隊(duì)論[3-4]是研究解決排隊(duì)問題的一門學(xué)科，因?yàn)樵撓到y(tǒng)中穿梭車的調(diào)度過程中不允許發(fā)生超車，即會(huì)出現(xiàn)排隊(duì)的情況。在排隊(duì)模型中，我們可以把穿梭車看成顧客，把服務(wù)機(jī)構(gòu)看成貨物口，排隊(duì)服從于先來先服務(wù)的規(guī)則，當(dāng)裝卸完畢之后視為服務(wù)結(jié)束。

由此建立N輛穿梭車的貨物調(diào)度模型，計(jì)算總完工時(shí)間，其可以描述為：

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

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

在穿梭車接收到指令到到達(dá)貨物口的這段過程中，穿梭車處于空載狀態(tài)，我們?cè)O(shè)這段距離所需要的時(shí)間為：

穿梭車裝載貨物完成后到達(dá)目的出貨口的過程，所需要花費(fèi)的時(shí)間為：

為了評(píng)定模型效率，建立評(píng)價(jià)模型，我們從以下三個(gè)方面來分析系統(tǒng)的花費(fèi)時(shí)間。

系統(tǒng)完成整個(gè)任務(wù)的總過程中，穿梭車的空閑時(shí)間為：

（n 是需要處理的貨物總數(shù)）

不考慮小車長(zhǎng)度穿梭車總的擁堵時(shí)間：

系統(tǒng) 100 秒內(nèi)的最大貨物吞吐量：

β為在時(shí)間段中完成的貨物個(gè)數(shù)。根據(jù)實(shí)際生活中的具體情況，我們對(duì)每個(gè)影響參數(shù)進(jìn)行加權(quán)平均，獲得系統(tǒng)總的效率評(píng)價(jià)模型：

其中為影響每個(gè)參數(shù)的權(quán)重因子。通過改變穿梭車數(shù)目，運(yùn)行程序100次，測(cè)得α1，α2，α3的平均值為 0.1，0.3，0.6。因此采用此比例作為最終的評(píng)價(jià)權(quán)重因子。

4實(shí)驗(yàn)仿真

在系統(tǒng)中，由于穿梭車速度的原因，導(dǎo)致穿梭車裝卸貨物的時(shí)間內(nèi)，后面的穿梭車只能處于等待狀態(tài)而浪費(fèi)了大量時(shí)間。因此我們利用問題模型結(jié)合遺傳算法，對(duì)小車的運(yùn)行速度進(jìn)行了優(yōu)化。

根據(jù)本問題的實(shí)際需求，本文使用自適應(yīng)量子遺傳算法[5-7]來對(duì)3穿梭車情況下的最優(yōu)速度問題進(jìn)行求解，受篇幅所限，自適應(yīng)量子遺傳算法原理在此不再贅述。算法在2.03s就跑出了結(jié)果，其進(jìn)化代數(shù)與相應(yīng)的調(diào)度總時(shí)間如圖2所示?？梢钥闯觯惴ǖ牡螖?shù)和收斂效果都非常的不錯(cuò)。

圖2 自適應(yīng)量子遺傳算法進(jìn)化代數(shù)效果圖

其中算法得到的最終結(jié)果與相應(yīng)時(shí)間如圖3所示。

從運(yùn)行結(jié)果可以看出，小車速度并不是越快越好，由于會(huì)發(fā)生堵塞等原因，3 穿梭車在速度為 5.0m/s 時(shí)，總調(diào)度時(shí)間最短為13126s。

5結(jié)束語

本文給出了環(huán)形穿梭車的動(dòng)態(tài)調(diào)度模型和時(shí)間最優(yōu)化算法。為了能夠?qū)崿F(xiàn)動(dòng)態(tài)調(diào)度最優(yōu)化，首先把問題分解為多個(gè)子問題：環(huán)形車的物料運(yùn)輸問題、環(huán)形車的排隊(duì)問題，環(huán)形車的分配派遣問題，根據(jù)不同的子問題建立總的的動(dòng)態(tài)規(guī)劃模型。并且將擁堵時(shí)間與理想時(shí)間的比值、單位時(shí)間貨物的最大處理量作為評(píng)價(jià)依據(jù)，建立評(píng)價(jià)模型。利用自適應(yīng)量子遺傳算法，對(duì)環(huán)形穿梭車系統(tǒng)的穿梭車速度參數(shù)進(jìn)行改進(jìn)，得到了良好的實(shí)驗(yàn)效果。

圖3 自適應(yīng)量子遺傳算法效果圖

參考文獻(xiàn)

[1] 鄒佰翰，夏鑫，張吉懿.基于貪心策略的環(huán)形穿梭車調(diào)度算法設(shè)計(jì)[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2020（4）：52-53.

[2] 向旺，吳雙，張可義，等.基于排隊(duì)論的環(huán)形穿梭車系統(tǒng)運(yùn)行參數(shù)分析[J].制造業(yè)自動(dòng)化，2018，40（6）：151-153.

[3] 楊少華，張家毅，趙立.基于排隊(duì)論的環(huán)軌多車數(shù)量與能力分析[J].制造業(yè)自動(dòng)化，2011，33（16）：102-104.

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

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

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

[7] WangY，F(xiàn)eng XY，HuangYX，et al. Anovel quantumswarm evolutionary algorithm and its applications[J].Neurocomputing，2007，70（4-6）：633-640.

作者簡(jiǎn)介

張雪玉（1998-），女，山東省煙臺(tái)市人;現(xiàn)就讀學(xué)校：山東理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，本科在讀，研究方向：智能優(yōu)化算法。

徐紅博（1998-），男，山東省聊城市人;現(xiàn)就讀學(xué)校：山東理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，本科，研究方向：遺傳算法與機(jī)器學(xué)習(xí)。

李赫（1997-），男，山東省濟(jì)南市人;現(xiàn)就讀學(xué)校：山東理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，本科，研究方向：計(jì)算機(jī)軟件與應(yīng)用。

肖愛梅（1973-），女，山東省膠州市;學(xué)歷：碩士，職稱：副教授，現(xiàn)就職單位：山東理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，研究方向：計(jì)算機(jī)軟件與應(yīng)用。