0 引言

随着互联网的普及, 网购优点愈加突出, 致使实体零售受到冲击.市场竞争不仅在于产品质量和价格机制, 更趋于供应链整体效益优化.供应链发展的过程是不断集成的过程, 为了适应市场竞争, 集成供应链管理(Integrated supply chain management, ISCM)应运而生.所谓ISCM, 就是对供应链中涉及的供应商、运输商、分销商等成员间的物流、信息流和资金流进行协调、控制等有效管理, 实现整体优化.其中可考虑将物流作为承载目标优化的出发点:一是集中于产品库存管理, 二是聚焦于货物运输配送^[1].对于降低物流成本实现精益供应链而言, 高效配送模式已成为零售实体竞争力的有效途径.

越库配送(Cross-docking)作为创新高效的配送策略在国外已初见成效:一方面降低了库存成本, 提高了产品流动, 实现了敏捷运作; 另一方面降低了运输成本, 达成了整车运输, 实现了规模效益.当零售供应链中实施越库配送时, 有效运用集送一体化的车辆路径问题(Vehicle routing problem with delivery and pick-up, VRPDP)不可或缺^[2].

回顾越库文献: Cota等^[3]研究了将越库中心车辆调度模拟成流水车间的问题; 陈杰等^[4]研究了不确定环境下两台机器越库调度问题; Boysen等^[5]研究了越库车辆调度分类问题; 但斌等^[6]研究了直通配送下配送中心时间优化问题; Ladier等^[7]研究了带时间窗的车辆调度问题; Konur等^[8]研究了越库系统灵活装卸时间的车辆分配问题; Yazdani等^[9]研究了越库中心入站、出站车辆调度问题.上述文献以越库中心为视角研究了车辆调度、流程规划等问题.此外, 越库模式在供应链中盛行, 也受到学者们的关注.施文等^[10]研究了从供应商到越库中心, 再到主厂仓库的零部件离散仿真分析; Shi等^[11]研究了第三方直通集配中心模式供应链库存管理仿真分析; Bachlaus等^[12]研究了敏捷性供应链越库配送问题; Buijs等^[13]研究了越库配送网络同步性和结构性问题.学者们认为供应链的无缝衔接是实施越库的关键, 更是实现整体利益的保障.在供应链物流环节, VRP扮演着重要角色.带越库配送的车辆路径问题(Vehicle routing problem with cross-docking, VRPCD)近10年逐渐凸显. Lee等^[2]首次通过禁忌搜索(Tabu search, TS)算法求解了VRPCD; Liao等^[14]对文献[2]算法进行了改进, 获得的结果更优; Ahmadizar等^[15]研究了产品价格约束的VRPCD; Enderer等^[16]研究了集成越库仓门分配和车辆路径优化问题; Maknoon等^[17]研究了越库装载和空间约束的车辆路径问题; Yin等^[18]研究了自适应记忆人工蜂群(Adaptive memory artificial bee colony, AMABC)算法的CO₂约束VRPCD.上述文献通过多种算法对VRPCD进行了寻优.综合分析, 国内文献主要集中于越库车辆调度和系统规划等问题, 国外主要侧重于VRPCD算法寻优, 从事供应链视角的研究相对较少.供应链作为联结供需双方的重要纽带, 运作是否合理, 直接决定着企业效率的高低; 物流配送作为供应链中关键环节, 配送路径优化是否合理, 直接影响供应链整体效益.对此的基本要求是协调好供应链中企业间协作关系, 实现整体效益优化.因此, 本文基于供应链物流优化理论, 分析越库系统实施要求, 构建集货车辆协同作业机制.针对城市多配送中心多样化产品配送, 实施送货车辆需求拆分模式, 建立车辆运输成本和操作成本为目标的路径优化模型.考虑模型特性, 设计改进遗传算法.最后结合算例对模型和算法进行验证分析.

1 问题描述

供应链管理不仅是为客户提供优质服务, 而且还需考虑企业物流成本.通过企业间协同互通、物流信息的供应链共享, 建立企业间物流、资金流、信息流的集成零售供应链结构, 如图 1所示.

在图 1中, 各门店根据销售情况向公司配送中心的信息中心发出补货订单; 信息中心对订单汇总, 再向供应商信息中心发送发货订单; 供应商信息中心收到订单后, 向配送中心发送预先发货通知, 然后配送中心按发货通知调用车辆, 形成协同作业集货路径; 货物到达配送中心后, 信息中心再预先根据各门店需求组织货物拣选、分装等越库作业, 然后调用车辆, 形成送货路径, 配送到各门店.

