遗传算法下物流配送中心订单拣选路径优化

何亿

内容摘要：订单拣选路径选择是物流配送中心运作效能的核心环节，运用遗传算法等先进算法优化订单拣选路径有助于提高配送中心运作效率。本文阐述了物流配送中心订单拣选路径优化研究的意义，从人工订单拣选模式、拣选路径选择和内设巷道型订单拣选决策方面回顾相关研究，设计遗传算法支持的配送中心订单拣选路径优化方案规划和具体实施步骤，提出构建多订单处理信息系统、强化订单拣选作业与越库配送系统对接能力建设等优化配送中心订单拣选的可行策略。

关键词：遗传算法   物流配送中心   订单拣选   路径优化

问题的提出

我国“一带一路”战略显著扩大了国民经济的活动空间和物流产业的生存和发展空间。为增强参与经济全球化的能力，第三方物流企业既需要强化物流基础设施与设备的投资力度，又需要强化对包括运用先进算法支持的物流管理软件领域的投资力度。以“第三方物流”为骨干的物流配送中心，在实际运作过程中通常会暴露出配送路线不合理、车辆满载率低和配送及时率较低等问题，由此产生的物流配送运作流程中的阻力已然成为制约物流客户企业健康发展的瓶颈。为此，物流配送中心有必要通过采购“第三方物流”企业服务的方式，提升其物流服务社会化和专业化水平，并以第三方物流企业的信息系统为平台，重构物流配送中心订单拣选路径，促进物流企业合理优化配送设备运动路线，降低配送系统运作成本。将遗传算法运用于物流配送中心订单拣选路径优化中，有助于提高物流配送中心订单拣选路径的优化速度，提高其订单拣选效率，提升物流配送客户企业的服务体验水平。

相关文献回顾

在关于物流配送中心的人工订单拣选模式分析方面，贾智、冯爱兰（2014）通过分析配送中心人工订单拣选路径的既有问题，从中找寻出既有的人工订单拣选模式的若干不足，然后在此基础上根据订单指向仓储区的差异化分布特点，设计配送中心的订单拣货点，并对订单拣选路径做了进一步优化，以提高拣货效率。朱杰、周丽等人（2012）研究了分类存储人工拣选随机服务系统效率问题，将服从泊松分布的订单代入M/G/1随机服务系统，以此研究随机服务系统的效率优化问题;研究比较五种货品的订单生成频率和仓储位置配置情形下的折返式和S型拣选方式的效率，仿真结果可为传统四边形物流配送中心的订单拣选决策提供依据，有效优化物流配送中心的订单拣选时间、拣选路径和拣选方式选择方案。前述研究讨论了诸如限定拣选场地形状和拣选人数的有限情形下的拣选优化方案，但对点到点式拣选配送问题缺乏深入探讨。

在物流配送中心拣选路径选择研究方面，张峰、殷秀清（2015）在精益生产模式下从订单紧急度探讨供料路径问题，运用可拓评价法和改进层次分析法找寻受供料路径和订单紧急度两个因子作用下的供料路径规划方案;最后运用基于混合粒子群算法的TSP搜索算法计算供料路径，该方案有效增强精益生产系统的运作效率。Hall（1993）在对跨越仓储中心的订单拣选策略、中点折返式订单拣选策略和最大间距式订单拣选策略做深入研究的基础上，采取系统仿真算法求解三类策略下的配送中心订单拣货路径的优劣，其研究结果表明最大间距式订单拣选策略效果更优。前述研究深入讨论了诸如折返式拣选路径情形下的订单拣选优化策略，其成果在涉及多配送节点的订单拣选问题处理上缺乏推广价值。

在内设巷道的物流配送中心订单拣选问题研究方面，Vaughan和Petersen（1999）探讨了存在仓库内部通道的订单拣选最优方案选择问题，通过设计实验组和对照组的订单拣货路径进行比对计算，结果表明在仓库内部通道的长度增加值与内部通道宽度存有关联性关系时，可以计算出最优内部通道数量。Roodbergen和Koster（2001）给出了动态仿真技术条件下的仓库规模、订单规模与订单拣选时间的最优方案计算方法，其计算结果表明仓库内部通道数量与订单拣选效率之间的关系。前述研究讨论了物流配送中心内部巷道数量与拣选订单效率之间的关系，从优化仓库内部结构角度揭示了订单拣选优化的新思路。

