大批量訂單整體分揀問題建模及其分布式并行方法①

趙云波 李天舒 汪鈺皓

(浙江工業(yè)大學(xué)信息工程學(xué)院 杭州 310000)

0 引 言

大型生產(chǎn)和銷售需要對大批量訂單進(jìn)行揀取，典型場景可見于大型電商的倉庫系統(tǒng)。在較短時間內(nèi)倉庫收到從電商平臺產(chǎn)生的大量訂單，倉庫系統(tǒng)需按照每份訂單中包含的商品種類和數(shù)量從倉庫中揀選貨物并打包，隨后交付物流系統(tǒng)。這一訂單分揀過程的準(zhǔn)確性和快速性影響著整體電商流程的效率，已經(jīng)引起如亞馬遜、京東等各大電商的廣泛注意，應(yīng)用了各種尖端技術(shù)[1-2]。

常用的訂單分揀方式將所有待處理訂單中的所有貨物歸為統(tǒng)一的待揀貨集合進(jìn)行統(tǒng)一處理。系統(tǒng)從倉庫貨架上依照待揀貨集合逐一揀選商品，然后運(yùn)送至特定地點(diǎn)按照訂單進(jìn)行打包。訂單分揀過程分為3個步驟，即貨物揀選、貨物運(yùn)送和訂單打包[3]。貨物揀選大多手工進(jìn)行，可通過優(yōu)化物品和貨架擺放[4-7]、劃分批次等方式提升效率[8-11]。貨物運(yùn)送過程通?？梢越栌蓚魉蛶Щ驘o人車自動化進(jìn)行[12]，傳送帶路線設(shè)置、無人車路徑規(guī)劃等是這一步驟效率提升所需考慮的問題[13-16]。訂單打包的物理過程較為簡單，但其執(zhí)行依賴于訂單中的貨物是否可以準(zhǔn)確快速到達(dá)，這是衡量整個分揀系統(tǒng)效率的標(biāo)志。

現(xiàn)有訂單分揀方式存在的主要問題是大批量訂單“整體分揀”能力低。整體分揀是指對任意訂單中的貨物完整地分揀出來并打包，而不將訂單分拆為子訂單，每一子訂單僅包含所考慮訂單貨物的真子集。整體分揀是電商系統(tǒng)的天然要求，因為電商的每一個訂單都對應(yīng)唯一一個運(yùn)送目的地，將一個訂單分拆為多個子訂單將成倍增加后續(xù)物流包裹的數(shù)量，增加物流成本。但是，現(xiàn)有訂單分揀方式本質(zhì)上不適應(yīng)這一整體分揀的要求，其核心原因是對訂單打包點(diǎn)的限制。大多數(shù)方法的訂單打包點(diǎn)都設(shè)置為較少的特定地點(diǎn)，比如使用傳送帶進(jìn)行已揀選貨物的運(yùn)送，打包點(diǎn)應(yīng)在傳送帶的出口(可設(shè)置多個出口)；若使用無人車方式進(jìn)行已揀選貨物的運(yùn)送，作為打包點(diǎn)的運(yùn)送目的地通常也較為集中，容易導(dǎo)致?lián)矶潞托实拖耓17]。現(xiàn)有的對整體分揀的研究，未從根本上解決這一難題[18-19]。在訂單分揀問題的研究中，大多關(guān)注于具體情境下的設(shè)置和算法，缺少描述問題的統(tǒng)一數(shù)學(xué)框架，導(dǎo)致對這一問題研究不足。

面向上述的大批量訂單整體分揀問題缺少嚴(yán)格模型和有效方法的現(xiàn)實，本文首先對該過程進(jìn)行嚴(yán)格的數(shù)學(xué)模型化，進(jìn)而提出一種基于智能貨架的分布式并行解決方案。該模型定量描述了整體分揀的靜態(tài)狀態(tài)和動態(tài)演化，給出了整體分揀問題的明確定義。依托這一模型，提出了相應(yīng)的解決方案，其核心思想是使用智能貨架作為訂單分揀點(diǎn)，將訂單分揀過程從原先的單一分揀點(diǎn)改造為分布式并行分揀點(diǎn)，從本質(zhì)上滿足了整體分揀的需求。這一改造方式引出了若干技術(shù)上的困難，如無人車在不碰撞前提下的高效運(yùn)行方式，訂單的分配方案等。本文在預(yù)測控制和優(yōu)化等框架下對問題進(jìn)行了有效解決，仿真實驗證明了所提出方法的有效性。

