考虑多充电桩排队和时间窗的电动货车路径规划

胡路; 乐诗彤; 朱娟秀

doi:10.3969/j.issn.0258-2724.20230084

考虑多充电桩排队和时间窗的电动货车路径规划

doi: 10.3969/j.issn.0258-2724.20230084

胡路^{1, 2,},
乐诗彤^{1, 2},
朱娟秀^{2, 3, ,}

1.
西南交通大学交通运输与物流学院，四川成都 610031
2.
西南交通大学综合交通大数据应用技术国家工程实验室，四川成都 610031
3.
西华大学管理学院，四川成都 610039

基金项目: 国家自然科学基金项目（62203367）

详细信息

作者简介:
胡路（1985—），男，副教授，博士，研究方向为共享交通和城市轨道交通，E-mail：hulu@swjtu.edu.cn

通讯作者:
朱娟秀（1989—），女，讲师，博士，研究方向为物流与交通系统建模与优化，E-mail：1220190011@mail.xhu.edu.cn

中图分类号: U492
计量
- 文章访问数: 314
- HTML全文浏览量: 93
- PDF下载量: 62
- 被引次数: 0
出版历程
- 收稿日期: 2023-03-02
- 修回日期: 2023-07-02
- 网络出版日期: 2024-11-07
- 刊出日期: 2023-07-13

Electric Truck Route Planning Considering Multiple Charging Pile Queues and Time Windows

HU Lu^{1, 2
,},
LE Shitong^{1, 2},
ZHU Juanxiu^{2, 3
, ,}

1.
School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, China
2.
National Engineering Laboratory of Integrated Transportation Big Data Application Technology, Southwest Jiaotong University, Chengdu 610031, China
3.
School of Management, Xihua University, Chengdu 610039, China

摘要

摘要:
在带时间窗的电动货车路径规划问题（EVRPTW）中，电动货车（EV）在前往充电站充电时可能需要排队. 为研究不同充电站配置方案对车辆路径和系统性能的影响，首先构建排队模型，刻画充电站中的排队现象；在EVRPTW基础上，综合考虑电量和流量约束，建立路径优化模型，并将充电站排队模型嵌入其中；优化目标包括最小化车辆耗电成本、司机工资、时间窗惩罚成本、充电桩总成本；为求解该模型，提出一种结合节约里程（C-W）和改进大邻域搜索（LNS）的混合启发式算法，其中，充电站的系统性能指标采用递归算法获得. 18组实验结果表明：同步增加充电桩数量可将车辆单次充电的平均排队时间控制在1～5 min，并有效减少2.6%～21.0%的总成本；增加充电站数量可缩短排队时间，但会增加整体路径总成本；当客户时间窗较短或服务时间较长时，充电桩数量变化对时间窗满足的影响更为显著.
- 物流 /
- 电动货车 /
- 充电站 /
- 混合启发式算法 /
- 递归算法
Abstract:
In the electric truck route planning problem with time windows, electric trucks may need to queue up when they go to charging stations for charging. To study the impact of different charging station configuration schemes on vehicle route planning and system performance, the queuing model was first built to describe the queuing phenomenon at charging stations. Then, a route optimization model was established by considering the power and flow constraints based on the electric truck route planning problem with time windows, with the queuing model of charging stations embedded into the optimization model. The optimization goals included minimizing vehicle power consumption costs, driver’s wages, penalty costs of time windows, and total costs of all charging piles. To solve the model, a hybrid heuristic algorithm combining mileage saving (C-W) and improved large neighborhood search (LNS) was designed, and the system performance metrics of charging stations were obtained by a recursive algorithm. 18 sets of experimental results show that increasing the number of charging piles simultaneously can control the average queuing time of a vehicle for charging within 1–5 minutes and effectively reduce the total cost by 2.6%–21.0%; increasing the number of charging stations can reduce the queuing time but increase the total cost of the entire route; when the customer time window is short, or the service time is long, the change in the number of charging piles has a more significant impact on the satisfaction of the time window.
- logistics /
- electric truck /
- charging station /
- hybrid heuristic algorithm /
- recursive algorithm

HTML全文

电动车辆路径规划问题（EVRP）是对车辆路径规划问题（VRP）的扩展延伸^[1]. 与VRP相比，EVRP还需要考虑电动车辆（EV）续航里程短和在行驶过程中需要充电的问题.

目前，关于EVRP充电的扩展研究已取得诸多成果，尤其是针对中途充电的EVRP、带时间窗的EVRP和时间依赖的EVRP的研究引起了广泛关注. 中途充电是EVRP研究中的基本特征. Schneider等^[2]对车辆去充电站的次数进行了限制，设定车辆在途中最多访问一次充电站，但这种限制会缩短车辆续航里程，进而增加车队规模. EV中途充电还涉及充电时间的优化问题，不同的行驶路径导致消耗电量不同，每辆车在充电站的充电时长也有所差异，因此，充电时间可作为一个重要的决策变量^[3-10].

部分研究在EVRP中引入时间窗约束以兼顾客户利益. Schneider等^[2]最早提出带时间窗的电动车辆路径规划问题（EVRPTW），以总旅行成本最小为目标. Keskin等^[11]在此基础上放宽了完全充电限制，允许车辆多次访问充电站. 但是Schneider等^[2,11]要求车辆必须在客户的时间窗内完成服务，这一严格限制可能导致路径长度显著增加. 为解决这一问题，葛显龙等^[12]提出带软时间窗的电动汽车路径优化问题，松弛了顾客的时间窗约束，从而减少不必要的绕路，降低了行驶成本，使路线规划更加经济且符合实际.

