考虑碳排放的两阶段选址-路径问题及其算法

汤希峰; 何杰; 张浩

doi:10.3969/j.issn.0258-2724.20210773

考虑碳排放的两阶段选址-路径问题及其算法

doi: 10.3969/j.issn.0258-2724.20210773

汤希峰^1,,
何杰^2, ,,
张浩²

1.
河海大学土木与交通学院，江苏南京 210098
2.
东南大学交通学院，江苏南京 211189

基金项目: 国家自然科学基金（71874067，52072069）；江苏省农业科技自主创新资金（CX(20)3074）

详细信息

作者简介:
汤希峰（1980—），男，讲师，博士，研究方向为运输与物流工程， E-mail：20110029@hhu.edu.cn

通讯作者:
何杰（1973—），男，教授，博士生导师，研究方向为载运工具运用工程，E-mail：hejie@seu.edu.cn

中图分类号: F252
计量
- 文章访问数: 682
- HTML全文浏览量: 366
- PDF下载量: 80
- 被引次数: 0
出版历程
- 收稿日期: 2021-10-01
- 修回日期: 2022-01-08
- 网络出版日期: 2023-04-13
- 刊出日期: 2022-01-14

Two-Echelon Location Routing Problem Considering Carbon Emissions and Its Algorithm

TANG Xifeng^1
,,
HE Jie^{2
, ,},
ZHANG Hao²

1.
College of Civil and Transportation Engineering, Hohai University, Nanjing 210098, China
2.
School of Transportation, Southeast University, Nanjing 211189, China

摘要

摘要:
为减少物流车辆的碳排放，基于以排放因子为主要参数的碳排放计算方法，建立以碳排放最小化为目标的两阶段选址-路线问题（2E-LRP）模型，并设计了一种可用于快速求解大规模问题的两阶段混合算法（TSHA）. 算法第一阶段将2E-LRP转化成不考虑车辆路径的两阶段设施选址问题，调用Cplex直接求解得到配送中心选址和客户分配方案；在此基础上，算法第二阶段中，物流园区到被选用的配送中心以及配送中心到所分配客户的车辆路径问题被进一步转化成若干个独立的VRP （vehicle routing problem）问题，再运用改进的蚁群算法进行求解；最后，对Prodhon标准算例集中全部6个最大规模的算例进行测试. 研究结果表明：与TSHA具有相同算法思想的TSHA-Ⅱ算法能够在求解质量下降2.3%的情况下将计算时长大大缩短至25 s左右；TSHA算法在求解考虑碳排放的2E-LRP算例时表现非常稳定，可以作为一种求解考虑碳排放2E-LRP的有效算法.
- 城市物流 /
- 两阶段选址-路径问题 /
- 碳排放 /
- 两阶段混合算法 /
- 蚁群算法
Abstract:
To reduce the carbon emissions from logistics vehicles, this paper presented a two-echelon location routing problem (2E-LRP) model aiming at minimizing carbon emissions based on a carbon emission calculation method employing emission factors as the key parameter. The paper also designed a two-stage hybrid algorithm (TSHA) capable of rapidly solving a large-scale problem. The algorithm first simplified the 2E-LRP into the two-echelon facility location problem without taking vehicle routes into account and called Cplex to solve it to obtain the location solution of distribution centers and the assignment solution of customers. Based on the above solutions, the 2E-LRP was transformed into independent vehicle route problems, and then an improved ant colony algorithm was employed for a solution. All six largest-sized instances from the standard Prodhon benchmark were tested. The test results show that the TSHA-Ⅱ, with the same algorithm ideas as TSHA, can reduce the computation time to about 25 seconds with a decrease of 2.3% in solution quality. The TSHA is stable in solving 2E-LRP considering carbon emissions and can be used as an effective algorithm to solve the 2E-LRP considering carbon emissions.
- city logistics /
- two-echelon location routing problem /
- carbon emissions /
- two-stage hybrid algorithm /
- ant colony algorithm

HTML全文

城市是生产、生活的主要集中地，也是物流活动最为集中的地方. 两层的物流网络作为一种可行的城市物流解决方案正被国内外许多大中城市所采用^[1-4]，其核心问题之一是两阶段选址-路径问题（2E-LRP）. 经典的2E-LRP可以描述为：重型或中型货车负责将货物从一个位于城郊的物流园区运送至若干位于城市中心区周边的配送中心，货物在这些配送中心经过重新配装后再由轻型或微型货车送达终端客户，其目标是寻求最优的配送中心选址以及第一阶段和第二阶段货车的最优路径以实现总的物流成本最小化^[5].

