模擬退火算法求解排隊(duì)中的加急問題

鄧夢怡，吳旺春，胡春筠，俞龍，胡菁

（華南農(nóng)業(yè)大學(xué)電子信息工程與人工智能學(xué)院，廣州5106401）

1 綜述

1.1 問題的研究背景

近年來快遞市場的競爭日益激烈，越來越多的快遞企業(yè)為了縮短交貨期，開始開發(fā)更快捷的服務(wù)，如“次日交貨”、“次日早晨交貨”[1]。因此，快遞企業(yè)要想在快遞市場贏得更多的客戶，就必須形成核心競爭力。快遞中轉(zhuǎn)站作為物流行業(yè)的一個重要節(jié)點(diǎn)，每時每刻需要面對無限的快件數(shù)，快件流量大，隨機(jī)性強(qiáng)，工作情況變化快。因此，如何及時、高效、準(zhǔn)確地將快遞運(yùn)送至顧客手中，這對于獲取消費(fèi)者的好評、延續(xù)與商家的合作至關(guān)重要。

1.2 問題來源

快遞中轉(zhuǎn)站如若無法及時合理地處理快件，就會導(dǎo)致工作效率低，許多快件也會無法按時發(fā)出。而快遞中轉(zhuǎn)站中機(jī)器調(diào)度可能受到機(jī)器類型、工作特點(diǎn)、機(jī)器成本等諸多因素的制約。由于不同類型的快件處理所規(guī)定的時間不同，且快件到達(dá)數(shù)隨機(jī)性強(qiáng)[2]，因此，機(jī)器調(diào)度問題并非簡單的線性規(guī)劃問題，機(jī)器處理方案導(dǎo)致的時間沖突也成為機(jī)器調(diào)度中的關(guān)鍵問題。針對排隊(duì)問題，許多研究者做了大量的研究，目前有遺傳算法、禁忌搜索等優(yōu)化算法，將排隊(duì)問題簡化為單目標(biāo)規(guī)劃問題迭代求解，但《隨機(jī)排隊(duì)論對大型醫(yī)院急診觀察室工作流程的優(yōu)化》[4]、《航班登機(jī)口分配問題的數(shù)學(xué)建?！穂8]等文獻(xiàn)中提到的研究方法適于解決單位時間流量較少且隊(duì)長較穩(wěn)定情況下的問題，但由于快件具有隨機(jī)性強(qiáng)、流量大等特點(diǎn)，若將同樣的方法應(yīng)用在快件問題上，求解出的等待時間波動大且不穩(wěn)定，這不利于機(jī)器及時識別快件類型并及時做出調(diào)度，從而加劇了機(jī)器的阻塞。

1.3 基于不同快件類型的排隊(duì)問題研究模型

本文在隨機(jī)排隊(duì)論的基礎(chǔ)上對排隊(duì)問題加以完善，以時間為約束條件進(jìn)行多目標(biāo)規(guī)劃，并引入優(yōu)先級的概念，將加急快件與普通快件設(shè)置為不同的優(yōu)先級，通過模擬退火算法進(jìn)行迭代計(jì)算。在時間不沖突的條件下，綜合優(yōu)化機(jī)器的分配方案，適當(dāng)?shù)匮娱L普通快件的平均等待時間，提高加急快件優(yōu)先級，根據(jù)實(shí)時機(jī)器工作特點(diǎn)以及快件量做出響應(yīng)的調(diào)整，從而完善快件的處理方法、獲取消費(fèi)者以及商家對物流服務(wù)的滿意度[3]。

2 問題的描述與假設(shè)

為優(yōu)化快件的處理，可以將快件處理問題理解為先來先處理的排隊(duì)問題，通過對快遞中轉(zhuǎn)站每日到達(dá)快件數(shù)進(jìn)行分析，在快件量基本為飽和狀態(tài)的情況下，安排機(jī)器的工作休息時間?？爝f中轉(zhuǎn)站機(jī)器調(diào)度是指在考慮快件等待時間、機(jī)器工作特點(diǎn)、規(guī)定截止工作時間等因素的情況下對某個時間段內(nèi)到達(dá)的快件分配合適的機(jī)器。本文結(jié)合隨機(jī)排隊(duì)論分析等待時間，尋求縮短加急快件等待時間的方法；結(jié)合約束條件，快件流量最大化進(jìn)行多目標(biāo)分析如圖1所示。根據(jù)快件處理的不同需求，本文設(shè)置不同的權(quán)重系數(shù)，將多目標(biāo)轉(zhuǎn)化為單目標(biāo)[5]，運(yùn)用模擬退火算法求解。

