原文传递
绿色带时间窗的车辆路径优化算法研究
| 论文题名： | 绿色带时间窗的车辆路径优化算法研究 |
| 关键词： | 车辆路径规划;低碳减排;自适应大邻域搜索;变邻域搜索;自适应大邻域搜索算法 |
| 摘要： | 物流行业如今已成为我国的支柱产业，作为物流场景必须面对的问题，路径规划一直被物流行业从业者所重视。经典的车辆路径问题将求解问题的重点放在了如何减少使用的车辆数、如何减少行驶的总路程长等与经济成本直接挂钩的问题上。但高效的物流运输，是以对环境的极大破坏作为代价的。绿色的车辆路径问题是一类在优化目标上区别于经典的车辆路径问题的新问题，它针对物流运输过程造成的污染问题进行研究,优化的目标是降低对环境造成的负面影响，其中包括减少碳排放量以及使用新能源替代传统能源从而减少传统能源的消耗两个方面。本文对优化这两方面的绿色带时间窗的车辆路径问题分别进行了研究。 燃料汽车是绿色带时间窗的取送货车辆路径问题中使用的运输主体之一。在该问题场景里，车辆需在各顾客点间往来，以满足在订单规定时间内完成配送任务的要求。每个订单对应的顾客点仅能访问一次。由于燃料汽车的能源来自化石燃料，在行驶过程中必然会产生大量的温室气体，从而破坏大气环境。为了减少车辆运输时造成的碳排放，本文提出了基于距离的自适应大邻域搜索算法，通过对比实验验证了该算法在减碳上的有效性，同时在经济效益上也优于对比算法。本文还研究了该模型和所提出算法的适用场景。在相同数据集和相同算法上，用不同问题模型求得的实验结果表明，当顾客点处于聚集分布状态时，算法的减碳优势更明显。 另一种降低碳排放的方式是使用以电能为代表的新能源作为汽车的主要能源。开放式路径问题常见于物流外包、快递寄送等场景。在该场景下，车辆不需要在完成配送任务后返回起始出发地，但需要在最大路径时间内完成所有的配送任务。以电能作为主要能源的货车将在公路物流中承担着越来越多的工作，但目前尚无以电动汽车作为运输主体的开放式路径问题的研究。针对这一研究空白和市场应用的需求，本文建立了相应的数学模型，并提出了改进的变邻域搜索和模拟退火两阶段组合算法用于求解该问题。该问题的优化目标为最短的路径总时长。在对比实验中，提出的算法可在多数算例中取得最短的行驶总路程长，体现了算法的优化能力。而针对不同类型的充电点，实验根据充电点类型的分布方式生成两组数据集并分别进行了实验。实验结果表明，类型随机分布的充电点对复杂场景路径的规划有正面作用。同时，在加入驾驶员主观情绪的测试实验中发现，算法在处理复杂场景的路径优化时效果更好。 |
| 作者： | 卢金莹 |
| 专业： | 计算机科学与技术 |
| 导师： | 黄荷姣 |
| 授予学位： | 硕士 |
| 授予学位单位： | 哈尔滨工业大学 |
| 学位年度： | 2020 |
检索历史
应用推荐