众所周知，货车相较于客车容易导致交通事故和交通拥堵，更是污染物和碳排放的主要贡献者. 以我国为例，2019年全国货车保有量虽然只占汽车总量的10.71%，货车CO、HC、NO_x、PM排放量却占到了汽车排放总量的29.7%、26.3%、83.5%、90.1%^[6]. 随着生态环境保护问题日渐受到重视，如何优化2层网络结构的物流运作以减少货车的碳排放引起了国内外学者越来越多的研究兴趣. Govindan等^[7]围绕生鲜配送，建立了以物流成本最小化和环境影响最小化为目标的2E-LRP多目标优化模型，并设计了多目标粒子群优化算法（MOPSO）和改进的多目标可变邻域搜索算法（AMOVNS）2种求解算法；胡大伟等^[8]针对燃油车和电动车不同的行驶与排放特性，分别建立了燃油车和电动车的2阶段开放式选址-路径问题模型，并提出了一种改进的模拟退火算法；刘成清等^[9]以经典的2阶段开放式选址-路径问题模型为基础，通过考虑车辆的燃油消耗和CO₂排放以及车辆路径选择的灵活性，建立了基于路径灵活性的两阶段开放式低碳选址-路径问题模型，并运用Cplex进行了求解；Pitakaso等^[10]以燃油消耗最小化为目标，建立了考虑碳排放的绿色两阶段选址路径问题（G2ELRP）优化模型，并设计了相应的可变邻域策略的自适应搜索（VANSAS）算法.

一方面，鉴于车辆的碳排放受到车型、车速、载重、行驶距离以及驾驶行为等诸多因素的影响^[11-12]，现有文献大多基于车辆的燃油消耗进行碳排放的计算，所需参数较多，实用性不强；另一方面，现有的用于求解各种2E-LRP的算法多适用于求解小规模问题（客户数量n≤100, 候选配送中心数量m<10），求解大规模问题（n>100, m≥10）时计算耗时较长，很难实际应用. 为此，本文基于一种简单实用的以排放因子为主要参数的碳排放计算方法，建立了考虑碳排放的2E-LRP优化模型，并针对所研究问题的计算复杂性，设计了一种可快速求解大规模问题的两阶段混合算法.

1. 模型构建

1.1 问题描述

基于图论，考虑碳排放的2E-LRP可以描述为G ={V, E}，V =V₀∪V_s∪V_c，V₀为物流园区，V_s = （1, 2,…,m）为配送中心候选集，V_c = （m+1, m+2,…,m+n）为客户集；E = E₁∪E₂，E₁ = {（i, j）: i, j ∈V₀∪V_s; i≠j} 为物流园区与配送中心之间的路线集，E₂ = {（i, j）: i, j∈V_s∪V_c; i, j $\notin $ V_s × V_s; i≠j} 为配送中心与客户以及客户与客户之间的路线集；H为可供物流园区使用的重型或中型货车的集合，每台重型或中型货车具有相同的载重能力，记为Q_H，满载和空载时的碳排放系数分别为ε_vfH、ε_veH （单位： kg/km, 下同）；K为可供配送中心共用的轻型或微型货车的集合，每台轻型或微型货车也具有相同的载重能力，记为Q_K （Q_K < Q_H），满载和空载时的碳排放系数分别为ε_vfK、ε_veK （ε_vfK < ε_vfH，ε_veK < ε_veH）；W_i为配送中心i （i ∈V_s）的作业能力；d_j为客户j的货运需求量（j ∈V_c, d_j ≤ Q_K）；L_ij为路线（i, j）的距离；目标是寻求最优的配送中心选址和2个阶段最优的车辆路径使货车的碳排放总量最小. 为方便建模，假设如下：1）可供物流园区使用的重型或中型货车以及可供配送中心共用的轻型或微型货车数量不限；2）货车在道路上处于正常的行驶状态；3）货车完成任务后必须返回原先出发的物流园区或配送中心；4）物流园区和配送中心内作业所产生的碳排放暂忽略不计；5）客户只能由从配送中心出发的货车提供服务，每个客户仅且只能被服务一次. 包含10个客户、4个候选配送中心和1个物流园区的2E-LRP示意如图1.

图 1 2E-LRP示意

Figure 1. An illustration of the 2E-LRP

下载: 全尺寸图片幻灯片

1.2 数学模型

若用q_ijh和q_ijk分别为货车h （h∈H）在路线（i, j）∈E₁ 、货车k （k∈K）在路线（i, j）∈E₂上行驶时的载重量；决策变量x_ijh =1表示货车h （h∈H）经过路线（i, j）∈E₁，否则x_ijh=0；y_ijk=1表示货车k （k∈K）经过路线（i, j）∈ E₂，否则y_ijk=0；z_i=1表示配送中心i （i∈V_s）被选用，否则z_i =0；u_ij =1表示客户j由配送中心i提供服务，否则u_ij =0；则以碳排放最小化为目标的2E-LRP数学模型可表示为