本文其他部分組織如下。第1節(jié)通過對訂單分揀系統(tǒng)的靜態(tài)狀態(tài)、動態(tài)演化和系統(tǒng)目標(biāo)等描述，給出了大批量訂單整體分揀問題的數(shù)學(xué)模型。第2節(jié)描述所提出的分布式并行整體分揀方法，包括其基本思路、改進(jìn)模型、關(guān)鍵技術(shù)問題和完整算法等方面。第3節(jié)利用仿真對比實驗證明了所提出的分布式并行方法的有效性。第4節(jié)總結(jié)全文。

1 大批量訂單整體分揀問題的模型化

考慮某一封閉倉庫區(qū)域H內(nèi)使用無人車進(jìn)行貨物運(yùn)送的訂單分揀系統(tǒng)。該系統(tǒng)具有如下特點(diǎn)：在任一時刻有大量的訂單待處理；每一訂單需將其包含的所有貨物全部分揀出來并整體打包，不允許進(jìn)行分拆。本節(jié)對這一訂單整體分揀問題模型化，首先描述訂單系統(tǒng)在任一固定時刻t的靜態(tài)狀態(tài)，然后刻畫訂單系統(tǒng)在時間[t,t+1)內(nèi)的動態(tài)演化過程，最后給出問題的明確定義。

本文中所用符號較多，故將本文所用符號及其含義列為表1。

1.1 訂單分揀系統(tǒng)在t時刻的靜態(tài)狀態(tài)描述

首先對訂單分揀系統(tǒng)在t時刻的靜態(tài)狀態(tài)給出符號化描述。這包含貨物和貨架的狀態(tài)、待處理訂單情況和無人車的狀態(tài)。

表1 符號列表

貨物和貨架設(shè)該倉儲區(qū)域內(nèi)中有Ns個貨架，記第i個貨架為Si，設(shè)貨物種類總數(shù)為Ng，每一貨物以其標(biāo)識號g為唯一識別，并均存放于某一貨架Sg上。記標(biāo)號為g的貨物為Gg，則Gg可表示為

Gg:={g,Sg,Ig}

(1)

其中，Ig為貨物Gg在當(dāng)前時刻的處理狀態(tài)，定義如下：

(2)

注意其中Ig=0，即“貨物在分揀中”的含義是該貨物已經(jīng)交由某無人車運(yùn)送處理，但尚未取回。

待處理訂單每一個訂單包含其唯一的訂單標(biāo)識號o，該訂單進(jìn)行整體分揀處理的打包點(diǎn)po，訂單到達(dá)訂單分揀系統(tǒng)的時刻to，和它所包含的所有貨物，記該訂單為Oo，則：

(3)

記Io(t)為t時刻所有待處理訂單的標(biāo)識號集合，其個數(shù)記為No(t):=|Io(t)|。則t時刻待處理訂單的集合可寫為

Θ(t)∶={Oo|o∈Io(t)}

(4)

無人車設(shè)該倉庫區(qū)域內(nèi)有Nv輛無人車用于貨物運(yùn)送。記第i輛無人車為Vi，所有無人車的集合記為V，即：

V∶={Vi|i=1, …,Nv}

(5)

無人車接受貨物運(yùn)送的指令，從相應(yīng)貨架取得貨物，并將其運(yùn)送到目的地。在時刻t的無人車狀態(tài)由其當(dāng)前位置、運(yùn)動情況、承擔(dān)貨物運(yùn)輸情況等信息描述。記無人車Vi在t時刻的狀態(tài)為Vi(t)，則：

(6)

其中，li(t)、vi(t)和ai(t)分別為無人車Vi的位置、速度和加速度。在笛卡爾坐標(biāo)系下(假設(shè)已經(jīng)建有原點(diǎn)和x，y軸)，有：

(7)

(8)

(9)

其中，上標(biāo)x和y分別表示相應(yīng)向量在x軸和y軸的分量。

由以上定義可知，t時刻空閑的無人車集合VI(t)可計算如下：

i=1,…,Nv} (10)

從而，正在執(zhí)行某項任務(wù)的無人車集合Vo(t)可計算如下：

