基于0-1分塊矩陣求解的B2C配送中心訂單分批優(yōu)化模型構(gòu)建

于嵐　高貴晨　孫術(shù)發(fā)　武晉峰　熊武興

摘要：在同一時(shí)間窗下研究多品種、多批次、少批量的訂單分批處理具有較高的理論和實(shí)際意義。本文在考慮按單揀貨和并單揀貨的最優(yōu)揀貨策略的基礎(chǔ)上，構(gòu)建針對(duì)B2C配送中心揀貨時(shí)間數(shù)學(xué)模型，運(yùn)用分塊矩陣以及MATLAB對(duì)模型進(jìn)行求解。將模型應(yīng)用到配送中心實(shí)際訂單揀選中，得到最優(yōu)訂單分批處理方案，證明該模型具有可行性和實(shí)際應(yīng)用價(jià)值，可為B2C配送中心訂單分批處理問(wèn)題提供定量決策方法。

關(guān)鍵詞：B2C;揀貨策略;訂單分批;數(shù)學(xué)模型;分塊矩陣

中圖分類(lèi)號(hào)：F724;F253文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1006-8023（2019）02-0112-07

Construction of B2C Distribution Center Order Batch?Model Based on 0-1 Block Matrix

YU Lan?1， GAO Guichen?2， SUN Shufa?3*， WU Jinfeng?3， XIONG Wuxing?4

（1. Harbin Jiao Yan Transportation Engineering Co.， Ltd， Harbin 150080;?2. Shenzhen Institute of Advanced Technology， Chinese Academy of Sciences， Shenzhen 518055;?3. College of Engineering and Technology， Northeast Forestry University， Harbin 150040;?4. Ministry of Management and Economics， Dalian University of Technology， Dalian 116033）

Abstract：The research under the same time window of multi species， multi batch， small batch order batch has a high theoretical and practical significance. Based on the consideration of the optimal strategy of picking by order and merging by order， this paper constructs of a mathematical model of picking time for B2C distribution center， and solves the model by using block matrix and MATLAB. The model is applied to the actual picking of distribution center， the optimal order batch processing scheme is obtained. It is proved that this model is feasible and practical， and can provide quantitative decision method for B2C distribution center batch order.

Keywords：B2C; picking strategy; order batch; mathematical model; block matrix

0引言

B2C是一種通過(guò)網(wǎng)上商店節(jié)省企業(yè)和客戶(hù)時(shí)間與空間的電子商務(wù)模式。但電子商務(wù)是網(wǎng)絡(luò)虛擬交易平臺(tái)，貨物的送達(dá)需要依靠物流配送環(huán)節(jié)。配送中心作為物流體系的重要組成，其運(yùn)作活動(dòng)決定了整個(gè)物流環(huán)節(jié)的優(yōu)劣?[1-3]。配送中心揀貨決策對(duì)配送效率的影響很大?[4-5]。目前，關(guān)于揀貨決策的研究多集中在訂單分批?[6-9]處理問(wèn)題上。Ackerman在文獻(xiàn)[10]中首次提出訂單分批分揀的概念，Gibson和Sharp?[11]運(yùn)用計(jì)算機(jī)仿真的方法直觀(guān)的證明了訂單分批分揀方式比普通的揀貨方式更優(yōu)，之后，國(guó)外的研究從啟發(fā)式算法?[12]到現(xiàn)在的智能優(yōu)化算法?[13]層層遞進(jìn);而國(guó)內(nèi)物流行業(yè)起步較晚，對(duì)訂單分批?[14-16]的研究相對(duì)滯后，主要運(yùn)用聚類(lèi)分析?[17-19]、啟發(fā)式算法?[20]等進(jìn)行研究。但相似系數(shù)反映的是內(nèi)在聯(lián)系的指標(biāo)，當(dāng)數(shù)據(jù)量較大時(shí)，不容易獲得聚類(lèi)結(jié)論?[21]。啟發(fā)式算法不一定能保證解的可行性與最優(yōu)性，多數(shù)情況下無(wú)法描述該解與最優(yōu)解的近似程度?[22]。結(jié)合上述問(wèn)題以及配送中心多品種、多批次、小批量的特點(diǎn)，借鑒多學(xué)科的觀(guān)點(diǎn)和方法，本文提出建立同一時(shí)間窗下的數(shù)學(xué)模型，并采用針對(duì)非線(xiàn)性有限問(wèn)題的0-1分塊矩陣法得出最優(yōu)揀貨決策，得到耗時(shí)最少的訂單分批揀貨策略。