除中途充电和时间窗约束外，越来越多的EVRP研究引入动态参数或随机参数，以更贴近实际情况. 动态参数的EVRP主要聚焦在时间依赖的行驶时间^[13-15]和非线性充耗电函数^[16-18]. 随机参数的EVRP主要关注车辆到达、充电、配送作业等过程的随机性. 比如，Poonthalir等^[19]考虑车辆到达和服务时间的随机性，将每个能源补给站描述为M/M/1排队系统，考虑了单充电桩的路径规划问题，分析排队等待时间对车辆路径的影响. 由于电动车辆续航能力有限，车辆可以多次访问充电站，在充电站充电设备有限的情况下，多个车辆同一时段到达同一充电站就有可能出现排队现象. Keskin等^[20]在车辆路径问题中采用M/G/1排队模型刻画单个充电桩的充电过程，并采用求解器加自适应大邻域搜索算法求解大规模实例；在此基础上，设计两阶段混合启发式算法^[8]求解带M/M/1排队模型的EVRPTW. Keskin等^[20]的研究与本文最为相关，采用M/G/1排队模型模拟单个充电桩的充电过程，电动汽车到达充电站时间间隔服从参数为 $\lambda$ 的指数分布，充电时间是从一个不确定分布中得出，但已知其平均值和标准差. 基于该模型，可以计算车辆在充电站的排队时间.

上述文献回顾表明，现有电动货车路径规划研究要么假设充电站有足够多的充电桩来回避排队问题，要么假设充电站只有一个充电桩来简化问题. 然而，充电桩的数量直接影响车辆在充电站的排队时间，而排队时间又会影响配送时长和时间窗口的满足情况，进而影响车辆的路径规划. 而建模多个充电桩的排队模型并不是一个简单问题，主要面临以下挑战：1）各个充电桩的充电时间分布可能不同，这取决于电动车的电量耗费，因此无法简化为同分布的经典并联排队模型；2）电动车到达充电站的时间间隔分布不确定，受车辆从起点站的出发时刻、路段行程时间和上游节点服务时间的影响.

为解决这些问题，本文构建一个非经典的G(t)/ G(t)/c充电站排队模型. 其中：G(t)表示到达时间间隔和充电时间分布，会随时间t变化，受到排队系统中每辆车历史事件的影响；c为充电桩数量. 在此基础上，构建考虑充电站排队的EVRPTW优化模型，并设计一种混合启发式算法进行求解，其中充电站排队模型采用递归算法求解. 最后，通过18组实例对该算法进行测试和分析，以验证其有效性与优越性，并评估不同充电站配置方案对车辆路径和系统性能的影响.

1. 问题描述

本文研究同一类型电动货运车队覆盖所有客户的配送路线规划问题. 已知客户点的需求、位置以及客户要求的时间窗. 电动货车在配送途中可能需要前往充电站充电，并且在充电时可能会发生排队现象. 若电动货车在最早服务时间之前到达客户点处，则需等待直到服务时间开始；若在最晚服务时间之后到达，则会产生与延误时长成比例的惩罚. 在配送过程中，需要合理规划电动货车配送路径，以使包括车辆运输成本、时间窗惩罚成本、车辆固定成本和充电桩成本在内的总成本最低.

2. 数学模型

2.1 模型假设

本文基于Keskin等^[20]的研究，作出以下基本假设：

假设1　电动货车从配送中心出发，完成任务后需回到配送中心，每辆电动货车只行驶一条路线.

假设2　每个客户只能由一辆车提供服务.

假设3　每条路线上每个客户的需求总量不超过车辆的承载能力.

假设4　车辆在充电站完成充电后方可继续行驶.

2.2 符号说明

本文的电动货车路径规划定义在一个完全有向图中，有向图的顶点 $i$ 包括客户点、充电站及车辆中心出口和入口，其相关集合定义为： $V=\left\{1,\text{2},\cdots ,n\right\}$ ，为客户集合，共有 $n$ 个客户； $F$ 为充电站的集合，顶点 $0$ 和 $n + 1$ 分别表示车辆中心出口和入口； $V_{\mathrm{F}} = V\cup F$ ，为客户和充电站的合集； ${V_0} = \left\{ {V,\left\{ 0 \right\}} \right\}$ ，为客户和顶点 $0$ 的合集； ${V_{n + 1}} = \left\{ {V,\left\{ {n + 1} \right\}} \right\}$ ，为客户和顶点 $n + 1$ 的合集； ${V_{0,n + 1}} = \left\{ {V,\left\{ 0 \right\},\left\{ {n + 1} \right\}} \right\}$ ，为客户点与车辆中心出口和入口的集合； ${V}_{{\mathrm{F}},0}=\left\{{V}_{\mathrm{F}},\left\{0\right\}\right\}{\text{和}}{V}_{\mathrm{F},{n + 1}}=\left\{{V}_{\mathrm{F}},\left\{n + 1\right\}\right\}$ 为客户、充电站分别与顶点 $0$ 和 $n + 1$ 的合集； ${V_{{\mathrm{F}},0,n + 1}} = \left\{ {V_{\mathrm{F}},\left\{ 0 \right\},\left\{ {n + 1} \right\}} \right\}$ ，为有向图中所有顶点的合集； $\tilde{V}= \left\{\left(i,j\right)|i\in F,j\in {V}_{n + 1}或\;i\in {V}_{0},j\in {{V}}_{{\mathrm{F}},n + 1}\right\}$ 为充电站与客户点、顶点 $n + 1$ 或客户点、顶点 $0$ 与所有顶点组成的边合集. EFVRP的完全有向图定义为 $G = \left( {{{V}_{{\mathrm{F}},0,n + 1}},E} \right)$ ，其中， $E = \left\{ {\left( {i,j} \right)\left| {i,j \in {{V}_{{\mathrm{F}},0,n + 1}},i \ne j} \right.} \right\}$ ，表示有向图中所有顶点之间的边合集.

本文模型构建需要的符号及其说明如所示. 表中， $x_{i,j}$ 、 $y_i^{\mathrm{a}}$ 、 $y_i^{\mathrm{d}}$ 、 $v_i$ 、 $a_i$ 、 $f_i$ 、 $u_i$ 、 $w_{i,k}$ 、 ${\textit{z}}_{i,k}$ 、 $a_{i,k}$ 为决策变量.

表 1 符号说明

Table 1. Symbol descriptions