$\begin{split} & {\rm{min}}{\text{ }}\sum\limits_{\left( {i,j} \right) \in {E_1}} {\sum\limits_{h \in H} {\left[ {{{\left( {\varepsilon_{{\rm{vf}}H} - \varepsilon_{{\rm{ve}}H} } \right) q_{i jh}} / {Q_{H} + \varepsilon_{{\rm{ve}}H}}}} \right]} } {L_{i j}} x_{i jh} + \\ & \quad \sum\limits_{\left( {i,j} \right) \in {E_2}} {\sum\limits_{k \in K} {\left[ {{{\left( {\varepsilon_{{\rm{vf}}K} - \varepsilon_{{\rm{ve}}K}} \right) q_{i jk}} / {{Q_K} + \varepsilon_{{\rm{ve}}K}}}} \right]} } {L_{i j}} y_{i jk} ,\end{split}$

(1)

s.t.

$\sum\limits_{i \in {V_{\rm{s}}}} {x_{V_0ih}} \leqslant 1,\quad \forall h \in H,$

(2)

$\sum\limits_{i \in {V_{\rm{s}}}} {\sum\limits_{j \in {V_{\rm{c}}}} {y_{i jk}} } \leqslant 1,\quad \forall k \in K,$

(3)

$\sum\limits_{j \in {V_0} \cup {V_{\rm{s}}}\backslash\{i\}} {x_{jih} = \sum\limits_{j \in {V_0} \cup {V_{\rm{s}}}\backslash \{i\}} {x_{ijh}} } ,\quad\forall{i} \in {V_0} \cup {V_{\rm{s}}},h \in H ,$

(4)

$\sum\limits_{j \in {V_{\rm{s}}} \cup {V_{\rm{c}}}\backslash\{i\}} {y_{jik}} = \sum\limits_{j \in {V_{\rm{s}}} \cup {V_{\rm{c}}} \backslash\{i\}} {y_{ijk}} ,\quad \forall i \in {V_{\rm{s}}} \cup {V_{\rm{c}}},{\text{ }}k \in K ,$

(5)

$\sum\limits_{i \in {V_{\rm{s}}}} {{u_{ij}}} = 1,\quad \forall j \in {V_{\rm{c}}}，$

(6)

$\sum\limits_{t \in {V_{\rm{c}}}} {y_{itk} + \sum\limits_{t \in {V_{\rm{s}}} \cup {V_{\rm{c}}} \backslash\{j\}} {y_{t jk}} } \leqslant 1 + {u_{ij}},\;\;\; \forall{i} \in {V_{\rm{s}}},{\text{ }}j \in {V_{\rm{c}}},{\text{ }}k \in K ,$

(7)

$\sum\limits_{j \in {V_{\rm{c}}}} {{d_j} {u_{ij}} \leqslant {{\textit{z}}_i}{W_i}} ,\quad\forall i \in {V_{\rm{s}}} ,$

(8)

$\sum\limits_{j \in {V_{\rm{c}}}} {\sum\limits_{i \in {V_{\rm{s}}} \cup {V_{\rm{c}}}\backslash\{j\}} {{d_j}y_{ijk}} } \leqslant {Q_K},\quad\forall k \in K,$

(9)

$\sum\limits_{i \in {V_{\rm{s}}}} {\sum\limits_{j \in {V_0} \cup {V_{\rm{s}}}\backslash \{i\}} {\sum\limits_{t \in {V_{\rm{c}}}} {{d_t} {u_{it}}} x_{ijh}} } \leqslant {Q_H},\quad\forall h \in H ,$

(10)

$\sum\limits_{i \in {{V_{\rm{c1}}}}} {\sum\limits_{j \in {{V_{\rm{c1}}}\backslash \{i\}} } {y_{i jk} \leqslant \left| {{{V_{\rm{c1}}}}} \right|} } - 1,\;\;\; \forall k \in K,{\text{ }}{V_{\rm{c1}}} \subseteq {V_{\rm{c}}},{\text{ }}\left| {{{V_{\rm{c1}}}}} \right| \geqslant 2,$

(11)

$\sum\limits_{i \in {{V_{\rm{s1}}}}} {\sum\limits_{j \in {{V_{\rm{s1}}}}\backslash\{i\}} {x_{i jh}} } \leqslant \left| {{{V_{\rm{s1}}}}} \right| - 1,\;\;\; \forall h \in H,{\text{ }}{V_{\rm{s1}}} \subseteq {V_{\rm{s}}},{\text{ }}\left| {{{V_{\rm{s1}}}}} \right| \geqslant 2 ,$

(12)

$q_{itk} - {d_t} = q_{t jk},\quad \forall \; \left ( {i,t} \right),\left( {t,j} \right) \in {E_2},{\text{ }}t \in {V_{\rm{c}}},{\text{ }}k \in K ,$

(13)