i=1,…,Nv} (11)

可知，在t時刻訂單分揀系統(tǒng)的靜態(tài)狀態(tài)可由式(4)中的待處理訂單集合Θ(t)和式(6)中的所有無人車的狀態(tài)Vi(t),i=1, …,Nv完全描述。

1.2 訂單分揀系統(tǒng)在[t, t+1)時間間隔內(nèi)的動態(tài)演化

本節(jié)定量描述訂單分揀系統(tǒng)在[t,t+1)時間間隔內(nèi)的動態(tài)演化。包含新訂單的產(chǎn)生過程、訂單的處理過程和無人車的運(yùn)動。注意，[t,t+1)時間間隔的大小主要由無人車的運(yùn)動情況確定，在該時間間隔內(nèi)，無人車的運(yùn)動不會過大而影響算法設(shè)計，具體數(shù)值需由具體應(yīng)用確定。

新訂單的產(chǎn)生考慮大型電商訂單的復(fù)雜性，假定訂單的到來是隨機(jī)的。類似情形的隨機(jī)分布一般建模為指數(shù)分布。指數(shù)分布假設(shè)在很小的時間間隔Δt內(nèi)，一個新訂單到來的概率是λΔt，其中λ是指數(shù)分布的強(qiáng)度，即：

Pr{一個新訂單在[t,t+Δt)到達(dá)}=λ

(12)

由上式可知，[t,t+ 1)時間間隔內(nèi)新到訂單數(shù)的期望為λ/Δt。

根據(jù)式(3)，新到的標(biāo)號為N的訂單可記為

(13)

(14)

(15)

在具體的訂單系統(tǒng)中，可通過調(diào)節(jié)上述概率κi和ηj描述訂單包含貨物的數(shù)量變化和貨物在貨架的擺放情況。

同時也需注意，上述新訂單產(chǎn)生過程是對真實訂單分揀系統(tǒng)的模擬，是為了在數(shù)學(xué)模型中對該過程進(jìn)行描述，有利于后續(xù)訂單分揀方法的設(shè)計。而在實際的訂單分揀系統(tǒng)運(yùn)行中并不需要上述模擬過程，新訂單是系統(tǒng)實際產(chǎn)生的。

訂單的處理在[t,t+ 1)時間內(nèi)，待處理訂單中的貨物Gg若被訂單分揀系統(tǒng)處理，則其狀態(tài)會相應(yīng)發(fā)生變化。將貨物的狀態(tài)變化標(biāo)記為ΔIg，令：

(16)

本文選擇的時間間隔足夠小，保證了在每一步貨物的3種狀態(tài)最多只能發(fā)生一步變化。因此，

Ig(t+1)=Ig(t)+ΔIg

(17)

令co為訂單Oo中所有貨物的處理狀態(tài)的最小值，即：

co∶=minIg∈Gg∈OoIg

(18)

注意訂單Oo仍待處理的充要條件是該訂單中仍有貨物未分揀完，即：

(19)

注意co<1包含了co=0和co=-1兩種可能。若co=0，則Oo內(nèi)所有貨物都已經(jīng)安排分揀，但尚有貨物還未分揀完成；若co=-1，則Oo內(nèi)尚有貨物未安排分揀。不管是哪種情況，訂單Oo都尚未完成分揀。

由此，在[t,t+ 1)時間內(nèi)處理完的訂單集合為

ΘC(t+1)={Oo∈Θ(t)|co(t+1)=1}

(20)

從而，t+1時刻的待處理訂單集合可由下式計算：

Θ(t+1)=

(21)

其中，符號“”表示集合的差集。

無人車的運(yùn)動無人車Vi在[t,t+ 1)內(nèi)的運(yùn)動取決于無人車的初始位置li(t)、初速度vi(t)和此時間間隔內(nèi)的加速度ai(t)。由于[t,t+ 1)很小，可假設(shè)在此時間內(nèi)加速度為常值，即在[t,t+ 1)內(nèi)有：

(22)

由式(6)可知，無人車在t+1時刻的狀態(tài)可寫為