圖1 多目標(biāo)分析

3 模型的建立

普通快件與加急快件處理時間范圍不同，在機(jī)器被全部使用的情況下，快件只能等待，可能對物流的速度帶來不利影響。因此，快件與機(jī)器的調(diào)度應(yīng)首先把機(jī)器盡可能多地分配到加急快件中確?？旒磿r發(fā)出，實(shí)際數(shù)據(jù)處理過程中，我們應(yīng)根據(jù)快件的性質(zhì)合理地設(shè)置排隊(duì)序列，具體流程如圖2所示[5]。

圖2 快件處理流程

3.1 排隊(duì)序列的設(shè)置

生成1到n之間的隨機(jī)整數(shù)序列（代表n臺機(jī)器），以先到先服務(wù)的原則對快件隨機(jī)地進(jìn)行機(jī)器分配。為體現(xiàn)分配情況，將一天化為86400秒，產(chǎn)生n×86400的全零矩陣，代表每件快件可分配秒數(shù)，若快件成功分配則對應(yīng)機(jī)器秒數(shù)記1，否則記0[6]，即若機(jī)器與快件處理時間沖突，該時刻機(jī)器記0，返回上一層；若不沖突，則分配至此[7-8]。

3.2 隨機(jī)排隊(duì)論

中轉(zhuǎn)站對快件的處理是一個典型的M/（M×N×∞）排隊(duì)等待服務(wù)問題，單位時間內(nèi)所需生產(chǎn)加工處理的普通快件數(shù)符合到達(dá)率為λ的泊松分布[9]，其中緊急快件等待時間要盡可能地縮短才能滿足需求。因此，引入具有優(yōu)先級的排隊(duì)分析，設(shè)置普通產(chǎn)品優(yōu)先級較低，服從到達(dá)率λ1泊松分布；加急產(chǎn)品優(yōu)先級高，服從到達(dá)率λ2泊松分布[10]。令單位時間機(jī)器處理快件能力為μ件/小時，則單件產(chǎn)品處理時間T為1/μ，相關(guān)性能指標(biāo)如表1所示[11-12]。

表1 相關(guān)性能指標(biāo)

根據(jù)加急快件的比例，除以一個趨近1的數(shù)，可以適當(dāng)延長普通快件平均等待時間：

由于快件平均處理時間不變，根據(jù)各類快件比例，解出加急快件平均等待時間：

3.3 多目標(biāo)規(guī)劃

每臺機(jī)器開始處理快件的時刻都是隨機(jī)的、獨(dú)立的，而且所有機(jī)器處理快件必須滿足每天工作要求。考慮到在t時刻到達(dá)的普通快件須在t1時刻前完成，加急快件須在t2時刻前完成從而建立約束條件。針對表1的3個目標(biāo)，為了保證機(jī)器的工作效率最大化，可建立以機(jī)器處理快件量最大化，且快件平均排隊(duì)時間最短最小化的多目標(biāo)規(guī)劃模型[13]：

其中，zk為第k個目標(biāo)，Cij為第i臺機(jī)器在j時刻處理或生產(chǎn)的物品件數(shù)，xij為第i臺機(jī)器在j時刻的工作狀態(tài)，當(dāng)機(jī)器處于工作狀態(tài)時xij=1，當(dāng)機(jī)器處于不工作狀態(tài)時xij=0。

對機(jī)器處理快件量、快件平均排隊(duì)時間、加急快件平均排隊(duì)時間分別賦予加權(quán)系數(shù)a、b、c構(gòu)建關(guān)于λ的單目標(biāo)模型[14-15]：

3.4 模擬退火算法

單目標(biāo)模型較難求解，因此考慮用模擬退火算法來解決快件處理問題，以便較好地處理復(fù)雜目標(biāo)函數(shù)。算法通過a、b、c設(shè)置普通快件與加急快件的優(yōu)先級后，根據(jù)適應(yīng)值，判斷是否接受新的處理方案進(jìn)行對比計(jì)算，通過迭代進(jìn)而求得最佳方案[16-20]。對目標(biāo)函數(shù)進(jìn)行求解方法如下：

（1）以最大快件量為初始解（設(shè)置退火溫度）；

（2）結(jié)合優(yōu)先級設(shè)懲罰系數(shù)，求解目標(biāo)函數(shù)，計(jì)算目標(biāo)值的變化量D，并與初始解比較；

