涉及固定费用的可持续不确定性多目标 5D 最短路径问题的求解方法：在鱼类运输系统中的应用

《Journal of Computational and Applied Mathematics》：A solution approach for sustainable uncertain multi-objective 5D shortest path problem involving fixed-charge: Application to fish transport system

　　

摘要
可持续性涵盖了环境、经济和社会系统在多个层面的相互作用。车辆在运输系统中依赖各种燃料来满足其能源需求。然而，这些燃料排放温室气体，导致环境污染。鉴于此背景，本研究调查了一种可持续的固定费用多目标多路径多运输方式多司机最短路径问题。主要目标是确定在源点和终点之间旅行时，能使成本、时间、风险、碳排放和距离最小化的最高效路径。在实际场景中，固定费用多目标多路径多运输方式多司机最短路径问题的参数通常涉及不确定性，这种不确定性可以根据人类判断进行预期。刘的不确定性理论被广泛接受为处理此类不确定性的合法工具。因此，将锯齿状不确定变量纳入提议模型中，以表示不确定参数。本研究开发了固定费用不确定多目标多路径多运输方式多司机最短路径问题的期望值模型和乐观值模型，并提供了相应的确定性转化。此外，使用两种多目标遗传算法，即基于目标水平的非支配排序遗传算法 -II 和 III 来解决确定性模型。通过鱼运输系统问题展示了所提模型的应用。对从上述技术获得的折衷解进行了比较，并与混合遗传算法、非支配排序遗传算法-II 和 III 一起，以及对目标函数关于形状参数和目标水平的敏感性分析。最后，计算覆盖性能指标以展示所提方法的有效性。

引言
元启发式算法因其有效解决复杂优化问题的能力而备受关注。随着时间的推移，设计了各种元启发式算法来解决特定的挑战。其中，基于种群的元启发式算法，如进化算法，尤为显著。它们通过模拟自然进化，在单次仿真运行中保留多个结果。这些算法的一个著名例子是遗传算法 (GA)，它有效地解决了各种复杂的优化挑战。遗传算法受约翰·霍兰德在 20 世纪 60 年代早期工作的启发，基于达尔文的“适者生存”原则。该方法从初始种群生成随机解，然后应用遗传算子进化和识别最优解。

当处理多个目标时，通常有几个折衷解，称为非支配解。Schaffer [1] 通过将种群划分为子种群，根据特定目标为每个子种群分配适应度值，从而增强了 GA 以解决多目标优化问题。该算法在帕累托最优前沿的特定区域收敛，突出了根据手头问题对 GA 进行定制修改的必要性。随后，开发了各种用于多目标问题的 GA，例如 Fonseca 和 Fleming [2] 的多目标遗传算法 (MOGAs) 以及 Hajela 等人 [3] 的基于权重的遗传算法。Goldberg 在 1989 年将支配概念整合进多目标进化算法，标志着开创性的进步。此后，Srinivas 和 Deb [4] 是率先将非支配排序明确纳入其非支配排序遗传算法 (NSGA) 算法的先驱。然而，该算法有几个局限性，例如缺乏精英主义、依赖用户定义的参数以及高计算复杂度。为解决这些问题，Deb 等人 [5] 引入了 NSGA-II，这是一个增强版本，具有优越的多样性保持算子，并消除了对用户定义参数的需求。文献中突出了 NSGA-II 的众多有趣应用，包括车辆路径问题 [6]、不确定最短路径问题 [7] 等。随后，Deb 和 Jain [8] 开发了 NSGA-III，它依赖于参考点方法。在此方法中，决策者 (DM) 寻求接近预定义参考点的解，解决了 NSGA-II 中拥挤比较算子的高计算复杂度。许多研究人员在其工作中使用了 NSGA-III。例如，Bhesdadiya 等人 [9] 将其应用于经济和环境的调度问题，Ji 等人 [10] 将其用于 MMC 控制器参数，Agnihotri 和 Dhodiya [11] 将其用于多目标固体运输问题。由于所有这些 MOGA 研究，人们意识到目标并未根据 DM 的需求进行优先级排序。为解决这个问题，Todkar 和 Dhodiya [12], [13], [14] 开发了两种基于目标水平 (AL) 的方法，即基于 AL 的 NSGA-II & III。

