B2C电子商务环境下订单拣选与配送联合调度优化

王旭坪，张 珺，易彩玉

(1.大连理工大学系统工程研究所，辽宁 大连 116023；2．大连理工大学商学院，辽宁 盘锦 124221)

B2C电子商务环境下订单拣选与配送联合调度优化

王旭坪1,2，张 珺1，易彩玉1

(1.大连理工大学系统工程研究所，辽宁 大连 116023；2．大连理工大学商学院，辽宁 盘锦 124221)

如何在顾客下单后协调好拣选和配送环节，在最短的时间、以较低的成本将商品从货架上拣出、打包后配送到顾客手中，已成为B2C电子商务物流管理中亟待解决的问题。本文尝试以最小化订单履行时间为目标，构建非线性拣选与配送联合调度模型，以解决订单拣选顺序、拣选作业方式、车辆行驶线路等联合决策。为求解此NP难问题，设计了三阶段启发式算法：首先采用“聚类-路径优化”思想，依据顾客位置进行配送方案确认；然后采用基于相似度聚类的订单分批规则对每条配送线路的订单进行分批合并；最后调整拣选任务与配送线路顺序。通过数据实验对模型进行验证，并与传统拣选与配送分开优化的结果进行对比。结果表明，三阶段算法能够有效缩短订单完成时间、降低配送车辆等待时间、改善配送资源利用率。

联合调度；订单拣选；路径优化；三阶段算法；遗传算法

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模型；ChenZhilong等[9]分别构建了多产品在单一和平行生产线上的IPDS模型；裴军等[10]、马士华和吕飞[11]、马士华和王青青[12]建立采取批量生产分批配送模式的生产与配送协同模型；冯鑫等[13]探讨了单机批量加工的生产配送调度模型；配送调度优化则包含直接配送、分批配送、配送路径优化及带时间窗的配送等方面。LiKai等[14]、李昆鹏和马士华[15]、王建华等[16]考虑了配送时间固定的直接配送模式；ChengBayi等[17]研究了考虑单一顾客的分批配送调度；GaoSu等[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个同城订单，每个顾客生成一个订单，大小为qi。订单按照某种分批规则合并后产生若干拣选批次，排序后分配给员工进行拣选，员工数为1。拣选后的订单打包后分配给对应的车辆进行配送，一个订单由且只由一辆车配送。车辆离开时间等于配送批次中的最后一个订单拣选完成时间，顾客的收货时间以车辆到达配送点并服务完该顾客的时间为准。车辆从配送中心出发，服务完该路径上所有顾客后返回配送中心。本文要解决的主要问题为寻找最优的分批拣选方案及配送方案，以最小化订单最终履行时间，从整体角度提升订单处理速度。模型假设如下：1)所有车辆类型相同，容量为Qc，车辆数不限；2)不考虑拣选准备时间、打包时间、装货和卸货时间；3)配送点间时间满足三角不等式，且配送时间具有对称性；4)拣选员工按照S-Shape型路径策略进行拣选[1]，拣选容量为Q；5)拣选区域布局如图2所示，仓库类型为单区型，通道的入口在仓库的最左端，且每个通道的宽度相同。

图1 订单拣选与配送示意

图2 拣选区域布局

基于上述分析，结合ChenZhilong[4]总结的IPDS问题表达形式α|β|π|δ|γ，本文研究IOPDS问题可抽象为：1,manual|off-line,S-shape|V(∞,Qc),routing|n|tmax其中α：拣选员工数为1的人工拣选系统；β：订单信息提前已知，拣货策略S-shape；π：配送车辆为容量Qc的同类型车辆，数量无限制，考虑路径优化；δ：n个顾客；γ：最小化订单最终履行时间。

2.2 IOPDS模型构建

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

常量：

N：配送点(订单)集合；

N0：包含配送中心的配送点集合；

M：订单合并批次集合；

V：车辆集合；

qi：订单i中包含的商品数量，i∈N；

vtravel：单位时间拣选人员的行走距离；

vpick：单位时间拣选员工拣出商品数量；

Q：每个拣选批次能容纳的最大商品数量；

Qc：最大车容量；

τij：从配送点i到j所需时间，i,j∈N0；

tservice：配送点所需服务时间，i∈N。

变量：

