遺傳算法下物流配送中心訂單揀選路徑優(yōu)化

■ 何 億（邵陽職業(yè)技術(shù)學(xué)院 湖南邵陽 422000）

遺傳算法下物流配送中心訂單揀選路徑優(yōu)化

■ 何 億（邵陽職業(yè)技術(shù)學(xué)院 湖南邵陽 422000）

訂單揀選路徑選擇是物流配送中心運(yùn)作效能的核心環(huán)節(jié)，運(yùn)用遺傳算法等先進(jìn)算法優(yōu)化訂單揀選路徑有助于提高配送中心運(yùn)作效率。本文闡述了物流配送中心訂單揀選路徑優(yōu)化研究的意義，從人工訂單揀選模式、揀選路徑選擇和內(nèi)設(shè)巷道型訂單揀選決策方面回顧相關(guān)研究，設(shè)計遺傳算法支持的配送中心訂單揀選路徑優(yōu)化方案規(guī)劃和具體實(shí)施步驟，提出構(gòu)建多訂單處理信息系統(tǒng)、強(qiáng)化訂單揀選作業(yè)與越庫配送系統(tǒng)對接能力建設(shè)等優(yōu)化配送中心訂單揀選的可行策略。

遺傳算法 物流配送中心 訂單揀選 路徑優(yōu)化

問題的提出

我國“一帶一路”戰(zhàn)略顯著擴(kuò)大了國民經(jīng)濟(jì)的活動空間和物流產(chǎn)業(yè)的生存和發(fā)展空間。為增強(qiáng)參與經(jīng)濟(jì)全球化的能力，第三方物流企業(yè)既需要強(qiáng)化物流基礎(chǔ)設(shè)施與設(shè)備的投資力度，又需要強(qiáng)化對包括運(yùn)用先進(jìn)算法支持的物流管理軟件領(lǐng)域的投資力度。以“第三方物流”為骨干的物流配送中心，在實(shí)際運(yùn)作過程中通常會暴露出配送路線不合理、車輛滿載率低和配送及時率較低等問題，由此產(chǎn)生的物流配送運(yùn)作流程中的阻力已然成為制約物流客戶企業(yè)健康發(fā)展的瓶頸。為此，物流配送中心有必要通過采購“第三方物流”企業(yè)服務(wù)的方式，提升其物流服務(wù)社會化和專業(yè)化水平，并以第三方物流企業(yè)的信息系統(tǒng)為平臺，重構(gòu)物流配送中心訂單揀選路徑，促進(jìn)物流企業(yè)合理優(yōu)化配送設(shè)備運(yùn)動路線，降低配送系統(tǒng)運(yùn)作成本。將遺傳算法運(yùn)用于物流配送中心訂單揀選路徑優(yōu)化中，有助于提高物流配送中心訂單揀選路徑的優(yōu)化速度，提高其訂單揀選效率，提升物流配送客戶企業(yè)的服務(wù)體驗(yàn)水平。

相關(guān)文獻(xiàn)回顧

在關(guān)于物流配送中心的人工訂單揀選模式分析方面，賈智、馮愛蘭（2014）通過分析配送中心人工訂單揀選路徑的既有問題，從中找尋出既有的人工訂單揀選模式的若干不足，然后在此基礎(chǔ)上根據(jù)訂單指向倉儲區(qū)的差異化分布特點(diǎn)，設(shè)計配送中心的訂單揀貨點(diǎn)，并對訂單揀選路徑做了進(jìn)一步優(yōu)化，以提高揀貨效率。朱杰、周麗等人（2012）研究了分類存儲人工揀選隨機(jī)服務(wù)系統(tǒng)效率問題，將服從泊松分布的訂單代入M/G/1隨機(jī)服務(wù)系統(tǒng)，以此研究隨機(jī)服務(wù)系統(tǒng)的效率優(yōu)化問題；研究比較五種貨品的訂單生成頻率和倉儲位置配置情形下的折返式和S型揀選方式的效率，仿真結(jié)果可為傳統(tǒng)四邊形物流配送中心的訂單揀選決策提供依據(jù)，有效優(yōu)化物流配送中心的訂單揀選時間、揀選路徑和揀選方式選擇方案。前述研究討論了諸如限定揀選場地形狀和揀選人數(shù)的有限情形下的揀選優(yōu)化方案，但對點(diǎn)到點(diǎn)式揀選配送問題缺乏深入探討。