配送中心订单拣选路径优化算法设计

（一） 方案规划

配送中心的订单拣选路径优化算法需要分为两段分别实现：一是初始路径的构造，即根据遗传算法进行全局寻优，并通过改进的启发式算法随机搜寻最邻近的初始路径中的较优方案，通过多次迭代的方式找寻初始优化结果;二是动态路径最优化方案的更迭，即通过对配送中心的订单拣选人员或车辆进行空间定位，在预设拣选人员或车辆空间位置的基础上，给其下达订单拣选任务并动态选择最优订单拣选路径，在完成订单拣选任务后，循环到下一阶段的订单拣选任务下达、接受、寻址和最优路径规划等任务，直至完成该工作时段上全部客户订单拣选需求。与传统的物流配送中心订单拣选路径设计相比较，二阶段的配送中心订单拣选路径最优化算法设计更符合物流配送中心的现场操作特点，故具有更强的实践意义。

订单拣选初始路径构造应从配送中心订单拣选的遗传算法全局优化算法构建启动。既有的研究成果表明，运用遗传算法求解Dynamic Vehicle Routing Planning（DVRP）问题具有优势。本文拟采取遗传算法解决多订单、多拣选操作单元和多道路交通信息的订单拣选问题，该问题的解决需要考虑对仓库内拣选路径上关键路径节点作出优化顺序安排。

（二） 实施步骤

配送中心订单拣选路径优化算法的具体操作步骤如下：第一，对该问题涉及的备择物流配送中心地址进行染色体标注，并运用二进制表示方式进行编码。其中，物流配送中心地址可以用染色体遗传编码的位数表达，而染色体遗传编码的数值表示配送任务选择状态。即不同位置的染色体编码代表不同的物流配送中心地址，数值“0”表示该配送地址未被选中，数值“1”表示该配送地址被选中。

第二，选择操作，即从可以被确定用于重组的个体或该个体染色体的子代中进行选择操作。就单个个体而言，其被执行选择操作的几率相同;但从种群角度而言，其种群规模大小、种群适应度和分布状态决定其被选中的概率。

第三，初始种群生成。物流配送中心的数据初始化，该过程涉及物流配送中心选址操作的初始化和配送路径的初始化数据两部分。具体而言，在确保配送中心各配送地址间库存数量调入和调出值一致的条件下，按照伪随机数规则从第x项染色体中选择若干配送地址，并依据临近匹配原则对其进行客户分配。此时系统随机生成若干初始数值，各初始数值构成单个染色体，并以编码形式进入下一步计算中，若干单体染色体构成初始化种群，其编码值与算法后续进程相关。

第四，染色体个体适应度计量。系统通过适配值函数f（x）评估各染色体既有状态下标值的最优性，以此决定染色体个体获取交叉和变异几率。其中，具有较低适配值函数值的染色体个体拥有更高的交叉变异机会。关于适配值函数值的选取问题，本文拟采用单位物流强度下的物流费用表示，相关变量值主要来源于调研统计数据和财务成本核算结果。

第五，交叉与变异操作。交叉操作的关键在于选择算子、交叉算子和变异算子的确定。其一，选择算子的确定通常在染色体种群个体适应度计量环节实现。由于适配值函数值表示该种群个体中遗传到下一代种群中的几率大小，其适配值函数值越小，其适应度水平越高，则其具有遗传能力的几率就越大。本文拟采用“最优值直接迭代”算法确定部分可遗传的染色体算子，紧前一代中的适配值函数值最小者可以拥有优先迭代权，即紧前一代中适应度最高的染色体个体直接迭代到紧后一代中，以便加快整个遗传算法的收敛速度，降低该算法的计量难度并提升其算法精度。另外，该遗传算法从当前的种群中按照适配值函数值由小到大进行排序，并运用选择概率函数对其被选中概率进行由大到小的赋值，最后采取“蒙特卡罗”算法从中选择进入交叉环节的染色体。其二，交叉算子的确定通常采取随机方式并按照预设交叉率函数进行交叉重组，由此产生的新染色体个体将与父代染色体进行比对后，从中选择高适应度的染色体个体进入下一步。其三，染色体变异操作有助于兼顾遗传算法的局部搜索能力优化目标和保持遗传算法种群个体多元化目标，从而避免遗传算法陷入局部最优化算法中。

