考虑碳排放及时间窗的LIRP模型与算法研究

王 宁，张玉萍，赵 姣，金子阳

(长安大学 汽车学院，陕西 西安 710064)

市场全球化的今天，能否快速、准确地满足客户的需求，越来越成为企业制胜的关键。现在企业之间的竞争，不仅仅是效益的角逐，更是供应链的竞争。如今实现供应链总体最优已是商界、学术界的热门话题。一直以来，物流系统优化中的3个核心问题都是设施选址、库存控制和车辆路径安排。早期研究学者们在这3个问题上进行研究，同时也取得了大量的成果。近些年越来越多的研究在选址−库存−路径问题(location-inventory-routing problem，LIRP)进行延伸。LIRP是指考虑潜在设施点固定成本、库存成本和运输成本的同时，明确设施位置，并确定库存水平和配送车辆的运输路线。集成化物流系统规划是企业管理的重要方面，也是物流系统规划研究的新方向。

目前，LIRP的研究已引起国内外学者的广泛关注。Liu等[1]是LIRP研究较早的学者，他们在原有的单一产品、多节点选址−路径问题的数学模型基础上考虑库存控制决策，针对模型提出两阶段的启发式算法。在此基础上，针对文献[1]中算法容易陷入局部最优的缺陷，Liu等[2]重新构建了LIRP模型，提出一种基于模拟退火算法的全局优化启发式算法，对文献[1]中的算法进行改进。Zeynep[3]对上述文献研究的问题进行扩展，建立单一产品、多节点的LIRP模型，运用禁忌搜索的两阶段算法来求解该问题。Shen等[4]研究随机需求下的LIRP模型，证实集成考虑选址库存路径决策的必要性。唐琼等[5]使用二层规划建模方法描述LIRP，并设计双层模拟退火算法求解。王婵婵[6]研究再制造闭环物流系统和再利用闭环物流系统优化中的LIRP。赵经纬[7]以医疗废气物回收为背景，针对感染性和非感染性的医疗废气回收建立LIRP模型。崔飞涛[8]考虑物流系统随时间变化的动态情况，建立动态环境下的LIRP模型。对于带时间窗的LIRP问题，吕飞[9]考虑备件需求的随机性和时间的紧迫性，建立客户需求服从泊松分布的LIRP模型，同时设计混合启发式算法来求解该模型。唐琼等[10]考虑到客户对送货时间的要求，建立带软时间窗的LIRP模型，并提出结合禁忌搜索算法的模拟退火算法求解该模型。吕飞等[11]考虑到备件物流系统优化中时间因素的情况，分别建立考虑订货周期和带软时间窗的LIRP模型。对于带碳排放的模型问题，曹剑东等[12]以总成本最小化为优化目标研究考虑碳排放因素的车辆路径问题(vehicle routing problem，VRP)。Jemai等[13]研究最小化运输路径和碳排放的多目标VRP模型。鲁建厦等[14]研究最小化成本和车辆数的VRP模型。

综上，目前对于传统LIRP问题的研究已较为全面和深入，基本涵盖了动态车辆调度、时间窗、环境限制等多种情况，求解方法主要以启发式算法为主。但将绿色交通、时间窗与传统路径优化相结合的研究相对较少，且在低碳物流研究方面，我国起步比较晚。因此，综合考虑碳排放成本和时间窗惩罚成本，与传统LIRP问题相结合构建模型。由于LIRP问题的复杂性，其求解方法主要以智能优化算法为主，包括模拟退火和其他智能算法，如遗传、禁忌搜索等。差分进化算法(differential evolution algorithm，DE) 作为一种高效且功能强大的全局优化算法，由Storn和Price首次提出，主要是用来求解实数优化问题。该算法已成功应用于各种领域，比如在电磁学、数据挖掘等方面都有较好的成果。DE是一种直接的、并行的、随机的搜索方法，也是基于实数编码的进化算法，具有结构简单、收敛速度快、鲁棒性强等特点。在搜索较复杂的全局最优问题时，DE是一种有效的算法，因此本文运用DE求解该模型。

1 问题描述与模型构建

1.1 问题描述