在物流配送中心揀選路徑選擇研究方面，張峰、殷秀清（2015）在精益生產(chǎn)模式下從訂單緊急度探討供料路徑問題，運(yùn)用可拓評價法和改進(jìn)層次分析法找尋受供料路徑和訂單緊急度兩個因子作用下的供料路徑規(guī)劃方案；最后運(yùn)用基于混合粒子群算法的TSP搜索算法計算供料路徑，該方案有效增強(qiáng)精益生產(chǎn)系統(tǒng)的運(yùn)作效率。Hall（1993）在對跨越倉儲中心的訂單揀選策略、中點(diǎn)折返式訂單揀選策略和最大間距式訂單揀選策略做深入研究的基礎(chǔ)上，采取系統(tǒng)仿真算法求解三類策略下的配送中心訂單揀貨路徑的優(yōu)劣，其研究結(jié)果表明最大間距式訂單揀選策略效果更優(yōu)。前述研究深入討論了諸如折返式揀選路徑情形下的訂單揀選優(yōu)化策略，其成果在涉及多配送節(jié)點(diǎn)的訂單揀選問題處理上缺乏推廣價值。

在內(nèi)設(shè)巷道的物流配送中心訂單揀選問題研究方面，Vaughan和Petersen（1999）探討了存在倉庫內(nèi)部通道的訂單揀選最優(yōu)方案選擇問題，通過設(shè)計實(shí)驗(yàn)組和對照組的訂單揀貨路徑進(jìn)行比對計算，結(jié)果表明在倉庫內(nèi)部通道的長度增加值與內(nèi)部通道寬度存有關(guān)聯(lián)性關(guān)系時，可以計算出最優(yōu)內(nèi)部通道數(shù)量。Roodbergen和Koster（2001）給出了動態(tài)仿真技術(shù)條件下的倉庫規(guī)模、訂單規(guī)模與訂單揀選時間的最優(yōu)方案計算方法，其計算結(jié)果表明倉庫內(nèi)部通道數(shù)量與訂單揀選效率之間的關(guān)系。前述研究討論了物流配送中心內(nèi)部巷道數(shù)量與揀選訂單效率之間的關(guān)系，從優(yōu)化倉庫內(nèi)部結(jié)構(gòu)角度揭示了訂單揀選優(yōu)化的新思路。

配送中心訂單揀選路徑優(yōu)化算法設(shè)計

（一） 方案規(guī)劃

配送中心的訂單揀選路徑優(yōu)化算法需要分為兩段分別實(shí)現(xiàn)：一是初始路徑的構(gòu)造，即根據(jù)遺傳算法進(jìn)行全局尋優(yōu)，并通過改進(jìn)的啟發(fā)式算法隨機(jī)搜尋最鄰近的初始路徑中的較優(yōu)方案，通過多次迭代的方式找尋初始優(yōu)化結(jié)果；二是動態(tài)路徑最優(yōu)化方案的更迭，即通過對配送中心的訂單揀選人員或車輛進(jìn)行空間定位，在預(yù)設(shè)揀選人員或車輛空間位置的基礎(chǔ)上，給其下達(dá)訂單揀選任務(wù)并動態(tài)選擇最優(yōu)訂單揀選路徑，在完成訂單揀選任務(wù)后，循環(huán)到下一階段的訂單揀選任務(wù)下達(dá)、接受、尋址和最優(yōu)路徑規(guī)劃等任務(wù)，直至完成該工作時段上全部客戶訂單揀選需求。與傳統(tǒng)的物流配送中心訂單揀選路徑設(shè)計相比較，二階段的配送中心訂單揀選路徑最優(yōu)化算法設(shè)計更符合物流配送中心的現(xiàn)場操作特點(diǎn)，故具有更強(qiáng)的實(shí)踐意義。

