[發(fā)明專利]一種物流配送中心作業(yè)任務(wù)處理與調(diào)度的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201510804089.1
• 申請(qǐng)日: 2015-11-20
• 公開(kāi)（公告）號(hào): CN105469201B
• 公開(kāi)（公告）日: 2021-12-14
• 發(fā)明（設(shè)計(jì)）人: 李英德;姚躍朋;何超群
• 申請(qǐng)（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號(hào): G06Q10/06
• 分類號(hào): G06Q10/06;G06Q50/28
• 代理公司: 杭州之江專利事務(wù)所(普通合伙) 33216
• 代理人: 林蜀

1.一種物流配送中心作業(yè)任務(wù)處理與調(diào)度的方法，對(duì)某一時(shí)段內(nèi)的訂單池內(nèi)的訂單進(jìn)行任務(wù)處理與調(diào)度，包括以下步驟：

步驟一，入庫(kù)時(shí)對(duì)品項(xiàng)進(jìn)行上架的貨位指派，貨位指派時(shí)根據(jù)歷史出庫(kù)訂單得出各品項(xiàng)間的相關(guān)性，根據(jù)相關(guān)性對(duì)品項(xiàng)進(jìn)行貨位變換，以使揀選歷史出庫(kù)訂單時(shí)長(zhǎng)最大的揀貨員的揀選時(shí)間最小化作為品項(xiàng)儲(chǔ)位；

步驟二，對(duì)訂單池內(nèi)的出庫(kù)訂單進(jìn)行分批；

步驟三，將分批的出庫(kù)訂單對(duì)揀貨員進(jìn)行指派；

步驟四，設(shè)計(jì)揀貨員最佳行走路徑；

揀貨時(shí)，同一個(gè)訂單的品項(xiàng)都裝到一輛揀選車的一個(gè)箱子中，訂單池中的品項(xiàng)裝到同一個(gè)箱子的次數(shù)越多，所謂的品項(xiàng)相關(guān)性就越強(qiáng)；并且設(shè)定每種品項(xiàng)只能被指派到一個(gè)貨位；

對(duì)于任意揀貨員m，在一個(gè)揀貨波次內(nèi)的總揀貨時(shí)間為：

當(dāng)H_j為偶數(shù)時(shí)：

當(dāng)H_j為奇數(shù)時(shí)：

目標(biāo)函數(shù)：Min Max(P_m)＝Min T

約束條件：

x_kzn,D_jm,G_jz∈{0,1}

p_t,U_j,v'≥0,C_jk為整數(shù)，H_j,z'j≥1

參數(shù)與變量說(shuō)明：

J為一批訂單需要的箱子數(shù)量，箱子編號(hào)為j；

Z為巷道總量，巷道編號(hào)為z；

N為每個(gè)巷道內(nèi)的貨位數(shù)，巷道的貨位編號(hào)為n；

K為一批訂單需要揀取的SKUs總量，SKUs編號(hào)為k；

M為一個(gè)班次的揀貨員人數(shù)，揀貨員編號(hào)為m；

R_c為貨架列數(shù)；

U_j為對(duì)箱子j進(jìn)行檢查、掃描、確認(rèn)初始化操作的時(shí)間；

p_t為揀取單件SKU的平均時(shí)間；

C_jk為放到第j個(gè)箱子里的SKU_k的件數(shù)；

G_jz，如果箱子j需要訪問(wèn)巷道z，其值為1，否則為0；

D_jm，如果將箱子j指派給第m個(gè)揀貨員，其值為1，否則為0；

H_j為箱子j需要訪問(wèn)的巷道總數(shù)，

z’j為箱子j需要揀取的最后一個(gè)SKU所在的巷道編號(hào)；

N_jRc為箱子j需要揀取的最后一個(gè)SKU所在的貨架列號(hào)；

P_m為第m個(gè)揀貨員的總揀貨時(shí)間；

T為耗時(shí)最長(zhǎng)的揀貨員的揀貨時(shí)間；

v'為揀貨員平均行走速度；

a為從一條巷道的出入口橫向走到相鄰巷道的出入口需要的時(shí)間；

x_kzn為決策變量，表示如果SKU_k被指派到第z巷道的第n個(gè)貨位，

其值為1，否則值為0；

對(duì)訂單池內(nèi)的品項(xiàng)采用如下方法進(jìn)行貨位的指派：