$q_{ith} - \sum\limits_{j \in {V_{\rm{c}}}} {{d_j} {u_{tj}}} = q_{t jh},\;\;\; \forall \left( {i,t} \right),\left( {t,j} \right) \in {E_1},{\text{ }}t \in {V_{\rm{s}}},{\text{ }}h \in H,$

(14)

${{\textit{z}}_i} \in \left\{ {0,{\text{ }}1} \right\},\quad\forall i \in {V_{\rm{s}}},$

(15)

${u_{ij}} \in \left\{ {0,{\text{ }}1} \right\},\quad\forall i \in {V_{\rm{s}}},{\text{ }}j \in {V_{\rm{c}}} ,$

(16)

$x_{i jh} \in \left\{ {0,{\text{ }}1} \right\},\quad\forall \left( {i,{\text{ }}j} \right) \in {E_1},{\text{ }}h \in H{\text{ }} ,$

(17)

$y_{i jk} \in \left\{ {0,{\text{ }}1} \right\},\quad\forall \left( {i,{\text{ }}j} \right) \in {E_2},{\text{ }}k \in K .$

(18)

式（1）为目标函数，表示从物流园区到配送中心以及配送中心到客户2个阶段的货车碳排放量之和最小，与经典2E-LRP模型的目标函数（关于车辆通行成本或车辆行驶距离的函数）不同，是一个关于车辆载重和车辆行驶距离的函数；式（2）、（3）表示2个阶段中某一货车要么不被使用，要么至多被使用一次；式（4）、（5）保证2个阶段中货车路线的连续性，同时保证货车完成任务后返回原先出发的物流园区或配送中心；式（6）表示客户只能由一个配送中心提供服务；式（7）表示客户若由某一配送中心提供服务，则必被从该配送中心出发的货车访问一次；式（8）表示某一配送中心要么不被选用，若被选用，所服务的客户总需求量不能超过其作业能力；式（9）、（10）表示2个阶段中货车服务的客户需求均不能超过其载重能力；式（11）、（12）为2个阶段中路线的完整性约束；式（13）、（14）表示2个阶段中货车载重量在相邻路段上的数量关系；式（15）～（18）为决策变量的取值约束.

2. 算法设计

由于设施选址问题和车辆路径问题都属于NP-hard问题，所以本文研究的考虑碳排放的2E-LRP是更为复杂的NP-hard问题，求解难度很大，尤其是随着问题规模的增大，计算耗时呈指数增加. 鉴于此，本文设计了一种可快速求解大规模问题的2阶段混合算法（TSHA ），算法流程如图2所示. 第1阶段，通过将2E-LRP转化成不考虑车辆路径的2阶段设施选址问题（2E-FLP），直接求解配送中心选址方案和客户分配方案；第2阶段，基于得到的配送中心选址和客户分配方案，物流园区到被选用的配送中心以及每个配送中心到所分配客户的车辆路径问题就变成了独立且较易求解的VRP问题，进而加以解决.

图 2 两阶段混合算法的算法流程

Figure 2. Flowchart of the TSHA

下载: 全尺寸图片幻灯片

2.1 第1阶段算法

由于迭代算法在求解过程中非常低效，为提高所建模型的求解效率，TSHA在第1阶段先将考虑碳排放的2E-LRP转化成不考虑车辆路径的2E-FLP，模型如下：

${\rm{min}}{\text{ }}\sum\limits_{i \in {V_{\rm{s}}}} {\sum\limits_{j \in {V_{\rm{c}}}} {\left( {{L_{ij}} + {L_{i{V_0}}}} \right) {d_j} {u_{ij}} } } ,$

(19)

s.t.

$\sum\limits_{i \in {V_{\rm{s}}}} {{u_{ij}}} = 1,\quad\forall j \in {V_{\rm{c}}},$

$\sum\limits_{j \in {V_{\rm{c}}}} {{d_j} {u_{ij}} \leqslant {{\textit{z}}_i}{W_i}} ,\quad\forall i \in {V_{\rm{s}}},$

$\begin{split} {{\textit{z}}_i} \in \left\{ {0,{\text{ }}1} \right\},\quad\forall i \in {V_{\rm{s}}} , \end{split}$

$\begin{split} \\ {u_{ij}} \in \left\{ {0,{\text{ }}1} \right\},\quad\forall i \in {V_{\rm{s}}},{\text{ }}j \in {V_{\rm{c}}}. \end{split}$

式（19）为目标函数，表示客户到配送中心以及配送中心到物流园区的以需求量为权重的距离之和最小，约束条件对应原问题模型中的式（6）、（8）、式（15）、（16）. 不难看出，上述2E-FLP模型为线性规划模型，可直接运用Cplex求解器进行求解，从而得到配送中心选址和客户分配方案.

2.2 第2阶段算法

基于得到的配送中心选址和客户分配方案，物流园区到被选用的配送中心以及每个被选用配送中心到所分配客户的车辆路径问题都变成了独立的VRP问题. 为求解以碳排放最小化为目标的VRP问题，TSHA在第2阶段采用了一种改进的蚁群算法，如图3所示.