第六，循环迭代。在经过交叉变异操作后，物流配送中心的订单拣选路径方案染色体种群发生变化，由此产生进一步计算其个体适应度的问题，故算法将从该步转入第四步进行迭代操作，直至触及算法终止条件。算法终止条件可以分为两类：一是适应度评估值函数，即对适应度评估值进行客观评估，当种群中个体触及最优适应度值时，算法即行终止;二是迭代次数限制方法，即对该遗传算法迭代次数的最大值MAXGEN做限定，在达到迭代次数最大值时，算法迭代操作即行终止。

配送中心订单拣选路径优化策略

（一）多订单处理信息系统构建

订单处理过程被视为增强客户企业市场竞争能力的关键业务过程。运用遗传算法有助于提升物流配送中心订单拣选路径优化决策效率，增强物流配送中心订单拣选路径决策的科学性和客观性。但物流配送中心订单拣选操作效能的提升需要以强健的信息系统支撑力的同步完善为基础。若缺乏良好的可同步处理多订单的信息系统的有力支撑，将无谓的耗费订单拣选工作人员的工作积极性，进而导致基于遗传算法的物流配送中心订单拣选路径优化方案缺乏必要的组织力和执行力，难以转化为现实生产力。故物流配送中心应当运用系统动力学原理和建模方法，刻画配送中心的订单拣选与配送能力之间的量化关系，将订单拣选与配送能力之间的匹配关系同步呈现给决策者和仓储管理者，并据此调整配送方式、订单响应时间和目标交货延迟策略。同时，物流配送中心应当建立仓储管理系统（WMS），在与进销存管理软件融合式运用的基础上，有效规范仓库中的订单拣选作业过程，合理配置订单处理优先顺序，提高订单拣选作业效率，增强订单快速响应能力。WMS应当具有批量处理订单和自动化合并订单以满足拼箱运输或合并运输需求的能力。通过批量化处理订单和合并订单操作，物流配送中心可以降低发车频率并严控流通成本，但却需要延长部分订单的处理时间，增加客户企业的等待成本，故物流配送中心应当基于WMS平台加强订单归并处理流程的管控，有效平衡订单处理时间和配送成本之间的关系，实现综合效益最优化目标。

（二）强化订单拣选作业与越库配送系统对接能力

常规的物流配送中心运作流程涉及货物承接（Receiving）、分拣（Sorting）、仓储（Storing）、订单拣选（Retrieving）和装货作业（Shipping）五项职能。其中，订单拣选作业的功能发挥并不具有独立效果，而需要与其它各项职能有机配合，方可确保其功能实现最优化目标，故订单拣选路径的选择应当与后续装货环节有机融合。而越库作业是在物流配送中心各项职能有机配合下可实现较高配送效率的一种装货作业方法，其要求订单拣选与装货作业环节之间无缝对接，以切实压缩整个配送业务流程时间并有效控制配送成本。为增强订单拣选与越库配送系统对接能力，物流配送中心应当选择合适的储存单元（SKU，Storage Keep Unit）作为订单拣选的基本单位。针对待配送货物品项内容繁多的问题，物流配送中心可采取ABC法或二八分类法分类处理待配货物;针对慢流货物，配送中心可以采用合并SKU处理方式，用延长订单处理时间的代价换取降低单位SKU处理成本的利益。越库配送需要供应商增加供货频率，故配送中心需强化与供销双方之间的沟通交流，就订单到达与完成时间和货物数量、质量和体积等关键指标问题，设置专岗负责与供应商事先商定;采购方应当建立供应商淘汰机制，及时淘汰不能达到越库作业要求的订单处理能力的供应商，以保障越库型订单处理流程畅通。