步驟1.1，根據(jù)歷史訂單信息，得出品項(xiàng)相關(guān)性列表，并設(shè)定初始參數(shù)：

參數(shù)ε：判斷系統(tǒng)是否達(dá)到平衡的閾值；

參數(shù)N_s：連續(xù)不再產(chǎn)生新解的步數(shù)；

參數(shù)α：退火速率；

參數(shù)Q：算法最大運(yùn)行時(shí)間；

步驟1.2，利用COI方法生成初始貨位向量S⁰，令當(dāng)前貨位向量S＝S⁰，計(jì)算初始貨位向量的目標(biāo)函數(shù)值T(S⁰)，令當(dāng)前最優(yōu)的貨位向量的目標(biāo)函數(shù)值T(S^*)＝T(S⁰)；初始化初始溫度y₀＝T(S⁰)/T_c，其中初溫控制參數(shù)T_c0，冷卻進(jìn)度表中其他溫度y₁＝y(tǒng)₀α，初始時(shí)冷卻進(jìn)度表中的溫度個(gè)數(shù)i'＝1，同時(shí)i'也是總迭代次數(shù)，每個(gè)溫度y_i’下的迭代次數(shù)e＝0；

步驟1.3，隨機(jī)生成[1,K_p]之間的整數(shù)w，利用位置變化策略對(duì)L(w)中的兩個(gè)SKUs進(jìn)行位置變換，其中位置變換策略為根據(jù)品項(xiàng)間的相關(guān)性，將相關(guān)性強(qiáng)的品項(xiàng)就近存儲(chǔ)，其具體步驟為當(dāng)品項(xiàng)b和品項(xiàng)j’的相關(guān)性大于品項(xiàng)b和品項(xiàng)y’的相關(guān)性時(shí)，品項(xiàng)j’與品項(xiàng)y’的位置互換，直至完成所有SKU對(duì)的位置交換為止；從而產(chǎn)生候選貨位向量S^c，計(jì)算候選貨位向量的目標(biāo)函數(shù)值T(S^c)，令e＝e+1；

步驟1.4，計(jì)算ΔT＝T(S)-T(S^c)；如果ΔT0，轉(zhuǎn)步驟1.6；如果ΔT＝0，轉(zhuǎn)步驟1.5；

步驟1.5，生成(0,1)之間的隨機(jī)數(shù)r，如果rexp(ΔT/y_i’)，轉(zhuǎn)步驟1.6；否則，轉(zhuǎn)步驟1.3；

步驟1.6，接受S^c為當(dāng)前解S，令S＝S^c,T(S)＝T(S^c)，如果T(S)T(S^*)，接受S為當(dāng)前最優(yōu)解S^*，令S＝S^*，T(S)＝T(S^*)，如果eE，轉(zhuǎn)步驟1.3，否則轉(zhuǎn)步驟1.7，其中內(nèi)循環(huán)參數(shù)E為每個(gè)溫度y_i’下的迭代總數(shù)，也就是溫度y_i’下候選解S^c的數(shù)目；

步驟1.7：如果系統(tǒng)在y_i’下未達(dá)到平衡，令e＝0，轉(zhuǎn)步驟1.3，其中為一個(gè)迭代周期內(nèi)目標(biāo)函數(shù)的均值，為前一次和當(dāng)前迭代周期內(nèi)目標(biāo)函數(shù)值的均值；否則，令e＝0，i'＝i'+1，y_i’＝y(tǒng)₀α^i’，如果i'N_s，轉(zhuǎn)步驟1.8；否則，算法結(jié)束，輸出各品項(xiàng)的存儲(chǔ)位置；

步驟1.8：如果運(yùn)行時(shí)間小于算法最大運(yùn)行時(shí)間Q，轉(zhuǎn)步驟1.3；如果運(yùn)行時(shí)間不小于Q，計(jì)算過(guò)程結(jié)束，得出各品項(xiàng)的存儲(chǔ)位置；對(duì)訂單池內(nèi)的訂單采用如下方法進(jìn)行分批：

步驟2.1：首先依據(jù)訂單中品項(xiàng)所在的巷道建立訂單包絡(luò)Q_k[N_min,N_max],[N_min,N_max]為品項(xiàng)存儲(chǔ)范圍的最小巷道和最大巷道；

步驟2.2：根據(jù)公式

當(dāng)最大通道號(hào)N_max為偶數(shù)時(shí)：