disk：完成批次k拣选任务所需行走距离(拣选路径优化策略采用S-shape策略)，k∈M；

xik：订单i是否分配给批次k，i∈N，k∈M；

yiv：订单i是否由车辆v负责配送，i∈N，v∈V；

zijv：车辆v是否从配送点i驶向j，i,j∈N0，v∈V；

ri：配送点i的流量，i∈N0。

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

MinTturnover

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

r0=0

(13)

(14)

(15)

(16)

(17)

目标函数(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特殊问题最优解构建的配送路径应仅由一条路径组成。反之若最优配送路径由两条配送线路构成：

tripv1={0,i1,i2,…,it,0}

将两条配送线路合并可得：

求解此类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问题。因此由同一辆车配送的订单需由拣选员工连续拣选完后立即配送。其次对目标函数Tturnover分析:

3.2 配送线路优化

3.3 订单分批优化

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

1)计算订单集合O(σv)中订单间相似度；

2)选取O(σv)中相似度最高的两个订单σv(p),σv(q)，两订单容量为qσv(p)+qσv(q)；

3)合并批次容量约束判断：如果qσv(p)+qσv(q)Q，选择其他相似度较大订单进行合并生产批次后，返回1)。

3.4 拣选顺序调整

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

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个顾客分布图及线路优化

图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)三阶段算法的解Tturnover要优于传统算法的解，解的改进程度为17.11%。可见统筹考虑拣选和配送系统优化调度的特点，能够改进传统的拣选与配送两个阶段分别优化的结果。

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

配送区域配送时间三阶段算法传统算法拣选开始时间车辆离开时间拣选时间结束时间最后拣选批次序号车辆离开时间结束时间A1206.9733.1753.3620.19260.3363171.82378.79A2141.17155.45169.4714.02310.6462169.72310.89A3180.5553.3670.4017.03250.9557159.03339.58A4146.85143.73155.4511.73295.5054150.08296.93A5107.25208.73218.8810.15326.1363171.82279.07A6180.5370.4082.4412.05262.9762169.72350.25A7223.0919.3833.1713.8256.2662169.72392.81A8154.36116.76126.589.82280.9450135.82290.18A9140.37169.47183.4613.99323.8362169.72310.09A10163.6095.20104.869.66268.4662169.72333.32A11135.19183.46196.8913.43332.0862169.72304.91A12157.14104.86116.7611.9273.9061167.59324.73A13166.8582.4495.2012.75262.0562169.72336.57A14151.79126.58143.7317.14295.5262169.72321.51A15228.820.0019.3819.38248.2063171.82400.64A16118.74196.89208.7311.84327.4763171.82290.56履行时间Tturnover=332.08Tturnover=400.64平均履行时间285.95328.80平均车辆等待时间123.67166.10

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

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

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

6 总语

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

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

[1]KosterR,ThoLD，RoodbergenKJ.Designandcontrolofwarehouseorderpicking:Aliteraturereview[J].EuropeanJournalofOperationalResearch, 2007, 182(1): 481-501.

[2] 王旭坪, 阮俊虎, 张凯, 等. 有模糊时间窗的车辆调度组合干扰管理研究[J]. 管理科学学报, 2011, 14(6): 2-15.

[3] 黄敏芳, 张源凯, 胡祥培. 有机蔬菜B2C直销的配送方案智能生成方法[J]. 系统工程学报, 2013, 28(5): 600-607.

[4]ChenZhilong.Integratedproductionandoutbounddistributionscheduling:Reviewandextensions[J].OperationsResearch, 2010, 58(1): 130-148.

[5]GeismarHN,LaporteG,LeiLei,SriskandarajahC.Theintegratedproductionandtransportationschedulingproblemforaproductwithashortlifespanandnon-instantaneoustransportationtime[J].INFORMSJournalonComputing, 2008, 20(1): 21-33.

[6]LowCY,LiRK,ChangCM.Integratedschedulingofproductionanddeliverywithtimewindows[J].InternationalJournalofProductionResearch, 2013, 51(3): 897-909.

[7]LowCY,ChangCM,LiRK,etal.Coordinationofproductionschedulinganddeliveryproblemswithheterogeneousfleet[J].InternationalJournalofProductionEconomics, 2014, 153(4): 139-148.