符号	说明	符号	说明
${d_{i,j}}$	顶点 $i$ 到顶点 $j$ 的行驶距离	${c_{\mathrm{s}}}$	所有充电站安装充电桩的总费用
${t_{i,j}}$	顶点 $i$ 到顶点 $j$ 的行驶时间	${x_{i,j}}$	当顶点 $i$ 与顶点 $j$ 在有向图中的路径被访问时为1，否则为0
${q_i}$	客户点 $i$ 的需求	$y_i^{\mathrm{a}}$	到达顶点 $i$ 时剩余电量
${s_i}$	客户点 $i$ 的服务时间	$y_i^{\text{d}}$	离开顶点 $i$ 时剩余电量
${e_i}$	客户点 $i$ 的最早服务时间	${v_i}$	到达顶点 $i$ 时的迟到时长
${l_i}$	客户点 $i$ 的最晚服务时间	${a_i}$	到达顶点 $i\;（i \in {V_{0,n + 1}}）$ 的时间
$G_0$	车辆装载容量	${f_i}$	在返回仓库之前，以顶点 $i$ 为最后访问节点的路线所花费的总时间
$Q$	车辆电池容量	${u_i}$	抵达顶点 $i$ 时的剩余货物容量
$g$	电池充电速率	${w_{i,k}}$	顶点 $i\;（i \in F）$ 进行第 $k$ 次所服务车辆需要的等待时间
$h$	电池单位距离消耗速率	${{\textit{z}}_{i,k}}$	顶点 $i\;（i \in F）$ 进行第 $k$ 次所服务车辆需要的充电时间
${c_{\mathrm{e}}}$	每单位距离消耗的电量成本	${a_{i,k}}$	顶点 $i\;（i \in F）$ 第 $k$ 次服务的车辆到达时间
${c_{\mathrm{p}}}$	每单位时间惩罚成本	$y_i^{\mathrm{a}}({a_{i,k}})$	当车辆到达顶点 $i$ 时间为 ${a_{i,k}}$ 时的剩余电量
${c_{\mathrm{f}}}$	每个顶点的运行成本，包括维护、购置成本以及在客户点工作的成本	${w_{i,k}}( {a_{i,k}} )$	当车辆到达顶点 $i$ 时间为 ${a_{i,k}}$ 时的等待时间
${c_{\mathrm{d}}}$	每单位时间司机工资

下载: 导出CSV

| 显示表格

2.3 模型建立

2.3.1 充电站排队模型

假设每个充电站都配备了相同数量c的充电桩. 每个充电站构成一个排队系统. 其中，充电桩为服务设施，电动货车为排队顾客. 电动货车在充电站根据先到先服务原则接受服务. 当电动货车到达充电站时，如果有充电桩是空闲的，车辆就立即接受服务；否则，到达的电动货车被分配到具有最短等待时间的充电桩（如果有多个充电桩可供选择，则选择编号最低的设备）. 每个充电站均可描述为一个独立的G(t)/G(t)/c排队系统.

以顶点i为例（ $i\in F$ ）描述其排队模型. 一旦充电站 $i$ 有充电桩可以使用，第 $k$ 次服务的车辆使用充电桩的时间为

${{\textit{z}}_{i,k}} = {{\left( {Q - y_i^{\mathrm{a}}({a_{i,k}})} \right)} \mathord{\left/ {\vphantom {{\left( {Q - y_i^a({a_{i,k}})} \right)} g}} \right. } g},\quad {\text{ }}i \in F,k \in {\bf{N}}.$

(1)

为计算与排队结果有关的统计数据，排队输出和评价指标采用递归方法，并引入一些中间变量来跟踪排队系统在一段时间内的状态. 充电站 $i$ 中第 $m$ 个充电桩提供服务前的排队时间矩阵 ${{\boldsymbol{D}}_{i,k,m}}{\text{ = }}\left( {{D_{i,k,m}}} \right)$ ，从 ${a_{i,k}}$ 开始计算，其中 $i \in F,k \in {\bf{N}},m = 1,{\text{2}}, \cdots ,c$ . 设置临时排队时间矩阵 ${{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{\boldsymbol D} }}_{i,k,m}} = ( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{D} }_{i,k,m}}} )$ ，表示充电站 $i$ 第 $k$ 次服务在每个充电桩需要排队的时间，其计算如式（2）所示.

${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{D} _{i,k,m}} = \left\{ {\begin{array}{*{20}{l}} {0,\quad k = 0,} \\ {\max \{ {{D_{i,k - 1,m}} - \left( {{a_{i,k}} - {a_{i,k - 1}}} \right),0} \},\quad k \in {\bf{N}}.} \end{array}} \right.$

(2)

利用该模型可以计算出2个重要的数量指标：充电站 $i$ 进行第 $k$ 次所服务车辆需要的等待时间 ${w_{i,k}}$ （式（3））、充电站 $i$ 第 $k$ 次所服务车辆使用的充电桩序号m （式（4））. m是通过一个反函数计算临时排队矩阵 ${{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{\boldsymbol D} }}_{i,k,m}}$ 中排队时间最小时的变量值，即所使用的充电桩序号. 结合原来的输入和输出参数，可以得到车辆的到达时间、服务开始时间、服务结束时间，离开时间.

${w_{i,k}} = \min \; {{{{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{D} }}}_{i,k,m}}} ,\quad {\text{ }}i \in F,k \in {\bf{N}},$

(3)

$m = \arg \min \; {{{{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{D} }}}_{i,k,m}}} ,\quad {\text{ }}i \in F,k \in {\bf{N}}.$

(4)

当车辆被分配到一个充电桩时，排队矩阵更新为下一个时间段，并将该车辆所花费的时间添加到所分配的充电桩的排队中. 更新排队矩阵如式（5）所示.

${{\boldsymbol{D}}_{i,k,m}} = {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{\boldsymbol D} }}_{i,k,m}} + {{\textit{z}}_{i,k}} + {a_{i,k}},\quad {\text{ }}i \in F,k \in {\bf{N}}.$

(5)

2.3.2 电动货车路径优化数学规划模型

本文的电动货车路径优化模型如下：

