鄧夢(mèng)怡，吳旺春，胡春筠，俞龍，胡菁

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

1 綜述

1.1 問(wèn)題的研究背景

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

1.2 問(wèn)題來(lái)源

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

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

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

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

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

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

3 模型的建立

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

圖2 快件處理流程

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

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

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

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

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

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

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

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

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

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

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

3.4 模擬退火算法

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

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

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

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

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

3.5 算例分析

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

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

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

圖4 普通快件所受影響

圖5 加急快件所受影響

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

模擬退火算法對(duì)目標(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件/小時(shí)為圖6中的拐點(diǎn)，經(jīng)迭代計(jì)算得到的拐點(diǎn)處目標(biāo)函數(shù)取得最大值、效率最高。

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

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

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

圖8 加急后普通快件等待時(shí)間對(duì)比

4 結(jié)語(yǔ)

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