1. 引言
随着人们生活水平的提高,对服装的需求也日益增加。在运输服装时,需要采取适当的运输条件来保护其不受损。同时,采用合理的装箱方案以提高车厢的空间利用率也十分必要[1] [2]。快时尚服装品牌如ZARA、H&M等,拥有众多零售门店,由于需要保持频繁的新品上市,高频的服装配送导致了大量的能源消耗。为减少对环境的污染、提高企业形象,这些服装企业逐渐开始使用电动汽车配送,这也符合我国碳达峰碳中和的目标[3]。电动汽车的补电方式包括快速充电、慢速充电和换电,其中换电的速度最快,能在5分钟内完成补电,可以最大程度减少物流配送时的等待时间。但由于基建成本高昂等原因,换电模式在我国物流配送行业还有待进一步推广[4]。
电池占电动汽车的价值比重约40%,减少电池损伤、延缓电池老化能延长电动汽车的使用价值。当电量低于某个阈值继续放电,即为深度放电。深度放电时对电池的损伤急剧增加,会加快电池老化,缩短电池寿命[5]。在“车电分离”的销售模式中,消费者只支付裸车的购买费用,电池采用从换电服务商处租赁的方式。这种模式能够降低物流企业的购车成本,减少物流企业的购车顾虑。换电服务商拥有电池所有权并承担相应的电池维护费用。本文对此情形下使用换电式电动汽车进行服装配送时的路径规划进行了研究。
在电动车辆路径问题(Electric Vehicle Routing Problem, EVRP)研究中,张佳佳等[6]假设在配送客户点允许进行边服务客户边进行充电作业,在此基础上添加了软时间窗约束,建立了以总配送成本最小为目标的模型,使用粒子群算法并结合实际案例进行优化求解。周鲜成等[7]考虑车辆时变速度和实时载重等因素对电动汽车能耗的影响,采用非线性能耗模型测度能耗。周筝等[8]提出了一种多因素下基于充电站路网拓扑结构的电动汽车充电路径规划方法,为用户规划充电路径与充电站选择。程坦等[9]的研究表明了部分充电策略提升了配送效率和车辆满载率。Kim等[10]研究了电池充放电状态对充放电速率的影响,开发了非线性充放电函数,数值实验得出对最佳充电方式的见解。Ren等[11]提出在电动汽车电量低时使用换电车提供移动电池交换服务,建立了混合整数规划模型,设计了一种基于Q-learning的大邻域搜索算法。上述研究所取得的成果显著拓展了电动车辆路径问题(EVRP)的研究范畴并深化了对该领域的理解,但针对采用换电模式的EVRP问题的研究尚显匮乏,因此本研究明确将换电型EVRP确立为研究焦点。
对于商品配送的研究,王勇等[12]针对当前生鲜商品配送效率低和成本高等问题,采用车仓温度可控的多仓车辆作为配送装备,并结合时间窗等约束,研究基于时间窗和多仓温控的生鲜商品配送车辆路径优化问题。李亚琴等[13]在物资供应点分配的基础上,构建了洪灾情景下的应急物资配送路径优化方法。姜广田等[14]通过预优化和动态调整两阶段来研究商品配送问题。尽管现有研究已对各类商品的配送问题进行了广泛探讨,然而针对服装配送这一特定领域,尤其是其在物流配送系统中的独特属性与需求,相关研究却相对匮乏。
综上,本研究专注于采用换电式电动汽车对服装门店进行配送这一核心问题,创新点如下:1) 构造了符合服装运输要求的装箱方案,并将其加入车辆路径规划模型中。2) 以“车电分离”模式为背景,采用分级定价和达到深度放电阈值前前往换电站换电的策略,构造换电模式下服装配送的电动车辆路径规划模型。3) 根据模型设计改进蚁群算法,结合实际路网和服装品牌配送数据求解模型,并将结果与不考虑深度放电时的结果进行对比,证明了该模型的合理性和有效性。
2. 模型构建
2.1. 问题描述与模型假设
本文建立的服装配送模型是由若干个门店、若干个换电站和一个配送中心构成的二级服装供应链网络。本文中服装配送车辆的补电方式为换电和慢充相结合,为了在配送时能及时完成配送任务,采用换电模式补电;而慢充需要大量时间但价格较低,适合在没有紧急需求时进行,利用车辆在配送中心的闲置时间采用慢充的方式补电,这样车辆在下次出发时就能保持满电状态。此外,根据供求关系,价格会影响产品或服务的需求水平。因此,调整电池更换时深度放电后的电价水平,使深度放电前后的电价产生差异,有助于激励消费者有意识地避免深度放电,从而达到减少电池损伤的目的。本文的服装配送示意图如图1。
配送网络可以表示为无向图
。门店节点集合表示为
,换电站节点集合表示为
,服装配送车辆集合表示为
。F表示节点集,节点0表示配送中心,则
。V表示弧集,
。决策变量包括xijk:0~1变量,其值为1表示服
装配送车辆k从节点i行驶至下一个节点j,否则为0;yik:0~1变量,其值为1表示门店i的配货由服装配送车辆k完成,否则为0;Tk:0~1变量,其值为1表示服装配送车辆k到达换电站时电量高于深度放电阈值,否则为0。
为使研究问题贴近现实及便于研究,对模型做出以下假设:1) 服装配送车辆从配送中心出发时,装载服装的总装载空间不能超过车厢限制,装载载重量不能超过服装配送车辆最大载重;2) 任一服装配送车辆进行配送任务时,当预估到下一个配送门店或配送中心时服装配送车辆电量会低于深度放电临界点时,不再继续配送任务,需去往换电站换电;3) 每个换电站每天可满足服装配送车辆不限次数的访问;4) 服装配送车辆满电状态下,电池电量可以满足任意两节点之间的配送需求;5) 每个门店配货量必须得到满足,每个门店只能由一辆车配送一次;6) 服装配送车辆从配送中心出发,完成配送任务后需返回配送中心;7) 配送均在一天的工作时间内完成;8) 服装配送车辆返回配送中心后采用慢充方式补满电。
Figure 1. Schematic diagram of garment distribution for battery replacement before deep discharge
图1. 深度放电前换电的服装配送示意图
2.2. 服装装载说明
服装运输不同于一般的货物,一些服装品类如风衣、衬衫等不能折叠,需要悬挂运输。而能折叠的服装一般使用包装箱打包。故运输时将服装分为两类,车厢通常为长方体,假设其长、宽、高分别为L、W、H,按其宽分为两部分,分别用于放置悬挂服装和装箱服装。用于放置包装箱的宽度为y1,用于放置悬挂服装的宽度为y2,
。包装箱均为同样大小的正方体,边长为a,装满时的平均重量为wm。每辆车最多可以放置的包装箱数量为
。([ ]表示取整,下同。)采用悬挂运输的服装长度均小于H,宽度为z,厚度为t,每件平均重量为w0。则每辆车最多可以放置的悬挂服装的数量为
。服装配送车辆最大载重量为qL。分别用ui表示门店i需要的悬挂服装数量,ci表示门店i需要的包装箱数量。wi表示门店所需服装的总重。使用服装配送车辆数目计算公式为:
(1)
实际情况下,由于服装产品的重量较轻,装车时重量通常不会超过限制,使用服装配送车辆数目主要受服装装载体积的限制。
2.3. 目标函数设计
本文目标函数为最小化总运输成本,总运输成本包括一项与行驶路程和载重变化等行驶变化因素无关的固定成本,和三项与行驶变化因素相关的变动成本:折旧和维护费用、换电成本、慢充成本。
2.3.1. 固定成本
固定成本是指与行驶距离无关的成本,包括司机工资、车辆管理费、车辆电池租赁费。
固定成本的计算公式为:
(2)
ks表示使用服装配送车辆数,cF表示一辆服装配送车辆一天所花费的固定成本。
2.3.2. 折旧和维护成本
服装配送车辆折旧和维护成本的计算公式为:
(3)
f表示服装配送车辆行驶每公里的折旧成本,e表示服装配送车辆行驶每公里的维护成本。
2.3.3. 换电成本
电量消耗的计算本文采用文献[15]的计算方法,电动物流车能耗基本由车辆速度、车辆总质量以及地形坡度三个主要因素决定,其中车辆总质量
,qijk表示车辆k在弧(i,j)上的载重,L0为车辆自重;分三个步骤来计算总质量为mijk的服装配送车辆k在弧(i,j)上的能耗Eijk(mijk):首先计算服装配送车辆所需的动力pF,然后计算相应的电力pE,最后计算电池需要消耗的电量Eijk(mijk)。
(4)
(5)
(6)
(7)
其中
表示pF和pE之间的转换系数,
表示电池效率,dij表示弧(i,j)之间的距离,vij表示服装配送车辆在弧(i,j)上的速度,
表示服装配送车辆在弧(i,j)上所需的动力,tij表示服装配送车辆在弧(i,j)上的行驶时间,cr和cd分别表示滚动摩擦系数和空气阻力系数,
表示空气密度,A表示服装配送车辆前侧表面积,g表示地球引力常数,mijk表示服装配送车辆k在弧(i,j)上的总质量,
表示地形坡度。
研究表明[16],电动汽车长时间深度放电对电池损伤极大,长时间深度放电会导致电池寿命大幅下降。换电模式下,电池损伤造成的成本由换电服务商承担,物流配送商只需承担换电成本。目前换电服务商普遍采用所有消耗电量按统一的收费标准收费。制定合理的价格策略可以减少深度放电、减少电池损伤,促进换电市场的发展。因此本文中未深度放电用电量和深度放电后用电量采用不同的收费标准。
未深度放电时,换电成本只包括未深度放电的电费;深度放电后,换电成本包括为未深度放电的电费和深度放电的电费两部分。换电成本的计算公式为:
(8)
B表示电池满电时的电量,
表示电池深度放电阈值点,
表示服装配送车辆k到达i点的电量,
表示服装配送车辆k离开i点的电量,t1表示深度放电阈值以上消耗电量的单位换电价格,t2表示深度放电阈值以下消耗电量的单位换电价格,s表示单位换电服务价格。
2.3.4. 慢充成本
服装配送车辆回到配送中心后,需要把电池电量采用慢充的方式补满,以保证服装配送车辆在下次出发时保持满电状态。慢充成本的计算公式为:
(9)
t3表示慢充时的单位电价。
2.4. 模型建立
(10)
s.t.
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
(21)
(22)
(23)
式(10)表示最小化总运输成本;式(11)表示运输时每个节点后只有一个后续节,可为门店、换电站或配送中心;式(12)表示服装配送车辆的载重不能超过其最大载重量;式(13)和式(14)为服装配送车辆装载货物的空间限制;式(15)表示每个门店只被一辆车配送一次;式(16)表示从配送中心出发的车必须回到配送中心;式(17)表示预测服装配送车辆电量到下一门店时会低于深度放电阙值,不继续进行配送任务;式(18)表示服装配送车辆载重变化;式(19)表示服装配送车辆配送过程中电池电量情况;式(20)表示服装配送车辆进入换电站换电后以满电状态离开;式(21)表示服装配送车辆以满电状态从配送中心和换电站出发;式(22)表示服装配送车辆在门店卸货时不进行补电;式(23)淘汰不经过配送中心的子回路。
3. GA-ACO算法设计
为求解本文模型,设计GA-ACO算法来求解。蚁群算法(Ant Colony Optimization,简称ACO)是一种模拟蚂蚁寻找食物的行为而设计的启发式算法。蚁群算法的基本步骤包括初始化信息素、模拟蚂蚁的移动、更新信息素以及重复若干次迭代。蚁群算法具有局部搜索能力强的特点,但前期可能由于搜索范围小,陷入局部最优解。遗传算法具有很强的全局搜索能力,因此本文先使用遗传算法构造初始信息素浓度。图2为GA-ACO算法流程图。
Figure 2. Flow chart of the GA-ACO algorithm
图2. GA-ACO算法流程图
3.1. 初始信息素分布
遗传算法能够在大范围内并行搜索,具有较强的全局寻优能力和跳出局部最优的能力。使用遗传算法进行初始信息素分布的操作步骤如下:
1) 输入参数:种群数目、最大迭代次数、交叉概率、变异概率等。
2) 初始化种群。假设种群数目为NIND,门店数目为N,配送中心最多允许T辆车进行配送,那么初始种群中任意一个个体都是1~(N + T − 1)的随机排列,其中N + 1~N + T − 1为将各条配送路径分开的数字,无实际意义。
3) 选择操作。使用轮盘赌法选择出适应度较高的Nsel个个体。
4) 交叉操作。找出两个个体的相同位置的片段,把片段分别交换到两个个体的前面,然后从前到后把两个个体中重复的基因位删除,形成新个体。
5) 变异操作。把一个个体上随机两处基因进行交换。
6) 重组。从父代种群中找出适应值排在前NIND-Nsel位的NIND-Nsel个个体,加入子代种群中。
7) 计算种群适应度,找出全局最优个体。若未达到最大迭代次数,重复(1)~(7);若达到最大迭代次数,进行(8)。
8) 对蚁群算法初始信息素浓度分布进行设置:
(24)
式中
表示初始信息素,Q表示信息素总量,
表示最优个体所有路径总长,
表示最优个体包括的边的集合。
3.2. 状态转移概率的设计
状态转移是指从当前点到下一个点。在设置状态转移概率时,要尽可能使电量消耗少、行驶路程短才能使总成本最低。由经验可知,优先选择配送量大的门店配送,可以减少服装配送车辆载重,减少电动物流车电量的消耗。因此将服装配送车辆行驶路径距离和门店配送量作为启发性因子引入状态转移概率计算公式。令
。设式作为蚂蚁状态转移规则:
(25)
表示蚂蚁q位于客户点i时接下来可以进行配送的门店集合,
表示当蚂蚁q在点i处时,离i点越近、门店配送量越多、信息素浓度越大的节点j越容易被选择,
表示蚂蚁在路径(i,j)上所释放的信息素浓度的大小,
表示蚂蚁在点i处可选择的门店j的配送量。
表示对每个节点上信息素重视的程度,
,
的大小表示启发信息受重视的程度。
3.3. 信息素更新策略
信息素浓度更新机制为
(26)
(27)
(28)
其中
表示信息素挥发程度,
表示所有蚂蚁在门店i到门店j路径上释放的信息素浓度之和,
表示蚂蚁k在门店i到门店j路径上释放的信息素浓度,Q表示信息素常数,
表示蚂蚁k所走的路径总长。
4. 实例求解与分析
4.1. 实例数据
为验证GA-ACO算法解决服装配送电动车辆路径规划模型的效果,以上海某服装品牌位置作实证分析。由于目前还没有电动物流车换电站设施,所以采用常用的某品牌换电站位置作为电动物流车换电站建设地址。上海该服装品牌门店分布较为稀疏,因此设置10个距离门店最近的换电站方便司机进行换电。根据实际路网,在百度地图中找到各门店、换电站和配送中心位置,如图3,并得到各门店、换电站和配送中心位置之间的车行道路线距离(两点间往返距离不同,则取其中较短的距离)。
Figure 3. Location map of stores, battery swap stations, and distribution centers
图3. 各门店、换电站和配送中心位置分布图
本文所用的实验算例样本是由1个配送中心、10个换电站和17个服装门店客户点组成,可以表示为
,
。门店配送量采用该服装企业某次配送的各门店所需服装相关数据,如表1。
Table 1. Table of quantities and weights of garments required for each store
表1. 各门店所需服装的数量和重量表
门店序号 |
需求量/(t) |
件数 |
箱子数 |
1 |
0.062 |
27 |
7 |
2 |
0.074 |
29 |
9 |
3 |
0.080 |
30 |
10 |
4 |
0.064 |
24 |
8 |
5 |
0.061 |
26 |
7 |
6 |
0.052 |
22 |
6 |
7 |
0.049 |
24 |
5 |
8 |
0.064 |
24 |
8 |
9 |
0.073 |
28 |
9 |
10 |
0.075 |
25 |
10 |
11 |
0.056 |
26 |
6 |
12 |
0.062 |
27 |
7 |
13 |
0.051 |
21 |
6 |
14 |
0.072 |
22 |
10 |
15 |
0.073 |
28 |
9 |
16 |
0.048 |
23 |
5 |
17 |
0.069 |
29 |
8 |
注:件数表示悬挂服装件数,箱子数表示折叠服装装箱后的箱子数量。
实地考察上海某物流配送商使用的配送电动物流车类型,获得如下服装配送车辆货厢相关具体参数以及相关服装配送车辆行驶参数:L0 = 1.73 t,qL = 2.7 t,L = 4.3 m,W = 2.1 m,H = 1.95 m,y1 = 1.1 m,y2 = 1 m,
,
,cr = 0.01,cd = 0.7,
kg/m3,A = 9.03 m2,v = 50 km/h,g = 9.81 m/s2,
,B = 35 kWh,
。装载服装相关参数:a = 0.5 m,wm = 5 kg,z = 0.05 m,t = 0.45 m,w0 = 1 kg。价格参数根据实际调查合理设 计为:cF = 400元/辆,f = 1元/km,e = 0.4元/km,t1 = 1元/kWh,t2 = 2元/kWh,s = 0.4元/kWh,t3 = 0.8元/kWh。
采用本文设计的ACO算法求解服装配送的最优路径方案,相关参数设置如下:遗传算法中种群数目NIND = 50,子代数目Nsel = NIND*0.9 = 45,最大迭代次数为100,交叉概率为0.9,变异概率为0.05,蚁群算法中
,
,
,
,
,Q = 5,最大迭代次数Ncmax = 100,蚂蚁数量定为30。
在实验所用硬件环境为Intel (R) Core (TM) i5-8250U CPU@1.60 GHz,8.0 GB内存,64位Windows11操作系统的情况下应用MATLAB R2018b编程求解。
4.2. 实验结果
结果取运行程序10次的最优解,最优解的求解时间为12.57秒。得到的最优服装配送车辆路径规划图,如下图4。最优配送方案如表2。
Figure 4. Optimal vehicle routing planning diagram using ACO
图4. 采用ACO的最优服装配送车辆路径规划图
Table 2. Optimal distribution solution with ACO
表2. 采用ACO的最优配送方案
车辆序号 |
配送方案 |
1 |
0→8→9→4→7→16→3→0 |
2 |
0→1→2→17→13→10→6→0 |
3 |
0→11→15→25→12→5→14→0 |
由表2可知服装配送车辆3在配送时经过25号换电站进行换电。从图4可以看出,服装配送车辆每次均选择离自己较近的门店进行配送,且三条路线分配得当。求得服装配送车辆使用数目为3辆,服装配送车辆行驶总距离为197.78 km,深度放电距离为0。总成本为1539.12元,包括固定成本1200元,折旧和维护成本276.89元,换电成本32.72元,慢充成本29.51元。证明该模型与算法对解决服装配送问题具有可行性,能够应对实际需求。
4.3. 算法对比
Figure 5. Convergence comparison plot of ACO algorithm versus GA-ACO algorithm
图5. ACO算法与GA-ACO算法的迭代收敛对比图
同样使用传统ACO算法对上面的算例进行了求解,两种算法的迭代收敛图如图5所示。从图5中可以看出,GA-ACO算法的初始解明显好于ACO算法的初始解,GA-ACO算法较快达到最优解,ACO算法则出现了较久的停滞才达到最优解,GA-ACO的最优解也好于ACO算法的最优解。通过以上的对比观察可以看出GA-ACO算法对求解本文模型展现出更为出色的性能。
4.4. 与不考虑深度放电模型的效果对比
上文模型要求在达到深度放电阈值前前往换电站换电(记为策略1)。通过与只要求电动汽车能完成配送任务,不考虑深度放电(记为策略2)时的结果对比分析,来验证该模型是否能降低配送成本。
根据经验,司机在驾驶时通常会保留能行驶到换电站的电量,即为Z。不考虑深度放电策略:将上文模型中式改为:
(29)
其他条件及参数不变,使用GA-ACO算法求解,同样取程序运行10次的最优解,结果与本文模型的计算结果进行对比,得到表3。
Table 3. Comparison of the results of strategy 1 and strategy 2
表3. 策略1与策略2结果对比
名称 |
策略1 |
策略2 |
车辆数 |
3 |
3 |
总距离(km) |
197.78 |
193.93 |
深度放电距离(km) |
0 |
9.51 |
总运输成本(元) |
1539.12 |
1597.15 |
固定成本(元) |
1200 |
1200 |
折旧和维护成本(元) |
276.89 |
271.50 |
换电成本(元) |
32.72 |
94.30 |
慢充成本(元) |
29.51 |
31.35 |
Table 4. The optimization effect of strategy 1 compared to strategy 2
表4. 采取策略1相比于策略2的优化效果
名称 |
减少量 |
减少百分比 |
深度放电距离(km) |
9.51 |
|
总运输成本(元) |
58.03 |
3.63% |
换电成本(元) |
61.58 |
65.3% |
从表3和表4中可以看出,采取策略1时深度放电距离为0,采取策略2时深度放电距离为9.52 km,使用策略1比策略2行驶总距离增加了3.85 km,但深度放电距离减少了9.52 km。随着行驶距离的增加,折旧和维修成本略有上升。但总运输成本降低了3.63%,换电成本降低了65.3%。相比于策略2,达到深度放电阈值前前往换电站换电的策略可以降低物流配送商总运输成本,尤其是换电成本。达到深度放电阈值后仍继续放电,会加速电池老化,采取达到深度放电阈值前前往换电站换电的策略能有效地避免这一点。
5. 结论
本文参考实际服装运输,根据服装特性设计了两种不同的装载方式,并且考虑服装货物的体积和车厢三维特征装车,计算出所需服装配送车辆的数目。另外,本文研究了对换电的电量实行分级定价的收费标准情形时的电动车辆路径问题。结合实际路网和服装品牌配送数据进行实例分析,结果表明,在分级定价收费标准下,采用达到深度放电阈值前前往换电站换电的策略,物流配送商可以有效减少换电成本。同时,采取分级换电收费标准是为了减少深度放电、减少电池损伤以延长电池寿命,因此对换电服务商来说也是有利的。政府应鼓励电动汽车和换电模式的发展,以促进电能有效合理的利用,促进全社会可持续发展。
基金项目
国家自然科学基金(71871143);上海“科技创新行动计划”社会发展科技攻关项目(22dz1203405);教育部人文社科基金项目(22YJC790189,23YJC790046)。