本文考虑碳排放以及时间窗的LIRP问题表述如下。汽车零部件企业为位置和需求已知的客户提供配送服务。该区域存在3个配送中心分区进行配送，配送中心拥有的配送车辆数不限，只考虑配送中心的库存成本，客户要求的配送时间用模糊时间窗表示，每条线路上的配送车辆早于或晚于客户要求的配送时间窗都会产生相应的惩罚成本。根据车辆对载重以及路程的限制为配送车辆安排合适经济的行驶路线，目标使总成本最小。对于多配送中心如何选择的问题，根据客户到达配送中心的距离，选择路程最短的来决定由几个配送中心进行配送。对于客户如何选择的问题，根据距离最近原则，计算客户与各配送中心的距离，该客户离哪个配送中心最近，将其分配到哪个配送中心，由该配送中心为其提供服务。且每个配送中心的服务能力均足以满足需求。配送中心作为车辆路径的起点和终点，每辆车必须从一个选定的配送中心出发，并最终返回该配送中心。区域配送网络结构如图1所示。

图1 区域配送网络示意图Figure 1 Schematic diagram of regional distribution network

本文基于以下假设进行研究。

1) 备选点为离散点，备选配送中心的位置已知，需求点的需求量已知；

2) 从生产中心到配送中心和配送中心到客户的距离及单位运价已知；

3) 每个客户的需求必须满足，且只能由一台配送车辆送货；

4) 每条配送路径的长度不超过配送车辆一次配送的最大行驶距离；

5) 所有运输车辆的规格相同，且每个线路上的运输由一辆车负责送货；

6) 车辆从配送中心发出，送完货后回到所隶属的配送中心；

7) 不关心零部件的配送途中所发生的任何突发情形，例如整车生产中心的生产需求改变、交通管制、天气原因等。

1.2 模型构建

1.2.1 参数和变量说明

本文所用参数和变量说明见表1。

表1 基本模型符号及定义Table 1 Basic model symbols and definitions

1.2.2 建立模型

根据问题描述及符号说明，建立企业配送路径多目标优化模型。

1) 配送中心的选址成本

2) 库存成本

3) 配送成本

4) 综合油耗模型

瞬时燃油消耗率 OR为

因此，总燃油消耗量 O等于瞬时燃油消耗率OR与运行时间tk=d/v的乘积，即

式(7)燃油消耗量O取决于3个方面，即发动机性能、运行速度和车辆载重。

5) 目标函数

其中，目标函数(8)表示成本函数，主要由选址费用、库存费用、运输费用、时间惩罚成本、碳排放成本5部分组成；约束(9)为决策变量的约束，保证每个客户由一个配送中心送货；约束(10)、(11)保证每个客户均能被服务到，且只能由一辆车服务；约束(12)保证运输路线的连续性，即将货物运至某一点的车辆，必须在同一点离开；约束(13)为决策变量的约束；约束(14)只有被选中的配送中心才能配送货物；约束(15)保证每条路径上各客户的货物需求量之和不超过配送车辆的载重量；约束(16)为决策变量的约束；约束(17)为客户时间窗，即客户可接受服务的时间；约束(18)保证配送中心最大库存量大于等于客户总需求量；约束(19)消除子回路约束；约束(20)到达时间的约束。

2 算法设计

本节将设计一个差分进化算法来求解LIRP问题。DE是一种采用实数编码，在连续空间中进行随机搜索的优化算法。相比于其他进化算法，DE保留了基于种群的全局搜索策略。其最大的特点就是变异操作是基于染色体的差异向量进行的，即在每个新个体的生成过程中用到父代多个个体的线性组合，它的整体结构类似于遗传算法。为了解决带有时间窗和碳排放的LIRP问题，提高全局搜索能力，本文对标准的差分进化算法在变异上进行改进，如图2所示。以8个客户点为例，对算例进行说明分析。

DE算法的主要算法过程主要有变异、交叉和选择操作。通过求解 f(X1,X2,···,Xl) 的 最小值问题，Xj满足, j=1,2,···,l，来介绍差分算法的进化过程。

图2 差分进化算法流程Figure 2 Flow of differential evolution algorithm

令 Xi(t)是第t代的第i个染色体，则

其中，l是解空间的维数，即变量的个数；NP为群体规模； tmax为最大的进化代数。

1) 生成初始种群。

种群中每个个体代表一个可行解，个体中的每一位代表了一个客户，个体的顺序代表了车辆到达每个客户的次序。

