摘要：针对蔬果类商品B2C直销模式拣货包装环节存在的拣货节拍柔性、订单个性化强、配送时间性要求高、需满足装车时间窗和装车顺序等问题，引入JIT（justintime）准时制生产思想，基于流水作业和生产作业调度原理，以“准时拣货、准时装车”为目标，建立考虑装车时间窗、装车链顺序的拣货包装序列优化模型。基于定性定量相结合的思想，以降低搜索空间范围和提高算法计算速度为突破口，引入人工经验设计了以优先规则算法生成初始种群和修订递推式算法求解适应度的混合遗传算法。最后，通过应用实例分析和算法比较证明模型和算法的有效性。结果表明，本文的模型和算法比作业顺序有链优先约束模型和不考虑人工经验的遗传算法，能大大降低拣货包装时间和提早延迟成本，为B2C直销模式下的拣货包装方案生成提供了新手段。
关键词：蔬菜B2C直销；拣货包装序列优化；混合遗传算法；交货期窗口；链优先约束
作者：冯晓春，胡祥培（大连理工大学系统工程研究所，辽宁大连116023）
0引言
近年来，电子商务的迅猛发展已经改变了产业结构，改变了人民的生活，并对我国的经济和社会发展产生重大影响。目前我国已经成为世界头号电子商务大国（2013年电子商务交易突破了十万亿），1号店等大型网上超市的崛起，开辟了电子商务的新领域和新模式，也大大方便了百姓的日常生活。与此同时，蔬菜B2C网上直销模式2010年以来相继在北京、上海等地出现，又开启了我国蔬果类商品B2C电子商务模式的新篇章。然而，电子商务在发展进程中创造一个个奇迹的同时，又给物流配送作业提出了前所未有的挑战。物流配送中心的加工和配送是蔬菜B2C网上直销模式的关键作业环节。为了满足“当日订购当日送达”或“当日订购次日凌晨送达”的配送需求，让客户吃到当天采摘的新鲜蔬菜，在每天订单截止之后，企业要在非常短暂的时间内（约6小时）通过配送中心的最小销售单元包装、按单拣货包装和装车，将订单配送到客户手中。拣货包装作业作为最核心的环节，需在十分短暂的时间内完成大量订单的拣货包装任务。然而，蔬菜较易腐烂，订单个性化强，时间性极强的配送要求，给蔬菜的拣货包装和配送带来重重困难，传统的人工作坊拣货包装模式已不能满足B2C直销模式下的作业要求。因此，拣货包装作业已经成为限制蔬菜网上直销和配送的瓶颈。解决这一难题的一种思路是：引入JIT思想，建立流水作业的拣货包装模式，将拣货包装与物流配送作业相关联，以满足下游装车时间窗和装车顺序，以达到减少蔬菜订单缓存、降低蔬菜腐烂率、提高客户满意度等目的，这就给制定订单的拣货包装作业序列提出新挑战。因此，如何生成拣货包装序列，满足后续的装车配送要求，是目前蔬菜配送中心急切需要解决的难题。
关于拣货序列优化的研究，国内外学者已有大量研究。Klaus以减少拣货穿行时间为目标，对每一批中拣货顺序进行优化，并设计了相应的启发式算法进行求解[1]。Liu基于聚类技术对重力流架插槽的品项成组和客户拣货单顺序进行研究[2]。Van对圆盘传送带的多重拣货顺序进行了优化[3]。Zhang等以存储和检索变量为决策变量，以最小化完成时间为目标，对旋转架S/R系统的拣货顺序进行了研究，并基于对系统特性的分析设计了有局部搜索策略的混合遗传算法[4]。李晓春、钟雪灵、王雄志、王国庆等针对配送中心动态分区拣货系统，通过对按单拣货顺序优化及拣货员所在分区动态分配，使分区间等待时间减少，同时提高拣货效率[5]。李晓春等同样对双旋转货架系统提出了启发式算法以得到最优拣货顺序，并对相关模型及算法进行模拟测试以证明其有效性[6]。李艳茹根据配送中心按单拣货问题特点，以订单客户的满意度为目标，建立数学模型，并设计了相应的遗传算法来求解该问题[7]。综上可知，拣货序列与拣货效率息息相关，满意的拣货序列可以减少拣货人员的行走距离，节约拣货时间，提高拣货作业效率。拣货序列优化又与拣货模式类型密切关联。上述的拣货模式都是特定工业环境下的拣货模式，并不适用于蔬菜拣货。若将JIT的思想引入拣货包装作业，形成流水作业的拣货包装模式，其布局如图1。由图可知，蔬菜的拣货和包装在同一条流水线上，拣货包装同序，因而本文是对蔬菜拣货包装序列优化进行研究。可将每条拣货包装线看作平行机，将拣货任务看作工序，考虑装车时间窗和装车顺序的蔬菜拣货包装序列优化可以看作是同时有交货期窗口和链优先约束的平行机调度问题。因此，本文研究的蔬果网上直销的流水拣货包装作业序列问题可以归结为有交货期窗口和链优先约束的平行机生产调度问题。下面将从交货期窗口和链优先约束两个方面对平行机生产调度问题进行综述。
关于有链优先约束的生产调度问题，代表性的学术成果有：Chu研究了不仅有链优先约束，而且同一链中工序有差异时间窗的单机问题[8]。Brucker等对有链优先约束的相同工序的两同质机的调度问题进行了研究。Yuan等[10]对有链约束的相同长度的工序在两个机器上的调度问题提出了在线算法[9]。Agnetis等对有链约束的平行机问题进行了证明，对最小化总的完工时间问题和最小化延迟工序数量问题给出了有效的算法[11]。关于有交货期窗口的生产调度问题，代表性的学术成果有：Behnamian等对有时间窗约束和序列相关的准备时间的平行机问题进行了研究，提出了三个元启发式算法。Yin等[13]对有公共交货期约束的单机批送货问题进行了研究[12]。Chen对有公共时间窗的机器调度问题进行建模，并改进了分枝定界方法用于求解该问题[14]。Mosheiov等对有共同时间窗约束的机器调度问题中可用多项式求解的算例进行了研究[15]。Gerstl等对有限制的和无限制的时间窗的同质平行机调度问题的最优解的特性进行了数学证明[16]。王莉等提出了求解不同交货期窗口的并行机调度问题的混合遗传算法[17]。赵传立等研究任务间具有链约束的平行机调度问题，对于一般情况给出了最优解的必要条件，对于特殊情况给出了问题的最优解算法[18]。上述基于时间窗约束或基于链优先约束的机器生产调度相关研究，国内外学者已经取得了丰硕的成果，为求解这一NP难问题进行有益探索，丰富了机器生产调度理论，对实际应用有很大的借鉴意义。但是蔬菜B2C直销模式下的拣货包装作业问题由于具有订单量大、个性化强，且需考虑下游装车需求等特点，使得上述从数学模型及其启发式算法方面得到的相关成果难以适用本文的拣货包装序列优化问题，其原因是本文的拣货包装序列优化问题需要同时考虑装车时间窗和装车顺序这两种约束条件，且拣货包装流水线的作业节拍是柔性的，这些特点使得蔬果的拣货包装序列优化更加复杂。另外，本文欲研究的问题与链优先约束的机器生产调度问题的区别在于，本文需满足的装车顺序是拣货包装环节下游的装车链优先顺序，而目前学术上的链优先约束是当前生产加工时间需遵循某种优先约束，前者更复杂、解空间更大。因此，B2C直销模式下的蔬果拣货包装序列优化问题有待进一步的研究。
width=198.2，height=91.35
图1蔬菜拣货模式布局图
综上所述，本文基于前人的研究基础，首先分析蔬果类商品拣货作业的特点，引入JIT生产作业原理，建立满足装车时间窗和装车顺序的拣货包装序列优化模型；针对问题的复杂性，基于定性定量相结合的思想，以降低搜索空间范围和提高算法计算速度为突破口，引入人工经验设计混合遗传算法对模型进行求解；通过对不同规模算例的数值实验分析和算法比较，以证明该算法的有效性。本文的研究为解决B2C直销模式下蔬果拣货包装作业问题提供了科学有效的模型和算法，并丰富了现有的机器生产调度理论，具有重要的理论意义和实际意义。
1问题描述
在蔬果类商品网上直销近5年的发展进程中，实践证明蔬菜网上直销的物流配送成本以及顾客签收货品模式已经成为影响“农—宅”配送作业的两大关键环节，成为影响蔬果商品B2C电子商务模式生存和发展的关键要素。对于蔬菜配送的顾客签收货品模式，当前上下班高峰时段都市交通高度拥堵的现状以及居民一日三餐对蔬菜的需求，促使蔬菜的物流配送必须在道路较为通畅的凌晨时段实施，这就出现“为熟睡居民送菜”的扰民问题。为了解决送货时间与顾客签收货品时间不匹配的难题，作者所在团队与北京昊宇神鹰农业科技有限公司合作，通过建立社区蔬菜智能配送柜，实现了“客户用手机上网定菜→物流配送蔬菜到小区楼下→送货员将蔬菜放入社区蔬菜智能配送柜→向用户手机发送短信通知开箱密码”这一从农场到家庭的物流配送过程，消除了蔬菜公司早晨送菜到家产生的扰民烦恼，解决了蔬果类商品电子商务“最后一公里”的难题，并使我国蔬果类商品的销售进入了移动电子商务的新时代。
B2C直销模式下的蔬菜配送中心作业流程如图2所示，白天，市民在网上下单；下午5点，销售网站将当天的订单汇总并进行预处理，将需采摘的品种和数量信息传送给蔬菜大棚基地；下午6点，大棚将当天所需的所有蔬菜运输到配送中心；在配送中心，先对蔬菜进行最小销售单元包装（最小销售单元通常为一斤左右），然后按照订单进行拣货包装，最后是装车配送，运输到每个社区的智能配送柜；凌晨5点，完成所有配送任务。拣货包装作业一直是整个配送中心作业系统的核心。由于蔬菜易腐性，日订单量大，订单多品种、小批量的特点，本文引入JIT的作业思想，提出基于JIT的拣货包装作业模式，其物流与信息流如图3所示。
width=211.9，height=25.15
图2蔬菜配送中心作业流程
width=180.2，height=58
图3基于JIT拣货包装作业的物流与信息流
由图3可知，基于JIT作业思想的拣货包装模式，拣货包装和配送之间联系紧密，拣货包装序列（方案）需满足装车配送计划，降低中间库存，避免了再次按照装车顺序进行排序等环节，减少蔬菜腐败，提高客户满意度。
由于每天有上千的订单，同时调度每一个订单将导致编码困难，计算时间长，甚至得不到计算结果。为了减少调度单位，降低求解复杂性，基于同一小区订单一同装车、一同配送这一现状，本文将同一小区的订单聚在一起，看作一个整体。对拣货包装序列优化就转变为对配送小区之间拣货包装顺序优化。
由图1可知，基于JIT作业思想的拣货包装流水线是柔性节拍，订单的拣货包装时间由订单所包含的最小销售单元数量和工人的拣货数量程度有关。因此，本文将拣货包装时间定义如下：
width=68.15，height=15.8（1）
其中，width=13，height=15.65为第v条拣货包装线的拣货人员效率值，width=13.95，height=15.8为第j个小区中需拣货包装的最小销售单元数量；该函数是分别关于width=13，height=15.65的减函数和width=13.95，height=15.8的增函数。
基于JIT的蔬菜配送中心拣货包装作业，需要满足装车时间窗要求，同时希望拣货包装成本尽可能的少。拣货包装成本与所有拣货流水线上最大拣货包装时间的长短呈正比关系，为了平衡任务分配，充分利用拣货资源，本文的目标之一是最小化各拣货线中的最大拣货包装时间。为了使拣货任务尽可能地在时间窗内完成，目标之二是最小化提前和超出时间窗的时间成本，若未超出时间窗，则这部分的成本为0。因此，目标函数的第一项是最大拣货包装时间，第二项是订单提早时间窗完成拣货的成本和晚于时间窗完成拣货的成本之和。目标函数总体是对最大拣货包装时间成本与提早和延迟时间窗成本总和求最小。
width=226.4，height=118.8
图4B2C直销模式下的蔬菜拣货事例图
因此，本文所研究的问题可界定为：假设配送车辆数量不限，某一配送中心需要对J辆车的配送任务进行拣货包装装车，每辆车都包含若干个需要配送的小区，每小区的订单容量都小于配送车辆的容量。根据配送小区的先后顺序，每辆车都遵循某一固定装车顺序。蔬菜配送中心有M（M<J）条基于电子看板的蔬菜拣货包装线，每条蔬菜拣货包装线都包含所需的所有商品种类，即任何一小区任务都可在任一拣货包装线上完成，且最多只能在一条拣货包装线上拣货。由于雇佣的拣货人员的文化程度和熟练程度不同，每条拣货包装线上的作业效率存在差异。当拣货人员对某一小区的任务进行拣货包装时，是对该小区的订单逐一进行拣货，小区内部的订单不存在拣货顺序。配送中心需要根据装车计划制定拣货包装序列，使得拣货包装同时既要满足车辆的装车时间窗，又要满足装车顺序，以避免按照装车计划再次排序的多余作业环节。如图4所示。
2模型构建
2.1基本假设
（1）每个小区最多只能在一条拣货包装线上作业；
（2）一条拣货包装线在一个时间内只能作业一个小区的订单；
（3）同一小区内的订单不能分割在多条拣货包装线上；
（4）不同小区拣货包装任务可在不同拣货包装线上进行作业；
（5）当前小区的拣货包装完工时间需大于紧前小区的拣货包装完工时间；
（6）一旦一个小区的拣货包装作业开始，就必须连续完成，不能中断；
（7）拣货包装线与拣货包装线之间是独立的；
（8）小区在不同拣货包装线上的拣货包装时间由所包含的最小销售单元数量和该流水线的人员效率有关；
（9）拣货包装流水线不会发生故障中断且总是可用；
（10）装车时间忽略不计；
（11）配送车辆的装车时间窗和装车顺序已知。
2.2参数及变量表示
J：所需配送的小区集，width=51.6，height=14.05；
Z：配送车的数量，width=51.6，height=14.05；
M：拣货包装流水线集，width=56.1，height=14.05；
width=8.1，height=13.1：小区占用每个流水线位置的最大数量width=46.75，height=13.1，保证流水线最大的利用率，使得所有拣货包装流水线都得到利用；
R：位置集，width=48.85，height=14.05；
width=16.65，height=17.05：小区j在拣货包装流水线v上的拣货包装时间；
width=37.1，height=13.75，width=21.5，height=10.35：配送车辆width=9，height=9.8的装车时间窗；
width=11.1，height=17.05：小区j的紧前小区；
width=10.15，height=13：一个常数；
该模型的决策变量如下：
width=18.1，height=17.05：当小区j在拣货包装流水线v上的r位置上生产时其值为1，否则为0；
width=15.3，height=16：车辆i中小区j的拣货完工时间；
width=14.65，height=14.55：流水线v的终止拣货包装时间；
width=10，height=11.8：拣货成本的权重值；
width=7.8，height=9.8：提早延迟成本的权重值。
2.3数学模型构建
该问题可以描述为如下的数学模型：
Minwidth=276.9，height=28.9（2）
St.width=82.5，height=29.8（3）
width=111.65，height=28.9（4）
width=186，height=28.9（5）
width=179，height=30.35（6）
width=135.4，height=26.8（7）
width=102.05，height=16.2（8）
width=113.35，height=14.8（9）
width=186.4，height=16（10）
目标函数（2）是拣货包装成本与提前延期成本之和最小；约束（3）保证每个小区都能分配到某个拣货包装流水线的某个位置上；（4）保证每个小区最多分配到某个拣货包装流水线的一个位置上；（5）保证只有当拣货包装流水线的占用位置被释放，才能再分配小区；（6）保证某拣货包装流水线的加工子序列中一个小区的完工时间至少大于前一小区的完工时间；（7）保证一个小区的拣货包装完工时间不少于其拣货包装时间；（8）保证链优先约束；（9）定义每条拣货包装线上终止拣货包装时间等于在该流水线上任务最大拣货包装完工时间；（10）决策变量的取值范围。
当机器数大于2时，单独考虑交货期和链优先约束其中一项的机器数量两个以上的调度问题都是NP-难问题[10][14]，当同时考虑两类约束时，其复杂性更大。通过对计算复杂性分析，本文问题的复杂性是width=28.35，height=13.1，m为拣货包装线条数，n为小区数。同时，本文的模型具有约束多样性，当配送小区数很大时，解空间很大。若用精确算法在短时间内难以求出最优解。本文求解的B2C直销模式下蔬菜配送中心拣货包装序列问题，从订单截止到蔬菜采摘—拣货包装—配送只有短短的12小时，从订单截止到生成拣货包装方案需要在1小时之内最好是在线实时生成蔬菜的拣货包装方案。因此，对求解上述模型的时间要求较高，若求解时间很长，无法满足实际快速的作业计划生成。由于启发式算法尽可能挖掘利用了调度问题本身的启发式信息，能够找到次优或较好的作业排序方案，并有计算量小、计算速度快的特点，实际调度中对时间性要求强，传统精确算法难以在有限时间求解，因此文本采用启发式算法进行求解。在过去的几十年里，遗传算法在求解组合优化问题方面获得了极大的关注和研究[19]。因此，本文以此为基础开展算法的改进工作，提出基于优先规则的混合遗传算法。
3基于优先规则的混合遗传算法
在现实中，当某工序的交货期很紧迫时，人们会优先安排该工序进行生产；另外，为了充分利用现有的机器资源，人们会尽可能平衡机器的使用效率，这样可以同时减少所有工序的最大完工时间。基于这些人工经验，本文开发了基于优先规则的启发式算法（PRHA，PriorityRule-basedHeuristicAlgorithm），用于初始种群的生成，一方面产生更接近现实的可行解，避免盲目搜索，另一方面减少整个遗传算法求解时间。为了快速地求解适应度，基于工人从前往后推的常规计算思维，本文设计了修订递推式算法（RRA，RevisedRecursiveAlgorithm）。将PRHA、RRA与遗传算法融合，从而得到基于优先规则的混合遗传算法。其算法流程如图5所示。
该混合遗传算法的主要步骤如下：
步骤1：编码
本文采用实数编码。设有n个小区需要分配到m条拣货包装流水线上，染色体用一个长为n+m的实数链进行表示。1到n的实数代表n个工序，m个带*的基因代表拣货包装流水线。因此，每条染色体可以划分成m个子染色体，每条子染色体表示分配到一个机器上的加工工序顺序。以9个小区4条拣货包装线为例，染色体的长度为13，设(7*3915*2862*134*4)表示一个染色体，则第7个小区被分配到第3条拣货包装线上，9、1、5这三个小区被分配到第2条拣货包装线上，且以9-1-5的顺序进行拣货包装，以此类推。如图6所示。
width=170.1，height=247.95
图5基于优先规则混合遗传算法流程图
width=198.2，height=49.1
图6染色体编码事例
步骤2：初始种群的生成
在本混合遗传算法中，初始种群的生成来自两个子种群，其中一个子种群通过PRHA生成，另一个子种群是将所有的小区在满足约束的情况下随机地分配到拣货包装线上，以保持种群的多样性。
在现实中，当某小区的装车时间窗很紧迫时，人们会优先安排该小区进行拣货包装；另外，为了充分利用现有的拣货包装流水线资源，人们会尽可能平衡拣货包装流水线之间的使用效率，这样可以同时减少所有拣货包装任务的最大完工时间。基于这一现实加工中的人工经验，本文开发了基于优先规则的启发式算法用于初始种群的生成。PRHA在每次迭代中，在满足优先约束的条件下选择优先小区和优先拣货包装线，优先小区基于装车的紧迫性进行选择，同时保持已调度小区的开始时间不变，为了平衡拣货包装流水线的使用效率，最先完成已分配小区的流水线优先选为下次作业的拣货包装线。小区的拣货包装紧迫性与装车时间窗的开始时间width=12，height=12.8和装车时间窗的跨度width=34.7，height=12.8有关，且是它们的减函数。本文将工序的紧迫性定义如下：
width=89.9，height=14.25（11）
width=14.65，height=14.1分别是width=12，height=12.8和width=34.7，height=12.8的减函数。
本文给出了PRHA的伪代码如表1所示。
表1基于优先规则的启发式算法伪代码
表1（续）基于优先规则的启发式算法伪代码
表2修订递推式算法伪代码
如表1所示，步骤1是初始变量，当迭代次数没有达到小区总数时，进入步骤2；2.1是求解第u次迭代时最小的拣货包装流水线释放时间和调度时间点t，2.2和2.3是求解已开始加工和完工小区集width=11，height=12.5；2.4表示选择紧迫性最大的那个小区作为优先小区；2.5是计算优先小区的紧前小区的完工时间；2.6到2.7是根据能最早完成已分配小区的流水线作为优先流水线，2.8到3是更新相关变量值。
该算法的目的是一方面产生更接近现实的可行解，避免盲目搜索；另一方面减少整个遗传算法求解时间。
步骤3：适应度求解
该算法的伪代码如表2所示。该算法总体思路是对每条流水线上的小区，由前一小区的完工时间，在满足链优先约束的前提下，计算当前完成小区的时间，进而得出适应度ff。该算法与文献[19]中的修订递归式算法相比，避免了基因的随机选择。
步骤4：选择
本文采用的选择算子是“保留精英的轮盘赌策略”。轮盘赌选择表现比较稳定，但是却可能失去上一代最佳个体，所以本文在轮盘赌策略中引入简单精英策略（即复制最佳个体直接进入新一代种群），用来防止通过遗传操作而导致种群中的最优个体消失。
步骤5：交叉
为了防止交叉过程中对重复的基因进行修复，本文的交叉策略采用文献[19]。其步骤如下：
（1）从父种群的选取的两个染色体，命名为父染色体1和父染色体2；
（2）随机生成一个n+m的字符串，其值为0或1；
（3）字符串首先匹配父染色体1，保留字符串对应位置值为1的基因且位置不变，保留为选择1；
（4）从父染色体2中提出选择1中基因，剩下的基因命名为选择2；
（5）从选择2填补选择1，生成新的子染色体；
图7为交叉事例说明。
步骤6：变异
本文采用的是交换变异算子，交换变异根据给定的变异概率选取染色体，随机对染色体中的两个基因进行交换。该变异机理是随机选取染色体中不同子染色体的两个基因进行交换。图8是变异的说明事例。
width=198.1，height=105.55
图7交叉算子事例
width=198.5，height=63.2
图8变异算子事例
交叉和变异会使得染色体不满足链优先约束，本文采用文献[20]的修补策略进行调整。
步骤7：终止条件
本文的终止条件有两个：（1）当前的迭代次数超过事先给定的最大迭代次数；（2）在最大迭代次数范围内，当某迭代次数的种群的最小适应度值和平均适应度值相差小于给定的可接受值时。其中，平均值的定义如下：
width=116.8，height=22.6。
4应用实例
作者及其研究团队成员2010年开始，与北京昊宇神鹰农业科技有限公司合作在北京及河北省廊坊市开展了蔬菜B2C网上直销的示范工程建设，已取得了显著的社会效益和经济效益，中央电视台进行了专题报道，开启了我国蔬果类商品B2C电子商务模式的新篇章。该公司的蔬菜加工配送中心坐落于廊坊境内的蔬菜生产基地，毗邻北京城郊，主要服务于北京的相关小区。公司每日下午5点截止当日订单，由于北京早晚高峰期交通车辆行驶拥堵，车辆每日配送时间为凌晨。在每日下午5点至次日凌晨公司需完成采摘、标准销售单元包装、订单分拣与装车配送等一系列工作。为提高配送效率，先对所面对的数十个小区进行地区上的聚类，生成配送顺序和装车时间窗，基于“先上（车）后下（车）”原理，得到装车顺序。在拣货包装环节，拣货包装方案需满足后续的配送需求。
公司现有蔬菜种类40种，日处理订单约4000个，其中一个订单平均重量4公斤、包含8种蔬菜（日采摘蔬菜近16000公斤，标准销售单元32000个）。为了贴近实际同时有利于数值实验，本文设蔬菜种类为30种，每个订单所包含的蔬菜种类在1-10之间生成且服从泊松分布；每种蔬菜对应的最小销售单元份数在1-10之间，所有蔬菜对应的最小销售单元为1斤左右，订单的平均重量为5公斤。每一小区的订单数在30-80之间随机生成。配送车的容量为200个订单。装车时间窗的两个时间点分别在[100-170]和[200-300]之间随机生成。
拣货人员的熟练程度和认真态度决定拣货包装效率，拣货人员效率越低，则拣货包装时间越长，每个小区包含的最小销售单元越多，则拣货包装时间越长，因此，拣货包装时间定义如下：
width=55.3，height=16.4（12）
其中，width=13，height=14.55为第v条流水线的效率值（大于0），width=15.4，height=16.2为第j个小区包含的最小销售单元数量，T为每拣选一个最小销售单元的平均时间。根据对北京昊宇公司配送中心拣货包装模式的跟踪统计，得出拣货人员每拣一个最小销售单元的平均时间T：width=29.05，height=11.6。由于人的拣货效率很难实际测量，为了便于进行数值实验，本文的效率E值是在0-1之间随机生成，不同拣货线的E值不同。更进一步，目标函数中设置各成本的权值均设置为1，这是因为，本文提出的基于优先规则的启发式算法，能尽可能的利用流水线进行拣货，对同一算例的拣货包装成本差异不是很大，因而拣货包装成本和提早延迟成本之间的冲突并不明显。文章最后会对各成本的权重进行灵敏度分析，以验证本文的初期分析的正确性。
表3是本文混合遗传算法（以下图表中简称HGA）的相关参数列表。同时，算例采用的紧迫性函数如下：
width=108.85，height=16.2（13）
表3混合遗传算法的相关参数
算例分析是在Intel(R)Core(TM)DueCPU2.10GHz机器上进行，HGA和GA都是采用matlab2012b进行编写，同时算例在windows732位操作系统下进行。
本文欲通过数值实验对以下问题进行探讨：
（1）拣货包装完成时间有链优先约束和拣货包装时间有链优先约束有何区别？
（2）本文混合遗传算法的有效性如何？
4.1完成时间有链优先约束和加工时间有链优先约束的对比分析
本文以J=15，M=5（J为配送小区数，M为流水线条数）为例进行详细分析。设共需要3辆车配送，即有3条装车顺序，其相关数据如表4所示，2-4-7-10-13小区以此顺序装车，且装车时间窗为[130-210]，3-5-8-11-14小区以此顺序装车，且装车时间窗为[150-210]，以此类推。
表4J=15、M=5事例的相关数据
本文的模型和算法是基于拣货包装完工时间服从装车顺序（以下图表中简称为FTCP，FinishTimebasedonChainPrecedence），而企业一般所采用的是拣货包装时间服从链优先约束（以下图标中简称PTCP，Pick-packingTimebasedonChainPrecedence），不考虑装车顺序之间小区作业时间长短关系。因此，本文将对两者进行比较分析。将算法程序运行50次，剔除异常结果，取其中总成本最低的解进行比较。表5是本文方法与加工顺序服从链优先约束的求解比较。
由表5可以看出，本文的方法相比PTCP，在拣货包装成本、提早延迟成本以及总成本上都有很大的改进。具体来说，本文得到的拣货包装序列，同一装车顺序上的拣货包装任务，紧后任务可以在紧前任务拣货包装同时，在其他流水线上进行作业，只需晚于紧前任务完成即可。而对于PTCP，当紧前任务还未完成时，紧后拣货任务都不能在任何流水线上进行拣货包装，这就导致拣货包装时间极大地拉长，从而导致拣货包装成本和提早延迟成本增大。
表5FTCP与PTCP的计算结果比较
图9和图10分别给出了本文方法与PTCP方法结果甘特图，纵轴表示流水线条数，横轴表示拣货包装时间，矩形条表示小区任务。从图对比可知，本文的方法得到的拣货包装序列比PTCP方法得到的结果，流水线作业分配能更均衡些，而PTCP得到的结果，拣货人员有时很忙，有时空闲，即存在很大的“闲忙不均”现象；其次，PTCP会尽可能的将任务安排在拣货包装时间相对较小的拣货线上，而本文的方法会权衡整个装车顺序的约束来安排拣货顺序，不一定将拣货任务安排在对应的拣货时间较小的拣货线上；另外，本文方法得到的结果会尽可能安排装车更紧迫的任务，甚至多条流水线线同时对一辆车的配送任务进行拣货，比如一开始所有拣货线都对链3的任务进行作业，而PTCP方法得到的结果在这一方面并不敏感。总之，本文的方法相比PTCP方法，能更好地均衡作业频率，降低资源浪费，减少作业中间的空闲，避免装车过程中产生更多的等待，导致蔬菜新鲜度降低，从而影响客户的满意度。
width=141.65，height=93.55
图9FTCP得到的拣货包装序列甘特图
width=141.6，height=99
图10PTCP得到的拣货包装序列甘特图
4.2灵敏度分析
如在引言所说，目前国内外大部分的相关文献都是从数学分析角度，证明特殊算例的复杂性和问题性质，并提出在多项式内可解的启发式算法。少部分做模型算法的文献，或考虑交货期，或考虑加工有链优先约束，本文是同时考虑装车时间窗和装车顺序的拣货包装序列优化研究，因而与本文的研究内容不同。由于本文基于人工经验设计了基于优先规则的启发式算法，将本文混合遗传算法（HGA）与常规遗传算法（GA）进行比较，以验证本文设计的启发式算法的可行性以及对参数灵敏度的反应。本部分主要分析小区数变化、拣货线条数变化、以及紧迫性变化时，本文方法与常规遗传算法的可行性，最后也对各目标的权值变化进行灵敏度分析。
首先是小区数量变化结果和比较分析，分为较小规模的算例和较大规模算例两种，结果如表6所示。
表6拣货包装线相同、小区数量变化所得的结果比较
表7小区数相同、拣货包装线数量变化所得的结果比较
由此看出，当小区数是9的时候，本文产生的拣货包装成本和提早延迟成本虽比GA较小但是相差不是很大；随着小区数的增加，本文产生的提早延迟成本的减少幅度呈增加趋势，但是拣货包装成本的减少幅度差异不大，总成本的减少幅度总体呈增加趋势。计算时间方面，随着问题规模的增加，计算时间减少的幅度随着问题规模的增大呈减少趋势。证明本文算法较常规遗传算法相比，在小区数量较少时，效果不是很突出，但是随着小区数量的增加，无论在提早延迟成本上，还是在计算时间上，都比常规遗传算法有很大的提升。本文的算法在求解较大规模的拣货包装序列调度上相比常规算法更有优势。
其次是拣货包装线条数变化结果和比较分析，如表7所示。
由表7可以看出，当小区数不变时，随着拣货包装线条数的增加，拣货包装成本和提早延迟成本会相对降低，即当任务量较大时，企业可以通过增加流水线条数来降低拣货包装成本和提早延迟成本，但是这会额外带来人工设备成本，所以企业需要权衡各方面利益。计算时间方面，随着问题规模的增加，计算时间减少的幅度趋势不是很明显。图11给出了HGA算法和GA求解15台机器和48个工序的收敛性情况，从图对比可以看出，HGA比GA能更快达到收敛，且适应度值更优。
width=142.2，height=92.6
图11收敛性情况对比
width=148.5，height=100.4
图12第一时间点相同、时间窗跨度规律变化情形下算例结果
通过对上述结果总结可知，本文设计的启发式算法，结合人工经验，一方面能产生更接近现实的可行解，避免盲目搜索，尽快达到收敛，另一方面减少整个遗传算法求解时间。
再者，本文对紧迫性进行了灵敏度分析。灵敏度分析是以3条拣货包装线、9个配送小区为例。表8和图12分别是装车时间窗跨度规律变化，第一时间点相同情形下各小区的时间窗算例及其求解结果，表9和图13分别是第一时间点不同，装车时间窗跨度相同情形下各小区的时间窗算例及其求解结果，表10和图14分别是装车时间窗相同、紧迫性参数a规律变化情形下各小区的时间窗a值算例及其求解结果。从三图可以看出，在第一时间点相同的情况下，HGA优先安排了时间窗跨度小的2号小区和4号小区，接着是7号小区，即HGA能优先安排时间窗跨度小的小区；在时间窗跨度相同的情况下，HGA优先安排了第一时间点近的2号、4号和7号小区，即HGA能优先安排第一时间点近的小区进行拣货包装；当时间窗相同时，HGA能优先安排a较小的小区（即较紧迫的小区），如2号、4号和7号小区。表明本文的算法能优先响应紧迫性较高的拣货包装需求，比如实际中的重点客户或者需提早拣货包装的客户订单。企业可对客户订单的重要性程度进行分类以确定订单的紧迫性顺序，优先满足特殊客户的订单拣货包装需求。
表8第一时间点相同，时间窗跨度规律变化情形下算例情况
表9时间窗跨度相同，第一时间点不同情形下算例情况
表10时间窗相同、紧迫性参数a规律变化情形下算例情况
width=141.65，height=96.4
图13时间窗跨度相同，第一时间点不同情形下算例结果
width=141.6，height=92.45
图14时间窗相同、紧迫性参数a规律变化情形下算例结果
width=170，height=97
图15权值比较分析
上述的算例，都是基于拣货包装成本和提早延迟成本权值都为1的结果，文章最后对两个成本之间的均衡关系进行研究。如图15所示，横坐标为提早延迟成本的权值变化，两成本的权值之和为1，纵坐标为拣货包装成本、提早延迟成本以及总成本的相对值变化。有图可知，将提早延迟成本的权值从0.1增至0.5，可以看到拣货包装成本和总成本没有较大幅度的增加。当提早延迟成本的权值超过0.5，提早延迟成本相对略有增加且幅度不大，总成本也相对略有增加且幅度不大，但拣货包装成本变化不大。由此看出，拣货包装成本和提早延迟成本之间的冲突不大，这是因为本文提出的基于优先规则的启发式算法在每次的计算中都尽可能充分利用拣货流水线资源，以减少流水线空闲，从而拣货包装成本相对变化不大；当提早延迟成本权值超过0.5，该成本在总成本中的占有比例增大，从而导致总成本的相对增大。
综上数值实验分析结果，当拣货包装采用流水作业模式时，首先需要考虑下游装车的时间窗和装车顺序，满足下游作业需求，保证拣货包装装车配送作业能够顺利进行，而不至于因中间环节断裂导致整个流水作业被停滞，同时使拣货包装成本尽可能的减少。拣货包装序列不应该局限于装车顺序，拣货包装完成时间只需满足装车顺序即可，这样可以减少作业中间的空闲时间，节约拣货包装时间，使拣货包装作业更加均衡。拣货包装作业中结合人工经验，这种定性定量相结合的方式，能够使生成的解尽可能的接近现实，降低运算时间，尽快达到收敛。考虑紧迫性，能够及时处理拣货包装中的特殊客户，响应不同类型客户的拣货包装需求。
5结论
本文基于JIT和流水作业思想对B2C直销模式下考虑下游装车顺序和装车时间窗的蔬菜拣货包装序列优化问题进行建模，设计启发式算法进行求解，最后通过算例验证，将得到的算例结果与加工顺序有链优先顺序进行比较，同时将本文算法与没有考虑优先规则的常规遗传算法进行比较。结果表明本文模型和算法比加工顺序有链优先顺序以及没有考虑优先规则的遗传算法在蔬菜拣货包装序列的拣货包装成本和提早延迟成本方面都有很明显的改善。
本文的模型和算法为求解B2C直销模式下蔬菜流水拣货包装作业难题提供了新的手段，它合理衔接了蔬菜的拣货包装和装车配送作业，并大大降低了作业过程中的拣货包装时间和提早延迟成本，减少蔬菜的腐败率，提高了客户的满意度，为企业大规模的拣货包装配送奠定基础，具有重要的实际意义；此外，本文将拣货包装流水作业抽象为机器调度问题，针对考虑装车时间窗和装车顺序的特点，建立了考虑拣货包装完工时间有链先后约束和装车时间窗的拣货包装序列优化模型，比现有的加工顺序有链优先约束问题，能减少拣货包装过程中的空闲时间，平衡作业效率；同时，本文基于定性定量相结合的思想，将人工经验加入到遗传算法中，设计了混合遗传算法，该算法能在较短时间内得到优化调度方案，且对求解大规模拣货包装调度问题极具优势，有助于丰富生产调度相关理论。
未来的研究将探索：配送车辆有容量和数量限制，以及考虑配送、装车以及拣货包装的联合优化调度等问题。