Vi(t+1)={li(t+1),vi(t+1),ai(t+1),

(23)

其中，ai(t+1)在t+1時刻由算法確定，且：

(24)

(25)

(26)

1.3 大批量訂單整體分揀問題

綜合1.1和1.2兩小節(jié)給出的訂單分揀系統(tǒng)運(yùn)行的基本描述。希望設(shè)計算法盡可能提升系統(tǒng)的運(yùn)行效率。在此之前，需要給出算法及其限制條件和運(yùn)行效率的定量描述。

算法的定義所設(shè)計的算法應(yīng)處理2方面的工作：一方面是將待處理訂單中的貨物分配給無人車進(jìn)行分揀和運(yùn)送；另一方面是協(xié)調(diào)指揮無人車的運(yùn)動。

注意到t時刻所有尚需分配無人車進(jìn)行分揀和運(yùn)送的貨物的集合為

Gg(t)={Gg|Gg∈Oo∈Θ(t),Ig(t)=-1}

(27)

首先，算法將Gg(t)中的貨物分配給空閑無人車VI(t)進(jìn)行運(yùn)輸，即設(shè)計如下函數(shù)：

fgv:Gg(t)→VI(t)

(28)

而假設(shè)函數(shù)fgv與時刻t無關(guān)。這是因為，上述映射的確定僅決定當(dāng)前的待處理貨物集合Gg(t)和空閑無人車集合VI(t)，而與時刻t無明顯依賴關(guān)系。

另一方面，算法也需要給出每一輛無人車在[t,t+1)內(nèi)的運(yùn)行規(guī)則。在已知t時刻無人車Vi的動力學(xué)狀態(tài)前提下(即li(t)和vi(t))，等價于給出在此時間內(nèi)每一輛運(yùn)行中無人車的加速度ai(t),Vi∈ VO(t)。從而，所設(shè)計的算法具有如下形式：

(29)

限制條件在本文中，限制條件主要指無人車的物理性質(zhì)及其動力學(xué)特性。

無人車所運(yùn)行的范圍、速度和加速度都有其限制，總結(jié)如下：

(30)

其中，vmax和amax分別是無人車的速度和加速度上界。本文假定所有無人車都有相同的動力學(xué)特性，因此vmax和amax對所有無人車都相同。這在大多數(shù)實際系統(tǒng)中是成立的。

無人車在運(yùn)行過程中不可相互碰撞。定義2輛無人車Vi，Vj間的歐氏距離為

(31)

(32)

其中，d(·，·)表示2點(diǎn)之間的歐氏距離。

任意2輛無人車的距離都不可超過某一事先預(yù)定的距離dv，即：

(33)

注意到，由于訂單是大批量的，其含有的貨物量很大，同時Gg(t)無人車的數(shù)量Nv也較大。因此，設(shè)計函數(shù)fgv(t)較為困難；進(jìn)一步地，在有限的空間內(nèi)如何調(diào)度所有無人車盡量高速運(yùn)行而不碰撞也變得異常復(fù)雜。

分揀效率的定義訂單分揀系統(tǒng)的運(yùn)行效率可由在統(tǒng)計時域[t,t+Nt)內(nèi)處理訂單或貨物的多少來衡量，其中Nt為某正整數(shù)，其值的大小表示了統(tǒng)計時域的大小。注意到使用貨物或訂單的完成量描述分揀效率并不等價，后者更多地與分揀的整體性相關(guān)。因此，本文使用在該統(tǒng)計時域內(nèi)訂單分揀系統(tǒng)所完成的訂單分揀數(shù)量來衡量分揀效率JNt(t)，由式(20)的定義，有：

(34)

綜上所述，大批量訂單整體分揀問題定義如下。

問題1(大批量訂單整體分揀) 給定封閉倉庫區(qū)域H，式(1)中定義的擺放于Ns個貨架上的Ng種貨物，式(5)～(11)中定義的無人車集合V及其狀態(tài)和式(22)～(26)描述的無人車運(yùn)動方式，式(12)～(15)中描述的新訂單產(chǎn)生方式和式(16)～(21)中描述的訂單處理過程。在限制條件式(30)～(33)下，設(shè)計式(29)中定義的算法A(t)以優(yōu)化在式(34)中定義分揀效率JNt(t)。

2 大批量訂單的分布式并行分揀

面向第1節(jié)定義的大批量訂單整體分揀問題，本節(jié)提出一種基于智能貨架的分布式并行解決方法。首先描述該方法的基本思路和硬件要求，進(jìn)而給出其模型化描述，然后解決其中的關(guān)鍵技術(shù)問題，最后給出詳細(xì)的算法描述。

2.1 分布式并行整體分揀策略及硬件要求

注意到大多數(shù)現(xiàn)有整體分揀系統(tǒng)的效率瓶頸在于打包處的稀缺性，本文提出如圖1所示的一種新型大批量訂單的分布式并行整體分揀模型。該模型的核心要點(diǎn)是允許所有的貨架都作為潛在的訂單打包處，從而使得訂單的打包成為分布式并行的。

圖1 分布式并行分揀模型示意圖

在該模型中，將所有Ns個貨架首尾相連，其封閉的內(nèi)部區(qū)域作為無人車的運(yùn)行區(qū)域，即H。要求任意2個貨架在內(nèi)H直線可達(dá)，無人車在貨架內(nèi)側(cè)取貨，并沿直線運(yùn)送至目的貨架。

該模型對現(xiàn)有訂單分揀系統(tǒng)的硬件改造主要涉及貨架，即原有單純陳列貨物的貨架，現(xiàn)其內(nèi)側(cè)陳列貨物，并可將相應(yīng)貨物交付無人車(實現(xiàn)方式可為推取式或機(jī)械手[20，21]等)，外側(cè)則改造為訂單的打包處?？山邮辗峙涞挠唵?。利用無人車從其他涉及的貨架上分揀貨物，并在訂單的所有貨物到齊后打包送出。所使用的無人車可以是較為簡單的，只需要具有無線通信和運(yùn)輸能力，并能在貨架配合下取卸貨物即可。

采用該分布式并行分揀模型的分揀流程如下所述：新訂單到達(dá)后被分配至某一貨架打包處處理，利用無人車將訂單的所有貨物從相關(guān)貨架中取出并運(yùn)至該打包貨架，待所有貨物齊備后完成訂單打包任務(wù)交給外部物流系統(tǒng)。

2.2 分布式并行整體分揀的模型化描述

本節(jié)把在第1節(jié)中提出的通用模型針對所提出的分布式并行策略進(jìn)行具體化(圖2)。該策略對一般模型描述的訂單和無人車均有影響，詳述如下。

2.2.1 分布式并行整體分揀下的訂單及其預(yù)處理

首先，在分布式并行策略下，訂單的打包點(diǎn)是某一貨架，因此式(4)中對訂單的一般靜態(tài)定義轉(zhuǎn)化為

(35)

其次，在分布式并行整體分揀下，每一個貨架都可以獨(dú)立接受訂單的到來，這意味著式(12)～(15)中新訂單產(chǎn)生的描述應(yīng)理解為對每一個貨架適用。從而，式(12)中的新訂單產(chǎn)生過程變?yōu)?/p>

