摘 要

在具备竞争力的供应链系统中，在确保产品和服务质量的同时，迅速满足客户期望已成为一种必需。因此，提高仓库的拣选作业效率对于整个物流配送系统来说是一个重要的研究方向。本文在分析以往学者研究不足的基础上，主要研究多区块仓库拣选过程中的订单分批和拣选路径优化问题。

多区块仓库比单区块仓库多了中间横向通道，因此，多区块仓库的拣选路径及距离计算是有差别的。在考虑分拣设备容积和载重量的基础上，本文主要做了如下工作：

（1）建立了以多区块仓库最大巷道相似度为目标函数的订单分批模型，在订单分批模型的基础上，设计了基于多区块仓库巷道相似度的种籽算法，并与传统的先到先服务的分批方法进行了比较。

（2）建立了以最短拣选距离为目标函数的拣选路径优化模型。在拣选路径优化模型的基础上，设计了遗传算法，并与传统的多区块仓库S型路径策略进行对比。

（3）对先到先服务 S型路径策略与基于巷道相似度的种籽算法 遗传算法进行联合对比优化，通过算例验证得出结论：订单分批和拣选路径问题的联合优化算法能最小化拣选路径距离，从而提高订单拣选效率和仓库服务水平。

关键词：订单分批；拣选路径优化；种籽算法；遗传算法；联合优化

Abstract

In a competitive supply chain system, it is a must to quickly meet customer expectations while ensuring the quality of products and services. Therefore, improving the efficiency of warehouse picking operations is an important research direction for the entire logistics distribution system. Based on the analysis of the lack of research by scholars in the past, this paper mainly studies the problem of order batching and picking path optimization in the process of multi-block warehouse picking.

Multi-block warehouses have more intermediate horizontal channels than single-block warehouses. Therefore, the selection path and distance calculation of multi-block warehouses are different. On the basis of considering the volume and load capacity of the sorting equipment, this paper mainly does the following work:

Firstly, an order batch model with the maximum lane similarity of multi-block warehouse as the objective function is established. Based on the order batch model, a seed algorithm based on the similarity of multi-block warehouse roadway is designed, which is compared with the traditional first-come first-service batching method.

Secondly, a picking path optimization model with the shortest picking distance as the objective function is established. Based on the picking path optimization model, the genetic algorithm is designed and compared with the traditional multi-block warehouse S-type path strategy.

Lastly, the first-come-first-served S-path strategy and the seeding algorithm based on roadway similarity genetic algorithm are combined and optimized, and the results are verified by the example: the joint optimization algorithm of order batching and picking path problem can minimize picking path distance to improve order picking efficiency and warehouse service levels.

Key Words: order batching; picking path optimization; seed algorithm; genetic algorithm; joint optimization

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1 研究背景 1

1.2 研究目的及意义 1

1.3 国内外研究现状 2

1.3.1 国外研究现状 2

1.3.2 国内研究现状 3

1.4 研究内容和目标 4

1.5 技术路线 4

1.6 论文框架 4

第2章 相关理论知识 6

2.1 拣选作业相关理论 6

2.1.1 拣选的概念和流程 6

2.1.2 拣选策略 6

2.1.3 影响拣选效率的因素 7

2.2 订单分批相关理论 7

2.2.1 订单分批问题概述 7

2.2.2 订单分批原则 7

2.2.3 订单分批启发式方法 8

2.3 拣选路径优化相关理论 9

2.3.1 拣选路径问题概述 9

2.3.2 传统启发式拣选路径策略 9

第3章 订单分批模型建立与算法设计 10

3.1 订单分批问题建模 10

3.1.1 问题描述 10

3.1.2 模型假设 10

3.1.3 多区块仓库巷道相似度概念及计算 10

3.1.4 模型建立 11

3.2 基于巷道相似度的种籽算法设计 12

第4章 拣选路径优化模型建立与算法设计 14

4.1 拣选路径问题建模 14

4.1.1 问题描述 14

4.1.2 模型假设 14

4.1.3 模型建立 14

