0 引言
车辆路径规划问题(vehicle routing problem，VRP)最早由Dantzig[1]于1959年提出，通过增加各种限制条件，众多学者对此问题进行了研究，然而绝大多数学者以行驶距离或配送车辆的数量为研究目标[2-5].随着人们对节能减排、绿色物流的关注不断加深，考虑降低物流成本的同时如何保护环境，已经成为学术界和环保部门关注的热点问题.
目前已有就低碳VRP问题而开展的相应研究，如Bektas等[6]实证研究了影响碳排放的诸多因素，通过实例验证了物流行驶速度、配送流程、时间窗限制等对碳排放量的影响程度. Zhu等[7]在综合分析碳排放量和车辆行驶里程之间关系的基础上，基于碳排放量和车辆行驶里程之间的正相关关系，构建了低碳路径规划问题模型.唐金环等[8]综合分析了旅行时间和碳排放量两个因素对多目标车辆路径的影响. Xiao等[9]基于碳排放量、物流配送成本、配送总路程三个角度下的配送路径对比分析物流配送过程中的碳排放量. Van等[10]考虑到道路拥挤对碳排放量的影响，对比分析了不同行驶速度情形下的碳排放量. Demir等[11]提出在影响车辆配送过程中燃料消耗量的众多因素中，车辆装载量、引擎类型、道路坡度大小等因素影响程度最为显著，同时进一步影响碳排放量.因此，随着全球变暖、节能降耗理念的提倡和盛行，物流配送过程中考虑降低碳排放量有助于建设低碳物流，为低碳经济助力.同时，大中型城市的物流配送体系中，一般存在多个配送中心的情形，因此，多配送站车辆路径规划问题(multi-depot vehicle routing problem，MDVRP)的研究更具有重要的现实意义. Renaud等[12]以总物流成本为目标，建立了车辆容量和行驶里程存在双约束情形下的MDVRP模型，并首次使用禁忌搜索算法进行求解该模型. Jin等[13]将MDVRP转化为二次规划问题，并采用两种求解方法对问题进行求解. Kuo等[14]将装载成本考虑到MDVRP中，设计了3阶段的变领域搜索算法求解问题模型. Seth等[15]将MDVRP应用到印刷电路板的生产过程中，提出基于网络流和路径分割算法的确定性求解方法. Imran等[16]通过MDVRP模型从车站共享、车辆类型数目、配送站库存等多个角度进行了扩展.
从前述研究综述可以看到，研究具有多个配送站的低碳VRP问题(multi-depot low-carbon vehicle routing problem，MDLCVRP)更加符合当下高速发展的物流配送环境，尤其随着近年来不断增长的电商快递需求，考虑节能减耗更符合时代特点.同时，在MDLCVRP的研究过程中，一方面，单纯考虑最小经济成本而忽视车辆配送过程中对环境的外在不经济，不符合绿色物流、低碳可持续的发展理念；另一方面，物流配送时效性作为物流企业竞争力的关键，深刻影响着客户的满意度和忠诚度，进一步地，影响企业的市场竞争力和长期发展.夏扬坤等[17]基于连锁超市配送的时效性，提出一种带工作时间与软时间窗的车辆路径问题，建立了该问题的混合整数规划并设计了一个自适应禁忌搜索算法进行求解.因此，本文提出低碳经济下考虑消费者满意度的物流配送优化问题，并建立考虑客户满意度的多配送站低碳车辆路径规划(satisfactory-multi-depot low carbon vehicle routing probelm，S-MDLCVRP)模型.考虑到S-MDLCVRP为VRP问题的变体，由于VRP问题是NP-hard的，因此S-MDLCVRP也是NP-hard的，这就使得本文求解过程变得异常复杂.在VRP等NP-hard问题的求解中，果蝇优化算法(fruit fly optimization，FFO)相比其它智能算法具有更少的参数设置、更快的优化速度等优良特性[18]，已经被广泛应用到NP-hard问题的求解中，如Hao等[19]应用果蝇优化算法求解TSP(traveling salesman problem)问题. Zheng等[20]则将果蝇优化问题应用到流水线车间调度问题中. Wang等[21]在智能物流背景下，采用混合果蝇优化算法求解多产品物流配送问题.因此，本文在果蝇优化算法求解NP-hard问题的优良性能和求解VRP问题的框架基础上，设计了多种群同时进化的改进果蝇优化算法(improved fruit fly optimization，IFFO)求解问题模型，以探究物流成本、环境保护、客户满意度三者之间的均衡关系.
1 模型构建 1.1 碳排放量模型当前已有不少学者研究了计算碳排放量的模型，较为经典的如Barth等[22-23]针对货车发动机的特点开发的综合模态排放模型(comprehensive modal emission model，CMEM).该模型中因为碳排放量与燃料消耗量具有显著的正相关关系，所以在计算碳排放量时只需要计算燃料消耗量即可.其中，燃料消耗率(g/s)模型为
|
(1) |
其中，FR表示配送车辆的燃料消耗率，v为车辆的行驶速度，τ表示车辆的加速度；θ表示道路坡度；M=ω+f表示车辆重量，包括车辆自身重量ω和货物重量f，其它符号意义及数值如表 1所示.这里设ψ为g/s转变为L/s的转换系数，同时为了简化模型，令λ=ξ/κψ，γ=1/1 000ηtfη，α=τ+gsin θ+gCrcos θ，β=0.5CdρA.设配送车辆k在配送完客户i驶往下一个客户j(j≠i)的路径距离为dij，在该路径上的平均行驶速度为vij且在该路径中的货物装载量为fijk(单位kg)，根据燃料消耗量与碳排放量之间的转化因子F，计算配送车辆在该路径上行驶过程中的碳排放量为
|
(2) |
| 参数 | 描述 | 取值 |
| ξ | 燃料空气质量比 | 1 |
| ε | 引擎摩擦系数 | 0.2 |
| N | 发动机速度 | 16 r/m~48 r/m |
| V | 发动机排气量 | 2 L~8 L |
| η | 发动机效率参数 | 0.9 |
| κ | 能效常数 | 44 |
| ηtf | 车辆传动效率 | 0.4 |
| Cd | 空气阻力系数 | 0.7 |
| Cr | 滚动阻尼系数 | 0.01 |
| ρ | 空气密度 | 1.20 kg/m3 |
| A | 车辆迎风面积 | 2.1 m2~5.6 m2 |
| g | 重力常量 | 9.8 |
| vl | 最低速度限制 | 20 km/h |
| vh | 最高速度限制 | 120 km/h |
其中，Mij=ω+fijk表示配送车辆k在配送完客户i驶往下一个客户j(j≠i)的路径上的整体重量，包括车辆重量和车辆的货物装载量.可以看到，由于配送车辆k行驶在任意路径(i，j)上的行驶里程和实际装载量不同，因此可以通过合理的调度配送车辆，优化配送路线实现碳排放量的降低，进而实现低碳配送.
1.2 S-MDLCVRP模型本文研究的考虑客户满意度的多配送站低碳配送路径规划问题，定义为：某城市物流配送系统包含有n个客户，m个配送站且客户和配送站的位置坐标已知；每辆配送车的最大载重量为Q，最大行驶距离为L；每个客户具有已知数量的需求qi(0≤qi≤Q)和确定的收货时间窗.通过计算得出的配送车辆和相应的行驶路径，满足客户货物需求：
1) 配送站能够使每个客户的货物需求得到满足，并且配送站的运力能够完成配送任务.
2) 每辆配送车按照指定的配送路线将货物送达到指定客户，完成配后回到起始配送站.
3) 每辆配送车同时为多个客户提供服务，但每个客户仅被服务一次.
4) 真实的配送过程中需要考虑每辆配送车的最大载量和最大行驶路程.
5) 车辆在任意两客户之间的行驶速度为匀速，即加速度为0；
6) 物流供应商承诺在客户时间窗内将货物送达指定客户，但允许一定的延迟，如果早于或者晚于客户时间窗送达，需要向客户支付违约罚金.
考虑到客户满意度在物流配送过程中主要体现在配送及时性上[24].因此，本文根据客户从下单到收到货物的等待时间建立客户违约赔偿函数.设客户i的配送开始时间为ai，客户i的的服务时间为si；客户i的时间窗为[ei，li]，客户的最早收货时间为e′i，最晚收货时间为l′i且有e′i < ei < li < l′i；当配送车辆在ei之前或者超过li时间点送达时，客户的满意度将面临着下降，并且超过最晚送达时间l′i后配送时，客户的满意度为0，即配送过程中要满足硬时间窗限制，但允许一定的时间窗扰动，考虑到实际配送中，客户对于晚送达和早送达的不同感受，这里设置α < β，以体现相比于早到，送货延迟带给客户带来的感受更强烈.基于上述分析，建立罚金函数：
|
(3) |
1) 集合
C={c1，c2，…，cn}为n个客户集合.
D={d1，d2，…，dm}为m个配送站集合.
N=C∪D为配送站和客户组成的集合.
A={(i，j)|i，j∈N，i≠j}是由任意两点i和j组成的弧或边的集合.
K={k1，k2，…，kh}为配送车辆集合，车辆总数为h.
V={v1，v2，…，vR}为车辆的行驶速度集合，这里假设车辆的行驶速度是离散的且最大行驶速度为vr，最小行驶速度为v1.
2) 参数
qi：客户i的需求量(0≤qi≤Q).
si：配送车辆在为客户i提供配送服务时所耗费的服务时间.
[ei，li]：客户i的收货时间窗.
e′i：客户i的最早收货时间.
l′i：客户i的最晚收货时间.
dij：任意两点i和j之间的欧氏距离(这里的点不仅包括配送中心还包括客户位置点).
ω：配送车辆空车净重量.
Qk：配送车辆k的负载量.
Lk：配送车辆k的最大行驶里程.
cf：每辆车的租赁费用(也可以看作是每辆车的固定成本).
cv：每辆车配送过程中的变动成本费用(主要包括司机工资等费用).
μ：车辆单位碳排放成本(如政府征收的碳税或者碳排放造成的外部不经济成本).
α：早于收货时间窗送达时，给予客户的时间窗扰乱赔付罚金.
β：晚于收货时间窗送达时，给予客户的时间窗扰乱赔付罚金.
F：燃料消耗量和碳排放量之间的转换因子.
xijk∈{0，1}，当0-1变量为1时，表示车辆k经过边(i，j)；当0-1变量为0时，则表示未经过边(i，j).
fijk：配送车辆k行驶在在边(i，j)上车辆的货物装载重量(单位kg).
zijkr：二维决策变量.如果车辆k以速度vr行驶在弧(i，j)上时，zijkr=1；否则，zijkr=0.
ai：配送车辆实际到达客户i的时间，i∈C.
pijk：车辆k从客户i出发到客户j的时间.
1.2.2 S-MDGVRP模型的构建根据车辆容量和行驶里程限制，结合上述所建立的碳排放模型及客户罚金函数，构建问题模型：
|
(4) |
|
(5) |
|
(6) |
|
(7) |
|
(8) |
|
(9) |
|
(10) |
|
(11) |
|
(12) |
|
(13) |
|
(14) |
|
(15) |
|
(16) |
|
(17) |
|
(18) |
|
(19) |
|
(20) |
|
(21) |
其中，式(5)表示车辆租赁费和变动成本费用，式(6)和式(7)表示碳排放成本，因此式(5)~式(7)组成了目标函数；式(8)表示需要支付的客户扰乱时间窗罚金总额.限制条件(9)~(11)表示每个客户仅被一辆车服务一次且配送车辆完配送任务后回到配送站；限制条件(12)、(13)表示车辆实际装载量的变化限制；限制条件(14)、(15)分别表示车辆行驶里程约束和最大装载量约束；限制条件(16)、(17)表示客户实际收货时间限制，限制(18)表示客户的时间窗约束；限制(19)表示车辆只能以一个速度行驶在弧(i，j)上，当xijk=1时，zijkr=1；式(20)~式(22)表示变量xijk、zijkr、fijk的约束.
2 算法设计VRP属于NP-hard问题，很难通过精确求解方法获得最优解，因此国内外学者选择启发式或亚启发式算法求解此类问题[25-28].本文涉及多个配送站且存在消费者时间窗限制条件和低碳路径优化，因此无法在有限时间内获得最优解，需要通过设计算法来得到问题的满意解[29].基于果蝇优化算法(fruit fly optimization，FFO)[30-32]，本文在求解问题模型中，模拟果蝇嗅觉觅食和视觉觅食的过程，将算法分为种群初始化、嗅觉觅食过程、视觉觅食过程三个阶段.首先，初始化算法参数、种群数、果蝇初始位置；其次，模拟果蝇个体利用嗅觉进行觅食的行为特点，通过特定的搜寻策略得到新的果蝇个体；随后，模拟果蝇通过视觉觅食的行为特点更新最优果蝇个体位置；最后，当迭代过程满足一定终止条件时，输出算法的最终求解结果.本文在基本FFO的基础上，通过引入聚类种群的形式，构造多个种群的多种群果蝇优化算法，并结合遗传算法的计划进化策略，设计改进的果蝇优化算法(improved fruit fly optimization，IFFA)以求解本文模型.
2.1 解的编码方式如图 1所示，配送站1和配送站2各有两辆配送车，每辆配送车在满足容量和行驶里程约束的情况下执行配送任务.如配送站1中的配送车辆客户1为客户4、7提供配送服务，配送路线为：配送站1→客户4→客户7→配送站1.
|
| 图 1 编码方式示意图 Fig.1 Schematic diagram of the encoding scheme |
主要分为两个步骤来完成算法的初始化：算法的输入参数和种群个体的设置.
Step 1 算法的输入参数主要包含：N，NPopsize，NmaxIter，NInteraction，分别代表种群数量、果蝇个体数量、迭代次数、种群间交互的规则.
Step 2 为减少求解时间，提高求解精度，本文在种群初始化阶段设计了基于距离的聚类初始化策略，将MDVRP转化为多个VRP进行并行求解，然后分配车辆，设计行驶路线.首先，根据每个客户与所有配送站的距离选择距离最近的配送站为其提供配送服务；其次，完成所有的客户分配后采用逆时扫描法计算配送车辆；最后，随机排列每辆配送车辆所服务的客户服务顺序，增加果蝇个体种群的多样性.具体的种群个体初始化过程如图 2所示.
|
| 图 2 种群初始化方式 Fig.2 Initialization mode of population |
在NP-Hard问题求解中利用多种群思想可以快速地得到多个问题优化解[33-34].而单果蝇算法在求解NP-hard问题的过程中，容易陷入局部最优而无法得到问题的最优解.因此，采用多种群思想，将原果蝇种群中的个体进行细分，形成多个子种群，与此同时，设计子种群之间的信息交换规则，通过彼此间的信息交互，共同协作来提升搜索效率，求解问题的最优解.具体的交换规则如图 3所示，从种群1中选择d1的概率为P0，从其它种群中选择一个个体的概率为P1，从种群最优个体中选择一个个体的概率为P2.这种通过以一定概率相互交叉的方式可以提升算法的全局搜索能力.
|
| 图 3 子种群之间的信息交换规则 Fig.3 Information exchange rules between subpopulations |
针对原果蝇算法中容易陷入局部最优的问题，本文设计的IFFO算法，采用了多种群间的相互交叉策略，提升算法的全局最优搜索能力，具体的相互交叉过程如图 4所示.随机从父代1和父代2中选择一个基因，在父代2中删除选中的父代1的基因，然后将父代1中选中的基因插入到父代2中，其中插入位置为能够使得父代2的函数值降低最多的位置，得到子代1.类似地，可得到子代2.
|
| 图 4 交叉算子示意图 Fig.4 Schematic diagram of the crossover operator |
同时，在IFFO算法中，利用sweap，insert，invert三种方式来完成个体之间的变异操作，如图 5所示.其中，交换算子即是交换两个不同点之间的位置，通过随机选择两个不同点位置，交换两个位置上的客户信息，实现两个点位置信息的变异；而移位变异是将位置上的随机客户随机的插入另外一个位置，另外变换变异和移位变异可以适应于同一路径和不同路径上的位置，所以可以增加搜索空间实现不同路径上的“信息交流”.倒置变异是将两个位置的信息进行倒置交换，如在一条配送路线上将两个位置上的客户顺序进行对换.通过这种交叉和变异的方式可以完成个体之间的优化选择.
|
| 图 5 交换、倒置、插入示意图 Fig.5 Schematic diagram of the swap, invert, and insert |
因此，在嗅觉搜索中设Xcurrtr为子种群的位置，NPopsize为通过上述规则产生的新的个体数量，表示为{X1r，X2r，…，XNpopszier}，新个体中的最优个体为Xbestr，在视觉搜索中替换为新的个体，如果f(Xbestr)<f(Xcurrtr)，则Xcurrtr=Xbestr.
2.3 IFFO伪代码IFFO伪代码如算法1所示.
| 算法1 改进的果蝇优化算法(FIFO)伪代码 |
| 1.输入：目标函数和参数值 2. \初始化 3.设定N，Npopsize，Nmaxlter，NInteraction等算法参数组和模型参数值 4.种群初始化 5. \迭代 6. while (count < limit) do 7. \嗅觉搜索阶段 8. for 1 to popsize 9. 每个果蝇个体随机搜索产生新的果蝇位置 10. end for 11. 得到果蝇种群中的最优个体 12. //视觉觅食阶段 13. for 1 to popsize 14. if(f(xi)>f(xnew)) 15. xi=xnew 16. end if 17. end for 18. if满足种群交流机制 19. 种群交流 20. else 21. go嗅觉觅食阶段 22. end if 23. 检查是否有不可行解，并经行修复 24. end while 25. \ the final stage 26.输出最优解及目标函数值 |
为验证问题模型及IFFO算法的有效性，对电商平台的物流配送公司的数据进行仿真.假设物流公司配送站数量为3，每辆车的最大载重量为200 kg，最大行驶距离为500 km，租赁成本为500元，损耗成本为5元/km，油耗成本为7.5元/L，碳排放成本为1.5元/kg.使用欧氏距离表示客户与配送站、配送站与配送站之间的距离，共有3个配送站和40个客户，从上午10:00开始配送，预计17:00之前完成配送，最晚不超过18:00，平均车速为60 km/h，客户的罚金参数α=0.5，β=1.除此之外，本文中的碳排放模型参数如表 1所示(其中区间值采用区间两端的平均值，加速度和道路坡度均为0)进行模型求解.要求通过计算得出的配送车辆和车辆行驶路线可以降低物流配送成本和缩短客户收货时间.其中配送站的信息如表 2所示. 40个客户的信息如表 3所示.
| 配送点编号 | 横坐标X /km | 纵坐标Y /km | 车辆数目n /辆 |
| 1 | 21.38 | 17.11 | 2 |
| 2 | -16.12 | 39.10 | 3 |
| 3 | -31.20 | 3.26 | 2 |
| 编号 | 横坐标x /km | 纵坐标y /km | 需求/kg |
| 1 | -29.73 | 64.13 | 12 |
| 2 | -30.66 | 5.46 | 8 |
| 3 | 51.64 | 5.47 | 16 |
| 4 | -13.17 | 69.33 | 5 |
| 5 | -67.43 | 68.32 | 12 |
| 6 | 48.90 | 6.27 | 5 |
| 7 | 5.24 | 22.26 | 13 |
| 8 | -65.00 | 77.23 | 20 |
| 9 | -4.17 | -11.56 | 13 |
| 10 | 23.35 | 21.2 | 18 |
| 11 | 25.48 | 6.28 | 7 |
| 12 | -42.66 | -26.39 | 6 |
| 13 | -66.67 | 89.34 | 9 |
| 14 | -20.67 | 57.89 | 9 |
| 15 | -52.25 | 6.59 | 16 |
| 16 | -41.37 | 50.82 | 25 |
| 17 | -71.94 | 27.58 | 5 |
| 18 | -65.11 | 30.21 | 17 |
| 19 | 18.59 | 86.71 | 10 |
| 20 | -40.94 | 53.28 | 16 |
| 21 | -37.75 | -33.32 | 25 |
| 22 | 23.76 | 29.08 | 9 |
| 23 | -43.03 | 20.45 | 8 |
| 24 | -35.29 | -24.89 | 19 |
| 25 | -54.75 | 14.36 | 14 |
| 26 | -49.32 | 33.37 | 6 |
| 27 | 57.40 | 23.82 | 16 |
| 28 | -22.75 | 55.41 | 9 |
| 29 | -56.62 | 73.32 | 20 |
| 30 | -38.56 | -23.75 | 13 |
| 31 | -16.77 | 19.57 | 10 |
| 32 | -11.56 | 11.60 | 16 |
| 33 | -46.54 | 57.05 | 19 |
| 34 | 16.22 | 9.32 | 22 |
| 35 | 3.29 | 17.39 | 14 |
| 36 | -26.40 | 29.59 | 10 |
| 37 | 14.35 | 14.68 | 11 |
| 38 | -50.66 | -23.12 | 15 |
| 39 | -22.83 | -9.81 | 13 |
| 40 | -7.84 | 32.07 | 8 |
遗传算法(genetic algorithm，GA)在求解车辆路径规划问题中收敛速度非常快，已经被广泛应用于此类问题的求解[35].为了验证IFFO的有效性，采用FFO，IFFO，GA三种算法分别求解配送路线，对3种不同算法的求解结果进行对比分析.其中，GA和FFO的种群数量为60，IFFO的子种群数量为6，子种群个体数量为10，GA的交叉率为0.9、变异率为0.1，IFFO子种群间消息交换的频率为1/10，算法的迭代次数为500.采用C++编程实现3种算法，并在DELL笔记本电脑(双核，8 G内存)上运行算法程序，每种算法程序运行30次取得其中最优的结果，然后形成如图 7所示的迭代流程图.
|
| 图 7 3个算法物流成本对比 Fig.7 The logistics cost comparison of three algorithms |
从图 6和图 7可以看到，在算法迭代的过程中，GA相比FFO和IFFO，求解得到的目标函数值之间的差距不断增大，由于采用了贪婪策略的启发式初始化方式，使得在前期迭代过程中，IFFO求解得到的目标函数值比FFO求解的结果有较为明显的降低，这说明本文提出的贪婪搜索策略的有效性；同时随着算法迭代次数的不断增加，从图 6可以明显看到，当迭代次数达到350次数，FFO寻优能力趋向于降低，IFFO求解的目标函数值仍然有较为明显的降低，这进一步说明了本文提出的多种群交流机制可以扩大解的搜索范围，提高解的寻优速度和精度.
|
| 图 6 算法迭代过程 Fig.6 Algorithm iterative process |
从图 8和图 9可以看到，IFFO和FFO两种求解算法得到的配送路线数目是相同的，均为5辆车，车辆的使用率为71.43%；但是，两种算法求解得到的路线是不同的，这也进一步说明了在物流配送过程中，合理的配送路线可以减少物流配送公司的配送成本以及提升用户的满意度.
|
| 图 8 IFFO得到的配送路线 Fig.8 IFFO′s delivery route |
|
| 图 9 FFO得到的配送路线 Fig.9 FFO′s delivery route |
分析图 10可以发现，遗传算法GA得到的6条配送路线，车辆使用率为85.71%，这说明可以通过合理规划路线，减少配送车辆的使用，进而达到物流配送成本的降低.同时也可以看到，3个算法中，IFFO算法求解结果最优，也说明本文提出的启发式初始化方式可以将客户聚类到距离其最近的配送站，实现就近配送，使得配送车辆不必要绕远路配送距离其较远的客户，从而实现了碳排放量和物流配送成本的降低.
|
| 图 10 GA得到的配送路线 Fig.10 GA′s delivery route |
为了验证考虑客户满意的重要性，本节对比了考虑客户满意和不考虑客户满意两种情形下的配送路线(如图 11)，通过两种情形的配送路线对比分析，可以发现物流公司考虑客户满意度对物流公司的发展具有重要的意义.从图 11可以看到，在不考虑客户满意度情形，即物流公司仅仅重视经济成本，忽视客户层面，这使得物流公司站在经济成本节约基础上，减少了车辆的使用量(减少了一辆车的使用)，大大减少了物流配送成本，然而却降低了客户的满意程度，即由于不考虑客户满意层面，造成了配送中客户收货时间的大大延长，提高了客户的赔偿金额.
|
| 图 11 不考虑客户满意情形下的配送路线 Fig.11 Distribution route without consideration of customer satisfaction |
将两种情况下的各个成本组成部分绘制成表 4所指示的表格中，其中升降情况一列中表示不考虑客户满意情形下与考虑客户满意情形下各组成部分的升降情况，“+”表示增加，“-”则代表降低.从表 4中两种情形下的各个成本指标的对比表可以发现，需要赔付给客户的延迟收货罚金金额具有较大的差异，即客户的满意度具有较大的差距，这就说明，物流公司在实际的配送运作中，需要关注客户的满意度层面，枉顾客户满意度仅仅重视经济成本的做法，只会降低客户的满意度，最终导致物流企业的市场竞争力的降低.
| 指标 | 考虑客户满意 | 不考虑客户满意 | 升降情况 |
| 总配送成本 | 11 673.80 | 10 805.20 | - |
| 基本配送成本 | 6 219.22 | 6 008.29 | - |
| 低碳成本 | 5 578.83 | 6 012.43 | + |
| 客户罚金额 | 1 508.05 | 3 558.92 | + |
如图 12所示，可以发现不同的平均行驶速度对碳排放成本具有显著的影响，当平均行驶速度在35 km/h~ < 55 km/h区间内，碳排放成本呈现递减趋势；而当平均行驶速度在>55 km/h~70 km/h区间内，碳排放成本呈现上升趋势；在速度等于55 km/h时，碳排放成本最低.同时，由于碳排放成本是碳排放量和碳单位成本的乘积，因此碳排放量也在速度等于55 km/h时呈现最优，这说明配送车辆在配送的行驶过程中，可以通过优化速度来实现碳排放量的降低.然而，这与路况和司机的驾驶习惯等因素有关，需继续深入研究.
|
| 图 12 不同的平均行驶速度下碳排放成本变化图 Fig.12 Carbon emission cost chart at different average speed |
本文在电商物流行业快速发展的背景下，综合考虑物流配送成本、碳排放量、消费者满意度三个方面，构建考虑消费者满意度的多配送站低碳物流路径规划模型，考虑到问题的NP-hard特性，设计了改进后的果蝇优化算法进行求解.本文的工作有：
1) 基于综合模态排放模型CMEM，建立了多个配送站情形下的低碳物流碳排放量模型，将碳税成本作为物流配送过程中的一部分，将碳税成本作为低碳物流决策的一部分.
2) 根据客户的收货时间窗限制，为提高客户的满意度，建立了基于客户时间窗的罚金函数，为物流配送过程中客户等待时间提供了一种衡量工具.
3) 构建了考虑客户满意度的包含有多个配送站的低碳物流配送路径规划模型，设计了贪婪启发式初始化方式，采用多种群交流机制，设计了改进后的果蝇优化算法对模型进行求解，为求解此类物流路径规划等NP-hard问题提供了求解的途径.
下一步工作将研究客户收货时间存在不确定性且存在退换货情形的多配送站物流配送优化问题.
| [1] | Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80–91. |
| [2] | Baker B M, Ayechew M A. A genetic algorithm for the vehicle routing problem[J]. Computers & Operations Research, 2003, 30(5): 787–800. |
| [3] | Ibaraki T, Imahori S, Nonobe K, et al. An iterated local search algorithm for the vehicle routing problem with convex time penalty functions[J]. Discrete Applied Mathematics, 2008, 156(11): 2050–2069. DOI:10.1016/j.dam.2007.04.022 |
| [4] | Chen P, Huang H K, Dong X Y. Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem[J]. Expert Systems with Applications, 2010, 37(2): 1620–1627. DOI:10.1016/j.eswa.2009.06.047 |
| [5] | Sun P, Veelenturf L, Hewitt M, et al. The time-dependent pickup and delivery problem with time windows[J]. Transportaion Research Part B:Methodological, 2018, 116(10): 1–24. |
| [6] | Bektas T, Laporte G. The pollution-routing problem[J]. Transportation Research, Part B:Methodological, 2011, 45(8): 1232–1250. DOI:10.1016/j.trb.2011.02.004 |
| [7] | Zhu X, Garcia-Diaz A, Jin M, et al. Vehicle fuel consumption minimization in routing over-dimensioned and overweight trucks in capacitated transportation networks[J]. Journal of Cleaner Production, 2014, 85: 331–336. DOI:10.1016/j.jclepro.2013.10.036 |
| [8] |
唐金环, 戢守峰, 沈贵财.
时变网络下考虑碳排放的车辆路径优化[J]. 系统工程, 2015, 33(9): 37–44.
Tang J H, Ji S F, Shen G C. Optimization of vehicle routing considering carbon emissions under time-varying networks[J]. Systems Engineering, 2015, 33(9): 37–44. |
| [9] | Xiao Y, Konak A. The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion[J]. Transportation Research, Part E:Logistics and Transportation Review, 2016, 88: 146–166. DOI:10.1016/j.tre.2016.01.011 |
| [10] | Van W T, Creten R, Vandaele N. Managing the environmental externalities of traffic logistics:The issue of emissions[J]. Production and Operations Management, 2000, 10(2): 207–223. |
| [11] | Demir E, Bektas T, Laporte G. A comparative analysis of several vehicle emission models for road freight transportation[J]. Transportation Research Part D:Transport & Environment, 2011, 16(5): 347–357. |
| [12] | Renaud J, Boctor F F, Laporte G. An improved petal heuristic for the vehicle routeing problem[J]. Journal of the Operational Research Society, 1996, 47(2): 329–336. DOI:10.1057/jors.1996.29 |
| [13] | Jin T, Guo S, Wang F, et al. One-stage search for multi-depot vehicle routing problem[C]//Information Systems and Control Conference. 2004: 446-129. |
| [14] | Kuo Y, Wang C C. A variable neighborhood search for the multi-depot vehicle routing problem with loading cost[J]. Expert Systems with Applications, 2011, 38(7): 6949–6954. |
| [15] | Seth A, Klabjan D, Ferreira P M. Analyses of advanced iterated tour partitioning heuristics for generalized vehicle routing problems[J]. Networks, 2013, 61(4): 290–308. DOI:10.1002/net.21478 |
| [16] | Salhi S, Imran A, Wassan N A, et al. The multi-depot vehicle routing problem with heterogeneous vehicle fleet:Formulation and a variable neighborhood search implementation[J]. Computers & Operations Research, 2014, 52(PB): 315–325. |
| [17] |
夏扬坤, 符卓.
带软时间窗的连锁超市配送车辆路径问题[J]. 信息与控制, 2018, 47(5): 91–97.
Xia Y K, Fu Z. Distribution vehicle routing problem in chain supermarket with soft time window[J]. Information and Control, 2018, 47(5): 91–97. |
| [18] | Han J, Liu C. Fruit fly optimization algorithm based on bacterial chemotaxis[J]. Journal of Computer Applications, 2013, 33(4): 964–938. DOI:10.3724/SP.J.1087.2013.00964 |
| [19] | Hao Q, Fang L, Tao S. A discrete fruit fly optimization algorithm for traveling salesman problem[C/OL]//International Conference on Industrial Informatics-computing Technology. Piscataway, NJ, USA: IEEE, 2017. (2018-04-02)[2019-07-01]. http://ieee.explove.ieee.org/documat/18328631. |
| [20] | Zheng X, Ling W. A knowledge-guided fruit fly optimization algorithm for dual resource constrained flexible job-shop scheduling problem[J]. International Journal of Production Research, 2016, 54(18): 1–13. |
| [21] | Wang C L, Li S W. Hybrid fruit fly optimization algorithm for solving multi-compartment vehicle routing problem in intelligent logistics[J]. Advances in Production Engineering & Management, 2018, 13(4): 466–478. |
| [22] | Barth M, Younglove T, Scora G. Development of a heavy-duty diesel modal emissions and fuel consumption model[R]//Berkeley, CA, USA: Institute of Transportation Studies, UC Berkeley. |
| [23] | Barth M, Boriboonsomsin K. Real-world C02 impacts of traffic congestion[C]//Transportation Research Board Conference. CA, USA: University of California Transportation Center, 2008: 036807. |
| [24] | Afshar-Bakeshloo M, Mehrabi A, Safari H, et al. A green vehicle routing problem with customer satisfaction criteria[J]. Journal of Industrial Engineering International, 2016, 12(4): 529–544. |
| [25] |
刘毅, 丛明, 刘冬, 等.
基于改进遗传算法与机器视觉的工业机器人猪腹剖切轨迹规划[J]. 机器人, 2017, 39(3): 377–384.
Liu Y, Cong M, Liu D, et al. Porcine abdominal cut path planning of industrial robot based on improved genetic algorithm and machine vision[J]. Robot, 2017, 39(3): 377–384. |
| [26] | Jiang J, Ng K M, Poh K L, et al. Vehicle routing problem with a heterogeneous fleet and time windows[J]. Expert Systems with Applications, 2014, 41(8): 3748–3760. DOI:10.1016/j.eswa.2013.11.029 |
| [27] | Kim G, Ong Y S, Heng C K, et al. City vehicle routing problem (City VRP):A review[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(4): 1654–1666. DOI:10.1109/TITS.2015.2395536 |
| [28] | Gaur D R, Mudgal A, Singh R R. Improved approximation algorithms for cumulative VRP with stochastic demands[J]. Discrete Applied Mathematics, 2018(3): 176–189. |
| [29] | Azadeh A, Farrokhi-Asl H. The close-open mixed multi depot vehicle routing problem considering internal and external fleet of vehicles[J]. Transportation Letters-The International Journal of Transportation Research, 2017, 11(2): 78–92. |
| [30] | Pan W T. A new evolutionary computation approach: Fruit fly optimization algorithm[C/OL]//2011 Conference of Digital Technology and Innovation Management. 2011: 1-5.[2019-06-15]. http://www.scienceopen.com/document?vid=f780a215-6c07-45be-93fo-655c65c650147362. |
| [31] |
张晓茹, 张著洪.
求解多模态函数优化的微果蝇优化算法[J]. 信息与控制, 2016, 45(3): 361–370.
Zhang X R, Zhang Z H. Micro-drosophila optimization algorithm for multimodal function optimization[J]. Information and Control, 2016, 45(3): 361–370. |
| [32] | Li H Z, Guo S, Li C J, et al. A hybrid annual power load forecasting model based on generalized regression neural network with fruit fly optimization algorithm[J]. Knowledge-Based Systems, 2013, 37(2): 378–387. |
| [33] | Marinakis Y, Marinaki M. A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem[J]. Computers & Operations Research, 2010, 37(3): 432–442. |
| [34] | Liang J J, Pan Q K, Chen T, et al. Solving the blocking flow shop scheduling problem by a dynamic multi-swarm particle swarm optimizer[J]. International Journal of Advanced Manufacturing Technology, 2011, 55(5/6/7/8): 755–762. |
| [35] | Liu S, Huang W, Ma H. An effective genetic algorithm for the fleet size and mix vehicle routing problems[J]. Transportation Research, Part E:Logistics and Transportation Review, 2009, 45(3): 434–445. DOI:10.1016/j.tre.2008.10.003 |