1問(wèn)題描述

B2C配送中心的特點(diǎn)為多品種、多批次、少批量。每天都需要對(duì)不同門(mén)店進(jìn)行商品的配送。訂單到達(dá)時(shí)，配送中心揀貨人員根據(jù)訂單分配情況進(jìn)行揀貨作業(yè)。揀貨員使用揀貨車(chē)揀選貨物時(shí)，可同時(shí)揀選多個(gè)訂單，將同種商品放置在同一周轉(zhuǎn)箱中。揀選完成后，按單揀貨的貨物直接送至分揀復(fù)核區(qū);并單揀貨的貨物送至二次分揀作業(yè)區(qū)，完成貨物的分揀。

在揀貨作業(yè)過(guò)程中，影響揀貨效率的因素包括揀貨員行走路徑、揀貨時(shí)間以及二次分揀作業(yè)時(shí)間。揀貨作業(yè)效率對(duì)配送中心的成本影響巨大。

2模型建立

2.1模型假設(shè)

（1）按照時(shí)間窗固定分批。

（2）一個(gè)訂單中至少包括一個(gè)品項(xiàng)。

（3）訂單的完成要完整。

（4）形成批次的訂單中揀選同種貨物的總量不超出揀貨車(chē)的容量。

（5）將訂單信息錄入后，WMS可根據(jù)模型給出訂單分類(lèi)結(jié)果。

（6）同一時(shí)間窗下，訂單為多品種、多批次、少批量。

（7）揀選不同品項(xiàng)耗時(shí)以及二次分揀耗時(shí)可求。

（8）立體存儲(chǔ)區(qū)貨物數(shù)量不受揀貨車(chē)容量限制。

2.2模型建立

（1）目標(biāo)函數(shù)：

minZ=∑li=1∑mij=1tij+dij+∑nk=1∑mkj=11-Cktjk

（1）

約束條件：

xij≤Qi=1，2，…，l;j=1，2，…，mi（2）

按單揀貨訂單的確定應(yīng)滿(mǎn)足下列約束條件：

Sj=1?aj∩aj?'=Φ，aj?j=1，2，…，mn（3）

當(dāng)按單揀貨時(shí)，不考慮揀貨車(chē)容量問(wèn)題。

變量解釋如下：

（2）波次單總數(shù)?l?的確定：

當(dāng)Sj>1時(shí)，將j從1到mn的aj逐次比較，將包含相同k的aj合并。若aj不能合并，看其是否滿(mǎn)足約束條件xij≤Q，若可以，則為一個(gè)波次單。若不可以，在約束條件以及目標(biāo)函數(shù)下再次分單;若aj可以合并，在約束條件xij≤Q下，運(yùn)用分塊矩陣求解∑li=1∑mij=1tij+dij最小的訂單分批。

3案例分析

某配送中心為B2C模式，中心總體布局包含倉(cāng)儲(chǔ)功能作業(yè)區(qū)和辦公區(qū)域。其中，倉(cāng)儲(chǔ)功能作業(yè)區(qū)包含立體存儲(chǔ)區(qū)、托盤(pán)存儲(chǔ)區(qū)、閣樓式貨架揀貨區(qū)、電子標(biāo)簽揀貨區(qū)、揀貨復(fù)核區(qū)、二次分揀作業(yè)區(qū)以及出入庫(kù)平臺(tái)。

為提高該配送中心的揀貨作業(yè)效率，本文依據(jù)銷(xiāo)售額和銷(xiāo)售量對(duì)該配送中心貨物進(jìn)行ABC分類(lèi)，按照分類(lèi)結(jié)果以及貨物周轉(zhuǎn)率對(duì)配送中心貨物儲(chǔ)位進(jìn)行合理安排，該配送中心配有WMS系統(tǒng)，訂單接收后能得知各品項(xiàng)所在具體位置，使模型可快速求解得到該B2C配送中心的最優(yōu)訂單分批。案例分析之前，給出算法分析流程圖如圖1所示。