VRP作为物流的呈现载体, 通过路径优化实现物流成本控制.假定城市区域是由2个越库中心、5个供应商和5个零售商组成的供应链网络, 产品类型A、B分别由越库中心C₁、C₂拣选分装, 如图 2所示.

图 2中各线型表示各车辆路线, 如两辆车从越库中心C₁出发, 访问供应商1 ~供应商3;一辆车从越库中心C₂出发, 访问供应商4和供应商5, 集货后协同返回越库中心.根据零售商需求, 在越库中心拣选分装, 最后越库中心C₁调用两辆车将产品A配送给零售商1 ~零售商4, 越库中心C₂调用两辆车将产品B配送给零售商3 ~零售商5, 送货后返回越库中心.

2 数学模型

以最小化车辆运输成本和车辆操作成本为目标, 建立多配送中心的越库配送车辆路径问题模型.为便于理解, 模型中常量和变量如表 1和表 2所示.

基于上述说明, 建立供应链环境下带越库配送的多配送中心车辆路径问题模型, 即

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

式(1)目标函数为最小化车辆运输成本与车辆操作成本的总和; 式(2)和(3)表示集货过程车辆到达和离开各节点; 式(4)和(5)表示送货过程车辆到达和离开各节点; 式(6)表示车辆连续运作; 式(7)表示集货节点i仅由一台车辆访问; 式(8)表示送货节点j至少由一台车辆访问; 式(9)和(10)分别表示集货和送货车辆不超载; 式(11)表示送货过程节点i只由访问该节点的车辆提供服务; 式(12)和(13)表示车辆是否离开和返回对应越库中心; 式(14)表示越库配送网络车辆数量在规定范围; 式(15)表示集货过程运量等于送货过程运量; 式(16)和(17)表示车辆离开该集货节点时装载货物总量; 式(18)和(19)表示车辆离开送货节点时已配送货物总量; 式(20)表示车辆访问每个节点的时间以及节点间的运输时间的总和不超过规定时间范围; 式(21)表示车辆k从节点j离开的时间点等于离开上个节点i的时间点加上节点i到节点j的行驶时间, 再加上访问该节点j的时间; 式(22)表示集货车辆到达越库中心的时间; 式(23)表示集货车辆协同返回越库中心.

3 算法设计

随着VRP涉及的问题域的扩展, 运用启发式算法求解的优越性日益凸显.同时, 本文模型在求解效率上对算法要求更高.相比其他启发式算法, 遗传算法集聚鲁棒性、并行性和搜索较强等特性, 为解决VRP提供了较好的途径.遗传算法虽具有全局搜索能力, 但不能保证大概率收敛最优, 迭代也易早熟.针对上述不足, 在此基础上进行改进.

3.1 编码结构

相比于0-1编码, 自然数编码更具简洁、直观和可读性强等优点.特别是在遇到多车型、多配送中心、租赁车辆时, 优势更加突出.因此, 本文采用自然数序列作为染色体编码形式.采用越库中心C₁、C₂分别对产品A、B类进行拣选分装.用k台车辆完成m个供应商集货和n个零售商送货作业, 形成k + m + n + 1染色体编码, 由m + n个自然数和k + 1个0组成.

染色体编码如图 3所示, 其中0为越库中心, 1 ~ 7编码为供应商节点, 8 ~ 13编码为零售商节点.整体染色体结构表示:一台车辆由越库中心C₁出发, 访问供应商4, 5, 1节点后回到C₁, 形成路径route1;同时另一台车辆由C₁出发, 经3, 2后回到C₁, 形成路径route2, 两台车辆协同完成产品A的集货.同理, 越库中心C₂的路径route1完成产品B的集货.各越库中心拣选分装后进入送货过程, 越库中心C₁的路径route3和越库中心C₂的路径route2共同对零售商8, 11, 12节点的两类产品进行配送, 并以此方式服务剩余的零售商.

3.2 种群初始化