MOGAs 及其各种适应性调整对于解决涉及多个目标的广泛复杂优化挑战非常有效。此类问题的一个特定例子是最短路径问题 (SPP)。供应链管理，涉及从源点到终点的旅行，通常包含 SPP。传统的 SPP 是图论中的一个基本网络优化问题，具有三个主要约束：源点、终点和中间顶点。SPP 的目标是识别源点和终点之间的最短路线，最小化总边权重。这个问题在交通和物流、电信、网络路由、供应链管理、机器人和自动驾驶汽车等各个领域中至关重要。Dijkstra [15], Bellman [16], Floyd [17] 和 Dreyfus [18] 等先驱研究人员在 20 世纪 50 年代和 60 年代为开发解决 SPP 的算法做出了重大贡献。

在实际场景中，从一个地方到另一个地方旅行通常涉及多种类型的车辆，称为多运输方式。因此，传统的 2D SPP 被扩展为 3D SPP，称为多运输方式 SPP。在当代环境中，源点和终点通过各种路径连接，有些状况良好且平滑，而另一些可能粗糙、拥堵或经过修补。在这种情况下，即使表面粗糙的较短路径也可能比平滑路径花费更长的时间穿越。此外，旅行成本因路径状况而异——路径越粗糙，成本越高。因此，所选路径的长度和状况对于最小化总体旅行成本和时间至关重要。因此，考虑地点之间所有无数直接路线是至关重要的。因此，在 SPP 中同时考虑路径和运输方式的选择更为实际。因此，当多运输方式 SPP 结合多条路径和运输方式时，它演变为 4D SPP，称为多路径多运输方式 SPP。车辆的速度在最小化旅行时间方面起着关键作用，这主要受司机行为和风格的影响。因此，司机在减少总体旅行时间方面做出了重大贡献。司机行为受路线维护不善和交通拥堵等因素的影响，进而影响驾驶风格。此外，旅行成本因驾驶行为而异；例如，熟练的司机产生的成本比效率较低的驾驶风格更低。此外，长途旅行由于单个司机处理漫长路线的不便，需要多名司机。迄今为止，SPP 尚未探索涉及多路径、运输方式和司机的场景。因此，4D SPP 演变为 5D SPP (5DSPP)，具体为多路径多运输方式多司机 SPP (MRMCMDSPP)。

在现实应用中，仅关注最小化像距离或时间这样的单一目标通常是不够的。许多人还旨在节省燃料、在更安全的路径上旅行 (风险)，并实现这些目标的组合。因此，现实场景需要从单一目标 SPP 转向多目标 SPP (MOSPP)。因此，5DSPP 转化为 MO5DSPP。在多目标领域，Hansen 是第一个研究 MOSPP 的。随后，许多研究人员 ([19], [20], [21] 等) 对 MOSPP 的研究做出了贡献，这对网络理论至关重要。已经开发了多种方法来求解具有确定性边权重的 SPP。然而，现实场景通常涉及诸如通信网络故障、道路维护、燃料价格波动、通行费支出和交通拥堵等不确定因素，导致非确定性边权重。传统方法对于具有此类不确定性的网络是不够的。研究人员建议随机现象可以有效地表示这些不确定性，应用概率论来表征 SPP 中的不确定边权重。Frank 和 Hakimi [22] 通过探索具有随机能力的通信网络奠定了基础，随后 Frank [23], Mirchandani [24], Hall [25], Nie 和 Wu [26] 进行了值得注意的研究。然而，概率理论依赖于从足够的观测数据得出的准确概率分布函数。当数据不足时，使用随机变量来解释不确定现象违反了概率理论的假设。专家通常需要表示对事件发生可能性的信念程度，但人类信念可能与实际频率显著偏差，导致悖论结果 (Kahneman 和 Tversky [27], Liu [28])。为此，Liu [29] 引入了不确定性理论以合理地处理人类信念，并通过后续作品 ([30], [31], [32]) 进一步完善了它。