[8] 李凯, 王明星, 杨平, 等. 单机多车情形生产与配送协同调度算法[J]. 计算机集成制造系统, 2014, 20(12): 3011-3019.

[9]ChenZhilong,VairaktarakisGL.Integratedschedulingofproductionanddistributionoperations[J].ManagementScience, 2005, 51(4): 614-628.

[10] 裴军, 刘心报, 范雯娟, 等. 基于生产与运输的供应链调度优化问题[J]. 中国管理科学, 2012, 20(S1): 586-593.

[11] 马士华, 吕飞. 基于Supply-Hub的生产与配送协同模式研究[J]. 中国管理科学, 2014, 22(6): 50-60.

[12] 马士华, 王青青. 同步物流系统下准时化生产与配送调度问题研究[J]. 中国管理科学, 2012, 20(6): 125-132.

[13] 冯鑫, 郑斐峰, 徐寅峰. 批加工生产配送二级供应链协同调度[J]. 系统管理学报, 2015, 24(2): 275-279.

[14]LiKai,YangShanlin,MaHuawei.Asimulatedannealingapproachtominimizethemaximumlatenessonuniformparallelmachines[J].MathematicalandComputerModelling, 2011, 53(5-6): 854-860.

[15] 李昆鹏, 马士华.ATO供应链中航空运输及并行机生产协调调度问题[J]. 系统工程理论与实践, 2007, 27(12): 8-15.

[16] 王建华, 李南, 郭慧. 基于时间槽的敏捷供应链集成调度模型及优化[J]. 系统工程理论与实践, 2011, 31(2): 283-290.

[17]ChengBayi,LiKai,HuXiaozuan.Approximationalgorithmsfortwo-stagesupplychainschedulingofproductionanddistribution[J].InternationalJournalofSystemsScience:Operations&Logistics, 2015，2(2): 78-89.

[18]GaoSu,QiLian,LeiLei.Integratedbatchproductionanddistributionschedulingwithlimitedvehiclecapacity[J].InternationalJournalofProductionEconomics, 2015，160: 13-25.

[19]AmstrongR,GaoSu,LeiLei.Azero-inventoryproductionanddistributionproblemwithafixedcustomersequence[J].AnnalsofOperationsResearch, 2008, 159(1): 395-414.

[20]LowCR,ChangCM,LiRK,etal.Coordinationofproductionschedulinganddeliveryproblemswithheterogeneousfleet[J].InternationalJournalofProductionEconomics, 2014，153: 139-148.

[21]LowCR,LiRK,ChangCM.Integratedschedulingofproductionanddeliverywithtimewindows[J].InternationalJournalofProductionResearch, 2013，51(3): 897-909.

[22] 冯鑫, 郑斐峰. 面对单客户的生产与配送二级供应链协同调度探讨[J]. 运筹与管理, 2014, 23(4): 19-24.

[23]LeungJYT,ChenZhilong.Integratedproductionanddistributionwithfixeddeliverydeparturedates[J].OperationsResearchLetters, 2013, 41(3): 290-293.

[24]ZhongWeiya,ChenZhilong,ChenMing.Integratedproductionanddistributionschedulingwithcommitteddeliverydates[J].OperationsResearchLetters, 2010, 38(2): 133-138.

[25]ArmentanoVA,ShiguemotoAL,LøkketangenA.Tabusearchwithpathrelinkingforanintegratedproduction-distributionproblem[J].Computers&OperationsResearch, 2011, 38(8): 1199-1209.

[26]LamCHY,ChoyKL,HoGTS,etal.Anorder-pickingoperationssystemformanagingthebatchingactivitiesinawarehouse[J].InternationalJournalofSystemsScience, 2014, 45(6): 1283-1295.

[27] 王旭坪, 张珺, 马骏. 考虑完成期限的电子商务在线订单分批模型及算法[J]. 管理科学,2014, 27(6):103-113.

[28] 朱杰, 周丽, 郭键. 分类存储人工拣选随机服务系统效率研究[J]. 管理科学学报,2012,15(2):59-71.

[29] 陈方宇, 王红卫, 祁超, 等. 考虑多拣货员堵塞的仓库拣选路径算法[J]. 系统工程学报, 2013, 28(5): 581-591.