$\begin{split} & \min\ c_{\mathrm{e}}\sum\limits_{i\in V_{\mathrm{F},0}}^{ }\sum\limits_{j\in V_{\mathrm{F},n+1}}^{ }t_{i,j}x_{i,j}+c_{\mathrm{p}}\sum\limits_{i\in V}^{ }v_i+ \\ & \quad c_{\mathrm{f}}\sum\limits_{i\in V_{\mathrm{F},0}}^{ }\sum\limits_{j\in V_{\mathrm{F},n+1}}^{ }x_{i,j}+c_{\mathrm{d}}\sum\limits_{i\in V_{\mathrm{F}}}^{ }f_i+c_{\mathrm{s}},\end{split}$

(6)

$\sum\limits_{j \in {{V}_{{\mathrm{F}},n + 1}}} {{x_{i,j}}} = 1,\quad {\text{ }}i \in V,i \ne j,$

(7)

$\sum\limits_{i \in {V_{\mathrm{F},0}}} {{x_{i,j}}} = \sum\limits_{i \in {{V}_{{\mathrm{F}},n + 1}}} {{x_{j,i}}} ,\quad {\text{ }}j \in V_{\mathrm{F}},i \ne j,$

(8)

$\begin{split} & {a_i} + \left( {{t_{i,j}} + {s_i}} \right){x_{i,j}} - M\left( {1 - {x_{i,j}}} \right) \leqslant {a_j}, \\ &\quad {\text{ }}i \in {V_0},j \in {V_{{\mathrm{F}},n + 1}}, \end{split}$

(9)

$\begin{split} & {a_{i,k}} + \left( {{t_{i,j}} + {{\textit{z}}_{i,k}} + {w_{i,k}}\left( {{a_{i,k}}} \right)} \right){x_{i,j}} - M\left( {1 - {x_{i,j}}} \right) \leqslant {a_j},{\text{ }} \\ &\quad i \in F,j \in {V_{n + 1}},k \in {\bf{N}}, \end{split}$

(10)

$\begin{split} & 0 \leqslant {u_j} \leqslant {u_i} - {q_i}{x_{i,j}} + \left( {1 - {x_{i,j}}} \right)G_0,{\text{ }} \\ &\quad i \in {V_{\mathrm{F},0}},j \in {{V}_{{\mathrm{F}},n + 1}},i \ne j , \end{split}$

(11)

$0 \leqslant {u_0} \leqslant G_0,$

(12)

$y_j^{\text{a}} \leqslant y_i^{\mathrm{d}} - h{d_{i,j}}{x_{i,j}} + \left( {1 - {x_{i,j}}} \right)Q,\quad \left( {i,j} \right) \in \tilde V,$

(13)

$y_j^{\text{a}} \geqslant y_i^{\mathrm{d}} - h{d_{i,j}}{x_{i,j}} - \left( {1 - {x_{i,j}}} \right)Q,\quad\left( {i,j} \right) \in \tilde V,$

(14)

$0.1Q\sum\limits_{j \in {V_{\mathrm{F},0}}} {{x_{j,i}}} \leqslant y_i^{\text{a}},\quad {\text{ }}i \in {V_{{\mathrm{F}},n + 1}},i \ne j,$

(15)

$y_i^{\text{a}} \leqslant y_i^{\mathrm{d}} \leqslant Q,\quad {\text{ }}i \in {V_{\mathrm{F},0}},$

(16)

${e_i} \leqslant {a_i},\quad {\text{ }}i \in V,$

(17)

${v_i} \leqslant {a_i} - {l_i},\quad {\text{ }}i \in V,$

(18)

${x_{i,j}} \in \left\{ {0,1} \right\},\quad i \in {V_{\mathrm{F},0}},j \in {V_{{\mathrm{F}},n + 1}},i \ne j,$

(19)

式中：M为一个足够大的数字.

式（6）为目标函数，使得总成本最小，由5个部分组成：能源成本、与违反时间窗有关的惩罚成本、车辆的固定成本、司机工资、设立充电桩的总成本. 式（7）表示每个客户只能被服务1次；式（8）为车流量守恒约束；式（9）、（10）为跟踪车辆分别从客户和充电站出发后到达下一个顶点的时间；式（11）、式（12）确保每个客户的需求得到满足；式（13）、（14）为跟踪车辆分别离开充电站和客户时的电池状态；式（15）、（16）将电池的充电状态限制在10%～100%；式（17）是确保顶点 $i$ 在时间窗的最早服务时间开始之后才服务；式（18）确保当车辆晚到时晚到时间是非负数. 式（1）～（19）构成本文考虑多充电桩排队和时间窗的电动货车路径优化数学规划模型.

3. 算　法

EVRPTW是一个经典的NP-Hard问题，且本文建立的模型为非线性模型. 为此，设计一个混合启发式算法求解路径规划问题，充电站排队模型采用递归算法计算数量指标.

3.1 两阶段启发式算法

在路径规划求解算法中，节约里程法（C-W）简单易行，能够生成较好的可行解，但不一定是最优解. Shaw^[21] 首次提出大邻域搜索（LNS）算法，通过对初始解进行优化，包含移除部分客户并重新插入客户的过程，最终得到优化解. 刘小兰等^[22]提出的改进LNS算法具有更强的寻优能力，其结果非常接近已知最优解. 因此，本文采用C-W与改进LNS相结合的混合启发式算法来求解路径规划问题.

3.2 递归算法

本文将递归算法扩展至多个充电站的场景，用于求解充电站排队模型. 以路径优化模型提供的车辆到达充电站信息为输入，通过递归算法计算车辆在充电站的等待时间、充电时间以及每辆车使用的充电桩编号；然后，将这些输出参数返回路径优化模型，以更新各条路线的到达时间.

3.3 算法设计

算法流程如图1所示.

图 1 算法流程

Figure 1. Algorithm flowchart

下载: 全尺寸图片幻灯片

步骤1　采用C-W算法获得初始解 ${x_0}$ . 原C-W算法是以2条回路合并后运输距离减小幅度最大为求解目标，本文以运输时间为求解目标.