在l维空间里随机产生满足约束条件的NP个染色体，实施措施为

首先对8个个体进行编码处理，采用自然数1～8分别表示8个客户点，对客户进行随机的排列组合，形成8位数向量的初始种群。假设产生的初始种群为Xi(t)为245 | 186 | 37，作为目标向量，表示该路径需要3辆车配送，配送顺序为2-4-5，1-8-6，3-7。

2) 变异操作的改进。

从群体中随机选择3个染色体Xp1,Xp2,Xp3(i ≠p1≠p2≠p3)，则标准的变异操作为

其中， Xp2j(t)−Xp3j(t) 为 差分向量； η为缩放因子，用于控制差分向量的影响力。

而改进的变异操作，先随机选取一个向量为Xp1(t)作为目标向量，对目标向量的各分矢量乘以2得到新的向量 Xp2(t)， 再随机选取一个向量 Xp3(t)，将 Xp2(t)、 Xp3(t)相减得到Ui(t+1)。对Ui(t+1)进行处理。具体说明如下。Xp1(t)=2 4 5 1 8 6 3 7；Xp2(t)= 4 8 10 2 16 12 6 14； Xp3(t)= 4 5 7 1 3 6 8 2；Ui( t+1)= 0 3 3 1 13 6 −2 12。

删除为0的分向量，大于8或者小于0的分向量则减去8或者加上8，出现重复分向量则留下前一位分向量，按照顺序依次补上目标向量中没有出现的分向量，即得到新的变异向量Ui(t+1)。

修正后的变异向量Ui(t+1)=3 1 5 6 4 2 8 7。

3) 交叉操作。

交叉操作是为了增加群体的多样性。按规则选择目标个体，把目标个体与变异个体进行参数混合产生实验个体。

其中，r and(0,1)是 [0,1]之 间的随机小数；r and(i)是[1,l]之 间的随机整数；CR为交叉概率，C R ∈[0,1]。

4) 选择操作。

为了决定 Xij(t)是否成为下一代的成员，把实验个体 Vij(t+1)与 目标个体 Xij(t)进行比较。若实验个体的适应度值更优，则实验个体取代目标个体，否则保留目标个体。

反复执行2至4操作，直至达到最大的进化代数tmax。

3 算例分析

3.1 案例介绍

某汽车企业配送零部件，拥有1个生产中心和3个备选配送中心A、B、C，由配送中心向多个客户点进行配送，生产中心到配送中心的单位距离运费为20元，配送客户的单位距离运费为25元，速度为40 km·h−1。建设成本为1 000元，单位库存成本分别是10元及15元，惩罚成本分别是C1=50元；C2=60元。设定种群规模NP=100，交叉概率取值0.3，缩放因子取值0.5，最大迭代次数为500。

本文以国内物流配送常用的江淮HFC1082KD厢式货车为例，给出了计算式中的参数取值，如表2所示。

3.1.1 小规模算例

该算例中通过Matlab随机生成10个坐标点，其中有6个客户点，3个备选配送中心，1个生产中心。车辆载重为2 t。随机生成10组数据，通过Matlab与Lingo对目标函数进行求解，对比分析如表3所示。

设计差分进化算法对考虑碳排放和时间窗的LIRP问题进行求解。采用Matlab R2016a进行编程，所有实验均在处理器为Windows 2.20 GHz、inter Core i5-5200U CPU、内存为4G的电脑上进行，并将其结果与采用Lingo11.0求解的结果进行比较。

表2 车辆燃油消耗参数Table 2 Vehicle fuel consumption parameters

表3 实验数据对比Table 3 Comparison of experimental data

通过表3可以看出，DE求解的平均时间为49.88 s，与Lingo相比平均偏差均在2%以内，其中对于算例1、3、5、6、8、10等6组算例DE均获得了最优解，证明本文提出的DE算法在求解该问题小规模算例时的有效性。对于小规模算例，Lingo平均求解时间达到1.5 h，对于大规模算例无法快速获得全局最优或者局部最优解。因此，本文用DE算法求解大规模算例。

3.1.2 中规模算例

对于中规模算例，随机生成23个节点。其中包含1个生产中心，坐标为(25,30)；3个备选配送中心A、B、C，坐标分别为(43,21)、(10,20)和(38,38)，车辆由配送中心向20个客户点配送零部件，车辆载重为5 t。客户信息及客户需求量如表4所示。