3.1訂單信息整合

現(xiàn)有10張訂單，根據(jù)銷(xiāo)售量和銷(xiāo)售額依據(jù)ABC分類(lèi)法以及儲(chǔ)位安排原則?[22-24]，將訂單原有信息加以分類(lèi)和存儲(chǔ)，得到訂單信息見(jiàn)表2。根據(jù)配送中心實(shí)際數(shù)據(jù)，需揀選的A類(lèi)貨物存儲(chǔ)在立體存儲(chǔ)區(qū)，由巷道式堆垛機(jī)直接揀貨出庫(kù)，為簡(jiǎn)化算例，求解目標(biāo)函數(shù)時(shí)不考慮A類(lèi)貨物揀貨時(shí)間;需揀選的B、C類(lèi)貨物所在儲(chǔ)位以及揀貨員位置坐標(biāo)如圖2所示。

圖2為該配送中心需揀選訂單貨物的部分儲(chǔ)位分布圖，電蒸鍋與小砍骨刀為B類(lèi)貨物，周轉(zhuǎn)率相對(duì)C類(lèi)貨物高，存儲(chǔ)在距離輸送線(xiàn)較近的位置。結(jié)合配送中心實(shí)際距離，以左下角揀貨員所在位置為原點(diǎn)，構(gòu)成平面直角坐標(biāo)系。其中，貨架寬0.6 m，長(zhǎng)4 m，貨架橫向間隔1.2 m，縱向間隔1.5 m，輸送線(xiàn)與貨架最近距離為1 m。貨物位置的給定采用橫坐標(biāo)為揀貨一側(cè)坐標(biāo)，縱坐標(biāo)為貨格中點(diǎn)坐標(biāo)。

3.2十張訂單最優(yōu)揀貨策略求解

針對(duì)同一時(shí)間窗下所有品項(xiàng)的歸屬訂單來(lái)構(gòu)造分塊矩陣，在滿(mǎn)足約束條件前提下，將不同訂單排列組合，逐個(gè)求解不同訂單分批揀貨作業(yè)耗時(shí)，將耗時(shí)最少的訂單分批作為最優(yōu)解。對(duì)各品項(xiàng)所在訂單進(jìn)行匯總見(jiàn)表3。

算例求解：

（1）該配送中心揀貨員行走速度平均為1.6 m/s，從貨架取一箱貨物平均耗時(shí)1.5 min。揀選的面條機(jī)和電蒸鍋的包裝箱尺寸為440 mm×320 mm×300 mm，小砍骨刀和廚房多用剪刀的包裝箱尺寸為300 mm×230 mm×240 mm，該配送中心對(duì)這兩種類(lèi)型貨物的揀貨車(chē)容量?Q?=4箱。

對(duì)各品項(xiàng)進(jìn)行數(shù)量匯總得到表3。其中，小砍骨刀與廚房多用剪刀為20件一箱，在進(jìn)行數(shù)據(jù)整理時(shí)，采用“進(jìn)一”原則，將十張訂單中小砍骨刀和廚房多用剪刀的需求量分別換算為4箱和2箱。根據(jù)前文所述，A類(lèi)品項(xiàng)由立體存儲(chǔ)區(qū)直接揀貨出庫(kù)，不用揀貨車(chē)進(jìn)行人工揀選，因此，對(duì)其數(shù)量不予考慮。結(jié)合揀貨車(chē)容量為4，由表3可得：含有品項(xiàng)2的訂單1，4，8，9或含有品項(xiàng)4的訂單2，6，10不能合成一張波次單。

（2）根據(jù)模型構(gòu)建，Sj>1不存在按單揀貨。

（3）分塊矩陣的定義及求解思想如下。

設(shè)A是一個(gè)m×n的矩陣，如用若干橫線(xiàn)條將它分成r塊，再用若干縱線(xiàn)條將它分成s塊，于是有rs塊的分塊矩陣，A=A11…A1s?………?Ar1…Ars，其中Aij表示的是一個(gè)矩陣。

