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

何億

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

關(guān)鍵詞：遺傳算法 ? 物流配送中心 ? 訂單揀選 ? 路徑優(yōu)化

問題的提出

我國“一帶一路”戰(zhàn)略顯著擴(kuò)大了國民經(jīng)濟(jì)的活動(dòng)空間和物流產(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)作過程中通常會(huì)暴露出配送路線不合理、車輛滿載率低和配送及時(shí)率較低等問題，由此產(chǎn)生的物流配送運(yùn)作流程中的阻力已然成為制約物流客戶企業(yè)健康發(fā)展的瓶頸。為此，物流配送中心有必要通過采購“第三方物流”企業(yè)服務(wù)的方式，提升其物流服務(wù)社會(huì)化和專業(yè)化水平，并以第三方物流企業(yè)的信息系統(tǒng)為平臺(tái)，重構(gòu)物流配送中心訂單揀選路徑，促進(jìn)物流企業(yè)合理優(yōu)化配送設(shè)備運(yùn)動(dòng)路線，降低配送系統(tǒng)運(yùn)作成本。將遺傳算法運(yùn)用于物流配送中心訂單揀選路徑優(yōu)化中，有助于提高物流配送中心訂單揀選路徑的優(yōu)化速度，提高其訂單揀選效率，提升物流配送客戶企業(yè)的服務(wù)體驗(yàn)水平。

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

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

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

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

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

（一） 方案規(guī)劃

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

訂單揀選初始路徑構(gòu)造應(yīng)從配送中心訂單揀選的遺傳算法全局優(yōu)化算法構(gòu)建啟動(dòng)。既有的研究成果表明，運(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”表示該配送地址被選中。

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

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

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

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

第六，循環(huán)迭代。在經(jīng)過交叉變異操作后，物流配送中心的訂單揀選路徑方案染色體種群發(fā)生變化，由此產(chǎn)生進(jìn)一步計(jì)算其個(gè)體適應(yīng)度的問題，故算法將從該步轉(zhuǎn)入第四步進(jìn)行迭代操作，直至觸及算法終止條件。算法終止條件可以分為兩類：一是適應(yīng)度評估值函數(shù)，即對適應(yīng)度評估值進(jìn)行客觀評估，當(dāng)種群中個(gè)體觸及最優(yōu)適應(yīng)度值時(shí)，算法即行終止;二是迭代次數(shù)限制方法，即對該遺傳算法迭代次數(shù)的最大值MAXGEN做限定，在達(dá)到迭代次數(shù)最大值時(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)動(dòng)力學(xué)原理和建模方法，刻畫配送中心的訂單揀選與配送能力之間的量化關(guān)系，將訂單揀選與配送能力之間的匹配關(guān)系同步呈現(xiàn)給決策者和倉儲(chǔ)管理者，并據(jù)此調(diào)整配送方式、訂單響應(yīng)時(shí)間和目標(biāo)交貨延遲策略。同時(shí)，物流配送中心應(yīng)當(dāng)建立倉儲(chǔ)管理系統(tǒng)（WMS），在與進(jìn)銷存管理軟件融合式運(yùn)用的基礎(chǔ)上，有效規(guī)范倉庫中的訂單揀選作業(yè)過程，合理配置訂單處理優(yōu)先順序，提高訂單揀選作業(yè)效率，增強(qiáng)訂單快速響應(yīng)能力。WMS應(yīng)當(dāng)具有批量處理訂單和自動(dòng)化合并訂單以滿足拼箱運(yùn)輸或合并運(yùn)輸需求的能力。通過批量化處理訂單和合并訂單操作，物流配送中心可以降低發(fā)車頻率并嚴(yán)控流通成本，但卻需要延長部分訂單的處理時(shí)間，增加客戶企業(yè)的等待成本，故物流配送中心應(yīng)當(dāng)基于WMS平臺(tái)加強(qiáng)訂單歸并處理流程的管控，有效平衡訂單處理時(shí)間和配送成本之間的關(guān)系，實(shí)現(xiàn)綜合效益最優(yōu)化目標(biāo)。

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

常規(guī)的物流配送中心運(yùn)作流程涉及貨物承接（Receiving）、分揀（Sorting）、倉儲(chǔ)（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í)壓縮整個(gè)配送業(yè)務(wù)流程時(shí)間并有效控制配送成本。為增強(qiáng)訂單揀選與越庫配送系統(tǒng)對接能力，物流配送中心應(yīng)當(dāng)選擇合適的儲(chǔ)存單元（SKU，Storage Keep Unit）作為訂單揀選的基本單位。針對待配送貨物品項(xiàng)內(nèi)容繁多的問題，物流配送中心可采取ABC法或二八分類法分類處理待配貨物;針對慢流貨物，配送中心可以采用合并SKU處理方式，用延長訂單處理時(shí)間的代價(jià)換取降低單位SKU處理成本的利益。越庫配送需要供應(yīng)商增加供貨頻率，故配送中心需強(qiáng)化與供銷雙方之間的溝通交流，就訂單到達(dá)與完成時(shí)間和貨物數(shù)量、質(zhì)量和體積等關(guān)鍵指標(biāo)問題，設(shè)置專崗負(fù)責(zé)與供應(yīng)商事先商定;采購方應(yīng)當(dāng)建立供應(yīng)商淘汰機(jī)制，及時(shí)淘汰不能達(dá)到越庫作業(yè)要求的訂單處理能力的供應(yīng)商，以保障越庫型訂單處理流程暢通。