3个备选配送中心，分别计算客户到A、B、C、AB、AC、BC和ABC的距离，依据距离最近原则，得出选取两两配送中心的距离最短。因此，通过Matlab进行求解，结果如表5所示。

从表5可知，其中配送中心A有9次得到最优解，其成本为5 000.0元，运行时间约为30 s，而配送中心B有4次运行结果得到的解质量最高，其成本为5 120.9元，总成本为10 120.9元。

表4 客户坐标及需求量Table 4 Customer coordinates and demand

表5 差分进化算法求解结果Table 5 Solution results of differential evolution algorithm

同样，分别以A、C和B、C作为配送中心，在Matlab中进行求解，得到最优成本分别为11 407元和10 659.7元。比较3种方案，显然配送中心A、B成本最小，为10 120.9元。选取A、B作为配送中心。

为了便于分析，差分进化算法的寻优过程见图3。

图3 求解中规模算例算法寻优过程Figure 3 Optimization process of scale example algorithm in solution

从图3可以看出，在整个进化的过程中，差分进化算法的局部搜索能力较强。随着迭代次数的增加，解的质量越来越高。且仅需很少的迭代次数就可得到质量较高的解，体现了差分进化算法具备较好的收敛性。

路径配送方案如表6所示，0为配送中心。

为了直观体现，客户点分布在一个50 km的正方形区域内，最优配送路线如图4所示，点23为生产中心，点21、22为配送中心A、B。

3.2 结果分析

整个过程分析采用3组起始种群NP和迭代次数G：1) NP=10，G=20；2) NP=20，G=20；3) NP=100，G=200。以配送中心A为例进行分析。

表7为NP=10时随机产生的初始化种群，总配送路程最长为218.86 km，最短为145.97 km，平均为194.19 km。总成本最高为7 610.2元，最低为5 811.77元。这些初始化种群的可行解相比上文得到的最优解5 000元还差较远。

表8为当NP=10时，经过20次迭代后的可行解。可知车辆的运输总里程与总成本都有了减少，最短总里程为142.96 km，平均为157.58 km，总成本最低为5 712.4元。

表9为当NP=20时，经过20次迭代运行10次后的优化解，车辆的运输总里程为137.08 km，运费为3 427.1元，总成本为5 504.8元。

表10为当NP=100时，经过200次迭代后运行10次的优化解，车辆的运输总里程为114.54 km，运费为2 863.4元，总成本为5 000元。

表11为多种群多次迭代时运行10次得到的最优解，通过对比可知，随着种群的增多和迭代次数的增加，搜索结果会越来越趋向于最优解。在考虑碳排放的情况下，目标函数总成本随之提高，说明低碳出行的重要性。

表6 车辆路径配送方案Table 6 Vehicle route distribution scheme

图4 路径轨迹Figure 4 Path trace

表7 初始化种群(NP=10)Table 7 Initial population (NP=10)

4 结论

针对考虑碳排放和时间窗的LIRP问题，建立混合整数规划模型，设计改进的差分进化算法进行求解。针对小规模算例，通过将Lingo和DE求解结果进行对比，验证模型的正确性以及算法的有效性。针对中规模问题，考虑算法中种群数与迭代次数不同对结果的影响，以及碳排放对于物流成本的影响。该问题将碳排放、时间窗考虑到LIRP的研究中，对物流配送企业实际运作具有一定的参考价值。

表8 20次迭代后的种群(NP=10)Table 8 Population after 20 iterations (NP=10)

表9 20次迭代后的种群(NP=20)Table 9 Population after 20 iterations (NP=20)

表10 200次迭代后的种群(NP=100)Table 10 Population after 200 iterations (NP=100)

表11 多次迭代后最优解对比Table 11 Comparison of optimal solutions after multiple iterations

在实际的配送企业，客户的需求大多是不确定的，而且随着低碳生活的不断渗透，在未来的LIRP问题研究中，将考虑动态情况和无人车配送情况。在算法方面，虽然DE算法在求解全局最优问题时有明显的优势，但是随着迭代次数的增加，各个体之间的差异化逐渐缩小，导致后期收敛速度变慢。因此，将针对算法上进一步改进，更好地解决LIRP问题。