訂單揀選初始路徑構(gòu)造應(yīng)從配送中心訂單揀選的遺傳算法全局優(yōu)化算法構(gòu)建啟動。既有的研究成果表明，運(yùn)用遺傳算法求解Dynamic Vehicle Routing Planning（DVRP）問題具有優(yōu)勢。本文擬采取遺傳算法解決多訂單、多揀選操作單元和多道路交通信息的訂單揀選問題，該問題的解決需要考慮對倉庫內(nèi)揀選路徑上關(guān)鍵路徑節(jié)點(diǎn)作出優(yōu)化順序安排。

（二） 實(shí)施步驟

配送中心訂單揀選路徑優(yōu)化算法的具體操作步驟如下：第一，對該問題涉及的備擇物流配送中心地址進(jìn)行染色體標(biāo)注，并運(yùn)用二進(jìn)制表示方式進(jìn)行編碼。其中，物流配送中心地址可以用染色體遺傳編碼的位數(shù)表達(dá)，而染色體遺傳編碼的數(shù)值表示配送任務(wù)選擇狀態(tài)。即不同位置的染色體編碼代表不同的物流配送中心地址，數(shù)值“0”表示該配送地址未被選中，數(shù)值“1”表示該配送地址被選中。

第二，選擇操作，即從可以被確定用于重組的個體或該個體染色體的子代中進(jìn)行選擇操作。就單個個體而言，其被執(zhí)行選擇操作的幾率相同；但從種群角度而言，其種群規(guī)模大小、種群適應(yīng)度和分布狀態(tài)決定其被選中的概率。

第三，初始種群生成。物流配送中心的數(shù)據(jù)初始化，該過程涉及物流配送中心選址操作的初始化和配送路徑的初始化數(shù)據(jù)兩部分。具體而言，在確保配送中心各配送地址間庫存數(shù)量調(diào)入和調(diào)出值一致的條件下，按照偽隨機(jī)數(shù)規(guī)則從第x項(xiàng)染色體中選擇若干配送地址，并依據(jù)臨近匹配原則對其進(jìn)行客戶分配。此時系統(tǒng)隨機(jī)生成若干初始數(shù)值，各初始數(shù)值構(gòu)成單個染色體，并以編碼形式進(jìn)入下一步計算中，若干單體染色體構(gòu)成初始化種群，其編碼值與算法后續(xù)進(jìn)程相關(guān)。

第四，染色體個體適應(yīng)度計量。系統(tǒng)通過適配值函數(shù)f（x）評估各染色體既有狀態(tài)下標(biāo)值的最優(yōu)性，以此決定染色體個體獲取交叉和變異幾率。其中，具有較低適配值函數(shù)值的染色體個體擁有更高的交叉變異機(jī)會。關(guān)于適配值函數(shù)值的選取問題，本文擬采用單位物流強(qiáng)度下的物流費(fèi)用表示，相關(guān)變量值主要來源于調(diào)研統(tǒng)計數(shù)據(jù)和財務(wù)成本核算結(jié)果。