图 3 改进蚁群算法的伪代码

Figure 3. Pseudocode of the improved ant colony algorithm

下载: 全尺寸图片幻灯片

与经典的蚁群算法相同^[13]，改进的蚁群算法也包含2个关键步骤：1）主要负责路线的构建，即基于当前节点逐步选择下一个将要访问的节点；2）主要负责信息素浓度的更新，具体包括局部信息素更新和全局信息素更新.

从式（1）碳排放的计算式可以看出，货车的碳排放与其载重量和行驶距离密切相关. 为此，改进的蚁群算法采用了一种新的路线构建规则，如式（20）、式（21）所示.

$j=\left\{\begin{aligned} &{\rm{arg}}\text{ }\underset{j\in \varOmega }{{\rm{max}}}\left\{{\tau }_{ij} {\eta }_{ij}^{\alpha } {d}_{j}^{\beta }\right\},\quad q\leqslant {q}_{0},\\ & J,\quad q > q_0,\end{aligned}\right.$

(20)

$J:{p_{ij}} = \frac{{{\tau _{ij}} \eta _{ij}^\alpha d_j^\beta }}{{\displaystyle\sum\nolimits_{j \in \varOmega } {{\tau _{ij}} \eta _{ij}^\alpha d_j^\beta } }} ,$

(21)

式中：Ω为尚未被访问的节点集，Ω∈V_s或V_c；τ_ij 为当前节点i与未到访节点j 之间路线上的信息素浓度；η_ij 为节点i与节点j 之间距离的倒数；α 、β为重要度系数； q₀为给定的常数；q为 [0, 1] 上的随机数.

当随机产生的q ≤ q₀时，选择使${\tau }_{ij} {\eta }_{ij}^{\alpha } {d}_{j}^{\beta } $ 取值最大的j作为下一个将要访问的节点；当q > q₀时，则根据${\tau }_{ij} {\eta }_{ij}^{\alpha } {d}_{j}^{\beta } $ 的值所占的比例选择下一个将要访问的节点j ，在TSHA算法中采用轮盘赌的方式进行选择.

每只蚂蚁都按照上述的伪比例选择规则构建路线，当蚂蚁构建出一条路线（即达到货车的载重限制时，返回原先出发的物流园区或配送中心），然后重新出发构建下一条路线，如此反复，直至遍访所有客户. 当蚂蚁构建出一个完整的路线方案后，对该路线方案中的每条路线进行局部信息素更新，第t + 1次信息素浓度为

$\tau ^{(t + 1)}_{ ij} = (1-\rho) \tau^{(t)}_ {ij} + \rho \tau_{0},$

(22)

式中： ρ （0 ≤ ρ ≤1）为信息素的挥发系数；τ₀为初始的信息素浓度，取值为1/（mE_nns），E_nns为基于最近邻搜索算法得到的货车碳排放量.

当蚁群中每只蚂蚁均构建出一个完整的路线方案后，从中选择一个碳排放量最小的路线方案作为当次最优的路线方案，为在当次最优路线方案和当前最优路线之间取得平衡，亦即鼓励随后的蚂蚁在当次最优路线和当前最优路线附近的解空间继续搜索，改进的蚁群算法采用Ting等^[14]推荐的策略对当次最优和当前最优路线方案中的每条路线进行全局信息素更新，如式（23）、（24）所示.

${\tau _{ij} ^{(t+1)} } = (1 - \rho ) {\tau _{ij} ^{(t)} } + \rho \Delta \tau ,$

(23)

$\Delta \tau =\left\{\begin{aligned} &\left[({E}_{{\rm{IW}}}-{E}_{{\rm{GB}}}) + ({E}_{{\rm{IW}}}-{E}_{{\rm{IB}}})\right]/{E}_{{\rm{IW}}},\\ &\quad \text{ }若\text{ }(i,j)\text{ }属于当次或当前最优路线方案,\\ &{0,\quad}否则, \end{aligned}\right.$

(24)

式中：E_IW为当次最差路线方案产生的碳排放.

如此，通过若干次循环后即可得到所有以碳排放最小化为目标的VRP的最优路线方案. 考虑到由物流园区提供服务的配送中心数量较少而由每个配送中心提供服务的客户数量相对较多，对得到的配送中心到客户的VRP最优路线方案，本文运用3种局部搜索算法对其再进行改进：cross_relocation算法将从某个配送中心出发路线上的客户逐一插入从其他配送中心出发的路线中，若得到的路线可行且碳排放量小于原路线，则用改进后的路线替代原路线；cross_swap算法将从不同配送中心出发的两条路线上的客户两两交换并重新生成新的路线，若新路线可行且碳排放量较小，则替代原路线；最后，再对每一条路线运用3-opt算法进行改进. 至此，改进后的路线方案即可作为最终的最优路线方案.

3. 算例测试

由于目前还没有可用于测试2E-LRP碳排放的标准算例集，所以本文选取了Prodhon标准算例集^[15]中全部6个最大规模的算例稍加修改，用以测试本文所提出的模型和算法. Prodhon算例集中6个最大规模的算例均包括200个客户和10个候选配送中心. 算例的修改包括去掉原算例中的配送中心选址费用、增加不同类型货车的碳排放系数，其中重型或中型货车满载和空载时的碳排放系数分别为2.392、1.638 kg/km，轻型或微型货车满载和空载时的碳排放系数分别为1.096、0.772 kg/km，其他数据保持不变.

设计的TSHA算法采用MATLAB 2018b编程并嵌入Cplex V12.7求解器，改进的蚁群算法控制参数包括：求解物流园区到被选用的配送中心VRP问题时，循环次数设定为选用的配送中心个数的1/2，蚁群中蚂蚁的数量与选用配送中心个数相同；求解配送中心到被分配客户的VRP问题时循环次数均设定为被分配客户数量的1/2，蚁群中蚂蚁的数量均等于被分配的客户的数量；重要度系数α = 2，β = 1；给定常数q₀ = 0.5；挥发系数ρ = 0.2. 针对每个算例，独立运行程序20次，并分别记下计算结果和时间.

3.1 对TSHA算法思想的验证

为验证TSHA的算法思想，本文先编写了基于同样算法思想的TSHA-Ⅱ算法用以求解Prodhon算例集中6个最大规模的原算例. TSHA-Ⅱ与TSHA略微不同的是：1）用物流成本代替碳排放作为目标函数；2）改进的蚁群算法中，路线构建不考虑客户的货运需求量，即式（20）、（21）中去掉启发因子d_j. TSHA-Ⅱ算法的求解结果与目前文献中两种最新算法的求解结果对比如表1所示. 表中：B为目前文献所给出的最优解；C_min为基于某种算法得到的最优解；T_min为某种算法得到最优解所需的时间；G为某个算法求得的最优解与B之间的差异，即G = (C_min – B)/B.

表 1 TSHA-II算法与LNS-2E、Two-stage算法求解2E-LRP原算例的结果对比

Table 1. Comparison of the results obtained by LNS-2E, two-stage algorithm, and TSHA-II in solving original 2E-LRP instances

算例	B	LNS-2E 算法			Two-stage 算法			TSHA-II 算法
算例	B	C_min	T_min/s	G/%	C_min	T_min/s	G/%	C_min	T_min/s	G/%
200-10-1	548 703	550 672	725	0.36	561 840	8.15	2.39	557 751	25.179	1.65
200-10-1b	445 301	447 113	692	0.41	466 288	7.51	4.71	462 251	26.014	3.81
200-10-2	497 451	498 397	656	0.19	505 700	7.52	1.66	498 770	23.125	0.27
200-10-2b	422 668	422 877	601	0.05	428 749	7.67	1.44	424 170	24.794	0.36
200-10-3	527 162	533 174	668	1.14	546 708	7.31	3.71	541 628	23.366	2.74
200-10-3b	401 672	417 429	700	3.92	451 278	7.07	12.35	421 728	25.364	4.99
平均值			674	1.01		7.54	4.38		24.640	2.30

下载: 导出CSV

| 显示表格

通过对比可以看出：TSHA-Ⅱ算法求解大规模的2E-LRP算例时，求解质量稍逊于Breunig 等^[16]提出的LNS-2E算法，但明显优于Dai等^[17]提出的Two-stage算法；求解效率虽稍逊于后者，但大大优于前者. 这表明，TSHA-Ⅱ算法能够在求解质量与求解效率之间取得较好的平衡，可以在较短的时间内得到较高质量的解，TSHA的算法思想可行有效.

3.2 对考虑碳排放的2E-LRP算例的求解

算法思想通过验证后，TSHA再被用于求解考虑碳排放的2E-LRP大规模算例，计算结果如表2所示. 表中：E_avg为20次运算得到的平均碳排放量；E_max、E_min分别为20次运算得到的最大和最小碳排放量；T_avg为20次运算的平均耗时.

表 2 TSHA算法求解考虑碳排放的2E-LRP算例的结果

Table 2. Results obtained by TSHA in solving 2E-LRP instances considering carbon emissions

算例	E_avg/kg	E_max/kg	E_min/kg	T_avg/s	T_min/s
200-10-1	1860.3	1896.3	1818.9	23.195	23.087
200-10-1b	1341.9	1390.5	1275.6	27.905	24.598
200-10-2	1562.9	1579.4	1548.1	22.291	22.627
200-10-2b	1098.5	1110.3	1085.0	25.492	24.560
200-10-3	1968.5	1984.8	1947.6	26.037	26.508
200-10-3b	1357.4	1375.5	1342.5	26.570	27.128

下载: 导出CSV

| 显示表格

从表2可以看出，TSHA在求解考虑碳排放的2E-LRP大规模算例时，求解结果的最大值、最小值和平均值以及计算时长的最小值和平均值之间相差很小，表现稳定. 可见，TSHA可以作为求解考虑碳排放的2E-LRP大规模算例的一种有效算法.

4. 结　论

1）相较于经典的以物流成本最小化为目标的2E-LRP模型，本文基于一种简单实用的以排放因子为主要参数的碳排放计算方法，建立了以碳排放最小化为目标的2E-LRP优化模型.

2）对Prodhon标准算例集中全部6个最大规模算例的测试，表明TSHA-Ⅱ算法比现有算法更具兼顾求解结果和求解效率的优势，也证明了TSHA算法思想的可行性和有效性.

3） TSHA算法在求解考虑碳排放的2E-LRP大规模算例时表现得高效而且稳定，能够满足实际应用场景的计算要求.

4）本文提出的模型和算法有助于物流企业通过优化城市物流运作实现车辆的减排目标，服务国家“双碳”战略.

图 1 2E-LRP示意

Figure 1. An illustration of the 2E-LRP

下载: 全尺寸图片幻灯片

图 2 两阶段混合算法的算法流程

Figure 2. Flowchart of the TSHA

下载: 全尺寸图片幻灯片

图 3 改进蚁群算法的伪代码

Figure 3. Pseudocode of the improved ant colony algorithm

下载: 全尺寸图片幻灯片

表 1 TSHA-II算法与LNS-2E、Two-stage算法求解2E-LRP原算例的结果对比

Table 1. Comparison of the results obtained by LNS-2E, two-stage algorithm, and TSHA-II in solving original 2E-LRP instances

算例	B	LNS-2E 算法			Two-stage 算法			TSHA-II 算法
算例	B	C_min	T_min/s	G/%	C_min	T_min/s	G/%	C_min	T_min/s	G/%
200-10-1	548 703	550 672	725	0.36	561 840	8.15	2.39	557 751	25.179	1.65
200-10-1b	445 301	447 113	692	0.41	466 288	7.51	4.71	462 251	26.014	3.81
200-10-2	497 451	498 397	656	0.19	505 700	7.52	1.66	498 770	23.125	0.27
200-10-2b	422 668	422 877	601	0.05	428 749	7.67	1.44	424 170	24.794	0.36
200-10-3	527 162	533 174	668	1.14	546 708	7.31	3.71	541 628	23.366	2.74
200-10-3b	401 672	417 429	700	3.92	451 278	7.07	12.35	421 728	25.364	4.99
平均值			674	1.01		7.54	4.38		24.640	2.30

下载: 导出CSV

表 2 TSHA算法求解考虑碳排放的2E-LRP算例的结果

Table 2. Results obtained by TSHA in solving 2E-LRP instances considering carbon emissions

算例	E_avg/kg	E_max/kg	E_min/kg	T_avg/s	T_min/s
200-10-1	1860.3	1896.3	1818.9	23.195	23.087
200-10-1b	1341.9	1390.5	1275.6	27.905	24.598
200-10-2	1562.9	1579.4	1548.1	22.291	22.627
200-10-2b	1098.5	1110.3	1085.0	25.492	24.560
200-10-3	1968.5	1984.8	1947.6	26.037	26.508
200-10-3b	1357.4	1375.5	1342.5	26.570	27.128

下载: 导出CSV

参考文献(17)

[1]	CRAINIC T G, RICCIARDI N, STORCHI G. Advanced freight transportation systems for congested urban areas[J]. Transportation Research Part C: Emerging Technologies, 2004, 12(2): 119-137. doi: 10.1016/j.trc.2004.07.002
[2]	CRAINIC T G, RICCIARDI N, STORCHI G. Models for evaluating and planning city logistics systems[J]. Transportation Science, 2009, 43(4): 432-454. doi: 10.1287/trsc.1090.0279
[3]	CATTARUZZA D, ABSI N, FEILLET D, et al. Vehicle routing problems for city logistics[J]. EURO Journal on Transportation and Logistics, 2017, 6(1): 51-79. doi: 10.1007/s13676-014-0074-0
[4]	胡大伟,陈希琼,高扬. 定位-路径问题综述[J]. 交通运输工程学报,2018,18(1): 111-129. doi: 10.3969/j.issn.1671-1637.2018.01.011 HU Dawei, CHEN Xiqiong, GAO Yang. Review on location-routing problem[J]. Journal of Traffic and Transportation Engineering, 2018, 18(1): 111-129. doi: 10.3969/j.issn.1671-1637.2018.01.011
[5]	CUDA R, GUASTAROBA G, SPERANZA M G. A survey on two-echelon routing problems[J]. Computers & Operations Research, 2015, 55: 185-199. doi: 10.1016/j.cor.2014.06.008
[6]	中华人民共和国生态环境部. 中国移动源环境管理年报(2020)[EB/OL]. (2020-08-10)[2021-02-17]. https://www.mee.gov.cn/xxgk2018/xxgk/xxgk15/202008/t20200810_793252.html.
[7]	GOVINDAN K, JAFARIAN A, KHODAVERDI R, et al. Two-echelon multiple-vehicle location-routing problem with time windows for optimization of sustainable supply chain network of perishable food[J]. International Journal of Production Economics, 2014, 152: 9-28. doi: 10.1016/j.ijpe.2013.12.028
[8]	胡大伟,刘成清,胡卉,等. 基于低碳视角的两阶段开放式选址路径问题——燃油车与电动车对比[J]. 系统工程理论与实践,2020,40(12): 3230-3242. doi: 10.12011/SETP2019-0533 HU Dawei, LIU Chengqing, HU Hui, et al. The two-echelon open location routing problem based on low carbon perspective–fuel vehicles vs. electric vehicles[J]. Systems Engineering−Theory & Practice, 2020, 40(12): 3230-3242. doi: 10.12011/SETP2019-0533
[9]	刘成清,胡大伟,黄榕. 基于路径灵活性的两阶段开放式低碳选址-路径问题[J]. 科学技术与工程,2020,20(17): 7080-7087. doi: 10.3969/j.issn.1671-1815.2020.17.055 LIU Chengqing, HU Dawei, HUANG Rong. Two-echelon open low carbon location-routing problem based on path flexibility[J]. Science Technology and Engineering, 2020, 20(17): 7080-7087. doi: 10.3969/j.issn.1671-1815.2020.17.055
[10]	PITAKASO R, SETHANAN K, THEERAVIRIYA C. Variable neighborhood strategy adaptive search for solving green 2-echelon location routing problem[J]. Computers and Electronics in Agriculture, 2020, 173: 105406. doi: 10.1016/j.compag.2020.105406
[11]	DEMIR E, BEKTAS T, LAPORTE G. A review of recent research on green road freight transportation[J]. European Journal of Operational Research, 2014, 237(3): 775-793. doi: 10.1016/j.ejor.2013.12.033
[12]	蒋海青,赵燕伟,张景玲,等. 基于碳排放的开放选址-路径问题及算法[J]. 系统工程理论与实践,2020,40(1): 182-194. doi: 10.12011/1000-6788-2017-1375-13 JIANG Haiqing, ZHAO Yanwei, ZHANG Jingling, et al. Minimizing the carbon emission for the open location-routing problem and algorithm[J]. Systems Engineering−Theory & Practice, 2020, 40(1): 182-194. doi: 10.12011/1000-6788-2017-1375-13
[13]	DORIGO M, BIRATTARI M, STUTZLE T. Ant colony optimization: Artificial ants as a computational intelligence technique[J]. IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39.
[14]	TING C J, CHEN C H. A multiple ant colony optimization algorithm for the capacitated location routing problem[J]. International Journal of Production Economics, 2013, 141(1): 34-44. doi: 10.1016/j.ijpe.2012.06.011
[15]	PRODHON C. Classical instances for LRP[DB/OL]. Villetaneuse, Ile-de-France: Université Paris-Nord, (2010-02-25)[2021-02-17]. http://prodhonc.free.fr/Instances/instances_us.htm.
[16]	BREUNIG U, SCHMID V, HARTL R F, et al. A large neighbourhood based heuristic for two-echelon routing problems[J]. Computers & Operations Research, 2016, 76: 208-225.
[17]	DAI Z, AQLAN F, ZHOU Y. A two-phase method for multi-echelon location-routing problems in supply chains[J]. Expert Systems with Applications, 2019, 115: 618-634. doi: 10.1016/j.eswa.2018.06.050

施引文献

附加材料(0)

访问统计

点击查看大图

图(3) / 表(2)

计量

文章访问数: 682
HTML全文浏览量: 366
PDF下载量: 80
被引次数: 0

1. 模型构建
1.1 问题描述
1.2 数学模型
2. 算法设计
2.1 第1阶段算法
2.2 第2阶段算法
3. 算例测试
3.1 对TSHA算法思想的验证
3.2 对考虑碳排放的2E-LRP算例的求解
4. 结　论

考虑碳排放的两阶段选址-路径问题及其算法

doi: 10.3969/j.issn.0258-2724.20210773

作者简介: 汤希峰（1980—），男，讲师，博士，研究方向为运输与物流工程， E-mail：20110029@hhu.edu.cn

通讯作者: 何杰（1973—）， 男，教授，博士生导师， 研究方向为载运工具运用工程，E-mail：hejie@seu.edu.cn

计量

出版历程