當(dāng)最大通道號(hào)N_min為奇數(shù)時(shí)：

計(jì)算出每個(gè)訂單包絡(luò)對(duì)應(yīng)的訂單包絡(luò)編號(hào)k，并且按從大到小的降序排列，相同編號(hào)的訂單按其品項(xiàng)數(shù)從大到小降序排列；

步驟2.3：將排序第一個(gè)的訂單作為第一批訂單，按編號(hào)順序?qū)⑾乱粋€(gè)訂單加入，直至滿足約束條件即不大于揀貨車的容量為止，

從而完成所有訂單的分批；

對(duì)分批的訂單進(jìn)行指派，并且將每個(gè)批次中的訂單指派給一個(gè)揀貨員，以揀貨完成時(shí)間最小為目標(biāo)，為各揀貨員指派揀選任務(wù)，優(yōu)化模型為：

目標(biāo)函數(shù)min(max O_i)

約束條件

a'_ik＝{0，1},g_ik＝{0，1},

o_i,S'_i,t'_ik,a'_ik,g_ik≥0

參數(shù)與變量說(shuō)明：

n’為揀選任務(wù)數(shù)量，任務(wù)的集合為B_i＝{B₁，B₂，B₃…B_n’}，任務(wù)序號(hào)i＝1，2....n’；

m’為揀選員人數(shù)，揀選人員的集合為E’＝{E’₁…，E’_k，…E’_m’}，揀選人員序號(hào)k＝1，2，…，m’；

O_i是任務(wù)B_i的完成時(shí)刻；

S’_i表示任務(wù)B_i的開(kāi)始執(zhí)行時(shí)刻；

p為分配給員工E’_K的任務(wù)數(shù)量；

t’_ik為揀選人員E’_k執(zhí)行任務(wù)B_i所用時(shí)間；

g_ik表示員工E’_k能否勝任任務(wù)B_i的狀態(tài)，如果能勝任則g_ik＝1，否則g_ik＝0；

a’_ik表示任務(wù)B_i是否被指派給員工E’_k的狀態(tài)，如果是則a’_ik＝1，否則a’_ik＝0；

指派步驟如下：

步驟3.1：根據(jù)當(dāng)前揀選人員任務(wù)指派及調(diào)度優(yōu)化問(wèn)題的規(guī)模，構(gòu)造解的構(gòu)析圖G＝(N'，A)，其中N'是節(jié)點(diǎn)集合，A是連接N'中節(jié)點(diǎn)的邊的集合；

步驟3.2：初始化參數(shù)，包括信息啟發(fā)式參數(shù)α'，期望啟發(fā)式參數(shù)β，信息素?fù)]發(fā)系數(shù)ρ，蟻群規(guī)模N_ant，最大迭代次數(shù)t_max，最優(yōu)解保持不變的連續(xù)迭代次數(shù)W_max，令迭代次數(shù)t＝0，算法迭代時(shí)，迭代次數(shù)t→t+1；令圖上每條邊(u，v)的初始化信息素其中C表示常數(shù)，且初始狀態(tài)時(shí)螞蟻r未在各邊釋放信息素，即Δτ^r(0)＝0；

步驟3.3：構(gòu)造可行解：螞蟻r，r＝1，2，…，N_ant，從源點(diǎn)出發(fā)，按公式3.1計(jì)算每一相鄰節(jié)點(diǎn)的能見(jiàn)因數(shù)，η_uv^r(t)是邊(u,v)長(zhǎng)度d_uv的倒數(shù)，代表了第t次迭代時(shí)螞蟻r在節(jié)點(diǎn)u選擇節(jié)點(diǎn)v的期望程度；并按公式3.2確定下一游歷節(jié)點(diǎn)N_uv，最終構(gòu)造出可行解；式中表示在第t次迭代時(shí)，處于節(jié)點(diǎn)u上的螞蟻r選擇節(jié)點(diǎn)v作為下一個(gè)點(diǎn)的概率，N_u^r是節(jié)點(diǎn)u上螞蟻r下一步允許選擇的節(jié)點(diǎn)的集合，各節(jié)點(diǎn)用l表示，其中任意一個(gè)節(jié)點(diǎn)v∈N_u^r，

步驟3.4：信息素更新，每次迭代結(jié)束，螞蟻r根據(jù)下式

進(jìn)行全局信息素更新，其中τ_uv(t)是第t次迭代時(shí)邊(u,v)上的信息素濃度,h是第t次迭代時(shí)走過(guò)邊(u,v)的螞蟻總數(shù)，ρ是信息素?fù)]發(fā)系數(shù)，ρ∈{0，1}；是第t次迭代時(shí)螞蟻r經(jīng)過(guò)邊(u,v)后釋放的信息素濃度，路徑越短螞蟻所釋放的信息素就越多,L^r(t)是螞蟻r在第t次迭代時(shí)所走過(guò)的總路徑長(zhǎng)度；

