B2C电子商务环境下订单选择与配送的联合调度优化_电子商务环境论文

B2C电子商务环境下订单拣选与配送联合调度优化，本文主要内容关键词为：订单论文,环境论文,电子商务论文,B2C论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。

       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所示，仓库类型为单区型，通道的入口在仓库的最左端，且每个通道的宽度相同。

      

       图1 订单拣选与配送示意

      

       图2 拣选区域布局

       基于上述分析，结合Chen Zhilong[4]总结的IPDS问题表达形式

，本文研究IOPDS问题可抽象为：

       其中α：拣选员工数为1的人工拣选系统；β：订单信息提前已知，拣货策略S-shape；π：配送车辆为容量

的同类型车辆，数量无限制，考虑路径优化；δ：n个顾客；γ：最小化订单最终履行时间。

       2.2 IOPDS模型构建

       首先对模型中的常量和变量作如下定义：

       常量：

      

      

       基于上述分析，构建订单拣选与配送联合优化模型，以最小化拣选和配送完所有订单的履行时间：

      

      

       目标函数(1)表示最小化拣选和配送完所有订单的履行时间；约束(2)-(7)为拣选阶段约束，其中(2)和(3)是对订单分批的约束，即保证一个订单只能分配给一个合并批次，且每个合并批次商品量不超过上限Q；约束(4)定义批次k的服务时间，为行走时间、拣选时间之和；约束(5)和(6)为拣选开始时间约束，定义第一个开始拣选的批次时间记为0，且完成后即开始第二个批次的拣选工作；约束(7)定义订单的拣选完成时间为其所在批次开始拣选时间和拣选所需时间之后。约束(8)-(18)为配送阶段约束，其中约束(8)表示所属车辆v的所有订单都拣选完成后，车辆离开配送中心；约束(9)-(12)是对车辆的约束，定义一个配送点只由一辆车服务；每辆车从0点出发，并最终回到0点；进入配送点i的车辆k必须从配送点i离开；每辆车只能离开0点1次；约束(13)-(15)为配送点的流量约束；(16)对车辆v的服务结束时间进行了定义；约束(17)为履行时间表达式，为车辆最晚结束的时间。

       2.3 IOPDS模型复杂性分析

       本节分析IOPDS模型的复杂性，并证明此类问题为NP-hard问题，不存在多项式时间算法。

       定理1 IOPDS模型为NP-hard问题。

      

       此类IOPDS特殊问题最优解构建的配送路径应仅由一条路径组成。反之若最优配送路径由两条配送线路构成：

      

       求解此类IOPDS特殊问题可等同于求解TSP旅行商问题，由于TSP为NP-hard问题[30]，因此IOPDS问题同为NP-hard问题。

       3 拣选与配送联合调度优化三阶段算法

       由于IOPDS模型属于NP-hard问题，无法用精确算法求得最优解，本文构建三阶段启发式算法求解。

       3.1 算法可行性分析

       Chen Zhilong等[9]证明得出，IPDS问题存在最优解需满足以下几个条件：1)订单间生产不能存在空闲时间；2)每辆车的离开时间等于其配送所有订单中最后一个订单的完成时间；3)在同一机器上生产且由同一辆车配送的订单应在该机器上连续生产。本文研究的IOPDS问题为IPDS的一类特殊问题，上述条件也适用于IOPDS问题。因此由同一辆车配送的订单需由拣选员工连续拣选完后立即配送。其次对目标函数

分析：

      

      

       3.2 配送线路优化

       考虑到电子商务环境下订单通常都是按区域配送，每个配送区域由一辆车负责，本文基于“聚类—路径优化”的思想[31]，先采用K均值聚类方法对顾客进行聚类，再采用遗传算法对各区域配送线路进行优化，以最小化配送时间

。

      

       3.3 订单分批优化

       本文在拣选路径策略为S-shape型、货位分布已知的情况下，采用基于相似度聚类的订单分批规则对同一配送批次订单集合进行分批优化，以最小化