第五，交叉與變異操作。交叉操作的關(guān)鍵在于選擇算子、交叉算子和變異算子的確定。其一，選擇算子的確定通常在染色體種群個體適應(yīng)度計量環(huán)節(jié)實(shí)現(xiàn)。由于適配值函數(shù)值表示該種群個體中遺傳到下一代種群中的幾率大小，其適配值函數(shù)值越小，其適應(yīng)度水平越高，則其具有遺傳能力的幾率就越大。本文擬采用“最優(yōu)值直接迭代”算法確定部分可遺傳的染色體算子，緊前一代中的適配值函數(shù)值最小者可以擁有優(yōu)先迭代權(quán)，即緊前一代中適應(yīng)度最高的染色體個體直接迭代到緊后一代中，以便加快整個遺傳算法的收斂速度，降低該算法的計量難度并提升其算法精度。另外，該遺傳算法從當(dāng)前的種群中按照適配值函數(shù)值由小到大進(jìn)行排序，并運(yùn)用選擇概率函數(shù)對其被選中概率進(jìn)行由大到小的賦值，最后采取“蒙特卡羅”算法從中選擇進(jìn)入交叉環(huán)節(jié)的染色體。其二，交叉算子的確定通常采取隨機(jī)方式并按照預(yù)設(shè)交叉率函數(shù)進(jìn)行交叉重組，由此產(chǎn)生的新染色體個體將與父代染色體進(jìn)行比對后，從中選擇高適應(yīng)度的染色體個體進(jìn)入下一步。其三，染色體變異操作有助于兼顧遺傳算法的局部搜索能力優(yōu)化目標(biāo)和保持遺傳算法種群個體多元化目標(biāo)，從而避免遺傳算法陷入局部最優(yōu)化算法中。

第六，循環(huán)迭代。在經(jīng)過交叉變異操作后，物流配送中心的訂單揀選路徑方案染色體種群發(fā)生變化，由此產(chǎn)生進(jìn)一步計算其個體適應(yīng)度的問題，故算法將從該步轉(zhuǎn)入第四步進(jìn)行迭代操作，直至觸及算法終止條件。算法終止條件可以分為兩類：一是適應(yīng)度評估值函數(shù)，即對適應(yīng)度評估值進(jìn)行客觀評估，當(dāng)種群中個體觸及最優(yōu)適應(yīng)度值時，算法即行終止；二是迭代次數(shù)限制方法，即對該遺傳算法迭代次數(shù)的最大值MAXGEN做限定，在達(dá)到迭代次數(shù)最大值時，算法迭代操作即行終止。

配送中心訂單揀選路徑優(yōu)化策略

（一）多訂單處理信息系統(tǒng)構(gòu)建

訂單處理過程被視為增強(qiáng)客戶企業(yè)市場競爭能力的關(guān)鍵業(yè)務(wù)過程。運(yùn)用遺傳算法有助于提升物流配送中心訂單揀選路徑優(yōu)化決策效率，增強(qiáng)物流配送中心訂單揀選路徑?jīng)Q策的科學(xué)性和客觀性。但物流配送中心訂單揀選操作效能的提升需要以強(qiáng)健的信息系統(tǒng)支撐力的同步完善為基礎(chǔ)。若缺乏良好的可同步處理多訂單的信息系統(tǒng)的有力支撐，將無謂的耗費(fèi)訂單揀選工作人員的工作積極性，進(jìn)而導(dǎo)致基于遺傳算法的物流配送中心訂單揀選路徑優(yōu)化方案缺乏必要的組織力和執(zhí)行力，難以轉(zhuǎn)化為現(xiàn)實(shí)生產(chǎn)力。故物流配送中心應(yīng)當(dāng)運(yùn)用系統(tǒng)動力學(xué)原理和建模方法，刻畫配送中心的訂單揀選與配送能力之間的量化關(guān)系，將訂單揀選與配送能力之間的匹配關(guān)系同步呈現(xiàn)給決策者和倉儲管理者，并據(jù)此調(diào)整配送方式、訂單響應(yīng)時間和目標(biāo)交貨延遲策略。同時，物流配送中心應(yīng)當(dāng)建立倉儲管理系統(tǒng)（WMS），在與進(jìn)銷存管理軟件融合式運(yùn)用的基礎(chǔ)上，有效規(guī)范倉庫中的訂單揀選作業(yè)過程，合理配置訂單處理優(yōu)先順序，提高訂單揀選作業(yè)效率，增強(qiáng)訂單快速響應(yīng)能力。WMS應(yīng)當(dāng)具有批量處理訂單和自動化合并訂單以滿足拼箱運(yùn)輸或合并運(yùn)輸需求的能力。通過批量化處理訂單和合并訂單操作，物流配送中心可以降低發(fā)車頻率并嚴(yán)控流通成本，但卻需要延長部分訂單的處理時間，增加客戶企業(yè)的等待成本，故物流配送中心應(yīng)當(dāng)基于WMS平臺加強(qiáng)訂單歸并處理流程的管控，有效平衡訂單處理時間和配送成本之間的關(guān)系，實(shí)現(xiàn)綜合效益最優(yōu)化目標(biāo)。