[30]PapadimitriousCH.TheEuclideantravelingsalesmanproblemisNP-complete[J].TheoreticalComputerScience, 1977, 4(3): 237-244.

[31]RuanJunhu,WangXuping,ShiYan.Developingfastpredictorsforlarge-scaletimeseriesusingfuzzygranularsupportvectormachines[J].AppliedSoftComputing, 2012, 13(9): 3981-4000.

Integrated Scheduling of Order Picking and Delivery Under B2C E-commerce

WANG Xu-ping1,2, ZHANG Jun1, YI Cai-yu1

(1. Institute of Systems Engineering, Dalian University of Technology, Dalian 116023, China;2. School of Business, Dalian University of Technology, Panjin 124221, China)

It is an important issue to integrate the order picking with delivery problem under shorter time and lower cost by picking the items from the shelves, packaging them and delivering to customers. A nonlinear mathematical model is proposed to minimize the time required to complete picking the orders, delivering to customer and returning to the distribution center, which solves the joint decision-making problem such as order picking sequence, picking process method and vehicle routing. For this NP-hard problem, a three-phase heuristic algorithm is designed. Firstly, the “clustering-vehicle routing” method is used to get delivery solutions. Secondly, the similarity-based order batching rules are used to optimize each route’s orders. Thirdly, picking sequence is sorted based on the descending order of each route’s delivery time. The experiments are proposed to test the efficiency of the model. The results are compared with the traditional optimization algorithm, which show that the three-phase algorithm can reduce the throughput time, decrease the vehicle’s wait time and improve the delivery resource utilization. integrated scheduling; order picking; vehicle route; three-phase algorithm; genetic algorithmAbstract：With the development and wide-spread use of mobile technology, customers can shop anytime and anywhere through a business-to-consumer (B2C) e-commerce shopping platform. However small lot-size and high frequency customer orders make order picking and delivery difficult to implement. In order to accelerate the whole order fulfillment process, orders should be picked and delivered to customers in a very short lead time. It is therefore critical to integrate scheduling order picking and distribution under B2C e-commerce. Research on order picking problems, however, seldom takes delivery constraints into consideration.The integrated order picking and distribution scheduling (IOPDS) problem is studied to minimize the time required to complete picking the orders, delivering to customer and returning to the distribution center to meet the demand of a given set of customers. The picking processing method is order bathing optimization and distribution characteristic is batching delivery with vehicle routing problem. The problem is NP-hard in strong sense. A three-phase heuristic algorithm is proposed, analyze upper bounds and low bounds of the algorithm are analyzed. The first phase uses the “clustering-vehicle routing” method to get delivery solutions; the second phase uses the similarity-based order batching rules to optimize each route’s orders; the third one sorts picking sequence based on the descending order of each route’s delivery time. The traditional sequential approach is also proposed, which optimizes order picking and delivery processes separately.In order to verify the effectiveness of the proposed model and algorithms for IOPDS, several examples are tested. The locations for 300 customers are randomly generated in the 100*100 square, where the warehouse is in the center of the square. The three-phase algorithm’s relative difference from the lower bounds is good. The results are also compared with the traditional algorithm, which show several enlightening findings: 1) the throughput time of the three-phase algorithm is 17.11% shorter than the one of the traditional algorithm, which means it is significant to integrate order picking and distribution; 2) the average improvement of the three-phase algorithm is 13.03%, shows that it is helpful to improve the whole efficiency of the picking and distribution system; 3) it decreases the vehicle’s wait time and improve the delivery resource utilization.Theoretically the IOPDS model and algorithm in the work expand the order picking optimization theory and improve the scheduling of production and distribution problem. Moreover, it is beneficial to the e-commerce shopping platform, which can promote the shipping efficiency, save vehicle resources and improve customer satisfaction.

integrated scheduling; order picking; vehicle route; three-phase algorithm; genetic algorithm

1003-207(2016)07-0101-09

10.16381/j.cnki.issn1003-207x.2016.07.012

2014-11-19；

2016-03-22

国家自然科学基金面上资助项目(71471025,71171029);国家自然科学基金重点资助项目(71531002)

王旭坪(1962-),男(汉族),辽宁锦州人,大连理工大学系统工程研究所教授,博士生导师,研究方向:电子商务与物流管理、应急管理,E-mail：wxp@dlut.edu.cn.

F274

A