。

       步骤2：针对第v批次的配送线路

订单，优化其作业方式，以最小化拣选完成时间。采用种子算法中的相同通道数系数作为衡量订单间相似度的指标。两订单所包含相同通道数越多，其相似性越大，合并的可能性也越大。分批规则思路如下，具体规则详见王旭坪等[27]：

      

      

       3.4 拣选顺序调整

       在得出最优配送线路及拣选方案后，需对拣选顺序进行排序，以最小化订单履行时间。

       步骤3：订单集合的拣选顺序按照对应配送时间

从大到小排列。按照配送时间长的订单集合先拣选，配送时间短的订单集合后拣选的原则，对拣选顺序进行排列。已知订单集合O(

)的配送时间为

，对应拣选时间

。通常情况下，

要远大于

，则较长时间配送的订单能较早的到达顾客手中，从一定程度上减少了整体订单履行时间。

       4 拣选与配送联合调度优化传统算法

       传统的拣选与配送联合优化算法可归纳为一类两阶段算法：首先配送中心依据顾客订单信息确认订单的合并批次和拣选顺序，以最小化拣选所需时间；然后配送部门根据顾客位置来确定合理的配送方案，最小化车辆行驶路径且顾客收货时间。当某一配送方案包含的所有订单都拣选完成后，则装车配送，如未完成则车辆需在配送中心等待。算法简述如下：

       步骤1：订单拣选优化。此过程不考虑配送的影响，以最小化订单拣选时间为目标，采用3.3中基于相似度聚类的订单分批规则生成拣选批次。

       步骤2：配送线路优化。采用3.2中“聚类—路径优化”的思想计算订单配送线路，以最小化总配送时间。

       步骤3：开始配送服务。合并批次按照顺序依次进行拣选工作，当某一配送方案中的所有订单拣选完成后，则按照事先优化的线路离开配送中心；当订单拣选完成，且车辆服务完所有顾客返回配送中心后，算法结束。

       5 数据实验

       5.1 实验设置

       随机产生订单300个，由于订单具有小批量等特征，令每个订单的需求量在[1，3]上服从均匀分布。拣选区域参数如下：包含10个拣选通道和1000种商品，每列货架存放50种商品，每个员工一次拣选的最大商品容量为10个，通道长度50米，宽度2米。假设每个商品的体积相同，且只能存储在一个货架上；拣选员工行走在通道的中央，以便同时从左右两边拣选商品，员工拣取速度30个/分，行走速度125m/分；员工通常从最左边的入口进入，拣取完所有商品后回到入口处。

       顾客的位置坐标在[0，100km]]上服从均匀分布，且配送中心坐标为(50km，50km)，如图3所示。采用K均值聚类将A城的300个顾客分为16个配送区域，且每个区域的订单由一辆车负责，车辆行驶速度为60km/h，每个顾客服务时间1分钟。经过多次实验，遗传算法参数设置如下：初始种群大小100，最大迭代次数1000；交叉概率0.8，采用转轮法选择交叉点进行单点交叉；变异概率0.8，采用实值变异；染色体适应值为配送线路的距离。

       5.2 结果分析

       计算可得16区域的配送路径如图3所示，每个区域所需总配送时间范围在107.25～228.82分钟，最短为A5，最长为A15。表1给出两种不同算法的拣选与配送联合优化方案，可得各区域配送时间(车辆行驶时间+服务时间)、拣选开始时间、车辆离开时间、拣选时间、结束时间等信息。三阶段算法履行时间为332.08分钟，传统算法履行时间为400.64分钟。

      

       图3 300个顾客分布图及线路优化

       其中三阶段算法中，A1-A16每条配送线路的订单被分为若干拣选批次，最大分批数量为7，最小为3，拣选时间范围在9.66～20.19分钟之间。图4为各区域拣选与配送时间序列图，白色为拣选时间，黑色为配送时间。拣选顺序为A15-A7-A1-A3-A6-A13-A10-A12-A8-A14-A4-A2-A9-A11-A16-A5，最早结束区域为A15，总耗时248.20分钟，最晚结束区域为A11，总耗时332.08分钟，即300个订单从开始拣选到最终完成需5.53小时，平均履行时间285.95分钟。由于某区域订单未拣选完成时，所属区域配送车辆需在配送中心等待，计算可知平均车辆等待时间为123.67分钟，最长等待时间为218.88分钟。三阶段算法的上界