步骤2　以初始解 ${x_0}$ 为基础，利用LNS算法进行优化，包括移除客户和重新插入客户2个步骤.

1）移除客户

定义 $S$ 为将要移除的客户， $C$ 为移除客户组成的集合， $p$ 为移走的客户数目， ${x_{{\mathrm{cur}}}}$ 为从 ${x_0}$ 中移走 $p$ 个客户后剩余的部分解.

输入初始解 ${x_0}$ ，首先从 ${x_0}$ 中随机移走1个客户到 $C$ 中，作为集合 $C$ 的第1个元素. 剩下的 $p - 1$ 个元素按照如下方法来选定：将 ${x_0}$ 中剩余的客户按照与集合 $C$ 中所有客户的总体相关性由小到大的顺序排列；从 ${x_0}$ 中选出与集合 $C$ 中所有客户的总体相关性最大的客户 $S$ ，从 ${x_0}$ 中移走 $S$ ，并将其加入到 $C$ 中；重复该过程 $p - 1$ 次，直到选定剩下的 $p - 1$ 个元素.

客户 $i$ 和集合 $C$ 的总体相关性 $R(i,C)$ 如式（20）所示.

$R(i,C) = {{\sum\limits_{j \in C} {r(i,j)} } / {\left| C \right|}}\text{，}$

(20)

$r(i,j) = {1 \mathord{\left/ {\vphantom {1 {({t_{{\text{r}},i,j}} + {v_{ij}})}}} \right. } {({t_{{\text{r}},i,j}} + {v_{ij}})}} \text{，}$

(21)

式中： $\left| C \right|$ 为所有客户的数量； $r(i,j)$ 为客户i和j之间的相关性； $\mathop t\nolimits_{{\text{r}},i,j} = {{{t_{i,j}}} \mathord{\left/ {\vphantom {{{t_{i,j}}} {\max \;{t_{i,j}}}}} \right. } {\max \;{t_{i,j}}}}$ ，其值为0～1； ${v_{ij}}$ 为0-1变量，当 $i$ 和 $j$ 在同一条路径上时，取值为0，否则为1.

2）重新插入客户

重新插入过程是将移走的客户集重新插回部分解，以产生更好的解. 首先，计算集合 $C$ 中每个客户的最佳插入位置，将 $C$ 中的客户 $S$ 插回部分解，在多个插入位置中找出使运输时间增加最少的那个位置即为最佳插入位置，并记下对应的运输时间.

为把移出的客户插回部分解中，得到更好的解，比较 $C$ 中各个客户的最佳插入位置对应的运输时间，从中选一个能使运输时间增加最少的客户 $S$ ，按照运输时间递增的顺序，将 $S$ 插回部分解中，把 $S$ 从 $C$ 中移走，同时搜索将 $C$ 中剩余的客户都插回部分解 ${x_{{\mathrm{cur}}}}$ ，得到的所有解为 ${N_1}\left( {{x_{{\mathrm{cur}}}},C} \right)$ . 重复以上过程，直到 $C$ 为空集，表示当初被移走的客户都已经插回 ${x_{{\mathrm{cur}}}}$ . 比较 ${x_{{\mathrm{cur}}}}$ 与目前找到的最好解 ${x_{{\mathrm{pre}}}}$ ，如果 ${x_{{\mathrm{cur}}}}$ 比 ${x_{{\mathrm{pre}}}}$ 要好，则用 ${x_{{\mathrm{cur}}}}$ 替换 ${x_{{\mathrm{pre}}}}$ ，成为目前的最好解. 用记号 $f\left( {{N_1}\left( {{x_{{\mathrm{cur}}}},C} \right)} \right)$ 表示解 ${N_1}\left( {{x_{{\mathrm{cur}}}},C} \right)$ 所能达到的最小运输时间. 如果 $f\left( {{N_1}\left( {{x_{{\mathrm{cur}}}},C} \right)} \right)$ 的下界大于目前最好解 ${x_{{\mathrm{pre}}}}$ 的运输时间，则不用将 $C$ 中的客户再插回 ${x_{{\mathrm{cur}}}}$ . 只有当 $f\left( {{N_1}\left( {{x_{{\mathrm{cur}}}},C} \right)} \right)$ 的下界小于目前最好解 ${x_{{\mathrm{pre}}}}$ 的运输时间时，才继续搜索下去. 重复搜索，得到最优解.

步骤3　将获得的优化解插入充电站.

判断优化解中路线的可行性，即判断每条路线上客户点电量是否满足电量约束，若不满足，则需要在适当位置插入充电站，所有路线判断完毕，得到最终解.

充电站的插入位置按照以下方法执行：当检测到电量小于规定值的客户点时，在此不可行客户点同一条路线的上一个点后插入距离最近的充电站；检测到达最近充电站的电量，若到达充电站时电量为负，则再选择上一个客户点插入最近的充电站. 经过上述步骤就完成了充电站的插入，每插入一次，重新检验路径的可行性，若不可行，则重复上述操作，继续插入充电站，直到整条路径都满足电量约束.

步骤4　递归算法更新路线时间.

插入充电站之后，将路线中所有车辆前往充电站的信息，包括充电站序号、到达时间、充电时间等输入充电站排队模型. 采用递归算法计算充电站排队模型中的等待时间和每辆车在充电站使用的充电桩. 将计算出的结果返回最优解中，更新最优解.

4. 算例分析