同一時(shí)間窗下的訂單分批問(wèn)題屬于有限問(wèn)題，引入訂單分批矩陣A=ajkmn×n，行方向?yàn)槠讽?xiàng)，列方向?yàn)橛唵?[25-26]。若訂單包含品項(xiàng)，在矩陣對(duì)應(yīng)位置寫(xiě)入1，否則寫(xiě)入0，在列方向?qū)⒂唵畏殖蒼塊，構(gòu)成0-1分塊矩陣。對(duì)訂單分批矩陣依據(jù)含有相同品項(xiàng)的訂單可生成波次單，且同一張訂單只能存在于一張波次單中進(jìn)行滿(mǎn)足條件的矩陣分塊，對(duì)應(yīng)不同的矩陣構(gòu)造時(shí)間矩陣T，求解滿(mǎn)足條件的所有目標(biāo)函數(shù)值，最小的目標(biāo)值就是最優(yōu)解。同時(shí)可得到訂單分批結(jié)果。

十張訂單彼此之間都含有相同品項(xiàng)，構(gòu)造訂單分批矩陣A=ajkmn×n

A=1?1?1?0?01?0?0?1?11?0?1?0?11?1?1?0?00?0?1?0?11?0?1?1?01?0?1?0?11?1?1?0?01?1?1?0?01?0?0?1?1

（4）案例分析中，揀貨耗時(shí)為揀貨員到達(dá)揀選位置并取貨以及將貨物送至輸送帶的時(shí)間。由于揀貨員二次分揀作業(yè)耗時(shí)相比揀貨時(shí)間要小的多，求解時(shí)二次分揀時(shí)間在這里不作考慮。在滿(mǎn)足約束條件下，根據(jù)圖2貨物儲(chǔ)位布局、揀貨員平均行走速度1.6 m/s以及從貨架取一箱貨物平均耗時(shí)1.5 min，運(yùn)用MATLAB進(jìn)行求解最優(yōu)目標(biāo)函數(shù)值min?Z=∑li=1∑mij=1tij?，得到訂單分批情況表見(jiàn)表5。求解出最優(yōu)目標(biāo)函數(shù)值為?Z?=24.54 min，根據(jù)最優(yōu)訂單分批結(jié)果：b1=1，4，6，8?b2=2，3，5，7，9，10，揀貨員從貨物儲(chǔ)位布局圖的原點(diǎn)出發(fā)，按照b1、b2下的揀貨耗時(shí)最短繪制揀貨員揀選路徑如圖3所示。

該算例求解的揀貨耗時(shí)為揀貨員到達(dá)揀選位置取貨然后將貨物送至輸送帶的時(shí)間。從表5可以得出以下兩點(diǎn)推論，為下一步深入研究提供思考方向：

（1）當(dāng)波次單的數(shù)量相同時(shí)，揀貨耗時(shí)相差不大。這是因?yàn)楫?dāng)波次單的數(shù)量相同時(shí)，揀貨員的取貨時(shí)間相差不大，揀貨耗時(shí)的不同主要體現(xiàn)在揀貨員的揀選路徑上。該算例的求解中，品項(xiàng)所在位置相距較近，揀貨員行走路徑的不同對(duì)求解結(jié)果影響較小。當(dāng)品項(xiàng)相距較遠(yuǎn)時(shí)，會(huì)更好的反映出因訂單分批情況的不同，揀貨耗時(shí)的差異性。

（2）在約束條件下，繪制不同波次單數(shù)量下的平均揀貨耗時(shí)折線(xiàn)圖如圖4所示。圖4中顯示平均揀貨耗時(shí)隨波次單的增加呈上升趨勢(shì)。在同一時(shí)間窗下，訂單批次增加會(huì)使需要拆箱揀選品項(xiàng)的揀貨時(shí)間增加，因此，在滿(mǎn)足約束條件的情況下，應(yīng)盡可能的減少波次單的數(shù)量。

4結(jié)束語(yǔ)

合理的流程分析以及有效的揀貨作業(yè)策略可以提高配送中心的揀貨作業(yè)效率。本文通過(guò)對(duì)貨物進(jìn)行ABC分類(lèi)、儲(chǔ)位安排以及構(gòu)建綜合揀貨決策模型，運(yùn)用定量的方法給出了B2C模式下配送中心最優(yōu)訂單分批的作業(yè)方法。通過(guò)案例分析，利用MATLAB求解訂單分批矩陣的最優(yōu)組合，表明了方法的可行性。

