0论文0获得学位的目的0大学博士0特鲁瓦工科大学0专业：系统优化与安全0提交并支持0Gustavo Alfredo BULA02018年5月16日0危险物品运输车辆路径规划0评审委员会0M. M. SEVAUX 大学教授 主席0F. A. GONZALEZ 教授 导师0L. JOURDAN女士 大学教授 评审员0P. LACOMME女士 讲师 - HDR 评审员0C. PRODHON女士 讲师 - HDR 导师0K. SÖRENSEN教授 评审员0受邀人士0H. M. AFSAR 讲师0N. VELASCO女士 副教授0致谢0我特别要感谢特鲁瓦工科大学科技学院和哥伦比亚国立大学工程学院，感谢你们给予我的机会，我感激不尽。我要特别感谢我的导师卡罗琳∙普罗顿教授和法比奥∙冈萨雷斯教授，他们不仅鼓励和支持我的研究，还在我作为科学家的发展中做出了智力贡献。我还要感谢我的合作导师努比亚∙韦拉斯科教授和穆拉特∙阿夫萨尔教授，他们给予了我无条件的支持和指导。此外，我还要感谢本论文的评审委员会成员。你们提供了非常有用的建议，改进了这篇论文，我非常愿意接受。我还要感谢所有在这个不确定的任务中支持我的朋友们。通过分享一杯咖啡或茶，我们可以产生很多好的想法。0摘要0摘要（英语）0本论文的主要目标是研究危险物品（HazMat）运输问题，将其视为异构车队车辆路径规划问题。HazMat运输决策涉及不同且有时相互冲突的目标。本研究考虑了两个目标，即总体路径成本和总体路径风险。首先，我们制定了一个数学模型来最小化路径风险，该模型取决于车辆类型、运输物料以及车辆从一个客户到另一个客户时的负载变化。采用分段线性逼近来保持混合整数线性规划的形式。我们探索了基于邻域搜索的混合解决方法来解决路径风险最小化问题。这包括研究邻域结构以及开发一种变邻域下降（VND）算法进行局部搜索，以及一种扰动机制（摇动邻域）。我们还应用了后优化过程来提高解的质量。最后，我们采用了两种不同的解决方法，一种是基于支配的多目标算法，另一种是基于元启发式的 ϵ-约束方法，用于解决多目标版本的问题。我们使用了两个性能指标：超体积和 ∆-度量。前沿逼近结果表明，总体路径成本的轻微增加可能会导致预期后果的风险百分比大幅降低。关键词：数学模型，危险物质-运输，危险物质-风险评估，变邻域搜索，旅行推销员问题0简历（法语）0本论文的主要目标是研究危险物品（HazMat）运输问题，将其视为异构车队车辆路径规划问题。HazMat运输决策涉及不同且有时相互冲突的目标。本研究考虑了两个目标，即总体路径成本和总体路径风险。首先，我们制定了一个数学模型来最小化路径风险，该模型取决于车辆类型、运输物料以及车辆从一个客户到另一个客户时的负载变化。采用分段线性逼近来保持混合整数线性规划的形式。我们探索了基于邻域搜索的混合解决方法来解决路径风险最小化问题。这包括研究邻域结构以及开发一种变邻域下降（VND）算法进行局部搜索，以及一种扰动机制（摇动邻域）。我们还应用了后优化过程来提高解的质量。最后，我们采用了两种不同的解决方法，一种是基于支配的多目标算法，另一种是基于元启发式的 ϵ-约束方法，用于解决多目标版本的问题。我们使用了两个性能指标：超体积和 ∆-度量。前沿逼近结果表明，总体路径成本的轻微增加可能会导致预期后果的风险百分比大幅降低。关键词：数学模型，危险物质-运输，危险物质-风险评估，变邻域搜索，旅行推销员问题0摘要（西班牙语）0本论文的主要目标是研究危险品（HazMat）运输问题，将其建模为具有异构车队（HVRP）的车辆路径问题。在HazMat运输中，决策涉及考虑不同且有时相互矛盾的目标。本研究考虑了两个目标，即成本和总路径风险。首先，我们制定了一个数学模型来最小化路径风险，该风险取决于车辆类型、运输物料以及车辆在从一个客户到另一个客户时货物大小的变化。我们使用分段线性逼近目标函数，以保持一个整数线性规划模型。我们探索了基于邻域搜索的混合解决方法，以解决总路径风险最小化问题。这包括研究邻域结构和开发变邻域下降算法（VND）进行局部搜索，以及扰动机制（邻域结构用于扰动解决方案）。我们应用了一个后优化过程（SP）来提高解的质量。最后，我们采用了两种不同的解决方法来处理多目标版本的问题，即基于Pareto支配的算法和ϵ-约束启发式方法。我们使用两个多目标算法性能指标：超体积和∆指标。所得到的Pareto前沿近似表明，总路径成本的小幅增加可以显著减少预期后果的百分比，考虑到发生危险品运输事故的概率。关键词：数学模型，危险物质运输，物质风险评估，变邻域搜索，旅行商问题。1Introduction11.1Introduction (English) . . . . . . . . . . . . . . . . . . . . . . . .11.1.2Research Contributions . . . . . . . . . . . . . . . . . . .71.1.4Conclusion and Perspectives . . . . . . . . . . . . . . . .101.2.1Probl`eme de recherche et objectifs . . . . . . . . . . . . .141.2.3Contenu de cette dissertation . . . . . . . . . . . . . . . .201.3Introducci´on (Espa˜nol) . . . . . . . . . . . . . . . . . . . . . . .231.3.2Contribuciones de la investigaci´on . . . . . . . . . . . . .291.3.4Conclusiones y Perspectivas . . . . . . . . . . . . . . . .332.2Hazardous Material Routing. . . . . . . . . . . . . . . . . . . .382.4Multi-objective vehicle routing HazMat transportation works . . .432.4.1Overview of multi-objective vehicle routing problem (MO-VRP) . . . . . . . . . . . . . . . . . . . . . . . . . . . .442.4.2Multi-objective vehicle routing problem in HazMat trans-portation. . . . . . . . . . . . . . . . . . . . . . . . . .442.5Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .472.5.1Conclusions (English). . . . . . . . . . . . . . . . . . .472.5.2Conclusions (Franc¸ais) . . . . . . . . . . . . . . . . . . .48VII0目录01.1.1 研究问题和目标 . . . . . . . . . . . . 301.1.3 论文内容 . . . . . . . . . . . . . . . . . 901.2 引言（法语） . . . . . . . . . . . . . . . . . . . . . . . 1201.2.2 研究贡献 . . . . . . . . . . . . . . . . 1701.2.4 结论和展望 . . . . . . . . . . . . . . . . . 2101.3.1 研究问题和目标 . . . . . . . . . . . 2601.3.3 论文内容 . . . . . . . . . . . . . . . . . 3202 危险品（HazMat）运输中的路径问题 35 2.1 引言 . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 3602.3 异构车队车辆路径问题 . . . . . . . . . . . 402.5.3Conclusiones (Espa˜nol). . . . . . . . . . . . . . . . . .493Hazardous Materials (HazMat) Transportation Risk Modeling513.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .523.2Quantitative Risk Analysis in HazMat Transportation . . . . . . .533.2.1The probability of a HazMat transportation incident . . . .553.2.2The probability of incident outcomes. . . . . . . . . . .573.2.3The estimation of the consequences . . . . . . . . . . . .573.3Risk Route Evaluation Models . . . . . . . . . . . . . . . . . . .593.4Mixed Integer Linear Programming Model for Vehicle RoutingProblem for Hazardous Materials Transportation. . . . . . . . .603.4.1Problem Definition . . . . . . . . . . . . . . . . . . . . .613.4.2Linear Approximation . . . . . . . . . . . . . . . . . . .623.4.3Genetic Algorithm for Piecewise Linear ApproximationParameters. . . . . . . . . . . . . . . . . . . . . . . . .643.4.4Piecewise Linear Approximation Modeling . . . . . . . .643.5Numerical Tests . . . . . . . . . . . . . . . . . . . . . . . . . . .653.5.1Problem Instances. . . . . . . . . . . . . . . . . . . . .653.6Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .683.6.2Conclusions (Franc¸ais) . . . . . . . . . . . . . . . . . . .694Neighborhood Structures in Local Search Algorithms (LSA) for Het-erogeneous Vehicle Routing Problem (HVRP)734.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .754.2.1Combinatorial optimization problem . . . . . . . . . . . .764.2.3The search in the solution space . . . . . . . . . . . . . .794.3Local search methods . . . . . . . . . . . . . . . . . . . . . . . .804.3.2Iterated local search (ILS) . . . . . . . . . . . . . . . . .824.3.4Adaptive large neighborhood search (ALNS) . . . . . . .854.4.1Common neighborhood structures in VRP problems. . .87VIII03.5.2 结果 . . . . . . . . . . . . . . . . . . . . . . . . . . . 6703.6.1 结论（英语） . . . . . . . . . . . . . . . . . . . 6803.6.3 结论（西班牙语） . . . . . . . . . . . . . . . . . . . 7104.2 组合优化问题中的局部搜索 . . . . . . . 7604.2.2 邻域结构 . . . . . . . . . . . . . . . . . . 7704.2.4 算法性能 . . . . . . . . . . . . . . . . . . . 7904.3.1 贪婪随机自适应搜索过程GRASP . 8104.3.3 变邻域搜索(VNS) . . . . . . . . . . . . 8304.4 异构车队VRP问题中的邻域结构 . . 8704.4.2 解决HVRP的局部搜索算法 . . . . . . . 884.5.1Methodology . . . . . . . . . . . . . . . . . . . . . . . .914.5.2Performance Evaluations . . . . . . . . . . . . . . . . . .914.6Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .964.6.1Conclusions (English). . . . . . . . . . . . . . . . . . .964.6.2Conclusions (Franc¸ais) . . . . . . . . . . . . . . . . . . .974.6.3Conclusiones (Espa˜nol). . . . . . . . . . . . . . . . . .975Variable Neighborhood Search (VNS) to solve the Vehicle Routing Prob-lem (VRP) for Hazardous Materials (HazMat) Transportation995.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1015.2Problem definition. . . . . . . . . . . . . . . . . . . . . . . . .1045.3Solution method . . . . . . . . . . . . . . . . . . . . . . . . . . .1065.3.1Initial Solution s0 . . . . . . . . . . . . . . . . . . . . . .1075.3.2Basic moves. . . . . . . . . . . . . . . . . . . . . . . .1085.3.3Perturbation mechanism . . . . . . . . . . . . . . . . . .1115.3.4Local search heuristic. . . . . . . . . . . . . . . . . . .1125.3.5Intra-route improvement . . . . . . . . . . . . . . . . . .1135.3.6Post-optimization . . . . . . . . . . . . . . . . . . . . . .1135.3.7Algorithm structure . . . . . . . . . . . . . . . . . . . . .1155.4Experiments and results . . . . . . . . . . . . . . . . . . . . . . .1165.4.1Problem instances. . . . . . . . . . . . . . . . . . . . .1175.4.2Results for FSMVRP instances . . . . . . . . . . . . . . .1175.4.3Results for HVRP instances. . . . . . . . . . . . . . . .1185.4.4Impact of set partitioning . . . . . . . . . . . . . . . . . .1195.5Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1195.5.1Conclusions (English). . . . . . . . . . . . . . . . . . .1195.5.2Conclusions (Franc¸ais) . . . . . . . . . . . . . . . . . . .1205.5.3Conclusiones (Espa˜nol). . . . . . . . . . . . . . . . . .1216.1.1Multi-objective based neighborhood search (local search)algorithms. . . . . . . . . . . . . . . . . . . . . . . . .1266.1.3Performance metrics in multi-objective optimization . . .1306.3Dominance-based multi-objective neighborhood search algorithm136IX04.5 实验和结果 . . . . . . . . . . . . . . . . . . . . . . . . 9006 危险品运输的双目标车辆路径问题 (VRP) 123 6.1 引言 . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 12506.1.2 ϵ -约束方法 . . . . . . . . . . . . . . . . . . . . 12806.2 用于危险品运输的双目标异构车队车辆路径问题 . . . . . . . . . . . . . . . . . . . . . .. . . . 1326.3.1Initial Solution . . . . . . . . . . . . . . . . . . . . . . .1376.3.3Updating the neighborhood . . . . . . . . . . . . . . . . .1406.4ϵ-constraint multi-objective local search algorithm . . . . . . . . .1456.5Experiments and Results . . . . . . . . . . . . . . . . . . . . . .1486.5.2Results. . . . . . . . . . . . . . . . . . . . . . . . . . .1496.6Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1526.6.1Conclusions (English). . . . . . . . . . . . . . . . . . .1526.6.2Conclusions (Franc¸ais) . . . . . . . . . . . . . . . . . . .1546.6.3Conclusiones (Espa˜nol). . . . . . . . . . . . . . . . . .1587Conclusions, Recommendations and Perspectives1607.1Conclusions, Recommendations and Perspectives (English) . . . .1607.2Conclusions, recommandations et perspectives (Franc¸ais) . . . . .1657.3Conclusiones, Recomendaciones y Perspectivas (Espa˜nol). . . .169X06.3.2 邻域探索 . . . . . . . . . . . . . . . . . 13906.3.4 通用算法 . . . . . . . . . . . . . . . . . . . . 14106.4.1 局部搜索实现 . . . . . . . . . . . . . . . 14706.5.1 参数调整 . . . . . . . . . . . . . . . . . . . . . . 148List of Tables2.1Heterogeneous VRP Problems and Solution Methods . . . . . . .422.2Multi-objective VRP in HazMat Transportation . . . . . . . . . .463.1Total routing risk for optimal-cost solution using the first piecewiselinear approximation. . . . . . . . . . . . . . . . . . . . . . . .673.2Total routing risk for optimal-cost solution using the second piece-wise linear approximation . . . . . . . . . . . . . . . . . . . . . .683.3Optimal risk values for some instances of HVRP with unlimited fleet 694.1Average number of iteration for proposed neighborhoods for theFSVRP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .934.2Average size of neighbors for proposed neighborhoods for the FSVRP 934.3Average total improvement in percentage of the initial cost valuefunction for proposed neighborhoods for the FSVRP. . . . . . .944.4Average percentage gap to BKS for proposed neighborhoods forthe FSVRP. . . . . . . . . . . . . . . . . . . . . . . . . . . . .944.5Neighborhood structures experiment results for the FSVRP . . . .954.6Neighborhood structures experiment results for the FSVRP . . . .965.1Results for FSMVRP instances using multi-start VNS + SP algo-rithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1185.2Results for HVRP instances using multi-start VNS+SP algorithm.1185.3Performance evaluation of VNS-SP.. . . . . . . . . . . . . . . .1196.1Results for the parameters tuning of the multi-objective neighbor-hood dominance-based algorithm . . . . . . . . . . . . . . . . . .1486.2Results for bi-objective optimization for 20 nodes instances of FS-MVRP HazMat transportation problem . . . . . . . . . . . . . . .1506.3Results for bi-objective optimization for 50 nodes instances of FS-MVRP HazMat transportation problem . . . . . . . . . . . . . . .151XI6.4Results for bi-objective optimization for 75 and 100 node instancesof FSMVRP HazMat transportation problem . . . . . . . . . . . .151XIIList of Figures1.1Research Problem . . . . . . . . . . . . . . . . . . . . . . . . . .41.2Probl`eme de recherche (Research problem). . . . . . . . . . . .141.3Problema de investigaci´on. . . . . . . . . . . . . . . . . . . . .263.1Variables in HazMat transportation assessment. . . . . . . . . .533.2Risk Assessment Framework . . . . . . . . . . . . . . . . . . . .553.3Possible shapes of impact area around the route segment. . . . . .583.4Risk assessment in HazMat Transportation . . . . . . . . . . . . .603.5Piecewise linear approximation functions. . . . . . . . . . . . .633.6Genetic Algorithm Solution Encoding . . . . . . . . . . . . . . .6404.1Shift（下方）和swap（右方）的示例。删除/插入的弧线用虚线/粗线表示8804.2 2-opt选项1（下方）和选项2（右方）的示例。删除/插入的弧线用虚线/粗线表示8904.3 20个节点和使用5种不同车辆类型的无限车队的异构车辆路径问题。9205.1 分段线性逼近函数10605.2 初始解的构建10805.3 路线风险评估10905.4 风险路径计算示例11106.1 强化子空间和多样化子空间12706.2 给定三个不同冲突目标的超立方体13106.3 二目标空间中的∆度量13206.4 y k ij的分段线性逼近=（| σ r | �0e = d q σ r e ) α13406.5最近邻策略。最接近的解（由箭头指示）到两个极端解之间等间距点所形成的线上的每个点。1430XIII06.6Pareto前沿逼近。基于支配的多目标局部搜索算法◦和ϵ约束多目标局部搜索算法△20个节点实例15106.7Pareto前沿逼近。基于支配的多目标局部搜索算法◦和ϵ约束多目标局部搜索算法△50个节点实例15206.8Pareto前沿逼近。基于支配的多目标局部搜索算法◦和ϵ约束多目标局部搜索算法△75和100个节点实例1530XIV0算法列表01个贪婪随机自适应搜索过程GRASP8102个贪婪随机解8103个迭代局部搜索过程8204个通用VNS的步骤8405个大邻域搜索8606个局部搜索。VND算法（x'，确定性搜索，SR SP）11407个多起点VNS算法加SP的步骤11608个随机分割哈密顿回路的初始解13809个路径重连的初始解139010个前沿更新140011个局部搜索：更新邻域142012个基于支配的多目标局部搜索算法144013个双目标ϵ约束算法用于成本和风险最小化146014个邻域的探索：成本约束1470XV10第1章0引言01.1 引言（英文）0如今，不仅高效的交通运输重要，环境和安全问题也成为推动更高效和负责任的交通运输的重要因素。危险品运输和绿色物流是前者的例子。危险品运输是我们工业生活方式的重要组成部分。这些运输在大多数情况下起始和终止于世界各地的许多不同地点，这凸显了交通运输在危险品运输中的重要作用。危险品运输问题与其他物品的运输问题的区别在于在上传、运输和下载过程中这些物品意外泄漏所带来的风险。危险品在商业运输中可能对人、环境和财产构成不合理的风险。这些产品的大多数运输使用道路网络（国家道路和街道网络路线），它们对国家经济至关重要，并为托运人和货主提供收入。使用道路系统进行运输由于运输数量和规模的不断增加而成为一个日益紧迫的问题。道路危险品事故占事故总数的绝大多数，这表明道路上危险品运输的安全性的重要性。尽管在运输危险品时发生事故的车辆数量只占很小的比例，但危险品运输事故的平均后果更为严重，这说明了道路运输风险的低频高后果性质。评估危险品运输中的风险事件是一项困难的任务；这些事件的发生频率非常低，道路上的事故是不确定的，但这些事故对人员、建筑物和其他交通方式的爆炸或泄漏造成了巨大影响。20危险品运输。关于如何对风险进行建模，目前尚无共识，但普遍认为任何公式都将包括两个元素：意外危险品泄漏的概率及其相关后果。危险品运输旨在减少其中的风险，以提高人类、基础设施和自然环境的安全性。危险品运输问题的目标是通过最经济和最安全的路线将一定数量的被视为危险品的物质从起点运送到目的地。危险品运输涉及多个利益相关方，如发货人、承运人、制造商、居民、保险公司、政府和应急响应人员。他们通常对成本和风险有不同的优先级。危险品运输路由问题主要关注两个方面：最短路径问题（与满载货车配送相关）和车辆路径问题（与不满载货车配送相关）。与第一类问题相关的研究工作比第二类问题更多。根据这个方面，在这项工作中，重点放在危险品运输车辆路径问题上。危险品路由问题属于丰富的车辆路径问题，实际上不符合同质车队的假设。在异构车队问题中，战术决策涉及到要采购的车队组成，从而导致问题的无限版本。操作决策也可以与已经获得的车队（通常是长时间）和具有不同特征（包括运载能力）的车辆相关联，从而导致有限车队问题。异构车队车辆路径问题（HVRP）是一种具有挑战性的组合优化问题（COP），但需要记住的是，当涉及到危险品路由问题时，它们也是多目标的。近年来，在科学、工程、经济学和其他领域解决现实生活中的优化问题时，存在两个或更多相互冲突的目标函数之间的权衡，导致多目标优化。在许多多目标优化问题中，不存在同时优化每个冲突目标的单一解决方案。它们是权衡解决方案。为了使解决方案有趣，必须存在一种支配关系，如Pareto支配，该关系将被考虑的解决方案与其他解决方案联系起来。这意味着存在一组非支配或Pareto最优解。由于许多原因，获得这个集合是困难的，其中包括可能存在大量或无限的解决方案，这就是为什么提出了各种近似这个集合的方法，无论是部分还是全部。在VRP中，最小化总路由成本同时最大化路线平衡，或者最小化总路由成本同时最小化燃料消耗和污染物排放。30多目标路由优化问题的示例。首先，本文展示了总路由风险和总路由成本确实是相互冲突的目标。然后，它旨在近似两个目标函数之间的权衡函数的行为，当它们在使用异构车队的危险品车辆路由问题的背景下同时优化时。多个目标的存在通常不允许决策者确定一个普遍最佳决策，这意味着他们需要在所有可能的选择中进行选择以达到最佳决策。由于很难找到所有可能的决策选择甚至是它们的子集，因此需要确定潜在选择（Pareto最优集的近似）并从中选择最佳选择。鉴于近年来对多目标车辆路径问题中Pareto最优解集的近似的兴趣日益增长，本研究调查了开发一种用于近似HVRP在危险品运输中的解集的方法。在这项工作中，将优化技术与风险分析模型相结合，以近似Pareto最优集和/或Pareto最优前沿。同时，还开发了一个数学框架来正式考虑和评估所提出方法的潜力。出发点是提出一种用于路由风险评估的数学模型，该模型包括其值取决于路由决策的变量。该模型允许更实际地计算预期路由风险，该风险考虑了不同的车辆和路段特征，如车辆类型、负载大小、材料类型和道路段的邻近人口。这些方面对于更高效和负责任的危险品运输是一种贡献，并且旨在支持使用道路和街道网络进行这些材料的运输时的路由决策。为了进一步指导，第1章的一般组织概述如下。研究问题和研究目标的陈述包含在第1.1节中，而每个具体目标的研究贡献可以在第1.2节中找到。第2章到第5章的内容在第1.3节中进行了总结，结论性评论以及本工作的思路和研究方向在第1.4节中提出。01.1.1 研究问题和目标0研究问题0卡车或车辆路径被认为是危险品运输中的一项重要的主动风险缓解措施。这项措施旨在减少事故发生的概率及其后果。危险品的存储和运输受到当地政府、国际组织和40专题专家。此外，通过改善驾驶员培训和车辆维护，可以将危险品运输中的风险最小化，尽管运营研究在风险最小化中也很有用。本研究侧重于将运营研究模型和方法应用于危险品运输中的路径问题，以获得识别出具有最低成本和风险的路线的有效方法。在图1.1中，介绍了研究问题，即使用异构车队通过道路网络进行车辆路径问题的多目标优化，并考虑与风险评估相关的不同路径选择关键变量。0图1.1：研究问题0在危险品运输路线上最小化风险对其定义非常敏感。给定一种用于路段风险估计的定量方法，下一步是评估路径或路线上的风险的函数。对于危险品运输，
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
