详情

原文传递空间-时间-状态网络下考虑同时取送货的电动车辆路径研究

论文题名：	空间-时间-状态网络下考虑同时取送货的电动车辆路径研究
关键词：	电动车辆;同时取送货;路径规划;空间-时间-状态网络;交替方向乘子法
摘要：	电动汽车是一种环保的新兴交通工具，具有噪音小，污染小，节约能源等优势。随着充电设施的完善与相关的国家补贴政策的出台，越来越多的物流公司开始使用电动货车进行配送服务。相比于传统燃油车，电动车的充电是相当耗时的，即使是使用快充技术，充满电也需要耗费数小时的时间，这就给驾驶员带来了里程焦虑。因此，为了保证能源使用效率，物流公司需要将客户服务模式和充电策略的影响纳入到电力物流资源的优化中。　　本文将同时取送货的客户服务模式和部分充电的充电策略与车辆路径优化相结合，提出了同时取送货的电动车辆路径问题(EVRPSPD)。该问题允许客户同时具有取货和送货两类需求。车辆必须在客户对应的时间窗内提供服务，并且可以绕行到附近的充电站充电以保证电量能够完成剩余路线。针对该问题，本文研究的目标是通过合理的路径规划，使得总运输成本最小。具体的研究工作如下：　　(1) 为了更加清晰全面地认识车辆路径问题(VRP)，本文从底层网络出发，通过比较物理空间网络，时空网络和时空状态网络各自的特点和使用场景，论证了使用高维网络研究VRP问题的优势。基于此，本文构建了适用于EVRPSPD的空间-时间-状态网络,该高维网络将离散的车辆剩余电量和连续的车辆剩余取送货能力作为状态维度。围绕该高维网络，本文会介绍车辆经过不同类型路段时的状态转换规则，以及高维网络的构建方法。引入的时空状态网络可以同时在时间和空间维度上有效优化电力物流网络运行时的资源配置。　　(2) 基于构建的时空状态网络，本文给出了 EVRPSPD 问题的多商品网络流模型。模型的目标函数是最小化广义运输成本。模型的约束包括车辆路径约束、每个客户的需求满足约束、充电站的容量限制约束以及二元变量约束。在高维网络中建模，与时间相关的约束(如客户的时间窗约束)和车辆状态相关的约束(如电量约束，容量约束)都已嵌入到底层网络，因此优化模型更加精简。本文还将针对给出的模型，分析其约束条件的复杂程度。　　(3) 针对优化模型，本文设计了基于交替方向乘子法的分解框架，将模型分解为一系列资源约束的最短路问题。该分解框架包含拉格朗日松弛技术(LR)和增强拉格朗乘子法(ALR)两部分，其中LR的解是为了得到原问题的下界，ALR的解是为了得到原问题的上界。此外，为了有效地求解最短路子问题，本文还对动态规划算法进行改进，以适用于本文的研究问题。该算法通过计算每次迭代后的最佳上界和最佳下界，来评估当前解的质量。　　(4) 本文设计了不同规模，不同场景的算例以验证模型和算法的有效性。在七结点的简单网络中测试了二次惩罚参数对算法性能的影响。除此之外，还测试了与充电策略相关的输入参数(充电率、最小剩余电量、最大电量、充电站个数和充电站容量)对车辆路径的影响，以分析参数的敏感性。在SiouxFalls网络中和芝加哥网络中分别测试了不同规模网络，不同服务模式下算法的可行性。最后，在现实的大规模苏州古城区网络中验证了算法的有效性。
作者：	王辰阳
专业：	交通运输工程
导师：	程琳
授予学位：	硕士
授予学位单位：	东南大学
学位年度：	2022