本文考虑中途充电、带时间窗和随机参数的EVRP，而多仓库的EVRP不在研究范围内. 另外，本文需要分析充电站及充电桩数量变化对车辆排队时间的影响，客户数量太少车辆排队时间较短，不能很好地分析充电桩的变化对排队时间的影响；客户数量太多算例求解时间过长. 故为验证所提出的模型和算法的性能，算例分析部分使用Homberger实例^[23]，其中每个实例包括200个客户和1个仓库. Homberger中的实例^[23]并没有设置充电站. 参考文献[]，使用线性充电函数，并将充电速率 $g$ 设定为一次完全充电所需时间是平均客户服务时间的4倍. 电池的充电状态假定在0%～100%，其余参数参考文献[]. 本文采用的充电桩为专用50 kW充电桩，单个成本约为5万元，折算为每日成本约150元. 在本文的算例中，基于充电桩的每日成本进行计算. 在LNS中，移除客户的数量在上限 ${\bar n_{\text{c}}}$ 和下限 $\underline{n} { }_{\text{c}}$ 之间随机选择. ${\underline{n} { }_{\text{c}} } = \min \left\{ {0.1\left| n \right|,30} \right\}$ ， ${\bar n_{\mathrm{c}}} = \min \left\{ {0.4\left| n \right|,60} \right\}$ ，与Emec等^[25]研究类似.

4.1 充电桩数量影响分析

本文从Homberger的3个系列中各随机选择6个实例，分别为C系列（顾客比较集中、客户服务时间较长、充电速率较慢）、R系列（顾客均匀分布、客户服务时间较短、充电速率较快）和RC系列（C系列和R系列的合成）共计18个实例. 使用不同数量充电桩对每个系列的实例进行求解，并分析充电桩数量变化对车辆等待时间和路线成本产生的影响. 本节算例中，充电站数量设置为5个. 总成本为最终解对应的最小总成本，排队时间为车辆每次充电的平均排队时间，充电次数为所有车辆总充电次数.

图2（a）、（b）分别为各个系列在不同充电桩数量下的总成本平均值、排队时间平均值，图2（c）、（d）分别对应目标函数中违反时间窗的惩罚成本平均值和司机工资平均值.

图 2 不同充电桩数量的影响

Figure 2. Impact of different numbers of charging piles

下载: 全尺寸图片幻灯片

从图2中可以看出：增加充电桩数量对3个系列案列的总成本、排队时间、惩罚成本以及司机工资有不同程度的影响；C系列实例的客户服务时间较长，充电速率较慢，充电桩的数量变化对成本和车辆排队时间影响最明显；与充电桩为1个的情况相比，4个充电桩总成本减少21.0%，排队时间减少98%，平均排队时间降低到5 min内；R和RC系列实例的充电速率相同，都是快充，充电桩数量设置为4个比数量为1个时的总成本减少2.6%，排队时间可减少99%，平均排队时间可控制在1 min以内.

随着车辆在充电站排队时间降低，违反时间窗的惩罚成本和司机工资也随之降低. C系列实例充电速率较慢，违反时间窗的成本比其他2个系列高，增加充电桩数量对惩罚成本和司机工资的影响最大，充电桩数量增加到4个时，其惩罚成本可降低59.0%. R和RC系列排队时间相似，但是R系列客户点的时间窗属于窄时间窗，充电桩数量增加到4个时，其惩罚成本可降低18.0%，RC系列降低16.8%，说明违反时间窗对于窄时间窗的实例来说影响更大. 由于R、RC系列在充电站的充电时间和排队时间较短，当充电桩数量为3个时，车辆排队时间平均值接近0，当充电桩数量为4个时，惩罚成本变化小于充电桩成本的变化，导致充电桩数量为4个时的总成本反倒增加. 说明充电桩数量继续增加，每个系列的总成本都开始增加，但是其惩罚成本和司机工资都不变. 总的来说，充电桩的数量适当增加可以有效减少总成本和车辆排队时间.

4.2 充电站数量影响分析

为分析充电站数量变化对不同系列实例的路线成本、车辆在充电站等待时间、充电次数和电动车充电时间的影响，在上述18个实例中选择12个实例，将充电站数量设置为5～7个（实验表明，充电站数量低于5个时车辆无法找出同时满足充电需求和非负电量行驶的路径，故充电站数量从5个开始设置），车辆到达充电站的最低电量设置为10%，实例中充电桩数量均设置为2个，实验结果如图3所示. 图中，充电时间为车辆在充电站充电一次的平均充电时长. 实验表明，充电站数量为6个和7个时，电量约束更为严格，这使得车辆前往充电站的次数会增多.

图 3 不同充电站数量的影响

Figure 3. Impact of different numbers of charging stations

下载: 全尺寸图片幻灯片

图4展示了实例C1_2_5中当充电站数量从5个增加到6个时的最优路径对比. 充电站数量增加后，车辆前往充电站的次数更加频繁. 但从图3中可以看出，与设置5个充电站相比，充电站数量增加到6个或7个时，车辆单次充电的排队时间有所减少，其中C系列减少了18%，R系列减少了73%，RC系列减少了92%. 电量约束更为严格也导致车辆每次的充电时间减少. 但充电站数量增加到6个和7个时，总成本反而增加了12.0%～15.0%. 与6个充电站相比，7个充电站使得车辆服务客户后前往充电站的距离更短，从而减少了行驶途中电量的消耗，并降低了充电频率，但每次充电的时间有所延长. 由于C系列的充电速率较慢，增加充电站对其影响更为显著，图3显示其排队时间还可减少10%，总成本可降低2.0%. 对于R和RC系列的快充车辆，尽管充电时间增加导致排队时间略有上升，但总成本变化不大.

图 4 优化解路径对比

Figure 4. Comparison of optimized solution paths

下载: 全尺寸图片幻灯片

较高的电量约束条件使得充电次数增加，但是增加充电站数量可以减少车辆在充电站排队时间和充电时间. 车辆前往充电站的次数增多会导致车辆的行驶时间延长，进而增加车辆司机工资和充电成本. 此外，充电次数的增加和行驶时间的延长导致违反更多的时间窗口，客户的迟到成本大幅上升. 因此，尽管充电站数量增加至6个或7个时，排队时间有所减少，但总成本反而上升. 特别是当充电站数量增加到7个时，对于充电速率较快的实例，各项参数变化不明显.

5. 结论与展望

1）充电桩的数量会影响车辆在充电站的排队时间，进而影响整条线路的行驶时长和时间窗的满足，最终影响成本. 同步增加充电桩的数量到4个时，慢充的实例可以有效减少21.0%的总成本，平均排队时间可从400 min降低到5 min内；快充的实例减少16.8%～18.0%的惩罚成本，其平均排队时间可控制在1 min以内，但是其总成本比充电桩数量为3个时反倒增加. 总的来说，充电桩的数量适当增加可以有效减少总成本和车辆排队时间.

