| 标题 | 基于0-1分块矩阵求解的B2C配送中心订单分批优化模型构建 |
| 范文 | 于岚 高贵晨 孙术发 武晋峰 熊武兴 摘要：在同一时间窗下研究多品种、多批次、少批量的订单分批处理具有较高的理论和实际意义。本文在考虑按单拣货和并单拣货的最优拣货策略的基础上，构建针对B2C配送中心拣货时间数学模型，运用分块矩阵以及MATLAB对模型进行求解。将模型应用到配送中心实际订单拣选中，得到最优订单分批处理方案，证明该模型具有可行性和实际应用价值，可为B2C配送中心订单分批处理问题提供定量决策方法。 关键词：B2C;拣货策略;订单分批;数学模型;分块矩阵 中图分类号：F724;F253文献标识码：A文章编号：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是一種通过网上商店节省企业和客户时间与空间的电子商务模式。但电子商务是网络虚拟交易平台，货物的送达需要依靠物流配送环节。配送中心作为物流体系的重要组成，其运作活动决定了整个物流环节的优劣?[1-3]。配送中心拣货决策对配送效率的影响很大?[4-5]。目前，关于拣货决策的研究多集中在订单分批?[6-9]处理问题上。Ackerman在文献[10]中首次提出订单分批分拣的概念，Gibson和Sharp?[11]运用计算机仿真的方法直观的证明了订单分批分拣方式比普通的拣货方式更优，之后，国外的研究从启发式算法?[12]到现在的智能优化算法?[13]层层递进;而国内物流行业起步较晚，对订单分批?[14-16]的研究相对滞后，主要运用聚类分析?[17-19]、启发式算法?[20]等进行研究。但相似系数反映的是内在联系的指标，当数据量较大时，不容易获得聚类结论?[21]。启发式算法不一定能保证解的可行性与最优性，多数情况下无法描述该解与最优解的近似程度?[22]。结合上述问题以及配送中心多品种、多批次、小批量的特点，借鉴多学科的观点和方法，本文提出建立同一时间窗下的数学模型，并采用针对非线性有限问题的0-1分块矩阵法得出最优拣货决策，得到耗时最少的订单分批拣货策略。 1问题描述 B2C配送中心的特点为多品种、多批次、少批量。每天都需要对不同门店进行商品的配送。订单到达时，配送中心拣货人员根据订单分配情况进行拣货作业。拣货员使用拣货车拣选货物时，可同时拣选多个订单，将同种商品放置在同一周转箱中。拣选完成后，按单拣货的货物直接送至分拣复核区;并单拣货的货物送至二次分拣作业区，完成货物的分拣。 在拣货作业过程中，影响拣货效率的因素包括拣货员行走路径、拣货时间以及二次分拣作业时间。拣货作业效率对配送中心的成本影响巨大。 2模型建立 2.1模型假设 （1）按照时间窗固定分批。 （2）一个订单中至少包括一个品项。 （3）订单的完成要完整。 （4）形成批次的订单中拣选同种货物的总量不超出拣货车的容量。 （5）将订单信息录入后，WMS可根据模型给出订单分类结果。 （6）同一时间窗下，订单为多品种、多批次、少批量。 （7）拣选不同品项耗时以及二次分拣耗时可求。 （8）立体存储区货物数量不受拣货车容量限制。 2.2模型建立 （1）目标函数： minZ=∑li=1∑mij=1tij+dij+∑nk=1∑mkj=11-Cktjk （1） 約束条件： xij≤Qi=1，2，…，l;j=1，2，…，mi（2） 按单拣货订单的确定应满足下列约束条件： Sj=1?aj∩aj?'=Φ，aj?j=1，2，…，mn（3） 当按单拣货时，不考虑拣货车容量问题。 变量解释如下： （2）波次单总数?l?的确定： 当Sj>1时，将j从1到mn的aj逐次比较，将包含相同k的aj合并。若aj不能合并，看其是否满足约束条件xij≤Q，若可以，则为一个波次单。若不可以，在约束条件以及目标函数下再次分单;若aj可以合并，在约束条件xij≤Q下，运用分块矩阵求解∑li=1∑mij=1tij+dij最小的订单分批。 3案例分析 某配送中心为B2C模式，中心总体布局包含仓储功能作业区和办公区域。其中，仓储功能作业区包含立体存储区、托盘存储区、阁楼式货架拣货区、电子标签拣货区、拣货复核区、二次分拣作业区以及出入库平台。 为提高该配送中心的拣货作业效率，本文依据销售额和销售量对该配送中心货物进行ABC分类，按照分类结果以及货物周转率对配送中心货物储位进行合理安排，该配送中心配有WMS系统，订单接收后能得知各品项所在具体位置，使模型可快速求解得到该B2C配送中心的最优订单分批。案例分析之前，给出算法分析流程图如图1所示。 3.1订单信息整合 现有10张订单，根据销售量和销售额依据ABC分类法以及储位安排原则?[22-24]，将订单原有信息加以分类和存储，得到订单信息见表2。根据配送中心实际数据，需拣选的A类货物存储在立体存储区，由巷道式堆垛机直接拣货出库，为简化算例，求解目标函数时不考虑A类货物拣货时间;需拣选的B、C类货物所在储位以及拣货员位置坐标如图2所示。 图2为该配送中心需拣选订单货物的部分储位分布图，电蒸锅与小砍骨刀为B类货物，周转率相对C类货物高，存储在距离输送线较近的位置。结合配送中心实际距离，以左下角拣货员所在位置为原点，构成平面直角坐标系。其中，货架宽0.6 m，长4 m，货架横向间隔1.2 m，纵向间隔1.5 m，输送线与货架最近距离为1 m。货物位置的给定采用横坐标为拣货一侧坐标，纵坐标为货格中点坐标。 3.2十张订单最优拣货策略求解 针对同一时间窗下所有品项的归属订单来构造分块矩阵，在满足约束条件前提下，将不同订单排列组合，逐个求解不同订单分批拣货作业耗时，将耗时最少的订单分批作为最优解。对各品项所在订单进行汇总见表3。 算例求解： （1）该配送中心拣货员行走速度平均为1.6 m/s，从货架取一箱货物平均耗时1.5 min。拣选的面条机和电蒸锅的包装箱尺寸为440 mm×320 mm×300 mm，小砍骨刀和厨房多用剪刀的包装箱尺寸为300 mm×230 mm×240 mm，该配送中心对这两种类型货物的拣货车容量?Q?=4箱。 对各品项进行数量汇总得到表3。其中，小砍骨刀与厨房多用剪刀为20件一箱，在进行数据整理时，采用“进一”原则，将十张订单中小砍骨刀和厨房多用剪刀的需求量分别换算为4箱和2箱。根据前文所述，A类品项由立体存储区直接拣货出库，不用拣货车进行人工拣选，因此，对其数量不予考虑。结合拣货车容量为4，由表3可得：含有品项2的订单1，4，8，9或含有品项4的订单2，6，10不能合成一张波次单。 （2）根据模型构建，Sj>1不存在按单拣货。 （3）分块矩阵的定义及求解思想如下。 设A是一个m×n的矩阵，如用若干横线条将它分成r块，再用若干纵线条将它分成s块，于是有rs块的分块矩阵，A=A11…A1s?………?Ar1…Ars，其中Aij表示的是一个矩阵。 同一时间窗下的订单分批问题属于有限问题，引入订单分批矩阵A=ajkmn×n，行方向为品项，列方向为订单?[25-26]。若订单包含品项，在矩阵对应位置写入1，否则写入0，在列方向将订单分成n块，构成0-1分块矩阵。对订单分批矩阵依据含有相同品项的订单可生成波次单，且同一张订单只能存在于一张波次单中进行满足条件的矩阵分块，对应不同的矩阵构造时间矩阵T，求解满足条件的所有目标函数值，最小的目标值就是最优解。同时可得到订单分批结果。 十张订单彼此之间都含有相同品项，构造订单分批矩阵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）案例分析中，拣货耗时为拣货员到达拣选位置并取货以及将货物送至输送带的时间。由于拣货员二次分拣作业耗时相比拣货时间要小的多，求解时二次分拣时间在这里不作考虑。在满足约束条件下，根据图2货物储位布局、拣货员平均行走速度1.6 m/s以及从货架取一箱货物平均耗时1.5 min，运用MATLAB进行求解最优目标函数值min?Z=∑li=1∑mij=1tij?，得到订单分批情况表见表5。求解出最优目标函数值为?Z?=24.54 min，根据最优订单分批结果：b1=1，4，6，8?b2=2，3，5，7，9，10，拣货员从货物储位布局图的原点出发，按照b1、b2下的拣货耗时最短绘制拣货员拣选路径如图3所示。 该算例求解的拣货耗时为拣货员到达拣选位置取货然后将货物送至输送带的时间。从表5可以得出以下两点推论，为下一步深入研究提供思考方向： （1）当波次单的数量相同时，拣货耗时相差不大。这是因为当波次单的数量相同时，拣货员的取货时间相差不大，拣货耗时的不同主要体现在拣货员的拣选路径上。该算例的求解中，品项所在位置相距较近，拣货员行走路径的不同对求解结果影响较小。当品项相距较远时，会更好的反映出因订单分批情况的不同，拣货耗时的差异性。 （2）在约束条件下，绘制不同波次单数量下的平均拣货耗时折线图如图4所示。图4中显示平均拣货耗时随波次单的增加呈上升趋势。在同一时间窗下，订单批次增加会使需要拆箱拣选品项的拣货时间增加，因此，在满足约束条件的情况下，应尽可能的减少波次单的数量。 4结束语 合理的流程分析以及有效的拣货作业策略可以提高配送中心的拣货作业效率。本文通过对货物进行ABC分类、储位安排以及构建综合拣货决策模型，运用定量的方法给出了B2C模式下配送中心最优订单分批的作业方法。通过案例分析，利用MATLAB求解订单分批矩阵的最优组合，表明了方法的可行性。 本文仅在考虑按单拣货和并单拣货的最优拣货策略的基础上，构建了针对B2C配送中心拣货时间的数学模型，在模型时间复杂度与空间复杂度上未给出具体证明。但本文以求解方式更为简单的分块矩阵对具体实例进行分析，在订单数量较少的情况下可取得较好的实验结果。为后续进一步深入研究提供了思考方向。 【参考文献】 [1]朱国俊.试论摘取式与播种式拣货的异同[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]黄河，杨以雄.服装物流配送中心信息自动化升级决策及案例研究[J].东华大学学报（自然科学版），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]张文会，马俊.基于AHP和GCA的第三方医药物流中心选址研究[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]安立华，赵秋雅，郭清伟，等.配送中心选址问题研究[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电子商务环境下订单拣选与配送联合调度优化[J].中国管理科学，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]林双娇，何娜.价值链视角下的货运代理行业转型升级路径研究——以厦门为例[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]夏揚坤，符卓，谢九勇.依订单拆分的多自动导引车物料配送路径规划[J].计算机集成制造系统，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]夏扬坤，符卓.带软时间窗的连锁超市配送车辆路径问题[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]庞燕，邹爱辉.基于电子商务平台的家具企业采购模式分析[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]张贻弓，吴耀华.基于并行拣选策略的自动拣选系统品项分配[J].计算机集成制造系统，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]李诗珍.配送中心订单分批拣货问题的数学模型及算法[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]李诗珍，杜文宏.基于聚类分析的订单分批拣货模型及启发式算法[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]王雄志.配送中心配货作业计划方法研究[D].广州：暨南大学，2007. WANG X Z. Research on distribution center distribution operation planning method[D]. Guangzhou： Jinan University， 2007. [23]万杰，张少卿，李立.基于遗传算法的配送中心订单拣选优化问题研究[J].河北工业大学学报，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].工业工程与管理，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]李詩珍.拣货方式-存储策略与路径策略协同研究[J].工业工程，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. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。