本文僅在考慮按單揀貨和并單揀貨的最優(yōu)揀貨策略的基礎(chǔ)上，構(gòu)建了針對(duì)B2C配送中心揀貨時(shí)間的數(shù)學(xué)模型，在模型時(shí)間復(fù)雜度與空間復(fù)雜度上未給出具體證明。但本文以求解方式更為簡(jiǎn)單的分塊矩陣對(duì)具體實(shí)例進(jìn)行分析，在訂單數(shù)量較少的情況下可取得較好的實(shí)驗(yàn)結(jié)果。為后續(xù)進(jìn)一步深入研究提供了思考方向。

【參考文獻(xiàn)】

[1]朱國(guó)俊.試論摘取式與播種式揀貨的異同[J].科技信息，2013，446（18）：15.

ZHU G G. On the similarities and differences between picking and sowing picking[J]. Scientific & Technological Information， 2013， 446（18）：15.

[2]黃河，楊以雄.服裝物流配送中心信息自動(dòng)化升級(jí)決策及案例研究[J].東華大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，42（2）：287-293.

HHUANG H， YANG Y X. Decision-making and case study on information automation upgrading of garment logistics distribution center[J]. Journal of Donghua University （Natural Science）， 2016， 42（2）：287-293.

[3]張文會(huì)，馬俊.基于AHP和GCA的第三方醫(yī)藥物流中心選址研究[J].森林工程，2016，32（3）：81-84.

ZHANG H W， MA J. Research on the location of third party medical logistics center based on AHP and GCA[J]. Forest Engineering， 2016， 32（3）：81-84.

[4]KOSTER R D， LEDUC T， ROODBERGEN K J. Design and control of warehouse order picking a literature review[J]. European Journal of Operational Research， 2007， 18（2）：481-501.

[5]安立華，趙秋雅，郭清偉，等.配送中心選址問(wèn)題研究[J].森林工程，2015，31（4）：161-164.

AN L H， ZHAO Q Y， GUO Q W， et al. Research on location of distribution center[J]. Forest Engineering， 2015， 31（4）：161-164.

[6]VANDENBERG J P. A literature survey on planning and control of warehousing systems[J]. LIE Transactions， 1997， 31（8）：751-760.

[7]WU Y H， ZHANG Y G， WU Y Y. Compressible virtual window algorithm in picking process control of automated sorting system[J]. Chinese Journal of Mechanical Engineering： English Edition， 2008， 21（3）：41-45.

[8]王旭坪，張珺，易彩玉.B2C電子商務(wù)環(huán)境下訂單揀選與配送聯(lián)合調(diào)度優(yōu)化[J].中國(guó)管理科學(xué)，2016， 24（7）：101-109.

WANG X P， ZHANG J， YI C Y. Joint scheduling optimization of order picking and distribution under B2C e-commerce environment[J]. Chinese Management Science， 2016， 24（7）：101-109.

[9]林雙嬌，何娜.價(jià)值鏈視角下的貨運(yùn)代理行業(yè)轉(zhuǎn)型升級(jí)路徑研究——以廈門(mén)為例[J].森林工程，2015，31（3）：155-158.

LIN S J， HE N. A study on the transition and upgrading path of freight forwarder industry from the perspective of value chain - a case study of Xiamen[J]. Forest Engineering， 2015， 31（3）：155-158.

[10]AEKERMAN K B. Practical handbook of warehousing[M]. Boston： Materials Management， 1990.

[11]GIBSON D R， SHARP G. P. Order batching procedures[J]. European Journal of Operational Research， 2012， 58（1）：57-67.

[12]ROSENWEIN M B. A comparison of heuristics for the problem of batching orders for warehouse selection[J]. International Journal of Production Research， 2005， 34（6）：657-664.

[13]HSU C M， CHEN K Y， CHEN M C. Batching orders in warehouses by minimizing travel distance with genetic algorithms[J]. Computers in Industry， 2005， 56（2）：169-178.