2）当客户时间窗较短或者充电时间较长时，充电桩数量的变化对惩罚成本影响更明显. 充电桩数量同步增加到4个时，C系列的排队时间减少98%， R系列和RC系列的排队时间减少99%，但充电桩数量变化对充电时间较长的C系列其惩罚成本影响更大；R和RC系列充电时间相同，但是充电桩数量变化对客户时间窗较短的R系列惩罚成本影响更明显.

3）在提高电量约束的情况下，增加充电站数量可以适当地减少车辆在充电站排队时间和充电时间，但是较高的电量约束使得充电次数增加，导致车辆的行驶时间延长，进而增加车辆司机工资、充电成本以及客户的迟到成本，使得整个路线的总成本增加. 充电站数量同步增加到6个和7个时，车辆排队时间减少了18%～92%，电量约束更为严格也导致车辆充电时间减少了4%～23%，但是成本反而增加了12.0%～15.0%. 另外对比充电站数量为6个，充电站数量为7个时对于充电速率较快的实例来说各项参数并没有明显的变化.

4）本文的模型依然存在一定局限性，将在后续研究中进行完善. 例如，本文基于充电站排队进行建模，其车辆必须等到充电后才离开，但实际中车辆若在充电站等待时间过长会选择离开或者前往另一个充电站；充电站数量较少时，即使充电桩的数量足够，也不能保证所有的路径被覆盖. 车辆在前往充电站的过程中会有一段负电量行驶，这与现实不符. 此外，在下一步研究中，还将针对道路交通拥堵路段构建电动货车排队模型，考虑在充电站排队和拥堵路段排队下的车辆路径规划，车辆可综合选择在道路上行驶时间和充电站排队时间最短的充电路径.

图 1 算法流程

Figure 1. Algorithm flowchart

下载: 全尺寸图片幻灯片

图 2 不同充电桩数量的影响

Figure 2. Impact of different numbers of charging piles

下载: 全尺寸图片幻灯片

图 3 不同充电站数量的影响

Figure 3. Impact of different numbers of charging stations

下载: 全尺寸图片幻灯片

图 4 优化解路径对比

Figure 4. Comparison of optimized solution paths

下载: 全尺寸图片幻灯片

表 1 符号说明

Table 1. Symbol descriptions

符号	说明	符号	说明
${d_{i,j}}$	顶点 $i$ 到顶点 $j$ 的行驶距离	${c_{\mathrm{s}}}$	所有充电站安装充电桩的总费用
${t_{i,j}}$	顶点 $i$ 到顶点 $j$ 的行驶时间	${x_{i,j}}$	当顶点 $i$ 与顶点 $j$ 在有向图中的路径被访问时为1，否则为0
${q_i}$	客户点 $i$ 的需求	$y_i^{\mathrm{a}}$	到达顶点 $i$ 时剩余电量
${s_i}$	客户点 $i$ 的服务时间	$y_i^{\text{d}}$	离开顶点 $i$ 时剩余电量
${e_i}$	客户点 $i$ 的最早服务时间	${v_i}$	到达顶点 $i$ 时的迟到时长
${l_i}$	客户点 $i$ 的最晚服务时间	${a_i}$	到达顶点 $i\;（i \in {V_{0,n + 1}}）$ 的时间
$G_0$	车辆装载容量	${f_i}$	在返回仓库之前，以顶点 $i$ 为最后访问节点的路线所花费的总时间
$Q$	车辆电池容量	${u_i}$	抵达顶点 $i$ 时的剩余货物容量
$g$	电池充电速率	${w_{i,k}}$	顶点 $i\;（i \in F）$ 进行第 $k$ 次所服务车辆需要的等待时间
$h$	电池单位距离消耗速率	${{\textit{z}}_{i,k}}$	顶点 $i\;（i \in F）$ 进行第 $k$ 次所服务车辆需要的充电时间
${c_{\mathrm{e}}}$	每单位距离消耗的电量成本	${a_{i,k}}$	顶点 $i\;（i \in F）$ 第 $k$ 次服务的车辆到达时间
${c_{\mathrm{p}}}$	每单位时间惩罚成本	$y_i^{\mathrm{a}}({a_{i,k}})$	当车辆到达顶点 $i$ 时间为 ${a_{i,k}}$ 时的剩余电量
${c_{\mathrm{f}}}$	每个顶点的运行成本，包括维护、购置成本以及在客户点工作的成本	${w_{i,k}}( {a_{i,k}} )$	当车辆到达顶点 $i$ 时间为 ${a_{i,k}}$ 时的等待时间
${c_{\mathrm{d}}}$	每单位时间司机工资

下载: 导出CSV

参考文献(25)

