1 引言 当前移动互联网、手机APP等技术手段使得电子商务购买方式越来越便捷，同时消费者对商品到达的时效性要求越来越高。然而客户众多、位置分散，且每单需求量小、品类差异性大等新特征，使得B2C电子商务的订单拣选和配送难度增大。对于商家来说，能否在顾客下单后协调好拣选和配送环节，在最短的时间内，以较低的成本将商品从货架上拣出、打包后配送到顾客手中，已成为电子商务物流管理中亟待解决的问题。当前B2C电子商务企业(如天猫、京东、亚马逊等)开始通过自建物流提高拣选和配送效率，但订单从进入商家平台到送达顾客手中被分割成订单处理和配送两个阶段：订单处理部门依据订单到达的时间、包含的商品及其仓储信息等制定合理的拣选任务，其优化目标通常是订单完成时间最小化[1]；配送部门依据订单数量、顾客分布、期望最迟收货时间等优化配送线路，以最小化行驶距离或顾客等待时间[2-3]。由于配送过程的优化受到订单拣选顺序、拣选完成时间等拣选阶段因素的影响，很难实现整体效率最优。本文综合考虑拣选和配送系统优化调度的特点，尝试构建拣选与配送联合调度模型，并制定快速求解方案，以实现在最短的时间内拣选配送完所有顾客订单。关键决策问题包括：1)如何进行合理的订单分批优化，确定订单所属拣选批次；2)如何安排顾客所属配送车辆以及每辆车的行驶线路；3)如何安排不同拣选批次作业顺序及不同车辆开始配送时间。 订单拣选与配送联合调度问题(Integrated Order Picking and Delivery Scheduling，IOPDS)可抽象为生产与配送联合调度问题(Integrated Production and Delivery Scheduling，IPDS)，包括生产调度和配送调度两阶段：生产调度解决每个订单何时被处理及所需处理时间等问题；配送阶段则解决每个订单何时被配送、所需配送车辆数、车辆行驶路径及时间等。Chen Zhilong[4]构建了IPDS问题的通用表达形式：α|β|π|δ|γ，其中α表示生产配置集合，包括单一、并行、流水等生产形式；β表示订单约束集合，包括订单到达时间、处理时间、期望收货时间等；π表示配送参数，包括配送车辆参数、配送方式等；δ表示顾客数量，包括单一顾客和多个顾客等；γ表示优化目标，包括顾客服务质量、成本、收益等。当前学者对IPDS问题的研究多是在不同的α、β、π、δ、γ参数条件下建立生产与配送联合优化模型。生产调度包括单机/并行机条件下的直接/批量生产调度优化。Geismar等[5]构建单一有限生命周期产品的单机直接生产模式下的IPDS模型；Low等[6-7]、李凯等[8]构建考虑配送时间窗的单机多产品多车辆IPDS模型；Chen Zhilong等[9]分别构建了多产品在单一和平行生产线上的IPDS模型；裴军等[10]、马士华和吕飞[11]、马士华和王青青[12]建立采取批量生产分批配送模式的生产与配送协同模型；冯鑫等[13]探讨了单机批量加工的生产配送调度模型；配送调度优化则包含直接配送、分批配送、配送路径优化及带时间窗的配送等方面。Li Kai等[14]、李昆鹏和马士华[15]、王建华等[16]考虑了配送时间固定的直接配送模式；Cheng Bayi等[17]研究了考虑单一顾客的分批配送调度；Gao Su等[18]、Amstrong等[19]、Low等[6-7]、李凯等[8]研究了更为复杂的路径优化IPDS问题；Low等[20-21]构建了带配送时间窗的生产与配送联合调度问题；冯鑫和郑斐峰[22]对比分析了直接配送与批量配送对生产配送协同调度效果的作用。模型的优化目标有客户最大收货时间最小化[5-6]，车辆固定成本、配送成本及惩罚成本总和最小化[7]，制造商惩罚成本与配送成本总和最小化[8]，最大延迟时间与配送车辆数之间加权和的最小化[23]等。由于IPDS属于NP难问题[7]，当前的求解算法多为启发式算法，如基于遗传算法和Gilmore-Gomory算法的两阶段启发式算法[5]、两阶段自适应遗传算法[6-7]、2-近似算法[24]、禁忌搜索算法[25]、模拟退火算法[8]等。 当前IPDS的研究已较丰富，但缺少订单拣选与配送联合调度问题(IOPDS)的相关研究。IOPDS与IPDS存在一定的差异性，集中表现为：1)订单作业方式与加工时间更复杂。电子商务环境下订单具有小批量、高频次等特征，有必要采用订单分批策略提高拣选效率[26]。传统IPDS批量加工时间通常为批次订单加工时间之和、批次订单中最大加工时间或按某一固定加工速率计算，但IOPDS拣选时间更为复杂，由订单分批情况[26-27]、拣选路径策略[28]、货位分布[29]等多因素决定，属于NP-hard问题。2)考虑配送路径的批量生产批量配送方式。IPDS中批量生产批量配送问题多假设生产容量与配送容量相同，即批量生产完后立即由同一车辆配送，但IOPDS中拣选设备容量与车辆容量不同，即生产批次与配送批次并不一一对应，且同时考虑配送线路优化，增加模型的复杂性和求解的难度。3)最小化订单履行时间为优化目标。网购顾客更注重配送时效性，应结合订单分批优化、车辆路径优化等方法，合理制定拣选和配送联合调度方案，使得顾客尽早收到订购商品。 综上所述，本文以最小化订单履行时间为目标，研究考虑配送路径的批量生产批量配送的订单拣选与配送联合调度问题；构建IOPDS模型，并证明模型的复杂性；采用拣选与配送联合调度三阶段算法求解模型：首先采用遗传算法确定配送线路，再针对不同配送线路制定订单分批拣选任务，最后调整拣选任务与配送线路顺序；通过数据实验，从履行时间、平均履行时间、车辆等待时间等方面，对三阶段算法与传统算法完成结果进行对比分析，结果证明模型和算法的有效性，为B2C企业提高物流服务质量提供决策支持。 2 问题及模型 2.1 问题描述 本文研究B2C电子商务环境下订单拣选配送联合调度问题，由一个配送中心和多个顾客构成，如图1所示。研究对象为第一天晚上到第二天白天累计的n个顾客生成的n个同城订单，每个顾客生成一个订单，大小为
。订单按照某种分批规则合并后产生若干拣选批次，排序后分配给员工进行拣选，员工数为1。拣选后的订单打包后分配给对应的车辆进行配送，一个订单由且只由一辆车配送。车辆离开时间等于配送批次中的最后一个订单拣选完成时间，顾客的收货时间以车辆到达配送点并服务完该顾客的时间为准。车辆从配送中心出发，服务完该路径上所有顾客后返回配送中心。本文要解决的主要问题为寻找最优的分批拣选方案及配送方案，以最小化订单最终履行时间，从整体角度提升订单处理速度。模型假设如下：1)所有车辆类型相同，容量为
，车辆数不限；2)不考虑拣选准备时间、打包时间、装货和卸货时间；3)配送点间时间满足三角不等式，且配送时间具有对称性；4)拣选员工按照S-shape型路径策略进行拣选[1]，拣选容量为Q；5)拣选区域布局如图2所示，仓库类型为单区型，通道的入口在仓库的最左端，且每个通道的宽度相同。