（4）設(shè)置退火代數(shù)，如若達(dá)到，則視為最優(yōu)解[21]；

（5）通過最優(yōu)解結(jié)合加急快件占比求得相應(yīng)的排隊(duì)隊(duì)長，更新排隊(duì)序列。

3.5 算例分析

某快遞站所有設(shè)備處理快件能力約為5600件/小時，72小時中快件平均到達(dá)件數(shù)為5560件/小時（部分時間段超出5600件/小時），加急快件約占快件的3.245%。本方案求解得出的各項(xiàng)指標(biāo)如圖3所示。

圖3 各項(xiàng)指標(biāo)

圖3 在部分加急快件適當(dāng)插隊(duì)的情況下，由于加急快件的比例相對較低，加急快件對普通快件的排隊(duì)等待時間影響有限，故普通快件平均等待時長僅增比1.65%，而加急快件等待時長卻縮短了49.10%，效果較好，該方案可以大幅度地縮短加急快件處理時間，而普通快件的處理時間僅有小幅度的上升。為探究兩類快件所受影響的程度，下面根據(jù)加急快件所占比例及其波動程度作進(jìn)一步的探究，當(dāng)平均所有快件到達(dá)率為5560件/小時，加急快件占比不同的情況下排隊(duì)時間增減比例如圖4、圖5所示。

圖4 普通快件所受影響

圖5 加急快件所受影響

對比可知，隨著加急快件比例的增大，優(yōu)先級對加急快件的影響逐漸減弱直至消失。隨機(jī)排隊(duì)論對大多數(shù)比例的加急快件均表現(xiàn)出較好的效果，其中加急快件占比較小的情況下效果更佳。

模擬退火算法對目標(biāo)規(guī)劃中的式（7）求解，具體參數(shù)如下：迭代總數(shù)為1000，初始溫度為5560℃，溫度冷卻系數(shù)為0.97，且結(jié)合實(shí)際，將式（7）中的權(quán)重系數(shù)a、b、c設(shè)為1、5、10，迭代次數(shù)與目標(biāo)函數(shù)maxzz的關(guān)系如圖6所示。

圖6 迭代效果圖

在權(quán)重系數(shù)a、b、c分別為1、5、10的情況下，當(dāng)所有快件到達(dá)率為5410件/小時為圖6中的拐點(diǎn)，經(jīng)迭代計(jì)算得到的拐點(diǎn)處目標(biāo)函數(shù)取得最大值、效率最高。

《隨機(jī)排隊(duì)論對大型醫(yī)院急診觀察室工作流程的優(yōu)化》[4]通過排隊(duì)論求解排隊(duì)時間再根據(jù)加急快件所占比例縮短加急快件的排隊(duì)隊(duì)長，其與本文提出的方案各項(xiàng)指標(biāo)對比如圖7、圖8所示。

由圖7、圖8對比可知，對比方案中的兩個指標(biāo)在斷點(diǎn)附近（快件到達(dá)率超出設(shè)備處理能力）排隊(duì)時間大幅度增加、波動大；加急情況下求解出的加急快件的平均等待時間由76.2秒降至0.632秒可知其加急快件排隊(duì)隊(duì)長的設(shè)置是不合理的，這不利于機(jī)器及時識別快件類型做出機(jī)器的調(diào)度。而本文提出的方案通過式（1）以及目標(biāo)規(guī)劃設(shè)置優(yōu)先級，用模擬退火算法得出最優(yōu)解，從而使排隊(duì)時間更加穩(wěn)定波動減小，同時可通過調(diào)整優(yōu)先級設(shè)置更為合理的加急快件隊(duì)長。綜上所述，本文提出的排隊(duì)方案更加穩(wěn)定，且更有利于機(jī)器及時識別快件種類并做出調(diào)度。

圖7 快件平均排隊(duì)時間對比

圖8 加急后普通快件等待時間對比

4 結(jié)語

本文模型的建立考慮到機(jī)器工作特點(diǎn)、規(guī)定工作快件處理時間、快件加急情況等，通過隨機(jī)排隊(duì)論求解排隊(duì)時間、設(shè)置優(yōu)先級，確立多個目標(biāo)函數(shù)，結(jié)合約束條件，設(shè)置優(yōu)先級轉(zhuǎn)化為單目標(biāo)規(guī)劃，最后使用模擬退火算法實(shí)現(xiàn)三個優(yōu)化目標(biāo)效率的優(yōu)化并更新隊(duì)列，其結(jié)果對機(jī)器的調(diào)度具有一定的參考價值。