电动车路径的蚁群优化问题
1.问题表述
EVRP是传统VRP的变体，因此，它遵循本节所述的类似公式。EVRP实例由完全连接的加权图G=（N）建模cup; F、 L），其中N={1，hellip;，N}是一组N个客户（节点），F={N 1，hellip;，N s}cup; {0}是一组s能量充电站和一个中央仓库0，该仓库也是一个充电站和L={（i，j）| i，jisin; N} 是一组连接它们的链接（圆弧）。每个弧（i，j）isin; L与非负值tij=R 相关，代表客户i和j之间的旅行时间，可定义为：
式中，dij和sij是与弧（i，j）相关的距离（km）和平均速度（km/h）1isin; 五十、 分别。每个客户我isin; N与需要由m辆车队交付的某些货物的非负需求delta;i以及从车辆上卸载货物的服务时间sigma;i相关。注意，sigma;i与客户i的需求成正比isin; N（例如，需求越高，delta;i，所需服务时间越长）。电动汽车在电弧（i，j）上的车辆载荷，例如k，给定为l k ij（即0le; l k ijle; Q） ，其中Q是最大车辆容量（每辆电动汽车的最大容量可能不同）。每辆电动汽车的最大服务时间为J分钟（这对于电动汽车的所有驾驶员来说都是一样的，基本上定义了驾驶员的最大工作时间）。每个充电站iisin; F与表示可能等待时间的非负等待时间wi相关联。所有充电站的蓄电池充电率r相同且恒定。
每辆电动汽车都有一个电池电量（即k i），用于确定到达客户或充电站i时的当前电量isin; Ncup; 满足0的Fle; e k ile; BC，其中BC是最大电池容量。电动汽车在充电站i处的充电时间c k iisin; F由其当前能级e k i和电站的充电率确定，c k i=（BCminus;e k i）/r假设电动汽车将充满电（即达到其最大电池容量BC）。请注意，所有电动汽车在一天开始离开车辆段时都已充满电和负载。
该问题的目标是找到一组最小的M={1，hellip;，M}电动汽车，一次且仅一次访问所有客户，满足他们的需求，全部从车辆段开始并在车辆段结束，从而使总行程时间（包括驾驶时间、充电站的充电和等待时间）最小化。完整的EVRP解决方案pi;由节点排列（客户和能量充电站）定义，并由所有EV的完整路线组成。EVRP解决方案的评估如下：
式（2）定义了EVRP目标函数（以分钟为单位的输出），式（3）确保每个客户只访问一次，式（3）。（4）和（5）确保所有电动汽车离开并返回中央车辆段，等式（6）确保电动汽车在访问客户或充电站时也离开，等式（7）确保没有电动汽车过载，等式（8）确保电动汽车的最大服务时间得到遵守，等式（9）确保电池电量降低Bk ij（稍后等式（15）中有更详细的描述）当从客户i访问客户j时，等式（10）确保有足够的能量返回车辆段或访问充电站，等式（11）和等式（12）定义如下：
1.1.能源消耗
用于计算客户i和j之间第k辆电动汽车能耗的能耗模型定义如下[19]：
式中，aij=a g sintheta;ij gCR costheta;ij是一个特定于圆弧的常数，z=0.5CDAD是一个特定于车辆的常数，EF是发动机效率，w是车辆整备重量（kg），a是加速度（m/s2），g是重力常数（m/s2），theta;ij是与圆弧（i，j）相关的道路角度（度），A是车辆的正面表面积（m2），D是空气密度（kg/m3），CR是滚动阻力系数，CD是滚动阻力系数。请注意，对于不同的电动汽车（即使我们有相同的电动汽车车队），使用公式（15）计算的能耗在同一电弧上行驶可能会有所不同，因为它们的电流负载可能不同（即l k ij）。负载较重的电动汽车比负载较轻的电动汽车消耗更多的能量。请注意，每当服务客户（例如卸货）时，电动汽车的负载都会发生变化。还有其他动态因素会影响电动汽车的能耗，如交通状况[24]、怠速和加速情况的数量[1]、道路角度[23]、天气和座舱温度[2]以及许多其他不确定性。
2. 构造解决方案
通过蚂蚁阅读信息素来构造解决方案，并编写信息素来标记他们构造的解决方案（见算法1）。每个ant h代表一个完整的EVRP解决方案（即所有EV的路线）。概率（1）minus; q0）第h个蚂蚁使用概率规则从客户i（即勘探）中选择客户j，如下所示：
概率q0时，h-th蚂蚁从客户i中选择下一个客户j，其概率最高（即利用），如下所示：
其中q0（0le; q0le; 1） 是一个决策规则参数，tau;ij和eta;ij分别是客户i和j之间现有的信息素线索和先验可用的启发式信息。启发式信息的计算公式为eta;ij=（1/tij），其中tij的定义如式（1）所示。N h i是满足等式（7）中EV容量约束和等式（8）中与客户i相邻的第h个ant的最大服务时间约束的未访问客户集。当N h i=empty; 然后将中央车辆段（即0）添加到表示另一辆电动汽车路线的EVRP解决方案中。alpha;和beta;分别是决定tau;ij和eta;ij相对影响的两个参数。
2.1.访问充电站
为了确保电动汽车有足够的能量行驶，满足客户的需求并返回中央车辆段，他们可能需要参观（或参观）能源充电站。换句话说，满足等式中的能量约束。（9） 和（10）在每个解决方案构建步骤中，每个ant h必须确保留给EV足够的能量，以访问F组的至少一个充电站。请注意，同一辆或不同的电动汽车可以多次访问充电站。为了在能量方面构建可行的解决方案，算法必须向前看，以发现在拜访客户后，是否有任何充电站（包括作为充电站的车辆段）在其范围内。因此，在Eqs中，N-h-i是一组未访问的客户。（16） 和（17）还必须满足上述能量约束。如果没有，那么他们的潜在风险是电动汽车将在某个时候耗尽能源。假设一个EV，比如k，使用等式中定义的决策规则访问客户i。（16） 及(17)。然后，根据客户i的能量水平，访问充电站或中央车辆段所需的能量范围必须满足e k iminus; 比尔ge; 0, exist; Lisin; F能够随时充电（如果需要）。通过这种方式，该算法确保没有电动汽车没有能量，并消除了对等式中能量约束的违反。（9） 及(十)。最后，如果电动汽车能量范围内的所有客户违反等式（7）中的容量约束或等式（8）中的服务约束，则电动汽车必须根据等式（16）中的决策规则返回中央车辆段。
2.2. 更新信息素
本文采用了MMAS[25]、[26]的信息素更新策略。开始时，所有信息素轨迹初始化如下：
式中rho;（0lt;rho;le; 1） 是信息素蒸发率（见下文），C nn是最近邻启发式2生成的行程长度。然后，通过应用蒸发更新信息素轨迹，如下所示：
∆tau;best ij=1/Cbest是最好的蚂蚁储存的信息素量，C best是最佳解决方案pi;best的成本（即C best=phi;（pi;best））。允许存储信息素的“最佳”蚂蚁可以是迄今为止最好的蚂蚁3（pi;bs），在这种情况下，C best=C bs，或者迭代最佳蚂蚁（pi;ib），在这种情况下，C best=C ib，其中C bs和C ib分别是迄今为止最好的蚂蚁（即C bs=phi;（pi;bs））和迭代最佳蚂蚁（即C ib=phi;（pi;ib））。这两种蚂蚁是以另一种方式应用的。更准确地说，迭代最佳蚂蚁被允许作为默认值来存放信息素，并且迄今为止最佳蚂蚁仅在每一个固定的迭代次数中使用（即25次，更多细节见[26]）。施加信息素轨迹值的下限和上限tau;min和tau;max。tau;max值以1/（rho;Cbs）为界，其中Cbs最初是公式（18）中定义的估计最优回路（即cnn）的解质量，随后每当发现新的迄今为止最佳解质量时，更新。tau;min值设置为tau;min=tau;max（1minus; radic;n 0.05）/（平均值minus; 1)radic;n 0.05），其中avg是蚂蚁在每个溶液构建步骤中可用的不同选择的平均数量。由于只允许迄今为止最好的蚂蚁和迭代最好的蚂蚁来存储信息素，因此该算法可以快速达到停滞行为。为了解决这个问题，偶尔会将信息素轨迹重新初始化为tau;max值。例如，每当停滞行为4发生时，或者在给定次数的迭代中没有找到改进的解决方案时，信息素轨迹都会重新初始化。
3. 实验装置
在实验中，我们将ACO-EVRP应用于从VRPLIB5获得的三个典型VRP问题基准实例（即F-n45-k4.VRP、F-n72-k4.VRP和F-n135-k7.VRP）。考虑到第二节中所述的EVRP，电动汽车需要充电站进行充电。由于EVRP基准实例不可用，将充电站添加到三个常规VRP实例中，分别生成三个EVRP基准实例F-n45-k4.EVRP、F-n72-k4.EVRP和F-n135-k7.EVRP 6。充电站的分布方式可以覆盖问题实例的所有客户。由此产生的问题实例如图1所示，其规格如表1所示。此外，对传统VRP基准实例的容量和客户需求进行了修改，以符合史密斯-牛顿电动货车的规格[19]。考虑到这些电动汽车的车辆额定总重（GVWR）为7.5吨，其车辆整备重量为3.629吨，最大货物（或容量）估计为3.871吨（即等式（7）中的参数Q）。电动汽车驾驶员一天的最大服务时间设置为480分钟（8小时）（即等式（8）中的参数J）。我们的EVRP模型中用于模拟实验的其余参数值如表II所示。算法对50次独立执行（在同一组随机种子上）执行10e4次迭代，并记录平均总行程时间（以分钟为单位）以及总行程（以公里为单位）、可行性（以成功执行的百分比表示）、充电次数和使用的电动汽车数量。就每次执行的能量而言，完整EVRP解决方案的可行性必须满足ek ige; 0, forall;我isin; Ncup; Fforall;Kisin; M.还记录在执行过程中找到解决方案的平均迭代次数和CPU时间（以秒为单位）。实验是在Linux系统下进行的，该系统采用Intel Core i7-3930K 3.20GHz处理器，具有12MB缓存和16GB RAM。对于实验，使用了50个ANT，使用的常用参数设置为以下典型值：alpha;=1和beta;=5，而q0和rho;参数的影响将在下一小节中进一步研究。B.关于决策规则和蒸发率参数影响的结果众所周知，等式（17）和等式（19）中分别定义的q0和rho;参数对ACO metaheuris tic的勘探和开发有很大影响。由于它们是关键参数，我们系统地改变值如下：q0isin; {0.0,0.2,0.5,0.9}和rho;isin; {0.02, 0.2, 0.4, 0.6, 0.8}. 表III给出了所有参数组合的实验结果。此外，针对迭代的溶液质量（分钟）。从表III、图2和图3可以看出，ACO-EVRP溶液质量随着rho;值的增加而提高。对于F-n135-k7.evrp，当蒸发率设置为rho;=0.6，对于其他两种情况，当蒸发率设置为rho;=0.8时，可获得最佳平均结果。同样的观察结果适用于q0的所有值。然而，当决策规则参数设置为q0=0.0时，ACO-EVRP的性能更好。就效率而言，ACO-EVRP在几秒钟内输出其最佳解决方案（例如，F-n135-k7.EVRP为18.6秒，这是最大的问题实例）。对于其余的实验，对于所有问题实例，我们将决策规则参数设置为q0=0.0，对于F-n45-k4.evrp和F-n72-k4.evrp，蒸发率设置为rho;=0.8，对于F-n135-k7.evrp，蒸发率设置为rho;=0.6。值得一提的是，对于其他问题实例，不同的参数组合可能会执行得更好。
3.1信息素试验效果的结果
为了研究ACO-EVRP产生的信息素轨迹的影响，我们根据公式（16）设置了alpha;=0，因此在构建解决方案时不考虑信息素轨迹。ACO-EVRP与信息素追踪（表示为DACO EVRP ）和ACO-EVRP不含信息素追踪（表示为ACO-EVRP））的比较minus;) 表IV中给出了这些数据。此外，使用Mann–Whitney统计检验进行两两比较（粗体值表示与置信水平95%存在显著差
剩余内容已隐藏，支付完成后下载完整资料
一、外文资料译文：
电动车路径的蚁群优化问题
1.问题表述
EVRP是传统VRP的变体，因此，它遵循本节所述的类似公式。EVRP实例由完全连接的加权图G=（N）建模cup; F、 L），其中N={1，hellip;，N}是一组N个客户（节点），F={N 1，hellip;，N s}cup; {0}是一组s能量充电站和一个中央仓库0，该仓库也是一个充电站和L={（i，j）| i，jisin; N} 是一组连接它们的链接（圆弧）。每个弧（i，j）isin; L与非负值tij=R 相关，代表客户i和j之间的旅行时间，可定义为：
式中，dij和sij是与弧（i，j）相关的距离（km）和平均速度（km/h）1isin; 五十、 分别。每个客户我isin; N与需要由m辆车队交付的某些货物的非负需求delta;i以及从车辆上卸载货物的服务时间sigma;i相关。注意，sigma;i与客户i的需求成正比isin; N（例如，需求越高，delta;i，所需服务时间越长）。电动汽车在电弧（i，j）上的车辆载荷，例如k，给定为l k ij（即0le; l k ijle; Q） ，其中Q是最大车辆容量（每辆电动汽车的最大容量可能不同）。每辆电动汽车的最大服务时间为J分钟（这对于电动汽车的所有驾驶员来说都是一样的，基本上定义了驾驶员的最大工作时间）。每个充电站iisin; F与表示可能等待时间的非负等待时间wi相关联。所有充电站的蓄电池充电率r相同且恒定。
每辆电动汽车都有一个电池电量（即k i），用于确定到达客户或充电站i时的当前电量isin; Ncup; 满足0的Fle; e k ile; BC，其中BC是最大电池容量。电动汽车在充电站i处的充电时间c k iisin; F由其当前能级e k i和电站的充电率确定，c k i=（BCminus;e k i）/r假设电动汽车将充满电（即达到其最大电池容量BC）。请注意，所有电动汽车在一天开始离开车辆段时都已充满电和负载。
该问题的目标是找到一组最小的M={1，hellip;，M}电动汽车，一次且仅一次访问所有客户，满足他们的需求，全部从车辆段开始并在车辆段结束，从而使总行程时间（包括驾驶时间、充电站的充电和等待时间）最小化。完整的EVRP解决方案pi;由节点排列（客户和能量充电站）定义，并由所有EV的完整路线组成。EVRP解决方案的评估如下：
式（2）定义了EVRP目标函数（以分钟为单位的输出），式（3）确保每个客户只访问一次，式（3）。（4）和（5）确保所有电动汽车离开并返回中央车辆段，等式（6）确保电动汽车在访问客户或充电站时也离开，等式（7）确保没有电动汽车过载，等式（8）确保电动汽车的最大服务时间得到遵守，等式（9）确保电池电量降低Bk ij（稍后等式（15）中有更详细的描述）当从客户i访问客户j时，等式（10）确保有足够的能量返回车辆段或访问充电站，等式（11）和等式（12）定义如下：
1.1.能源消耗
用于计算客户i和j之间第k辆电动汽车能耗的能耗模型定义如下[19]：
式中，aij=a g sintheta;ij gCR costheta;ij是一个特定于圆弧的常数，z=0.5CDAD是一个特定于车辆的常数，EF是发动机效率，w是车辆整备重量（kg），a是加速度（m/s2），g是重力常数（m/s2），theta;ij是与圆弧（i，j）相关的道路角度（度），A是车辆的正面表面积（m2），D是空气密度（kg/m3），CR是滚动阻力系数，CD是滚动阻力系数。请注意，对于不同的电动汽车（即使我们有相同的电动汽车车队），使用公式（15）计算的能耗在同一电弧上行驶可能会有所不同，因为它们的电流负载可能不同（即l k ij）。负载较重的电动汽车比负载较轻的电动汽车消耗更多的能量。请注意，每当服务客户（例如卸货）时，电动汽车的负载都会发生变化。还有其他动态因素会影响电动汽车的能耗，如交通状况[24]、怠速和加速情况的数量[1]、道路角度[23]、天气和座舱温度[2]以及许多其他不确定性。
2. 构造解决方案
通过蚂蚁阅读信息素来构造解决方案，并编写信息素来标记他们构造的解决方案（见算法1）。每个ant h代表一个完整的EVRP解决方案（即所有EV的路线）。概率（1）minus; q0）第h个蚂蚁使用概率规则从客户i（即勘探）中选择客户j，如下所示：
概率q0时，h-th蚂蚁从客户i中选择下一个客户j，其概率最高（即利用），如下所示：
其中q0（0le; q0le; 1） 是一个决策规则参数，tau;ij和eta;ij分别是客户i和j之间现有的信息素线索和先验可用的启发式信息。启发式信息的计算公式为eta;ij=（1/tij），其中tij的定义如式（1）所示。N h i是满足等式（7）中EV容量约束和等式（8）中与客户i相邻的第h个ant的最大服务时间约束的未访问客户集。当N h i=empty; 然后将中央车辆段（即0）添加到表示另一辆电动汽车路线的EVRP解决方案中。alpha;和beta;分别是决定tau;ij和eta;ij相对影响的两个参数。
2.1.访问充电站
为了确保电动汽车有足够的能量行驶，满足客户的需求并返回中央车辆段，他们可能需要参观（或参观）能源充电站。换句话说，满足等式中的能量约束。（9） 和（10）在每个解决方案构建步骤中，每个ant h必须确保留给EV足够的能量，以访问F组的至少一个充电站。请注意，同一辆或不同的电动汽车可以多次访问充电站。为了在能量方面构建可行的解决方案，算法必须向前看，以发现在拜访客户后，是否有任何充电站（包括作为充电站的车辆段）在其范围内。因此，在Eqs中，N-h-i是一组未访问的客户。（16） 和（17）还必须满足上述能量约束。如果没有，那么他们的潜在风险是电动汽车将在某个时候耗尽能源。假设一个EV，比如k，使用等式中定义的决策规则访问客户i。（16） 及(17)。然后，根据客户i的能量水平，访问充电站或中央车辆段所需的能量范围必须满足e k iminus; 比尔ge; 0, exist; Lisin; F能够随时充电（如果需要）。通过这种方式，该算法确保没有电动汽车没有能量，并消除了对等式中能量约束的违反。（9） 及(十)。最后，如果电动汽车能量范围内的所有客户违反等式（7）中的容量约束或等式（8）中的服务约束，则电动汽车必须根据等式（16）中的决策规则返回中央车辆段。
2.2. 更新信息素
本文采用了MMAS[25]、[26]的信息素更新策略。开始时，所有信息素轨迹初始化如下：
式中rho;（0lt;rho;le; 1） 是信息素蒸发率（见下文），C nn是最近邻启发式2生成的行程长度。然后，通过应用蒸发更新信息素轨迹，如下所示：
∆tau;best ij=1/Cbest是最好的蚂蚁储存的信息素量，C best是最佳解决方案pi;best的成本（即C best=phi;（pi;best））。允许存储信息素的“最佳”蚂蚁可以是迄今为止最好的蚂蚁3（pi;bs），在这种情况下，C best=C bs，或者迭代最佳蚂蚁（pi;ib），在这种情况下，C best=C ib，其中C bs和C ib分别是迄今为止最好的蚂蚁（即C bs=phi;（pi;bs））和迭代最佳蚂蚁（即C ib=phi;（pi;ib））。这两种蚂蚁是以另一种方式应用的。更准确地说，迭代最佳蚂蚁被允许作为默认值来存放信息素，并且迄今为止最佳蚂蚁仅在每一个固定的迭代次数中使用（即25次，更多细节见[26]）。施加信息素轨迹值的下限和上限tau;min和tau;max。tau;max值以1/（rho;Cbs）为界，其中Cbs最初是公式（18）中定义的估计最优回路（即cnn）的解质量，随后每当发现新的迄今为止最佳解质量时，更新。tau;min值设置为tau;min=tau;max（1minus; radic;n 0.05）/（平均值minus; 1)radic;n 0.05），其中avg是蚂蚁在每个溶液构建步骤中可用的不同选择的平均数量。由于只允许迄今为止最好的蚂蚁和迭代最好的蚂蚁来存储信息素，因此该算法可以快速达到停滞行为。为了解决这个问题，偶尔会将信息素轨迹重新初始化为tau;max值。例如，每当停滞行为4发生时，或者在给定次数的迭代中没有找到改进的解决方案时，信息素轨迹都会重新初始化。
3. 实验装置
在实验中，我们将ACO-EVRP应用于从VRPLIB5获得的三个典型VRP问题基准实例（即F-n45-k4.VRP、F-n72-k4.VRP和F-n135-k7.VRP）。考虑到第二节中所述的EVRP，电动汽车需要充电站进行充电。由于EVRP基准实例不可用，将充电站添加到三个常规VRP实例中，分别生成三个EVRP基准实例F-n45-k4.EVRP、F-n72-k4.EVRP和F-n135-k7.EVRP 6。充电站的分布方式可以覆盖问题实例的所有客户。由此产生的问题实例如图1所示，其规格如表1所示。此外，对传统VRP基准实例的容量和客户需求进行了修改，以符合史密斯-牛顿电动货车的规格[19]。考虑到这些电动汽车的车辆额定总重（GVWR）为7.5吨，其车辆整备重量为3.629吨，最大货物（或容量）估计为3.871吨（即等式（7）中的参数Q）。电动汽车驾驶员一天的最大服务时间设置为480分钟（8小时）（即等式（8）中的参数J）。我们的EVRP模型中用于模拟实验的其余参数值如表II所示。算法对50次独立执行（在同一组随机种子上）执行10e4次迭代，并记录平均总行程时间（以分钟为单位）以及总行程（以公里为单位）、可行性（以成功执行的百分比表示）、充电次数和使用的电动汽车数量。就每次执行的能量而言，完整EVRP解决方案的可行性必须满足ek ige; 0, forall;我isin; Ncup; Fforall;Kisin; M.还记录在执行过程中找到解决方案的平均迭代次数和CPU时间（以秒为单位）。实验是在Linux系统下进行的，该系统采用Intel Core i7-3930K 3.20GHz处理器，具有12MB缓存和16GB RAM。对于实验，使用了50个ANT，使用的常用参数设置为以下典型值：alpha;=1和beta;=5，而q0和rho;参数的影响将在下一小节中进一步研究。B.关于决策规则和蒸发率参数影响的结果众所周知，等式（17）和等式（19）中分别定义的q0和rho;参数对ACO metaheuris tic的勘探和开发有很大影响。由于它们是关键参数，我们系统地改变值如下：q0isin; {0.0,0.2,0.5,0.9}和rho;isin; {0.02, 0.2, 0.4, 0.6, 0.8}. 表III给出了所有参数组合的实验结果。此外，针对迭代的溶液质量（分钟）。从表III、图2和图3可以看出，ACO-EVRP溶液质量随着rho;值的增加而提高。对于F-n135-k7.evrp，当蒸发率设置为rho;=0.6，对于其他两种情况，当蒸发率设置为rho;=0.8时，可获得最佳平均结果。同样的观察结果适用于q0的所有值。然而，当决策规则参数设置为q0=0.0时，ACO-EVRP的性能更好。就效率而言，ACO-EVRP在几秒钟内输出其最佳解决方案（例如，F-n135-k7.EVRP为18.6秒，这是最大的问题实例）。对于其余的实验，对于所有问题实例，我们将决策规则参数设置为q0=0.0，对于F-n45-k4.evrp和F-n72-k4.evrp，蒸发率设置为rho;=0.8，对于F-n135-k7.evrp，蒸发率设置为rho;=0.6。值得一提的是，对于其他问题实例，不同的参数组合可能会执行得更好。
3.1信息素试验效果的结果
为了研究ACO-EVRP产生的信息素轨迹的影响，我们根据公式（16）设置了alpha;=0，因此在构建解决方案时不考虑信息素轨迹。ACO-EVRP与信息素追踪（表示为DACO EVRP ）和ACO-EVRP不含信息素追踪（表示为ACO-EVRP））的比较minus;) 表IV中给出了这些数据。此外，使用Mann–Whitney统计检验进行两两比较（粗体值表示与置信水平95%存在显著差
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[596244]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