4.2 多区块仓库S型拣选路径策略 15

4.3 遗传算法设计 16

4.3.1 编码设计 17

4.3.2 生成初始种群 18

4.3.3 遗传算子设计 18

4.3.4 进化终止条件 20

4.3.5 遗传算法流程图 20

第5章 算例分析 22

5.1 算例说明 22

5.1.1 多区块仓库布局示意图 22

5.1.2 订单品项编码方式 23

5.1.3 拣选距离计算 24

5.1.4 生成模拟订单 25

5.2 S型路径策略下订单分批优化结果分析 25

5.3 先到先服务分批方式下拣选路径优化结果分析 26

5.4 联合优化结果分析 27

5.5 三种优化方式结果对比 27

第6章 总结与展望 29

6.1 全文总结 29

6.2 展望 29

参考文献 31

附 录 33

致 谢 63

绪论

研究背景

随着供应链管理的出现，仓库已经改变了角色，战略性地改变为实现更短的商品周转时间，更低的库存水平，更低的成本和更好的客户服务的物流目标。配送中心快速响应客户需求成为供应链的重要功能。

订单拣选是根据客户订单从指定存储位置取出物品的过程。订单拣选需要耗费大量的人力，提高订单拣选的性能可以节省大量的仓储成本。拣选作业是仓储作业一切操作中非常重要的一部分，它的作用相当于人体的心脏、空调系统的压缩机^[1]。配送中心频繁的物料流通导致了配送中心比较大的工作量。拣选业务量约占配送中心内部业务总量的60%，其经营成本占仓库总运营成本的50%-75%^[2]，仓库的运营性能和成本效益主要被订单拣选操作的效率影响。拣选操作是配送中心实际运行过程所有操作中成本最高且最耗时的部分。因而，配送中心要注重优化拣选作业这一环节，缩短拣选作业时间，提高拣选作业效率。

通过高效的仓储操作可以提高整体物流服务水平。在订单拣选操作中，拣选人员可以一次只选择一个订单（按订单拣选）。然而，目前仓库中的订单处理活动节奏更快。为了满足客户对更高物流服务水平的要求，产品可能只会在仓库中停留几天甚至几个小时。在拣选客户订单之前，有效地将订单合并分批可以显著加快仓库内的产品流通速度。仓库内有大量的产品流通，即使拣选距离在每趟拣选路途中只减少很少一部分，也可以有效降低拣选操作成本。批量拣货（即同时拣选多个订单）是一种更好的拣选方式，因为它可以在仓储操作中取得更高的拣选效率。订单分批问题被视作NP难题，并且在可容忍的计算时间内获得大规模问题的最优解决方案是极其困难的。

以前的研究主要集中在具有单通道的仓库中的订单分批问题或者仅仅只考虑拣选路径优化问题，却很少有学者在多区块仓库中把订单分批和拣选路径联合起来进行优化。多区块仓库更符合实际的仓库类型。单区块与多区块仓库的主要区别在于其仓库布局不同，多区块仓库除前后端横向通道外，还多了中间横向通道，因此，它们的拣选路径距离计算方式也不同。单区块与多区块的拣选路径策略是不同的，多区块仓库中，拣选人员可以更灵活地改变拣选通道，有更丰富的拣选路径可供选择。

在拣选操作中，行走时间在总拣选时间中占有较大比例，而合适的订单分批、排序和拣选路径的优化可以缩短拣选路径距离，提高拣选操作效率，从而降低仓库操作的总成本。

研究目的及意义

在规模较大的流通型仓库内，每天需要拣选的订单有成千上万个。拣选作业是决定配送中心服务水平的要素之一，也是其内部运营的瓶颈，拣选作业效率很大程度上决定着一个配送中心的服务水平。在仓库订单拣选过程中，管理者为了提高分拣效率，通常会增加拣选设备或拣选人员数量并同时作业，但这会导致固定成本增加等负面效应，并且在实际操作过程中，由于仓库巷道宽度较窄，同一巷道不能容忍多个拣选人员或设备同时工作，因此这种措施并非在任何仓库中均适用。另一种方法是通过在操作期间优化控制流程来提高分拣效率，并且可以充分提高设备的利用效率。该方法由于实现成本低、效率高，引起了国内外学者的密切关注。