遗传算法若能获得较好的初始解, 便能更快找到较优解.为此, 引进扫描算法获得初始种群, 获取较好初始解.具体步骤如下: 1) 获得越库中心、供应商和零售商节点坐标, 将越库中心设立为极点, 越库中心和上述节点连线设立为极轴的极坐标系. 2) 以顺时针或逆时针方向先扫描所有供应商节点, 每扫描完一个节点, 计算其节点的累计集货总量, 当且时, 在l_μ与l_{μ + 1}之间插入0, 同理对零售商节点进行全盘扫描.对于同一角度上多个节点, 按离越库中心由近到远的顺序扫描, 扫描完所有节点后获得一条完整染色体个体. 3) 将上个节点的一定角度选为极轴偏移, 重复步骤2), 如此反复产生N个个体的初始种群.

3.3 适应度评价

对于遗传算法而言, 适应度函数值是区分群体中个体好坏的标准.通常适应值越高, 染色体性能越好, 进入下一代的概率越大, 反之越差.本文目标函数值为最小车辆运输成本与操作成本之和, 将目标函数的倒数作为适应度函数, 即目标函数值越小, 适应度函数值越高.因此, 以第s条染色体为目标函数, 则该染色体s适应度函数为f_s =1/z_s.

3.4 选择算子

利用上述方法求得种群中个体的适应值, 将适应值进行大小排序.对于个体为N的种群, 记适应度最大的个体编号为0, 最小的适应度个体为N -1.随机产生一个标准正态分布的随机数e, 可知其落在[-3, 3]的概率为99.9 %, 取e^* = |e/3|(若e > 3, 则重新生成), 此时e^* ∈ [0, 1], 令v = e^*(N - 1).因此选取第v号染色体进入新种群.由正态分布特征可知, 所选染色体越靠近0, 其概率越大, 成为较优秀染色体的可能性越高.

3.5 交叉算子

由于VRP解的结构特性, 若采用传统单点交叉、多点交叉和变化交叉等, 将破坏染色体中优良子串, 且遇到两父代染色体相同时, 传统操作将无法进行.为此, 在其基础上进行改进, 避免破坏优秀子串, 在染色体子串中将交叉点选定在0位置.同时在交叉过程中, 不宜直接将子串复制交换到相应位置, 而是移到各交叉片段的编码首位, 这样可以对已有优秀子串进行保护.步骤如下: 1)在符合交叉概率Pc的两父代个体F₁和F₂中, 取其第j个越库配送区域的集货编码片段, 在[1, R]中随机生成两个自然数L₁和L₂, 定位所取编码中0的位置, 分别锁定其优秀子串T₁、T₂; 2)将T₁、T₂移到所取片段编码首位; 3)删除所取片段中与相应首位子串相同的编码, 将这些节点重新分配车辆, 保持车载率最优, 同时将0插入相应位置, 生成新的路径; 4)将步骤3)中新生成路径与首位优秀子串合并, 再将整条染色体首尾处添0, 得到供应商节点子代染色体片段f₁、f₂; 5)重复步骤1) ~步骤4), 使其所有越库配送区域的供应商节点编码父代个体及对应的零售商节点编码父代个体完成交叉操作.交叉操作具体过程如图 4所示.

3.6 变异算子

在符合变异概率Pm中随机选择父代个体F, 取其供应商或零售商节点编码片段, 在[1, R+S]随机产生两个自然数x₁和x₂, 对应非零编码位置, 交换两处基因码, 产生新个体编码片段.变异操作如图 5所示.

4 算例分析

为了验证模型及算法, 本文通过实例和数值部分进行分析.实验以Matlab R2015a实现, 在Intel(R) Core(TM) i5-2450M CPU 2.50 GHz、内存为2.98 GB、操作系统为Win7的PC上测试.算法程序中参数设置为:种群规模n=50, 迭代次数C=1 000, 交叉概率Pc=0.8, 变异概率Pm=0.2, 保留上一代优秀个体数P=6.

4.1 实例分析

重庆百货是重庆市知名商业企业, 旗下重百超市经营网点遍布城区.通过越库配送模式对其进行试验, 收集数据如下:

1) 19个供应商, 28个重百超市, 4个配送中心(各节点编号如图 6所示), 三者构成距离矩阵、时间矩阵, 在道路畅通的时间段, 可由百度地图导航驾车路线测得.

2) 各供应商供货量、重百超市需求量及其车辆装卸时间如表 3和表 4所示.

3) 送货过程中重百超市各类产品需求量及卸货时间如表 5所示.产品类型1由越库中心C₁、C₂分拣与重装, 产品类型2、3分别由越库中心C₃、C₄分拣与重装.