（二）強(qiáng)化訂單揀選作業(yè)與越庫配送系統(tǒng)對接能力

常規(guī)的物流配送中心運(yùn)作流程涉及貨物承接（Receiving）、分揀（Sorting）、倉儲（Storing）、訂單揀選（Retrieving）和裝貨作業(yè)（Shipping）五項(xiàng)職能。其中，訂單揀選作業(yè)的功能發(fā)揮并不具有獨(dú)立效果，而需要與其它各項(xiàng)職能有機(jī)配合，方可確保其功能實(shí)現(xiàn)最優(yōu)化目標(biāo)，故訂單揀選路徑的選擇應(yīng)當(dāng)與后續(xù)裝貨環(huán)節(jié)有機(jī)融合。而越庫作業(yè)是在物流配送中心各項(xiàng)職能有機(jī)配合下可實(shí)現(xiàn)較高配送效率的一種裝貨作業(yè)方法，其要求訂單揀選與裝貨作業(yè)環(huán)節(jié)之間無縫對接，以切實(shí)壓縮整個配送業(yè)務(wù)流程時間并有效控制配送成本。為增強(qiáng)訂單揀選與越庫配送系統(tǒng)對接能力，物流配送中心應(yīng)當(dāng)選擇合適的儲存單元（SKU，Storage Keep Unit）作為訂單揀選的基本單位。針對待配送貨物品項(xiàng)內(nèi)容繁多的問題，物流配送中心可采取ABC法或二八分類法分類處理待配貨物；針對慢流貨物，配送中心可以采用合并SKU處理方式，用延長訂單處理時間的代價換取降低單位SKU處理成本的利益。越庫配送需要供應(yīng)商增加供貨頻率，故配送中心需強(qiáng)化與供銷雙方之間的溝通交流，就訂單到達(dá)與完成時間和貨物數(shù)量、質(zhì)量和體積等關(guān)鍵指標(biāo)問題，設(shè)置專崗負(fù)責(zé)與供應(yīng)商事先商定；采購方應(yīng)當(dāng)建立供應(yīng)商淘汰機(jī)制，及時淘汰不能達(dá)到越庫作業(yè)要求的訂單處理能力的供應(yīng)商，以保障越庫型訂單處理流程暢通。

1.賈智，馮愛蘭.配送中心人工訂單揀選路徑優(yōu)化與決策研究綜述[J].物流技術(shù)與應(yīng)用，2014（10）

2.朱杰，周麗，郭鍵.分類存儲人工揀選隨機(jī)服務(wù)系統(tǒng)效率研究[J].管理科學(xué)學(xué)報，2012，15（2）

3.張峰，殷秀清.考慮訂單緊急度的供料路徑優(yōu)化[J].山東理工大學(xué)學(xué)報（自然科學(xué)版），2015，29（1）

4.于海璁，陸鋒.一種基于遺傳算法的多模式多標(biāo)準(zhǔn)路徑規(guī)劃方法[J].測繪學(xué)報，2014，43（1）

F252

A