Pr{一個新訂單在[t,t+Δt)到達(dá)貨架Sk}=λk

(36)

式(14)可相應(yīng)定義。

最后，與式(13)中的一般性表述不同，新到來的訂單自動分配至某一貨架作為打包點(diǎn)，這就引發(fā)了一個自然的預(yù)處理過程，即所有已經(jīng)在該貨架上的貨物都應(yīng)該直接可以用來打包，無需再使用無人車運(yùn)送。也就是說，在分布式并行整體打包框架下，所有[t,t+1)新到來訂單都要進(jìn)行預(yù)處理以得到如下新的訂單形式。

(37)

2.2.2 分布式并行整體分揀下的無人車

首先，在分布式并行整體分揀框架下，運(yùn)行中的無人車在t時刻的位置與一般描述并無不同，但t時刻空閑的無人車Vi∈VI(t)的位置li(t)一定與某一貨架相同。在系統(tǒng)運(yùn)行之后，這一貨架即為該無人車上次執(zhí)行貨物運(yùn)送時所運(yùn)送貨物所屬訂單的打包點(diǎn)，即：

(38)

圖2 分布式并行分揀方法的模型化示意圖

(39)

So=[xo,yo],Sg=[xg,yg]

(40)

因為So和Sg為不同貨架，則xg-xo和yg-yo至少有一個不為0。若，記貨架So和Sg之間連線與x軸的夾角為θog，則

(41)

進(jìn)而，如果xg-xo=0且yg-yo≠0，則若yg-yo>0則θog=0，若yg-yo<0則θog=π。