Liu [31] 引入了不确定规划作为不确定性理论在处理具有不确定变量的数学规划中的应用。在此基础上，Gao [33] 提供了不确定网络中最短路径长度的不确定性分布函数。Zhou 等人 [34] 为具有不确定边权重的网络开发了逆最短路径方法。Shi 等人 [35] 提出了不确定随机网络中最短路径的相对熵模型，而 Sheng 和 Gao [36] 应用机会论解决了此类网络中的 SPP。Majumder 等人 [7] 使用经典全局准则方法和两种 MOGA 建模并求解了不确定 MOSPP。Todkar 和 Dhodiya [14] 使用基于 AL 的 NSGA-II & III 解决了不确定多目标多路径 SPP。由于这些关于不确定 SPP 的研究，显然不确定性框架对于管理 MO5DSPP 中的不确定边权重至关重要。因此，我们在 MO5DSPP 中引入了这个框架，将其称为不确定 MO5DSPP (UMO5DSPP)。

在现代运输中，通常对从源点到终点的各种旅行路线收取额外费用，称为固定费用。这些固定费用可以包括许可证费、道路通行费和节日活动订阅费用。将这种固定费用纳入 UMO5DSPP 框架，得出固定费用 UMO5DSPP (FCUMO5DSPP)。此外，温室气体 (GHG) 排放已成为一个主要的环境问题。由于车辆中的内燃机，运输部门显著贡献了 CO2 和其他 GHG 排放。轻型车辆，如乘用车和小型巴士，负责其中 50% 的排放，而重型车辆，包括卡车和货船，贡献了另外 50%。因此，GHG 排放严重威胁环境和空气质量。影响碳排放的因素包括发动机类型、燃料类型、交通法规、道路状况、驾驶经验和驾驶限制。因此，在 SPP 系统中选择合适的路线、车辆和司机对于最小化碳排放至关重要。因此，我们开发了一个可持续固定费用不确定多目标多路径多运输方式多司机最短路径问题的模型，也称为 FCUMO5DSPP。该模型旨在最小化成本、时间、风险、碳排放和距离。

此外，本文的关键贡献如下：
1. 对具有固定费用的多目标多路径多运输方式多司机 SPP 进行建模，以最小化总成本、时间、风险、碳排放和距离。
2. 为了获得更真实的结果，在固定费用 MO5DSPP 中引入了不确定性。
3. 为 FCUMO5DSPP 制定了期望值模型 (EVM) 和乐观值模型 (OVM)。
4. 使用五种 MOGA 解决 FCUMO5DSPP，即 HGA、NSGA-II、NSGA-III、基于 AL 的 NSGA-II 和基于 AL 的 NSGA-III。
4. 作为应用，在 FCUMO5DSPP 的背景下考虑了鱼运输系统问题。

本文的其余部分组织如下：第 2 节介绍了与我们研究相关的一些基本概念。第 3 节讨论了 FCUMO5DSPP，包括其相关的 EVM 和 OVM。在第 4 节中，我们制定了 FCUMO5DSPP 的 EVM 和 OVM 的确定性转化。用于求解这些确定性等价模型的方法在第 5 节中详细说明。第 6 节探讨了 FCUMO5DSPP 在解决鱼运输系统问题中的应用，提供了结果和讨论。第 7 至 10 节解决了各个方面，包括敏感性分析、比较、性能指标和结论。

章节摘录
预备知识
本节简要介绍了本研究中使用的不确定性理论的基本概念。详细讨论可参见 Liu ([29], [30], [32])。
令 (Γ,ψ,M) 表示一个不确定空间，其中 Γ 是一个非空集，ψ 是 Γ 上的一个 σ-代数，M 是一个不确定测度。
不确定变量 ζ 定义为从不确定空间到实数集 R 的可测函数。