步驟3.5：精英解保留，每次迭代結(jié)束后，評(píng)價(jià)出精英解，將其保留；

步驟3.6：如果算法迭代達(dá)到穩(wěn)態(tài)，即螞蟻數(shù)量以線性規(guī)律減少，則轉(zhuǎn)到步驟3.7；如果沒(méi)有達(dá)到穩(wěn)態(tài)，則轉(zhuǎn)至步驟3.3；

步驟3.7：終止條件檢查，若tt_max或連續(xù)W_max代最優(yōu)解保持不變，則記錄當(dāng)前最優(yōu)解，否則轉(zhuǎn)至步驟3.3；

步驟3.8：輸出各揀貨員的揀選任務(wù)；

計(jì)算揀貨員最佳行走路徑，在揀選時(shí)間最小化的目標(biāo)下設(shè)計(jì)揀選人員的揀選路徑：

其中，x_i,x_j是揀選品的距離，v'是揀選車的速度

其中f為揀選時(shí)間；

F是貨位間運(yùn)行所需的時(shí)間矩陣；

X是所進(jìn)行揀選路徑形成的01矩陣，|X|≠0表示矩陣滿秩，即所有貨位都能夠被訪問(wèn)，0l矩陣中，1表示揀選路徑通過(guò)兩貨位點(diǎn)，0則表示未通過(guò)；

n'為待揀貨位總數(shù)；

按如下步驟確定作業(yè)人員的最優(yōu)揀貨路徑：

步驟4.1：對(duì)算法的相關(guān)參數(shù)進(jìn)行設(shè)定：人工魚(yú)的群體規(guī)模Fishnum，最大迭代次數(shù)Max-gen、擁擠度因子Delta、人工魚(yú)的感知距離Visual和覓食最多試探次數(shù)Trynum；

步驟4.2：生成初始魚(yú)群并計(jì)算其適應(yīng)值，在搜索區(qū)域即倉(cāng)庫(kù)的揀選區(qū)域內(nèi)找到每條人工魚(yú)的初始位置并計(jì)算其當(dāng)前位置和當(dāng)前狀態(tài)的食物濃度并帶入目標(biāo)函數(shù)得到人工魚(yú)的初始位置的狀態(tài)；

步驟4.3：公告板賦初值，將隨機(jī)設(shè)置的一條魚(yú)群狀態(tài)值放到公告板上作為初始值，然后將濃度值作為評(píng)價(jià)指標(biāo)，經(jīng)過(guò)數(shù)值比較后將較優(yōu)狀態(tài)記錄并保留；

步驟4.4：移動(dòng)策略，通過(guò)自身信息與環(huán)境信息的交互作為行為選擇的依據(jù)來(lái)進(jìn)行魚(yú)群算法基本操作并計(jì)算新?tīng)顟B(tài)下的食物濃度，通過(guò)不斷更新魚(yú)群自身位置狀態(tài)，始終向著較優(yōu)方向前進(jìn)，直到找到全局最優(yōu)解；

步驟4.5：公告板更新，比較人工魚(yú)每次移動(dòng)后的狀態(tài)和公告板狀態(tài)，若人工魚(yú)狀態(tài)優(yōu)于公告板，則更新公告板，否則保持公告板狀態(tài)不變；

步驟4.6：終止條件判斷，通過(guò)判斷是否達(dá)到最大迭代次數(shù)來(lái)決定循環(huán)是否終止，若循環(huán)終止則按公告板狀態(tài)輸出最優(yōu)計(jì)算結(jié)果，否則繼續(xù)步驟4.4；

步驟4.7：結(jié)束，當(dāng)滿足終止條件時(shí)會(huì)將最優(yōu)揀選路徑輸出，此時(shí)公告板中所記載的數(shù)據(jù)就是這次優(yōu)化的最終結(jié)果，輸出公告板記錄作為最優(yōu)解。