由于vi(t)和ai(t)方向相同(或相反)，無人車在任一時刻從打包貨架So到目的貨架Sg(未到達(dá)目的地前)的行進(jìn)距離為

(42)

從而，在t時刻無人車Vi的坐標(biāo)為

(43)

(44)

若無人車是從Sg到So行進(jìn)，其運(yùn)行軌跡可類似得到，此時θog=π-θog。

2.3 分布式并行分揀的關(guān)鍵技術(shù)問題

2.3.1fgv的構(gòu)建：優(yōu)先級優(yōu)先分配算法

由式(28)定義，fgv將當(dāng)前待處理貨物集合Gg(t)映射到空閑無人車集合VI(t)。在分布式并行整體分揀框架下，fgv的構(gòu)建應(yīng)考慮2個重要因素： 待處理訂單的完成情況，越接近完成分揀(剩余分揀貨物較少)的訂單應(yīng)給予較高處理優(yōu)先級，這有利于優(yōu)化式(34)中定義的整體分揀的分揀效率；空閑無人車與打包點(diǎn)距離，貨物運(yùn)送應(yīng)安排給較近的無人車執(zhí)行以減小運(yùn)輸距離。

首先，從式(4)定義的待處理訂單集合Θ(t)中，計算每個待處理訂單Oo中尚需處理的貨物數(shù)量。

(45)

待處理訂單Oo的處理優(yōu)先級PRIo以如下方法確定。

(46)

原先的待處理貨物集合Gg(t)變?yōu)?/p>

Ig(t)=-1}

(47)

(48)

其中，asc(·)表示將向量按升序排列的函數(shù)。

主要從優(yōu)化訂單整體分揀的角度提出如算法1中描述的解決方案，其核心是以貨物的運(yùn)送優(yōu)先級為先。注意該方法有利于在短期內(nèi)完成更多的訂單，但這個過程可能會使用更多的遠(yuǎn)距離無人車，從而造成對長期目標(biāo)的優(yōu)化不利。如何做到全局優(yōu)化仍是一個待研究的復(fù)雜問題。

算法1 fgv的優(yōu)先級優(yōu)先分配算法 輸入:t時刻的待處理貨物集合GGg(t)和空閑無人車集合VVI(t)。 輸出:fgv函數(shù)。 (1)由式(45)～(47)計算帶有優(yōu)先級的待處理貨物集合GGPRIg(t);由式(48)計算每件待處理貨物與空閑無人車的距離向量Dsg; (2)將優(yōu)先級最高的待處理貨物分配給其與無人車的距離向量中的第一個無人車(距離最短); (3)更新空閑無人車信息,將剛分配任務(wù)的無人車從VVI(t)中刪除;更新所有待處理貨物與無人車的距離向量,將剛分配任務(wù)的無人車的距離從向量中刪除; (4)從剩余待處理貨物中選擇優(yōu)先級最高的,重復(fù)步驟(2)和(3),直至任一條件滿足:1)所有待處理貨物全部分配完畢;2)空閑無人車集合為空集。

在本文的分布式并行整體分揀框架下，無人車的所有運(yùn)動決策都由某中心控制器給出。這一決策的核心是給出[t,t+1)內(nèi)每輛運(yùn)行中無人車的加速度。

從單獨(dú)一輛無人車的角度看，為了使其運(yùn)行效率最高，應(yīng)該使其一直在最高速度運(yùn)行。但多輛無人車在限定區(qū)域H中交叉運(yùn)行，如果不進(jìn)行限制不可避免會遭遇碰撞。按式(33)中的要求，Vi、Vj發(fā)生碰撞即二者之間距離小于某預(yù)定dv。注意到為了整體的效率優(yōu)化，考慮在多步運(yùn)行后的無人車狀態(tài)：如果讓某無人車在[t,t+1)內(nèi)保持高速運(yùn)行會極大提高在此后與其他無人車碰撞的可能，限制其在[t,t+1)內(nèi)的運(yùn)行速度，而這是只考慮在[t,t+1)內(nèi)的運(yùn)動無法得到的。為了系統(tǒng)運(yùn)行的整體最優(yōu)，需要預(yù)測系統(tǒng)很多步后的可能運(yùn)動狀態(tài)，并從中選取合適的運(yùn)動序列，但這種對未來軌跡的預(yù)測對計算能力有很高的要求，這一原因促使本文中做了2個決定：一方面，系統(tǒng)架構(gòu)中采用中央控制器進(jìn)行每輛無人車的路徑規(guī)劃，不允許每輛無人車自主規(guī)劃；另一方面，在路徑規(guī)劃上，采用如下的模型預(yù)測控制策略，以有限步長的滾動優(yōu)化來決定無人車的運(yùn)動。

