您好, 访客   登录/注册

全渠道零售场景下配送车辆路径问题

来源:用户上传      作者:

  摘要:为研究全渠道零售的配送系统对企业物流成本的影响,综合考虑时间窗、车型选择等因素,以运输成本最低为目标,建立高度协同的全渠道零售场景下的物流配送模型。该模型采用自适应遗传算法求解,利用MATLAB进行算例分析。结果显示:全渠道零售模式下的车辆调度方案能迅速响应消费者需求,与一般配送模式相比可以减少物流成本,优化车辆配置。与粒子群优化算法相比,自适应遗传算法的运行时间更短、优化结果更好,这验证了模型和算法的可行性和有效性。
  关键词: 车辆路径问题(VRP); 自适应遗传算法; 全渠道零售; 协同配送; 多车型调度
  中图分类号: F252.3; F274    文献标志码: A
  Distribution vehicle routing problem in omni-channel retailing
  SHI Tianjiao, YANG Bin, ZHU Xiaolin
  (Institute of Logistics Science and Engineering, Shanghai Maritime University, Shanghai 201306, China)
  Abstract: In order to study the effect of the omni-channel retailling distribution system on the logistics cost of enterprises, considering the factors of time window, vehicle type selection and so on, a highly coordinated logistics distribution model under the omni-channel retailling is established with the objective of the minimum transportation cost. The model is solved by the adaptive genetic algorithm, and the example is analyzed by MATLAB. The results show that, the vehicle scheduling scheme under the omni-channel retailing mode can quickly respond to consumer demand, and can reduce the logistics cost and optimize the vehicle configuration compared with the general distribution mode. Compared with the particle swarm optimization algorithm, the adaptive genetic algorithm is of shorter running time and better optimization results, which verifies the feasibility and effectiveness of the model and algorithm.
  Key words: vehicle routing problem (VRP); adaptive genetic algorithm; omni-channel retailing; joint distribution; vehicle scheduling with multiple vehicle types
  0 引 言
   全渠道零售是指供应链企业之间资源共享,以消费者为中心的一种经营方式。贝恩全球零售合伙人RIGBY[1]于2011年提出,全渠道零售指零售商通过各个渠道与消费者进行互动,将不同渠道资源整合以提供无缝的消费服务的经营方式。企业通过深度学习、感测融合和射频识别等互联技术,满足消费者在家、学校、公司等不同场景下自由购物的需求,同时企业提供智能配送服务。全渠道零售有几个显著的特征:第一,全线,即全渠道覆盖电商渠道、实体店渠道和移动端渠道,实现线上线下的高度融合;第二,全程,即消费者在从接触商品到拥有商品的全过程中能实时掌握商品信息;第三,全面,即企业能追踪、分析消费者消费数据,与消费者互动,提供个性化建议,提升购物体验。
  国内外對全渠道零售的研究多集中在这几个方面:第一,文献[2-3]认为全渠道零售是当前零售业发展的必然趋势,同时需要企业确定相应的运营模式,从而提供更优质的服务;第二,文献[4-6]研究了全渠道零售的演化过程以及相应的区别,分析全渠道零售的含义与成因,并且建立相应的运营框架;第三,文献[7-8]指出了大数据时代的到来为零售业带来机遇和挑战,同时说明创新型技术对全渠道零售的重要性;第四,文献[9]利用经济模型提高企业的运营效率,利用贝叶斯模型进行需求预测,文献[10]利用Tobit回归进行战略规划;第五,文献[11]研究了全渠道零售中实体店的配送调度问题,建立了一个全渠道配送模型并进行了求解。
  车辆调度是全渠道零售的一个重要环节,对于车辆路径问题(vehicle routing problem, VRP)国内外学者有较多研究。文献[12]研究了多车型车辆调度问题,建立了以油耗最低为目标的模型,采用量子遗传算法进行了求解;文献[13]研究了需求拆分的多车型路径问题,使用了两阶段法求解;文献[14]研究了基础设施位置对异质车队车辆调度的影响;文献[15]研究了带时间窗的异质车队的车辆调度问题,将自适应大邻域搜索算法与遗传算法混合进行了求解;文献[16]研究了带时间窗的货物交付问题,考虑存在交付顺序的车辆调度问题。一般用智能算法,如禁忌搜索算法[17]、分支定界法[18]等求解VRP。   綜上,对于全渠道零售的研究,主要集中在定义、发展历程和运营模式等方面,很少考虑全线、全程、全面高度协同的物流配送问题。对于车辆调度问题的研究,主要集中在一般配送模式下的车辆调度研究,很少涉及全渠道配送模式下的车辆调度研究。本文在已有研究的基础上,针对全渠道零售全线、全程、全面的特点,建立高度协同的全渠道配送模型:各渠道信息共享、资源整合,对商品进行实时监控。中心仓库和线下实体店均可以向终端消费者进行配送服务,以全渠道运输成本最低为目标,综合考虑配送主体、时间约束和车型的匹配问题,优化配送策略。使用自适应遗传算法对算例进行求解,并且对比粒子群优化算法验证模型和算法的可行性。
  1 问题描述
  全渠道与单渠道、多渠道不同:第一,商品线上线下价格一致,促进线上线下融合,推动单向销售向双向销售互动转变;第二,全渠道零售数据共享,实现订单、库存、会员信息、营销等数据互融共通,为消费者提供无缝式的消费体验;第三,私人定制盛行,全渠道零售为消费者提供个性化定制服务,提高消费者购物体验。全渠道包含中心仓库、最后一公里网点和终端消费者3个主体:中心仓库指各渠道货物的存储点;最后一公里网点即线下实体店,包含旗舰店、体验店、便利店等;终端消费者可以在电商渠道、线下实体渠道或移动端等多个场景下进行下单购买。企业根据消费者要求提供配送到家服务或到店自提服务;企业在提供配送服务时,可以从共享仓库或实体店发货配送给终端消费者。企业基于互联网等大数据平台,通过全面分析消费数据,提供多样的消费服务,提升消费者消费体验,同时能实现线上线下各渠道全线的物流配送服务。企业和消费者能全程追踪商品物流信息,提高商品全过程流转的可视化程度。在全渠道零售场景下:企业综合考虑车型选择、时间窗等实际约束,采取资源高度整合的全渠道配送交付方式;线下实体店也可以对消费者进行配送,它相当于中心仓库的前置仓。中心仓库和实体店能共同为终端消费者服务。具体配送模式见图1。根据全渠道配送模式建立运输成本最低的整数规划模型,求解得出中心仓库与线下实体店同时配送的车辆配置及路径安排。
  2 数学模型
  2.1 模型假设和符号定义
  模型假设:(1)全渠道零售物流网络中,车辆从中心仓库出发并最终返回;(2)为保证服务质量,每个消费者的需求都会被满足,且每个消费者只能被访问一次;(3)每个消费者的地理位置、需求和配送时间窗已知。
  符号定义:W为中心仓库集,w为中心仓库数量;R为实体店集,r为实体店数量;C为消费者集,c为消费者数量;N为所有节点集,N=W∪R∪C;A为弧集,A={(i, j)i, j∈N,i≠j};tie为允许车辆到达节点i的最早时刻;ti1为允许车辆到达节点i的最晚时刻;dij为节点i与j之间的距离;tij为车辆从节点i到j的运输时间;oi为车辆在节点i处的装卸时间;Sil为车辆l在节点i处开始服务的时间;V为车辆类型集,V={1,2,…,M},m∈V;Bm为m型车的集合,Bm={1,2,…,l,…,km};Cm为m型车的单位运输价格;fm为使用m型车的单位固定成本;Qm为m型车的容量;Qi为车辆到达节点i时的剩余容量;Ii为节点i的库存; Di为节点i的配送需求;3个0-1变量如下。
   xijml=1, 第l辆m型车从节点i到节点j
  0, 其他
   yijml=1, 消费者j的需求由中心仓库i配送
  0, 其他
   zijml=1, 消费者j的需求由实体店i配送
  0, 其他
  2.2 模型建立
   建立的模型如下,其中m∈V,l∈Bm。
  min FF=mlfmi∈Nj∈Nxijml+
  i∈Nj∈NmlxijmldijCm
  (1)
  s.t.
  i∈Nmlxijml=1, j∈R∪C
  (2)
  j∈Nxijml=1, i∈W
  (3)
  i∈Nxiqml-j∈Nxqjml=0, q∈N
  (4)
  i∈Nxijml=1, j∈W
  (5)
  i∈Wyijml+i∈Rzijml=1, j∈R∪C
  (6)
  j∈CzijmlDj≤Ii, i∈R
  (7)
  yijmlq∈Nxiqml-q∈Nxqjml=0,
  i∈W, j∈R∪C
  (8)
  zijmlq∈Nxiqml-q∈Nxqjml=0,
  i∈R, j∈C
  (9)
  Sjl≥Sil+tij+oixijml, i∈N, j∈N
  (10)
  Sjl≥Sil+tij+oiyijml,
  i∈W, j∈R∪C
  (11)
  Sjl≥Sil+tij+oizijml, i∈R, j∈C
  (12)
  tie≤Si≤ti1
  (13)
  Qm≥Qi≥ Qj+Dj xijml, i∈N, j∈N
  (14)
  j∈R∪CyijmlDj≤Qm, i∈W
  (15)
  Qi+j∈CzijmlDj≤Qm, i∈R
  (16)
  xijml∈{0,1}, i∈N, j∈N
  (17)
  yijml∈{0,1}, i∈W, j∈R∪C
  (18)
  zijml∈{0,1}, i∈R, j∈C   (19)
   式(1)表示目标函数为运输成本最低,包含固定成本和可变成本两个部分;式(2)表示要满足每个消费者的需求,且每个消费者只由一个中心仓库的一辆车进行服务;式(3)~(5)表示车辆从中心仓库出发并且返回中心仓库,同时遵守车流量守恒原则;式(6)表示中心仓库和实体店共同完成对终端消费者的物流配送服务,这体现了全渠道零售场景下线上线下各渠道共同配送的显著特点;式(7)表示实体店配送量小于该店库存量;式(8)和(9)表示车辆访问顺序,若终端消费者由实体店配送,则车辆必须先到实体店取货,再服务终端消费者,即线下实体店在全渠道零售场景下可以作为企业的前置仓库向终端消费者提供服务;式(10)~(12)表示时间限制,若终端消费者由实体店配送,则车辆到达实体店的时间必早于到达消费者的时间;式(13)表示时间窗限制;式(14)~(16)表示车辆容量限制,在全渠道零售场景下,企业对车辆进行全程控制,严格控制容量;式(17)~(19)表示0-1决策变量。
  上述模型为非线性数学模型,属于NP難问题,故将模型进行线性化处理确保解的存在性,使模型可以使用LINGO求解。将式(8)和(9)转化为式(20)~(23),式(10)、(11)、(12)和(14)转化为式(24)~(27)。q∈Nxiqml-q∈Nxqjml≤1-yijmlM,
  i∈W, j∈R∪C
  (20)
  q∈Nxqjml-xiqml≤1-yijmlM,
  i∈W, j∈R∪C
  (21)
  q∈Nxiqml-xqjml=1-zijmlM,
  i∈R, j∈C
  (22)
  q∈Nxqjml-q∈Nxiqml=1-zijmlM,
  i∈R, j∈C
  (23)
  Sil+tij+oi-Sjl≤1-xijmlM,
  i∈N, j∈N
  (24)
  Sil+tij+oi-Sjl≤1-yijmlM,
  i∈N, j∈N
  (25)
  Sil+tij+oi-Sjl≤1-zijmlM,
  i∈N, j∈N
  (26)
  Qj+Dj-Qi≤1-xijmlM,
  i∈N, j∈N
  (27)3 算法设计
   遗传算法是运用计算机模拟生物进化过程来寻找最优解的随机搜索算法。它在1969由Holland教授提出,被广泛应用于求解NP难组合问题以及数学模型比较复杂的最优化问题。本文为更好地提高遗传算法的收敛速度,采用自适应遗传算法,采用Srinvas等提出的公式,线性调整交叉概率和变异概率。
  (1)编码及初始种群。采用自然数编码方式,用1到w+r+c表示各节点,其中1到w表示中心仓库,w+1到w+r表示实体店,w+r+1到w+r+c表示需要配送的消费者。染色体的每个基因位值表示各节点编号,其基因顺序代表车辆访问的实际顺序。为弄清楚每条子路线由哪种类型的车进行配送,编码时加入一自然数,表示每条子路径所使用的车辆车型。如图2所示,车辆从节点1出发并且最后返回到节点1,其间依次经过节点3、5、7、9、2、4、6,同时选择的车型为第一类。
   (2)适应度函数的设计。本文求解的目标是运输成本最小,故定义适应度函数为fi=1/Fi,其中Fi表示第i条染色体的目标函数值。
  (3)遗传操作设计。遗传操作主要包括:选择操作,采用轮盘赌选择方法;交叉操作,采用顺序交叉;变异操作,采用逆转变异。
  (4)自适应交叉与变异概率设置。本文在交叉与变异操作过程中采用自适应策略进行调整,设交叉概率为pc,变异概率为pm。fmax为种群最大的适应度函数值;favg为种群平均的适应度函数值;f为两个交叉个体中较大的适应度值;f′为变异个体的适应度值;k1、k2、k3和k4为常数。计算公式如下:
   pc=k1(fmax-f)/(fmax-favg),f≥favg
  k2,f
  pm=k3(fmax-f′)/(fmax-favg),f′≥favg
  k4,f′
  为方便计算,本文设定pc1=0.8,pc2=0.4,pm1=0.2,pm2=0.1。
  (5)终止条件。当算法运行到最大迭代次数或者最优个体的适应度函数值等于种群平均适应度函数值时,算法运行结束,输出最优的配送调度方案。
  4 案例分析
  为验证模型和算法的有效性,引用Solomon基本数据库(http://neumann.hec.ca/chairedistributi-que/data/)中的算例,利用30个终端客户的信息进行具体的求解分析。表1为车型信息,表2为中心仓库和实体店的信息,表3为30个消费者的相关信息。企业拥有1个中心仓库、3个线下实体店和30个需要配送的消费者,车辆行驶速度为30 km/h。中心仓库和实体店的时间窗为[6:00,18:00],消费者的时间窗为[8:00,18:00],车辆的装载时间取[0,1 h]的随机数。使用自适应遗传算法求解,参数设置如下:初始种群=100,最大迭代次数=1 000,pc1=0.8,pc2=0.4,pm1=0.2,pm2=0.1。使用MATLAB进行运算。
   为验证全渠道配送模式的有效性,首先进行第一部分的实验。假设实体店的库存满足线上线下需要配送的终端消费者的需求,进行3个对比实验。实验1采用一般配送模式:线上线下终端消费者需求全部由中心仓库进行配送。实验2采用相对协同的配送模式:所有终端消费者需求全部由线下实体店进行配送,线下实体店相当于零售企业的前置仓,具有仓储配送功能。实验3为高度整合的全渠道配送模式:中心仓库、线下实体店联合配送。各实验运输成本见表4。实验3的配送路径见表5,其中第4辆车的配送路径见图3。    从表1~5和图3可以看出:实验3采用全渠道配送模式,其运输成本最低,为1 639元,配送效果最佳;其他2种配送模式所产生的运输成本较高;3个实验都需要2种车型进行配送,实验1所需要的车辆数量最多(7辆),实验2和实验3所使用的车辆数量是一样的(4辆),但是实验2的运输成本比实验3的高。因此,全渠道配送模式的效果比较好。
  为验证消费者时间窗对车辆路径策略的影响,对其进行调整使其在[8:00,18:00]中随机产生。调整后的配送策略如下:采用2辆车型为1的车辆和4辆车型为2的车辆,运输成本为1 856元,比之前增加了217元,多使用了2辆车。具体的配送路径见图4。
   为进一步验证模型和算法的有效性,本文將自适应遗传算法与粒子群优化算法进行对比,得出自适应遗传算法在求解大规模(w=2,r=5,c=50)问题时,其运行时间比粒子群优化算法的运行时间少10 s,而且最终的方案比利用粒子群优化算法得到的方案更优,运输成本减少了29.2%,具体对比结果见表6。利用本算法求解不同规模的算例,均可得到相应的解,验证了算法的可行性,具体结果见表7。
   综上,从运输成本看,全渠道配送模式下的运输成本比一般配送模式下的运输成本低,且需要的车辆数量减少。需求点配送紧急程度越高,所需的运输成本就越高,需要的车辆数量就越多。
  从求解规模看:一方面自适应遗传算法能求解大规模问题,求解效果良好;另一方面,在进行大规模问题求解时,自适应遗传算法的运行速度比粒子群优化算法的快,需要车辆数量少,运输成本大幅降低,算法可行性和适用性好。
  5 结 论
  本文研究高度协同的全渠道零售场景下的车辆路径问题,考虑配送过程时间窗限制、车型选择等因素,建立运输成本最低的车辆路径模型,同时采用自适应遗传算法和MATLAB对算例进行分析求解。对比不同资源配置方案得到全渠道零售场景下的配送路径策略最佳的结论;利用自适应遗传算法进行大规模问题求解,有效论证该算法的实用性,同时与粒子群优化算法对比得到自适应遗传算法求解较快、优化结果较好的结论,有效论证了模型和算法的可行性和适用性。企业可以基于全渠道配送模式,充分发挥线下实体店的前置仓功能,与中心仓库共同向终端消费者配送,优化中心仓库和实体店的库存量,加速库存流转。企业可以配置多车型车辆,根据货物的需求量,选择相适应的车型进行配送,减少车辆使用总数,提高车辆利用率。在全渠道零售场景下,企业可以根据消费点的需求和配送距离选择相应的配送点和车型。企业通过采用全渠道配送模式,快速响应市场消费需求,优化车辆配置,降低物流成本。随着大数据时代的到来,全渠道零售成为零售业发展的必然趋势,运用全渠道配送模式能有效降低成本和快速响应市场需求。
  本文只考虑确定性状态下全渠道配送车辆调度问题,没有考虑物流配送过程中的不确定情况,比如天气情况、交通事故等造成运输时间的不确定等,没有考虑消费者需求变化对最终方案的影响,这些都是实际存在的情况,也是全渠道零售企业配送过程中不容忽视的问题,这将是下一步的研究方向。
  参考文献:
  [1] RIGBY D K. The future of shopping[J]. Harvard Business Review, 2011(12): 64-75.
  [2] 马慧敏. 移动互联时代我国零售企业全渠道模式的应用[J]. 中国流通经济, 2017, 31(4): 10-16. DOI: 10.14089/j.cnki.cn11-3664/f.2017.04.002.
  [3] VEHRHOEF P C, KANNAN P K, INMAN J J. From multi-channel retailing to omni-channel retailing: introduction to the special issue on multi-channel retailing[J]. Journal of Retailing, 2015, 91(2): 174181. DOI: 10.1016/j.jretai.2015.02.005.
  [4] 李飞. 全渠道营销理论: 三论迎接中国多渠道零售革命风暴[J]. 北京工商大学学报(社会科学版), 2014, 29(3): 1-12.
  [5] 李飞. 全渠道零售的含义、成因及对策: 再论迎接中国多渠道零售革命风暴[J]. 北京工商大学学报(社会科学版), 2013, 28(2): 1-11.
  [6] SAGHIRI S, WILDING R, MENA C, et al. Toward a three-dimensional framework for omni-channel[J]. Journal of Business Research, 2017, 77: 53-67. DOI: 10.1016/j.jbusres.2017.03.025.
  [7] 刘煜, 刘遗志, 汤定娜. 互联网时代零售企业构建全渠道商业模式的探讨[J]. 北京工商大学学报(社会科学版), 2016, 31(6): 34-42. DOI: 10.16299/j.1009-6116.2016.06.005.
  [8] PIOTROWICE W, CUTHBERTSON R. Introduction to the special issue: information technology in retail: toward omni-channel retailing[J]. International Journal of Electronic Commerce, 2014, 18(4): 5-16. DOI: 10.2753/JEC1086-4415180400.   [9] 计国君, 余木红, KIM H T.大数据驱动下的全渠道供应链服务创新决策框架[J]. 商业研究, 2016(8): 152-162. DOI: 10.13902/j.cnki.syyj.2016.08.019.
  [10] 黄漫宇, 李圆颖. 零售企业全渠道发展水平对经营效率的影响路径及效应研究[J]. 北京工商大学学报(社会科学版), 2017, 32(6): 35-44. DOI: 10.16299/j.1009-6116.2017.06.005.
  [11] ABDULKADER M M S, GAJPAL Y, MEKKAWY T Y. Vehicle routing problem in omni-channel retailing distribution systems[J]. International Journal of Production Economics, 2018, 196: 43-55. DOI: 10.1016/j.ijpe. 2017.11.011.
  [12] 葛显龙, 许茂增, 王伟鑫. 多车型车辆路径问题的量子遗传算法研究[J]. 中国管理科学, 2013, 21(1): 125-133.
  [13] 潘雯雯, 郭海湘, 周光勇, 等. 基于两阶段算法的需求可拆分多车型车辆路径问题[J]. 中国管理科学, 2016, 24(s1): 55-61.
  [14] MARKOV I, VARONE S, BIERLAIRE M. Integrating a hetero-geneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities[J]. Transportation Research Part B, 2016, 84: 256-273. DOI: 10.1016/j.trb.2015.12.004.
  [15] KO , BEKTA 瘙 塁  T, JABALI O, et al. The fleet size and mix location-routing problem with time windows: formulations and a heuristic algorithm[J]. European Journal of Operational Research, 2015, 248(1): 33-51. DOI: 10.1016/j.ejor.2015.06.082.
  [16] NACCACHE S, CT J-F, COELHO L C. The multi-pickup and delivery problem with time windows[J]. European Journal of Operational Research, 2018, 269(1): 353-362. DOI: 10.1016/j.ejor.2018.01.035.
  [17] SCHNEIDER M. The vehicle-routing problem with time windows and driver-specific times[J]. European Journal of Operational Research, 2016, 250(1): 101-109. DOI: 10.1016/j.ejor.2015. 09.015.
  [18] OZBAYGIN G, KARASAN O E, SAVELSBERGH M, et al. A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations[J]. Transportation Research Part B, 2017, 100: 115-137. DOI: 10.1016/j.trb. 2017.02.003.
  (編辑 赵勉)
  收稿日期: 2019- 03- 17 修回日期: 2019- 05- 24
  基金项目: 国家自然科学基金(71471109)
  作者简介: 施天娇(1995—),女,江苏启东人,硕士研究生,研究方向为全渠道物流,(E-mail)tianjiaos806@sina.com;
  杨斌(1975—),男,山东招远人,教授,博导,博士,研究方向为物流与供应链管理,(E-mail)binyang@shmtu.edu.cn
转载注明来源:https://www.xzbu.com/4/view-15301994.htm