ζ的不确定性分布由φ(a)=M{ζ≤a}, a∈R给出。在本研究中，不确定参数是符号说明：构建多目标 5 维实体最短路径模型使用以下符号说明：
(i)G=(V,E) 为一个网络
(ii)V= 网络 G 的顶点集
(iii)E= 网络 G 的边集
(iv)n= 顶点数量
(v)m= 边数量
(vi)U= 直接路线数量
(vii)V= 运载工具数量（不同的运输方式）
(viii)W= 驾驶员数量
(ix)ζZp= 具有锯齿形不确定参数的第 p 个目标函数
(x)xabuvw= 从第 a 个顶点到第 b 个顶点，通过第 u 条路线，使用第 v 种运载工具和第 w 个驾驶员的流量
(xi)ζcabuvw= 确定性模型转换
由于不确定模型无法直接求解，有必要使用第 2 节概述的不确定性理论将其转换为确定性模型。本节解释了 EVM 和 OVM 的确定性转换。
定理 4 如果 ζcabuvw, ζtabuvw, ζrabuvw, 和 ζeabuvw 是具有相应正态不确定性分布 φζcabuvw, φζtabuvw, φζrabuvw, 和 φζeabuvw 的独立不确定变量，那么模型 2 中显示的 EVM 的确定性转换等价于，minE[Z
解决方案方法论：MOGA 根据目标函数为每个解决方案分配一个适应度向量。由目标函数确定的解决方案的适应度，允许与另一个解决方案的相同目标函数进行比较。染色体的适应度向量表示其与其他染色体相比的相对适应度。目标函数将染色体从基因型（决策变量空间）映射到表型（目标空间）。在选择过程中，适应度值较高的解决方案被
在鱼类运输系统中的应用：鱼类运输系统 (FTS) 通过确保鱼类在不同地点之间的安全高效运输，在水产养殖、渔业和水族箱行业中发挥重要作用。在实际的鱼类运输中，必须同时考虑运输成本、旅行时间、运输风险、碳排放和旅行距离等多个冲突因素。因此，FTS 问题自然地导出了一个在不确定
敏感性分析：敏感性分析是检查模型参数变化如何影响获得的目标值和妥协解决方案的重要工具。在本研究中，进行了敏感性分析以研究形状参数和渴望水平的不同组合对提出的基于 AL 的 NSGA-II 和基于 AL 的 NSGA-III 方法性能的影响。由于 ALs 反映了决策者（DM）的偏好，而形状参数影响行为
比较：本研究获得的结果无法与现有文献直接比较，因为提出的 FCUMO5DSPP 模型是首次被公式化并调查的。提出的问题同时结合了固定费用、不确定参数、多条路线、多种运载工具、多个驾驶员和五个冲突目标，与文献中现有的模型相比，这显著增加了最短路径问题的复杂度。
性能度量：多目标优化算法的有效性可以使用合适的性能指标进行评估。在本研究中，采用覆盖率指标来分析并提出和现有的多目标优化技术的性能。
结论与未来展望：本研究专注于带固定费用的不确定多目标 5D 最短路径问题的公式化和分析，称为 FCUMO5DSPP。该模型旨在确定网络 G 中源顶点和目的地顶点之间的最短路径，同时最小化总不确定成本、时间、风险、碳排放和精确距离。为了证明其实际适用性，FCUMO5DSPP 被应用于鱼类运输系统问题，该问题包含七个城市和十一个
资助：本研究未收到任何资金。作者贡献：Jayesh Dhodiya 博士引入了 UMO5DSPP 模型。Aniket Todkar 开发了基于 AL 的方法算法以解决 UMO5DSPP 并撰写了论文。
数据可用性：支持本研究结果的数据可向通讯作者索取。Aniket Todkar|Jayesh Dhodiya 数学系，SV 国立理工学院，Ichchhanath, Surat, 395007, Gujarat, India