拣选操作有很多优化方法，典型的操作过程优化控制方法包括订单分批和拣选路径优化。本文设计了多区块仓库的基于巷道相似度的种籽算法来解决订单分批优化问题，订单分批优化可以通过减少订单分批批数来减少分拣人员的劳动强度和作业时间，从而提高分拣效率；设计了遗传算法来求解拣选路径优化问题，拣选路径优化可以通过改变拣选物品的次序有效减少拣选过程中的行进距离。由于配送中心需要拣选的订单在前一天就录入到了计算机系统中，因此，使用种籽算法和遗传算法求解订单分批和拣选路径优化问题，在满足学术研究上的精确度要求的同时，也满足了客户对于订单拣选的时间要求。

国内外研究现状

国外研究现状

Ackerman于1990年第一次提出订单分批拣选的方法^[3]。

Gibson和Sharp通过计算机仿真对订单分批拣选与传统按订单拣选两种拣选方式进行了比较，并通过数值实验证明了分批拣选在缩短拣选距离方面更有效^[4]。

Y.-C. HO和Y.-Y. TSENG研究了在两种不同的路线规划方法和两种不同的过道拣选频率分布下九种种子订单选择规则和10种伴随订单选择规则的性能，还研究了路线规划方法和过道拣选频率分布对种子订单选择规则和伴随订单选择规则的性能的影响，生成并测试了不同的随机问题来完成这些研究^[5]。

Osman Kulak和Yusuf Sahin等人提出了一种新的禁忌搜索（TS）算法，该算法与一种新的聚类算法相结合，可以解决多交叉仓库系统的订单分批和拣选路径问题，并提出有效的最近邻和节约启发式算法以满足问题的特定功能。最后，随机生成包括订单数量，品项重量和拣选坐标在内的各种问题实例，并进行详细的数值实验设计来验证算法的有效性^[6]。

Tzu-Li Chen和Chen-Yang Cheng等人讨论了仓库中的联合订单分批，排序和拣选路径问题（IOBSRP）。综合非线性混合整数优化，在考虑客户订单的最小总延迟的情况下，建立模型以同时确定三个决策，包括订单分批，排序和拣选路径优化。为了验证所提出算法的优点，以不同需求、批次容量和订单的品项进行说明性示例和灵敏度分析^[7]。

AndréScholz和Daniel Schubert第一次提出了一种同时考虑订单分批、排序以及拣选员路径问题的方法，建立了该问题的数学模型，其适用于解决小规模订单问题。对于较大规模的订单，提出了可变邻域下降算法。通过数值实验，证明其算法提供了较为优质的解决方案^[8]。

Ehsan Ardjmand和Heman Shakeri对多个拣选员的订单分配，订单分批和拣选员路径问题进行了研究和数学建模，使用精确算法求解所提出的数学模型。由于精确算法占用较长的CPU运算时间，因此提出了一种拉格朗日分解启发式算法与粒子群优化算法相结合的算法（LD-PSO），该算法适用于小规模订单拣选。为了解决大规模问题，提出了一种混合并行模拟退火和蚁群优化算法（PSA-ACO），当订单与拣选人员数量或拣选设备能力的比率较高时，拣选数量和拣选能力的增加对减少完工时间的影响更大^[9]。

国内研究现状

1. 订单分批研究现状

李诗珍基于聚类启发式算法，提出了三种相似系数计算公式，建立了订单分批拣选模型，该模型以最小拣选距离为目标函数，将相似系数运用到模型中，提出了求解该模型的解决方案，最后设计了算例以验证算法的有效性^[10]。

王旭坪以带交付期的订单为研究对象，研究了电子商务中的订单分批问题，采用固定时间窗的订单分批启发式算法求解模型，研究表明，考虑交付期的情况下，所拣选出的订单数量更多^[11]。