[14]夏揚(yáng)坤，符卓，謝九勇.依訂單拆分的多自動(dòng)導(dǎo)引車(chē)物料配送路徑規(guī)劃[J].計(jì)算機(jī)集成制造系統(tǒng)，2017， 23（7）： 1520-1528.

XIA Y K， FU Z， XIE J Y. Material distribution route planning for multiple automated guided vehicles with split deliveries by order[J]. Computer Integrated Manufacturing Systems， 2017， 23（7）：1520-1528.

[15]夏揚(yáng)坤，符卓.帶軟時(shí)間窗的連鎖超市配送車(chē)輛路徑問(wèn)題[J].信息與控制，2018，47（5）：599-605.

XIA Y K， FU Z. Vehicle routing problem with soft time windows for the chain supermarkets[J]. Information and Control， 2018， 47（5）：599-605.

[16]龐燕，鄒愛(ài)輝.基于電子商務(wù)平臺(tái)的家具企業(yè)采購(gòu)模式分析[J].森林工程，2015，31（3）：159-163.

PANG Y， ZOU A H. An analysis of purchasing model of furniture enterprises based on e-commerce platform[J]. Forest Engineering， 2015， 31（3）：159-163.

[17]張貽弓，吳耀華.基于并行揀選策略的自動(dòng)揀選系統(tǒng)品項(xiàng)分配[J].計(jì)算機(jī)集成制造系統(tǒng)，2010，16（8）：1720-1725.

ZHANG Y G， WU Y H. Item distribution of automatic picking system based on parallel picking strategy[J]. Computer Integrated Manufacturing System， 2010， 16（8）：1720-1725.

[18]SARKER B R. The resemblance coefficients in group technology： a survey and comparative study of relational metrics[J]. Computers & Industrial Engineering， 1996， 30（1）：103-116.

[19]LIU C M. Clustering techniques for stock location and order picking in a distribution center[J]. Computer & Operations Research， 1999， 26（10）：989-1002.

[20]李詩(shī)珍.配送中心訂單分批揀貨問(wèn)題的數(shù)學(xué)模型及算法[J].鐵道運(yùn)輸與經(jīng)濟(jì)，2007，29（11）：65-67.

LI S Z. Mathematical model and algorithm on order batch picking issues in distribution center[J]. Railway Transport and Economy， 2007， 29（11）：65-67.

[21]李詩(shī)珍，杜文宏.基于聚類(lèi)分析的訂單分批揀貨模型及啟發(fā)式算法[J].統(tǒng)計(jì)與決策，2008（12）：53-56.

LI S Z， DU W H. Order batch picking model and heuristic algorithms based on cluster analysis[J]. Statistics & Decision Making， 2008（12）：53-56.

[22]王雄志.配送中心配貨作業(yè)計(jì)劃方法研究[D].廣州：暨南大學(xué)，2007.

WANG X Z. Research on distribution center distribution operation planning method[D]. Guangzhou： Jinan University， 2007.

[23]萬(wàn)杰，張少卿，李立.基于遺傳算法的配送中心訂單揀選優(yōu)化問(wèn)題研究[J].河北工業(yè)大學(xué)學(xué)報(bào)，2009，38（5）：10-14.

WAN J， ZHANG S Q， LI L. Research on order picking optimization of distribution center based on genetic algorithms[J]. Journal of Hebei University of Technology， 2009， 38（5）：10-14.

[24]伍經(jīng)緯，蔡臨寧.訂單分批算法的適用性研究[J].工業(yè)工程與管理，2007，65（4）;104-107.

WU J W， CAI L N. Applicability of order batching algorithms[J]. Industrial Engineering and Management， 2007， 65（4）：104-107.

[25]HO Y C， WEE H M， CHEN H C. A geometric design of zone picking in a distribution warehousing[C]. International Conference on Computational Science and Its Applications， 2007：625-630.

[26]李詩(shī)珍.揀貨方式-存儲(chǔ)策略與路徑策略協(xié)同研究[J].工業(yè)工程，2011，14（2）：37-43.

LI S Z. Collaborative research on picking mode-storage strategy and path strategy[J]. Industrial Engineering， 2011， 14（2）：37-43.