本文是一篇工程管理论文，本文在鞋服零售电商仓这个典型背景下，基于多区并行作业、人到货拣货模式等关键特点，研究拣货规划问题。
第一章 引言
第一节 研究背景及意义
一、研究背景
随着疫情的爆发，原本已经非常火热的电商领域更加烈火烹油。根据《2020年胡润中国10强电商》发布的数据，我们可以看到，在疫情的“加持”下，京东和拼多多的零售成交额分别较2019年增长了1倍和1.5倍。2020年，阿里巴巴国内零售成交总额高达6.6万亿元，京东和拼多多则分别为2万亿和1万亿元。其中，仅鞋服行业零售电商成交总额就达到了千亿级。
线上交易如此火爆的背后，依赖的是强大的履约系统，确保消费者下单后，可以如期保质收到货物。
消费者在各电商平台购物后，订单数据通常将经过如下系统的流转：
电商平台（如京东）->订单管理系统（OMS，Order Management System）->仓储管理系统（WMS, Warehouse Management System）->运输系统（TMS，Transportaion Management System）。
其中，仓库管理系统和运输系统构成了实物层面，交易履约的核心，也就是我们常听到的仓配：仓库作业、配送交付。
实体向线上零售的转变引入了巨大的业务量，同时国内各电商平台和消费者对配送时效有着极高的要求，各品牌、商家、电商代运营公司都意识到了仓配履约（仓储、拣选、包装、运输、配送等）的重要性、所代表的核心竞争力、以及面临的压力和挑战。
如果说交易的压力在履约，那么履约的压力就在仓库作业，而仓库作业最难最耗时最费力的就是拣货，货物拣选环节（据研究，拣选环节占出库作业总时长和总成本的比例高达50%-60%）。
第二节 国内外研究综述
常见的拣货规划研究，主要围绕如下策略：
1) 布局策略（Layout Design）：结合仓库服务的行业、品类、目标吞吐量、关键业务指标等要素，在仓库搭建和启动之初，通过仿真等手段，进行库区库位（库区、通道、作业区域等）、作业设施设备（自动化设备如自动化导引机器人、周转设备如周转箱、装卸设备如叉车等）的评估、设计和选型决策；
2) 分区策略（Zoning）：分区的核心思想是将拣货区域拆分成多个工作分区，每个工作分区可指定一到多个拣货员进行作业，从而实现并发作业的效果，提高作业效率；
3) 存储策略（Storage Assignment）：来货入库的存储策略（如随机存储、一品一位存储、ABC分类存储、靠近出口存储、关联存储等），库内的管理和补货策略（如呆滞品清理、水位补货策略、高低库位补货策略等）往往都是基于商品的销售或者出库周转情况，进行设定。出库的货位分配：海量订单随机高频下发到仓库，通过分析订单结构，如同品单件订单、同品多件订单、畅销品多件订单等，进行库位的分配，来缩小分配区域范围、形成高密度分配效果，使得相同时间和距离内能拣选出更多的订单；
4) 分批策略（Batching）：如何合理的将订单池中订单分成多个批次作业，来实现整体作业用时短、效率高的效果；
5) 路径策略（Routing）：实际作业中，受使用周转容器、仓库布局设计等影响，拣货任务有多种组织形态，如组车拣选、周转箱拣选、存储库位托箱拣选等。且每个批次可能对应多个拣货任务。电商仓同时可能有几百名员工进行拣货作业。存在多人多批次多任务的情况下，需要根据任务线路（需考虑线路拥堵等情况）、任务优先级、人力资源情况等调度任务并且规划拣货人员的行进路线。
第二章 相关概念和理论知识
第一节 鞋服零售电商相关知识
一、行业特点
鞋服、数码、家电、日用等均为电商热门类目。其中，鞋服类目每年的网上零售额高达上千亿，占全部类目网上零售总额的比例达30%到40%。 鞋服零售电商行业具有以下特点：
1. 人：购买人群极为广泛，不同细分类目受众群有所区别，比如奢侈品、女装、男装、童装
2. 货：商品种类多（单个品牌全网在售商品种类可高达十几万种）、有标准包装、单品体积和重量均相对较小（属于中小件）
3. 场：网上交易渠道众多
4. 交易：订单量庞大、单个订单购买件数较少、购买商品种类分散、退货率较高、随促销订单量波动较剧烈、发货准确率和时效要求较高
由于第2点和第4点所述特点，鞋服零售电商仓的出库作业压力，遥遥领先于其他行业。
二、出库作业流程
为满足订单的发货时效要求，电商仓库收到订单后，需要短时间内集中作业，将货物按订单备好，打包成一个个独立的包裹，交接给物流承运商（电商行业通常合作各快递公司，如顺丰），并最终配送到消费者手中。从收到订单，到将货物交接给快递公司的整个过程，称之为出库作业全流程。
鞋服零售电商仓库出库作业涉及重点环节简述如下：
1. 收到订单：仓库使用信息系统，如WMS，接收到订单请求
2. 制定作业计划：仓库管理人员基于订单的时效要求等，在信息系统中制定出库作业计划，决定先履行哪些订单
3. 分配拣货任务：主管分派拣货任务给到一到多个拣货员。第1到第3环节是连续的必不可少的环节，后续简称准备阶段
4. 拣选货物（后续简称为拣货）：拣货员从起点出发，按照指引（信息系统或纸质单证）前往库位（货架），将特定数量的指定货物挑出后，放到拣选容器（通常为周转箱），并循环这个过程，直至完成当前拣货任务，返回起点
第二节 算法理论
一、聚类算法
K-Means 是经典的划分聚类算法，其核心思想是通过选定初始种子，基于欧式距离等进行相似度测量，将相似度高的订单聚成一类，通过反复运算不断确定新的聚类中心及簇类，最终确定最优簇类。这种算法易于理解和掌握、兼之计算速度快，适合在实际工作中应用。实际上，K-Means已经得到了较为广泛的运用，并且衍生出较多改进算法。
正是由于K-Means 算法易于实施，且大数据量下计算效率高，时间复杂度小，较为契合本文鞋服零售电商的数据特点和需求，因此，选择此算法用来优化订单分批。不过，K值和初始聚类中心需要提前指定，并且K值的确定对最终聚类效果有较大影响，对实际应用带来一定困扰，也是本文评价算法应用效果尤为关注的。本文采用轮廓系数法，评价聚类效果。
二、遗传算法
遗传算法的核心在于，借用进化论“物竞天择，适者生存”的思想，将染色体作为问题解，通过种群自然的优胜劣汰，求得问题的最优解或者较优解。对于在可接受时间范围内可以求出最优解的问题，没有必要用遗传算法。无法在有效时间内，甚至完全无法求出最优解的情况下，比如NP HARD问题，则由于遗传算法抽象应用范围广泛和全局寻优效率高的特点，常被大家用来求取近似最优解。由于本文研究的批次集合问题也属于NP HARD问题，因此，选用遗传算法。
遗传算法计算的基本步骤简单介绍如下：
1. 初始化种群：种群由若干条染色体构成。染色体由基因片段组成。
2. 评价种群下所有个体的适应度：通过一定规则，评价当前种群下每个个体对环境的适应能力，或者说生命力。
3. 选择运算：使用轮盘赌或者锦标赛选择法，选择一些染色体，进入下一步计算。通常来说，适应力越强的染色体被选中的概率越高。
4. 交叉运算：选出的染色体，在一定概率下，相互之间交换基因片段，模拟实际物种的基因重组或者杂交。
5. 变异运算：在一定概率下，部分染色体发生基因变异。
6. 经过步骤3-5的运算，此时，初代种群已经进化为N+1代种群。通常，通过设定种群进化迭代的最大次数和停止进化的阈值来结束计算。如不满足结束计算条件，则继续循环上述进化过程。
第三章 订单分批优化问题研究 ............................. 24
第一节 问题描述 ............................. 24
第二节 模型构建 .................................. 25
第四章 批次集合优化问题研究 .......................... 32
第一节 问题描述 .................................. 32
第二节 模型构建 ........................ 32
第五章 算例分析 .................................. 43
第一节 数据采集和处理 ....................... 43
第二节 实验和结果 ............................... 46
第五章 算例分析
第一节 数据采集和处理
获取电商公司A某运动鞋服品牌真实脱敏后出库数据（无任何个人或品牌隐私信息），并提前做好数据处理工作。
清理后的数据包含如下关键内容：
第六章 结论和展望
第一节 总结
本文在鞋服零售电商仓这个典型背景下，基于多区并行作业、人到货拣货模式等关键特点，研究拣货规划问题。本文通过建立基于分步式融合算法的订单分批和批次集合拆分的优化模型，不再局限于单一拣货环节的效率提升，而是同时兼顾了拣货之后作业环节对拣货环节的依赖和要求、拣货任务的调度，最终优化拣货效率的同时，也兼顾了出库整体作业的连贯和高产。
针对订单分批问题，本文以分批结果的总的订单间距离最小为目标函数，结合了时间窗和智能算法分批策略，使得算法更符合鞋服电商仓业务需要，减小计算性能压力，更具实用性。智能算法方面，应用K-Means聚类算法，利用单多件订单的特性，分别使用单件订单所在库位间的距离和多件订单库位所在通道集合间的距离作为订单间的距离判断标准，进行聚类设计。从实验数据可以看出，单件订单使用本文算法拣货时间缩短效果显著，多件订单使用本文算法，同样也有明显效果，但总体表现不如单件订单。当然，对比其他学者的智能算法，拣货时间缩短程度差