吴天行和郭键建立了基于巷道相似度的订单分批聚类模型，设计了基于图论的订单分批聚类算法，最后通过一个实例验证了其设计算法的有效性^[12]。

王转等考虑拣选设备的容积，研究了电商配送中心的拣选订单分批问题，设计了基于节约里程的启发式算法，对比了所提出的算法与先到先服务算法和基于相似度的订单分批算法的表现优劣^[13]。

1. 拣选路径优化研究现状

陈方宇研究了多区块仓库中单拣货员拣货的情况，设计了基于偏离度的拣选路径优化算法，通过数值实验表明，只有当拣选密度在一定范围内时，拣选优化算法才有效^[14]。

李栋栋等根据双区型仓库的布局，设计了贪心遗传算法求解双区型仓库的拣选路径优化问题，并以双区型仓库为对象进行数值实验，验证了其算法的全局最优性和稳定性^[15]。

刘建胜等根据双区型仓库中拣选路径的特点，设计了蚁群算法求解拣选路径优化模型，通过算例验证了其设计算法的实用价值^[16]。

佘智勇等研究了双区型仓库中的拣选路径问题，使用改进的动态规划算法，通过与其他传统启发式拣选策略对比，证明了其设计的算法模式简单，具有较好的实用性^[17]。

研究内容和目标

本文主要研究内容包括：

（1）针对订单分批问题，模拟生成订单并设计订单分批策略，如先到先服务分批和基于相似度分批。对于订单分批问题，本文充分考虑拣选设备的容积和载重量限制，将研究对象确立为多区块仓库，然后建立以最大巷道相似度为目标函数的订单分批模型。

（2）针对拣选路径优化问题，以最短拣选距离目标，建立拣选路径优化问题的数学模型，将拣选路径优化问题用不同算法（遗传算法和S型策略）解决，比较所选用方法在解决拣选路径优化问题上的有效性。

（3）针对订单分批和拣选路径优化两个问题均为NP难题的特点，分别选用基于巷道相似度的种籽算法和遗传算法求解所建立的模型，详细设计遗传算法的遗传算子。将联合优化算法与传统的先到先服务分批 S型拣选路径策略进行对比，比较二者在优化拣选距离方面的表现优劣。

目标：使用订单分批及拣选路径优化算法，分别求解订单分批和拣选路径优化问题模型，使用Matlab编程实现配送中心多区块仓储拣选策略优化决策系统原型，联合优化订单分批和拣选路径问题，从而减少拣选过程中的行走距离，提高拣选效率和仓库服务水平。

技术路线

本文的研究思路如图1.1所示。

论文框架

本文的主要章节安排如下：

第一章是绪论。阐述了研究背景，研究目的及意义，研究现状、研究内容和目标，技术路线和论文框架，指出了论文的研究方向。

第二章是相关理论知识。简单介绍了拣选作业的相关概念及拣选策略，订单分批问题及分批策略，拣选路径优化问题及传统拣选策略。

第三章是针对订单分批问题的建模及算法设计。描述了订单分批问题，对其进行了简化预处理。将问题由单区块仓库改为多区块仓库，在此基础上，建立了以最大巷道相似度为目标函数的订单分批问题模型，设计了基于巷道相似度的种籽算法对订单分批模型进行求解。

第四章是针对拣选路径优化问题的建模及算法设计。描述了拣选路径优化问题，对多区块仓库拣选路径问题进行了简化预处理，在此基础上以拣选距离最短为目标，建立了拣选路径优化模型，介绍了多区块仓库下订单拣选的S型策略，设计了遗传算法对拣选路径优化模型进行求解。

第五章是算例分析。首先生成模拟订单，然后依次展示了S型策略下先到先服务订单分批和基于巷道相似度的种籽算法订单分批对拣选距离结果的对比结果，先到先服务分批方式下S型路径策略和遗传算法路径优化对拣选距离结果的对比结果，以及联合优化算法对拣选距离结果的对比，并对优化结果做出了详细分析。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：