[1]	袁庆达,杜文,周再玲. 带软时间窗的混合车队车辆路线问题的模型和算法研究[J]. 西南交通大学学报,2001,36(4): 401-406. doi: 10.3969/j.issn.0258-2724.2001.04.015 YUAN Qingda, DU Wen, ZHOU Zailing. Model and algorithms for mixed fleet vehicle routing problem with soft time windows[J]. Journal of Southwest Jiaotong University, 2001, 36(4): 401-406. doi: 10.3969/j.issn.0258-2724.2001.04.015
[2]	SCHNEIDER M, STENGER A, GOEKE D. The electric vehicle-routing problem with time windows and recharging stations[J]. Transportation Science, 2014, 48(4): 500-520. doi: 10.1287/trsc.2013.0490
[3]	DESAULNIERS G, ERRICO F, IRNICH S, et al. Exact algorithms for electric vehicle-routing problems with time windows[J]. Operations Research, 2016, 64(6): 1388-1405. doi: 10.1287/opre.2016.1535
[4]	GOEKE D. Granular tabu search for the pickup and delivery problem with time windows and electric vehicles[J]. European Journal of Operational Research, 2019, 278(3): 821-836. doi: 10.1016/j.ejor.2019.05.010
[5]	PELLETIER S, JABALI O, LAPORTE G. The electric vehicle routing problem with energy consumption uncertainty[J]. Transportation Research Part B: Methodological, 2019, 126: 225-255. doi: 10.1016/j.trb.2019.06.006
[6]	CORTÉS-MURCIA D L, PRODHON C, MURAT AFSAR H. The electric vehicle routing problem with time windows, partial recharges and satellite customers[J]. Transportation Research Part E: Logistics and Transportation Review, 2019, 130: 184-206. doi: 10.1016/j.tre.2019.08.015
[7]	DOPPSTADT C, KOBERSTEIN A, VIGO D. The hybrid electric vehicle–traveling salesman problem with time windows[J]. European Journal of Operational Research, 2020, 284(2): 675-692. doi: 10.1016/j.ejor.2019.12.031
[8]	KESKIN M, ÇATAY B, LAPORTE G. A simulation-based heuristic for the electric vehicle routing problem with time windows and stochastic waiting times at recharging stations[J]. Computers & Operations Research, 2021, 125: 105060.1-105060.15.
[9]	YANG S Y, NING L J, TONG L C, et al. Optimizing electric vehicle routing problems with mixed backhauls and recharging strategies in multi-dimensional representation network[J]. Expert Systems with Applications, 2021, 176: 114804.1-114804.48.
[10]	YAO C Q, CHEN S B, YANG Z Y. Joint routing and charging problem of multiple electric vehicles: a fast optimization algorithm[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(7): 8184-8193. doi: 10.1109/TITS.2021.3076601
[11]	KESKIN M, ÇATAY B. Partial recharge strategies for the electric vehicle routing problem with time windows[J]. Transportation Research Part C: Emerging Technologies, 2016, 65: 111-127. doi: 10.1016/j.trc.2016.01.013
[12]	葛显龙,竹自强. 带软时间窗的电动车辆路径优化问题[J]. 工业工程与管理,2019,24(4): 96-104,112. GE Xianlong, ZHU Ziqiang. The electric vehicles routing problem with soft time window[J]. Industrial Engineering and Management, 2019, 24(4): 96-104,112.
[13]	XIAO Y 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
[14]	XU Z T, ELOMRI A, POKHAREL S, et al. A model for capacitated green vehicle routing problem with the time-varying vehicle speed and soft time windows[J]. Computers & Industrial Engineering, 2019, 137: 106011.1-106011.14.
[15]	ZULVIA F E, KUO R J, NUGROHO D Y. A many-objective gradient evolution algorithm for solving a green vehicle routing problem with time windows and time dependency for perishable products[J]. Journal of Cleaner Production, 2020, 242: 118428.1-118428.14.
[16]	MONTOYA A, GUÉRET C, MENDOZA J E, et al. The electric vehicle routing problem with nonlinear charging function[J]. Transportation Research Part B: Methodological, 2017, 103: 87-110. doi: 10.1016/j.trb.2017.02.004
[17]	ZUO X R, XIAO Y Y, YOU M, et al. A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function[J]. Journal of Cleaner Production, 2019, 236: 117687.1-117687.18.
[18]	FROGER A, MENDOZA J E, JABALI O, et al. Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions[J]. Computers & Operations Research, 2019, 104: 256-294.
[19]	POONTHALIR G, NADARAJAN R. Green vehicle routing problem with queues[J]. Expert Systems with Applications, 2019, 138: 112823.1-112823.18.
[20]	KESKIN M, LAPORTE G, ÇATAY B. Electric vehicle routing problem with time-dependent waiting times at recharging stations[J]. Computers & Operations Research, 2019, 107: 77-94.
[21]	SHAW P. Using constraint programming and local search methods to solve vehicle routing problems[M]// GOEBEL R, WAHLSTER W, ZHOU Z H. Lecture notes in computer science. Berlin:Springer, 1998:417-431.
[22]	刘小兰,郝志峰,汪国强,等. 有时间窗的车辆路径问题的近似算法研究[J]. 计算机集成制造系统,2004,10(7): 825-831. doi: 10.3969/j.issn.1006-5911.2004.07.019 LIU Xiaolan, HAO Zhifeng, WANG Guoqiang, et al. Improved large neighborhood search algorithm for vehicle routing problem with time windows[J]. Computer Integrated Manufacturing Systems, 2004, 10(7): 825-831. doi: 10.3969/j.issn.1006-5911.2004.07.019
[23]	SINTEF Digital. Transportation optimization portal [DB/OL]. (2008-02-27)[2023-02-19]. https://www.sintef.no/projectweb/top/vrptw.
[24]	KESKIN M, ÇATAY B. A matheuristic method for the electric vehicle routing problem with time windows and fast chargers[J]. Computers & Operations Research, 2018, 100: 172-188.
[25]	EMEÇ U, ÇATAY B, BOZKAYA B. An adaptive large neighborhood search for an E-grocery delivery routing problem[J]. Computers & Operations Research, 2016, 69: 109-125.

施引文献

附加材料(0)

访问统计

点击查看大图

图(4) / 表(1)

计量

文章访问数: 314
HTML全文浏览量: 93
PDF下载量: 62
被引次数: 0

1. 问题描述
2. 数学模型
2.1 模型假设
2.2 符号说明
2.3 模型建立
3. 算　法
3.1 两阶段启发式算法
3.2 递归算法
3.3 算法设计
4. 算例分析
4.1 充电桩数量影响分析
4.2 充电站数量影响分析
5. 结论与展望

考虑多充电桩排队和时间窗的电动货车路径规划

doi: 10.3969/j.issn.0258-2724.20230084

作者简介: 胡路（1985—），男，副教授，博士，研究方向为共享交通和城市轨道交通，E-mail：hulu@swjtu.edu.cn

通讯作者: 朱娟秀（1989—），女，讲师，博士，研究方向为物流与交通系统建模与优化，E-mail：1220190011@mail.xhu.edu.cn

计量

出版历程