由式(7)可得：

由上式并注意到無人車不會倒向行駛且一直保持直線行駛，無人車Vi在[t,t+T)內(nèi)的運(yùn)動總長度Li[t,t+T)為

(49)

(50)

(51)

(52)

2.4 分布式并行整體分揀框架和算法

算法2 分布式并行整體分揀算法 輸入:t=0, Ns個貨架的位置,待處理訂單集合Θ(0)=?,無人車集合VV=VVI(0),VVo(0)=?,及其初始狀態(tài)Vi(0), Vi∈VV。 輸出:訂單的整體分揀運(yùn)行。 在t時刻, (1) 按式(12)～(15)和式(35)～(37)產(chǎn)生新訂單并更新待處理訂單集合,按式(2)更新待處理貨物集合; (2) 按式(45)～(48)和算法1確定fgv函數(shù),按(13)確定ati, Vi∈VVo(t); (3) 按式(22)～(26)更新無人車狀態(tài),按式(16)～(21)更新待處理訂單集合,按式(27)更新待處理貨物集合; (4) 令t=t+1。

3 仿真算例

考慮封閉倉庫區(qū)域H為長寬各為50 m和45 m的方形區(qū)域，將笛卡爾坐標(biāo)系的坐標(biāo)原點(diǎn)建于其中某頂點(diǎn)，x軸和y軸各沿方形的一邊，如圖3所示。

其中菱形表示某訂單的打包所在貨架，五角星表示某待

在仿真中,設(shè)貨架數(shù)Ns=88，無人車數(shù)量N=20，在仿真開始的初始位置是隨機(jī)確定的。式(36)中新訂單的到達(dá)強(qiáng)度λk=0.23，?k=1,…,Ns，式(14)中κ=0.1，ηj=1/88。無人車的速度和加速度約束為vmax=3 m/s，amax=2 m/s2，任意2輛無人車的距離都不可超過某一事先預(yù)定的距離dv=3.15 m。

其中菱形表示訂單的打包口，五角星表示某待取貨

考慮Nt=1時的分揀效率J1(t)，即在單位時間[t,t+1)內(nèi)所完成的訂單數(shù)。其演化規(guī)律在4種方法下的比較見圖5。從中可以看出，采用分布式整體分揀方式的分揀效率比常規(guī)分揀方法高出3倍。這一效率提升的原因可從分布式并行分揀允許多個訂單打包點(diǎn)的本質(zhì)特點(diǎn)解釋。

圖5 在統(tǒng)計時域[t, t+1)內(nèi)，4種分揀方法的分揀效率J1(t)隨時間的演化規(guī)律圖

這4種分揀方式在系統(tǒng)初裝和運(yùn)行成本上的差別主要在無人車方面。常規(guī)方法的無人車一般需要有相當(dāng)?shù)淖灾髂芰Γ绫苷系饶芰?，而本文所提出的分布式整體策略的無人車則可以簡化，只要可接受指令行進(jìn)即可。分布式整體方法需要對貨架進(jìn)行一定改造，但原先貨架若允許無人車分揀也應(yīng)已經(jīng)具有一定智能，添加打包點(diǎn)能力的改裝并不額外增加太多成本。因此總體上來說，分布式整體分揀方法的初裝和運(yùn)行成本也可以有一定降低。

4 結(jié) 論

大批量訂單的整體分揀是物流系統(tǒng)中的一個重要問題，其效率提升對整體物流效率的提升至關(guān)重要。本文提出的分布式并行模式的整體分揀策略和方法利用多打包點(diǎn)的想法，使用優(yōu)先級訂單分發(fā)和基于預(yù)測的無人車動態(tài)規(guī)劃等技術(shù)，提升了訂單分揀系統(tǒng)的整體分揀效率，具有較好的潛在應(yīng)用價值。本文研究較為初步，在后續(xù)研究中，還需要在貨架擺放、貨物擺放、高效算法即fgv和ai(t)的確定等方面做更為深入的研究。