电子商务环境下的物流配送产生了新的特点，在传统方式下建立的物流配送系统已不能完全满足电子商务的需要。针对电商配送终端客户具有配送需求量小、品种多、位置较分散的新特点，研究电子商务环境下的车辆调度问题，用聚类分析法划分配送区域，建立VRPTW模型，采用遗传算法对模型加以求解。通过仿真实验，与传统的VRP模型求解进行比较，发现优化后的成本比未优化的成本低，验证了关于VRPTW优化模型求解方法的有效性。
34 015,51(15) Computer Engineering and Applications计算机工程与应用 (2)聚类的簇数k值的确定 小区域,为后面的路径优化过程减少计算量。 基丁电子商务的特点,安排车辆调度假设每辆车配2.2各配送区域内实现车辆调度 送一个区域,即派岀的配送车辆的数目等于快速样本聚类221问题描述 的簇数。派出的配送车辆数可由公式k=∑q/aQ4|+1 在电了商务环境下,物流配送中追求的不仅仅是运 输成本的最低,客户对配送的满意度也尤为重要,然而 米计算,[”表示取整函数,q;表示客户氵的需求量,gk齐户对配送服务时间的要求是决定满意度的主导因 表示车辆k的最大载重量,a表示一个已知系数,0<素。由于电子商务环境下的物流配送时问的不同,车辆 α<1。通过公式确定了快速样本聚类簇数k的值 调度时间的不合理,或早或晚导致了时间成本的产生, (3)快速样本聚类算法的基本步骤 需要建立带时间窗的钅辆调度模型,使延误时间尽量 k- mcans算法是划分聚类算法的典型代表,实质上少,时间成本尽量小和运输距离尽量小作为目标函数的 该算法基于簇中对象的平均值。为了能达到全局基于主要考虑因素。通过聚类分析法把所有的客户点分为 划分的聚类要求穷举所有可能的划分。 不同的类,每一类都需要作出最优路径,满足RPTW 算法的处理过程如下 模型。 算法的输入:数据库中的对象与簇的数目k 22.2 VRPTW模型假设 算法的输出:使得平方误差准则最小的k个簇。 为了便于问题的描述和构建相应数学模型,本文针 方法如下: 对单配送中心多需求点配送车辆调度问题的特点,提出 ①从整个样本n即含n个对象的订单中,任意选择了如下的假设条件 k个对象作为初始的簇的中心m1(=1 (1)物品流向为单向,即纯送货 ②利用公式(1),将客户的位置坐标、需求量及服务 (2)只有一个配送中心,且每条线路的开始和结束 时间窗作为聚类评价指标,计算数据集中的每个对象P位置都在配送中心,所有车辆必须在规定的时间内返回 到k个簇中心的距离d(P,m2) 配送中心。 ③找到每个对象p的最小的d(p,m),将p归入到 3)配送中心和客户点的位置坐标已知。 与m,相同的簇中。 (4)车辆在配送过程中不得超过其额定载重量 (5)车辆为同种车型,且容量已知。 ④遍历完所有对象之后,利用公式(2)重新计算聚 (6)客户点的需求量已知,该点货物只能由一辆汽 类中心m,的值,作为新的簇中心。 车完成,且所有客户都应该得到服务。 ⑤重新将整个数据集中的对象斌给最类似的簇。2.2.3ⅴRPTw模型构建 这个过程反复进行直至平方误差准则最小。 (1)符号说明 (.0)=、(x1-xn)+(xa2-x2)+…+(xm-x q1为客户的货物需求量;Q为第k辆车的量大载 其中,1=(xmx…,x1)和产=(xmxn,…,x)是两个n里量;c为客户到客户的运输成本(即运输距离); 维数据对象。 为需要服务的客户总数;t为客户i到客户的行驶时 (2) 间;为从配送中心到客户i的行驶时间;s为车辆在 客户的服务时间;ET为允许的最早服务时间;LT为 其中,m代表第k个簇的簇中心,N代表第k个簇中允许的最晚服务时问;M为一个非常大的正常数:a为 数据对象的个数。 早于F7开始服务的惩罚系数,即早于E71h惩罚a 平方误差准则试图使聚类结果尽可能得独立和紫元;b为晚于L开始服务的惩胃系数,即晚于 凑,即簇内对象的相似度尽可能得高。定义如下: 惩罚b元。 F=∑∑D-m 车辆从点行驶到 0,否贝 其中F表示所有对象的平方误差的总和,D代表空间 点任务由车辆k完成 中的对象,m代表簇C的平均值 0,否则 将所有客户的位置坐标、需求量、服务要求时间这 (2) VRPTW数学模型 些属性作为聚类变量,100个对象(客户)中任意选择k 个对象作为初始聚类中心,通过SPSS软件重复②、③、 min=∑∑∑cyk+a∑max(Er,-1)0+ k-1a-1:-1 ④过程,直至聚类中心不再发生变化结束,具有相似性 较高的客户点聚为一类,可以把配送区域划分为不同的 b∑max[t1-LT)0 杨湑雄,李金丹,张浩:电商配送中的车辆调度问题优化研究 2015,51(15)35 s.∑q,x≤Q,k∈K (4) 并按照上述选择概率分布所决定的选中机会,每次 从S中随机选定1个个体并将其染色体复制.共做N次, y=x,Vk∈K (5)然后将复制所得的N个染色体组成群体S (5)按交义率P所决定的参加交义的染色体数c, 三x,Vk∈K 从S1中随机确定c个染色体,配对进行交叉操作,并川 产生的新染色体代替原染色体,得群体 (7) 6)按变异率Pn所决定的变异次数m,从S2中随 机确定m个染色体,分别进行变异操作,并用产生的新 0≤∑x ≤n (8) 染色体代替原染色体,得样体S3。 4+81+-M(-ya)≤l (9) (7)将群体S3作为新一代种群,即用S3代替S,t= 电子商务环境下的物流订货时间不同,不满足客户+1,转(3)。 的时间需求就会产生一定的时间成本,所以除了满足路 以 VRPTW模型为目标函数,用遗传算法求出最优 径最短,还要尽量使得时间成本最低。式(3)为目标函解,使电子商务物流配送的运输成本最低和时间成本最 数,分为两部分,第一部分使运输距离最短,第二部分使低,得出电子商务物流配送的最低总成本,并可以得到 时间成本最小 车辆调度的最优配送路径和车辆调度时间 式(4)保证每条路经上各客户的需求量之和不超过 配送车辆的载重量 3仿真分析 式(5)~(7)保证了每个客户点的需求只有一辆车来3.1案例概况 服务。 问题描述如下:随机产生100个客户点的位置坐标 式(8)保证了第k辆车服务的客户数不超过所有客和需求量,假设存在一个电子商务物流配送中心,其位 户的总数n。 置坐标为(0,0),某天配送中心需为100个不同地理位 式(9)保证了车锕的行车路线的总耗时不超过个置,不同需求量及送货时间要求的客户提供服务。配送 事先定下的数值,以满足客户对供货时问的要求。 中心的车辆都是相同型号的,具有相同的载重量,均为 2.2.4遗传算法求解ⅴRPTW模型 200个单位。 由于电子商务环境下的客户需求量小的特点,要求3.2案例求解 对配送路线进行优化,提高车辆的满载率,按照优化路321第一步聚类分析法运算分析 线来配送商品,所以对每一类的客户组用遗传算法进 根据快速样本聚类算法的步骤,将客户信息表中的 行路径优化、以带时间窗的车辆调度模型式(3)为目标位置坐标、需求量、服务要求时间这些属性输入SPSS软 函数,求得每一类客户组的最优路径。 件中,用k均值聚类算法进行聚类分析,对案例中的客 遗传算法是一种基于自然选择和遗传变异等生物广点进行区域划分。100个对象(客户)中任意进择k个 机制的全局性概率搜家算法。基本的遗传算法通过对对象作为初始聚类中心,通过sPSs软件重复②、③、④ 某一代种群经过对生物基因的复制、变换和变异,特产过程,直至聚类中心不再发生变化结束,具有相似性较 生新一代种群。再重复此过程,直到群体或最优点的性高的客户点聚为一类,可以把配送区域划分为不同的小 能达到满意程度。基本步骤为 区域,为后面的路径优化过程减少计算量。 (1)选择问题的一个编码方式,在搜索空间U上定 已知a=0.85,Q=200,由参考文献[13中的公式 义一个适应度函数f(x),给定种群规模N,交义率P和 变异率Pn,代数T k=∑qaQ|+1来计算聚类的个数k=10,即将配送区 (2)随机产生U中的N个个体S,s2…,s,组成初域化分为10个小区域。 始种群S1={s1,s2…,Sx},置代数计数器t=1。 最终的聚类结果通过SPSS软件运行界面如图2 (3)计算S屮的每个个体s的适应度函数f=f(s)。所示 (4)若满足算法终止规则,则算法终止,取S中适应 通过SPSS软件,用K均值聚类分析法得出结果, 度最大的个体作为所求结果,否则,计算概率: 客户点的分类结果如图3所示 3.22第二步遗传算法运算分析 2,…,N) 通过SPSS软件用K均值聚类算法将100个客广 划分为十类,即将配送区域化为十个小区城,接下米用 36 015,51(15) Computer Engineering and Applications计算机工程与应用 作算子,通过选择函数选取适应度高的个体,直到选满 为止 (5)交叉算子。本文通过交叉函数进行染色体交 叉,并产生子代。 (6)变异算子。本文采用均匀变异法,通过变异函 数,选取0.02的变异概率对父代染色体进行变异。 样体的吏新和终止。为保证计算随迭代次数的 增加,最优解越米越好,本例中每次变异后将每次的上 图2sPSS软件κ均值聚类分析运行界而 次迭代最优解加入群体,防止因交叉或变异而使最优解 大厶,出现退化现象。并为保持群体数目不变,变异后 第二类■第·类▲第三类第四类第五类 論第六类第七类第八类-第九类第十类 产生随机解加入群体。 150 终止条件最常用的有事先给定一个最大进化步 100 数,或者是判断最优化值是否连续若干步没有明显变化 两种 Matlab遗传算法的部分运行界面如图4所示。 200-154-1009-609 50:100150200 50 图3sPSS软件K均值聚类分析的结果分布图 Matlab的遗传算法T具箱对每个区域进行路径优化,对 建立的 VRPTW模型进行求解,最后在 Matlab软件上实 现并得出结果。 遗传算法相应的参数设置如下 惩罚系数a=5,b=5,交叉率P=0.8,变异率Pn 图4 Matlab的运行界面 002,种群规模N=1500,最大迭代次数r=100 对十个聚类区域分别进行路径优化,分别运行 Matlab (1)编码。本文采用自然数编码方法构造染色体,软件丨次,基于ⅤRPTW模型,遗传算法求得的解如表1 操作简单易行,遗传操作便于实现。 所示。 (2)种群初始化。本文给定群体规模1500,通过初 本文的计算结果为:10条路径的总成本为57847979, 始种样兩数随机产生1500个个体,构成初始种样,随机时间成本为1217.5,运输成本为45672979。 产生1500条初始可行路径 仅把路径最短作为H标函数,相同的参数设置条件 (3)适应度评估。通过适应度函数即目标函数来评下,遗传算法得到的路径优化结果如表2所示 价每条染色体的适应度函数值,目标函数值越小越接近 仅把路径最短作为目标函数的方法计算结果为:10 最优解。 条路径的总成本为6245.5432,时间成本为1900,运输 (4)选择算子。本文将随机竞争选择作为选择操成本为4345.5432。 表1基于ⅤRPTW为日标函数的遗传算法路径优化的最终结果 序号 客户配送顺序 时间成公总成 0-2122-33-32-51-76-93-73-7267-770 105.0 582.6620 0-20-16-23-11-4-7-24-94-71-78-2-99-68-0 556.0772 0-54-92-53-90-74-0 95.0 05.9761 112.5 0-46-34-48-50-66-35-2698-970 95.0 415.979 0-29-42-44-40-81-43-41-95-65-0 65.0 450.0809 0-70-6l-60-5591-75-69-5756-0 197.5 680.4658 100-5-18-39-37-30-36-14-59-88-89-27-100-96-38-28-0 135.0 849.9773 杨湑雄,李金丹,张浩:电商配送中的车辆调度问题优化研究 2015,51(15)37 表2基于ⅤRP为目标函数的遗传算法路径优化的最终结果 序号 客户配送顺序 运输成本时间成本 0-22-51-33-72-73-76-93-67-32-77-21-0 400.5971 205.0 123 0-58-86-87-82-640 362.55 0-68-99-23-20-16-2-78-94-24-71-7-4-11-0 407.4461 292.5 0-5492-53-90-74-0 410.9761 95.0 0-3-1.98-17-13-31-12-19-25-10-6-15-0 325.6606 207.5 5678 0-26-9798-66-50-48-34-35-46-0 307.573 185.0 0-4243-44-81-9565-4140-290 355.5952 0-60-56-57-69-55-75-91-70-61-0 470.6237 172.5 0-63-83-49-45-62-79-80-84-85-52-47-0 639.2384 245.0 10 0-18-37-39-36-38-27-28-100-5-59899688-14-30-0665.7777 290.0 323结果分析 策研究[门商场现代化,2007,9(2):126-127 本文的研究方法是以ⅤRPTw模型为目标函数,不[3]贺喜基」B2C电子商务下的配送问题研究[D]北京:北京 仅考虑了运输距离,还考虑了客户的时问成本,即惩罚 交通大学,2009 成本也作为H标函数的一部分,对比表1和表2,由此得41李良伟我国电了务物流模式创新研究D哈尔滨:哈尔 出的优化结果比以不包括惩罚成本的数学模型为目标 滨工程大学.2007 函数的优化结果节约了总成本4607453。本文的研究5朵剑桥电子商务主体责任追溯制度探析印北京工商大学 方法得出的结果运输成本增加了221.7547,但时间成本 学报:社会科学版,2012,27(5):58-64. 相对铰小,节约了时间成4682.5,表明该方法配送更具 antzig G. Ramser J. The truck dispatching problem[J Management Science, 1959, 22(6):80-91 有时效性,更符合电子商务物流配送的新特点,达到“限 [7 Clarke G, Wright J W Scheduling of vehicles from a cen 时物流¨配送的新要求,提高了配送的服务效率,同时总 tral depot to a number of delivery points [J]. Operations 成本也降低了,为企业节约了资金,提高企业竞争力。 Research,1964,12(5):568-581 6 Gcndrcau M, Hertz A, Laporte GA tabu scarch hcuristic 4结束语 for the vehicle routing problem M. Montreal: Publication 本文分析∫电子商务物流配送的特点,针对其业务 Centre de recherche sur les transport, 1991 范闱广,客户规模大的特点,采用聚类分析法将配送网91 Lawrence S, Mohammad A Parametric experimentation with 点化为若干小区域,为下一步路径优化减轻了计算量, a genetic algorithmic configuration for solving the vehicle 提高优化效率。并针对电子商务物流配送对时间的严 routing problem[C]iProcccdings-Annual Mccting of the 格要求,建立ⅤRrIW模型,将车辆行驶的总路程尽量 Decision Sciences Institute, 1996: 488-490 少、车辆延误时闺尽量少作为目标函数的上要考虑因10谢天保,雷西玲,席文玲.物流送中心配载车辆词度间 素,更符合电子商务物流配送的要求。通过算例分析, 题研究[计算机工程与应用,2010,46(36):237-240. 本文以增加了时间惩罚成本的模型求得结果,比传统的1 [1]李海龙物流配送与跟踪的动态车辆调度问題研究[黑 龙江工程学院学报,2008,22(2):51-54. 只考虑路径距离为目标函数求得的结果更节约成本,且 更具有时效性。但模型在目标函数、约束条件及求解算 [12]弓晋丽、程志敏基」 Matlab物流配送路径优化问题传 算法的实现[物流科技,2006(7):103-105 法等方面还有待进一步深化研究,下一步的研究重点可 13]唐俊时间窗约束下的配送车辆调度问题研究计算机 以考虑车辆的体积,在约束条件中增加车辆体积的限 工程与应用.2011,47(21):243-245. 制,并可适当考虑综合各种算法来实现H标最优 「14]杨浩雄,胡静,何明珂配送中多车场多任务多车型车辆 调度研究[J计算机工程与应用,2013.49(10):243-246 参考文献: [15]方越建电子商务环境下的物流配送车辆调度方法研究[D] []中国电子商务研究中心2012年度中国网络零售市场数据 杭州:浙江大学,2006 监测报告[R杭州,2013 [16]雷英杰 MATLAB遗传算法工具箱及应用[M]西安:西安 [2]蒋家添我国电子商务中物流配送的发展现状、问题与对 电子科技大学出版社,2005:3-5