4) 调用厢式轻卡配送, 载量Q_k =4.49 t.调查获取单位距离油耗f_u=0.19 L / km, 燃油成本为重庆市0#柴油价格6.17元/ L, 集货、送货车辆操作成本分别是Fc_k=97元/次、F'c_k=105元/次.求得各配送区域集货、送货过程最优路径方案, 如表 6和表 7所示.

表 6中各越库中心集货车辆数可由车辆序号得到, 车载率最高达98 %.由路径编码可知, 以越库中心C₁为例, 其第2条子路径行车时间为52 min, 车辆访问供应商节点8、5、9, 装货42 min, 其子路径时间为上述之和, 即94 min.其路径成本=子路径长度×单位距离油耗×单位油耗价格, 综合成本由路径成本与操作成本构成, 为126.77元. 3条子路径中用时最长为(C₁-8-5-9-C₁), 由越库操作设定集货作业协同返回策略, 集货3台车辆返回越库中心的时间范围为[83, 94], 调用车辆先后顺序为车辆序号2、1、3.

表 7为送货车辆路径方案, 各超市由多个越库中心配送, 例如超市编号24的3条行车路径(C₂-42-45-47-46-24-C₂、C₃-23-24-22-21-40-C₃、C₄-24-C₄)由3个越库中心实施配送.超市编号42由越库中心C₃的车辆序号3和越库中心C₂的车辆序号1进行配送.用时最长子路径(C₄-25-40-38-37-26-27-39-36-41-C₄)为183 min, 也是访问超市节点最多的路径.由表 6和表 7可得, 集货、送货子路径最长时间分别为94 min、183 min, 合计277 min.由集货和送货过程各路径合计总成本为3 854.33元.综上, 整个越库配送网络可在一个工作日内完成, 配送时间方面有显著优势, 满足了终端销售时效性需要.在快速经济环境下, 越库作业提升了配送速度, 快速响应了超市的需求, 提高了服务质量; 越库作业使企业更能胜任多频次、少批量的供货要求, 形成了规模经济效益; 货物在越库中心有效整合、统一分拣, 实现“化零为整”, 既减少了车辆数量、配送次数, 又降低了配送难度, 也降低了配送成本, 达到配送效率提高和成本降低的双重效益.在供需双方的供应链纽带中, 配送中路径优化提高了供应链整体效益, 越库配送模式提升了企业协同效率, 带动了供应链中企业的市场竞争力, 开启了供应链各企业间的协作关系, 实现了效益最大化.

4.2 数值仿真

为进一步对算法进行测试, 本文结合文献[14]数据及算法进行对比分析, 数据参数值如表 8所示.数值分析部分通过单个越库区域的配送网络进行测试.

表 8是分别由10、30和50个节点组成的3类问题, 每类问题生成30个算例.在文献[14]的数值实验部分的3类问题中各选30个算例, 取各最优上限值(BUB)、下限值(BLB)和平均值(AVG)组成算例集, 通过本文的改进遗传算法对上述算例集进行求解, 与文献[14]中算法进行比较, 结果如表 9所示.

由表 9可知, 序号1(10-BUB-7)表示10个节点“问题1”的30个算例中, 各最优解数值最大的算例7为最优上限值.同理, 序号2(10-BLB-10)为“问题1”的30个算例中最优解数值的最小下限值, 序号3为“问题1”的30个算例最优解的平均值.算例中访问节点的规模变大时(如从序号4到序号9), 改进禁忌搜索算法和改进遗传算法均能取得较好效果.在求解质量上, 改进遗传算法通过有效改进策略增强了算法的搜索能力, 在多次求解中能得到较好的最优解, 改进遗传算法能有效获取本文问题的求解.

5 结论

本文对供应链环境下带越库配送的多配送中心车辆路径问题展开研究, 面对网购冲击, 零售实体着力于供应链集成化管理, 对供应商、配送中心进行有效整合, 提升竞争优势, 提高效益.应对零售业产品多样化需求, 建立集货过程车辆协同作业时间, 送货过程需求可拆分运作机制, 建立车辆运输成本和操作成本为目标的路径优化模型, 提出改进遗传算法.实例部分以重百超市进行仿真, 结果表明, 越库配送模式有效满足了超市及时供货, 在配送成本、时间方面有显著优势, 同时通过数值仿真部分对改进遗传算法性能进行了对比分析.此外, 随着零售业终端销售需求量的增加, 车辆的调用可通过租赁等形式, 车型的组合可实现多样化.因此, 接下来可考虑对相关问题进行研究.