，其中所有订单的拣选时间之和为218.88，最长配送时间228.82，最短配送时间107.25。三阶段算法得出的履行时间与下界之比

，说明此算法所得结果接近最优解。另外，可以看出每条线路的结束时间与各区域拣选顺序、拣选开始时间、配送时间等因素有关。A15最早开始拣选却不是最早完成，A5最后开始拣选，服务结束时间却早于A11和A16。

      

       图4 三阶段算法各区域拣选与配送时间序列图

       传统算法下对订单进行分批优化，300个订单分为63个批次，平均每个批次拣选时间2.73分钟。图5为各区域的配送时间序列图，车辆离开顺序A8-A4-A3-A12-A2-A6-A7-A9-A10-A11-A13-A14-A1-A5-A15-A16，A8为最早开始配送区域，需等待第50个批次拣选完成；最晚开始配送区域A1、A5、A15、A16，需等待最后一个批次拣选完成。300个订单总履行时间400.64分钟，平均履行时间328.80分钟，车辆平均等待时间166.10分钟。综上所述，我们可以分析得到如下结论：

       1)三阶段算法的解

要优于传统算法的解，解的改进程度为17.11％。可见统筹考虑拣选和配送系统优化调度的特点，能够改进传统的拣选与配送两个阶段分别优化的结果。

      

       图5 传统算法各区域配送时间序列图

      

       2)三阶段算法平均履行时间的改进程度为13.03％。可见整体考虑拣选和配送过程有利于提高系统配送效率，提升顾客满意程度。

       3)车辆等待时间一定程度上说明了配送资源的利用情况，三阶段算法平均车辆等待时间的改进程度为25.54％，其幅度要高于总服务时间及平均服务时间，对配送资源利用率改善明显。

       实验结果验证了模型和算法的有效性，三阶段算法有利于从整体上提高订单处理速度，改善配送资源利用率，从订单拣选和配送两个环节协同优化提升了电子商务物流配送速度。

       6 总语

       为解决B2C电子商务环境下订单拣选环节和物流配送环节分开优化造成效率较低的问题，本文尝试研究订单拣选与配送联合调度优化，并将其抽象为

的表达形式，以最小化订单履行时间为目标，构建单拣选员工和多配送车辆情形下的订单拣选与配送联合调度模型。为求解此NP难问题，构造了三阶段启发式算法，首先构建最优配送方案，再进一步对配送方案中订单进行拣选优化，最终确定最优的拣选方案和批次拣选方案的排列顺序。通过数据实验与传统拣选与配送分开优化算法进行比较，结果表明：综合考虑拣选和配送优化调度系统的特点，能够缩短订单履行时间，降低配送车辆等待时间，改善配送资源利用率。本文构建模型和算法有利于从提升效率、节约资源和提高顾客满意度等多方面优化电子商务物流管理问题。

       本文只考虑单拣选员工下的订单拣选情况，且顾客对配送时间无要求，进一步的研究可考虑顾客时间窗的多拣选员工拣选与配送联合调度问题；另外，本文研究背景为同城配送，可进一步研究采用干线和最后一公里联合配送的城际订单拣选与配送联合优化；对于实时订单到达情况下的拣选与配送联合优化也有待进一步的研究。

标签：电子商务环境论文;  电子商务论文;  优化论文;  批次管理论文;  算法论文;