考虑载重的带时间窗电动车路径规划问题

作     者：陈晨 

作者单位：北京交通大学 

学位级别：硕士

导师姓名：张菊亮

授予年度：2020年

学科分类：08[工学] 082303[工学-交通运输规划与管理] 082302[工学-交通信息工程及控制] 0823[工学-交通运输工程] 

主      题：电动车路径规划 时间窗 载重 大规模自适应邻域搜索算法 

摘      要：由于近年全球变暖以及石油资源日益短缺,国家大力推广绿色物流理念,同时也因为电动车电池技术的发展,很多电商与快递企业（如顺丰、京东等）已经使用电动车进行城市配送。与此同时,由于快递行业竞争压力增大,很多公司推出“限时物流服务来提高其企业核心竞争力。对于电动车来说,车辆行驶过程中电量消耗除了与行驶距离相关外,还受车辆载重因素影响。基于上述背景,本文对考虑车辆载重的带时间窗电动车路径规划问题进行研究。具体的工作如下:（1）基于相关文献的研究内容,梳理车辆路径规划问题、带时间窗的车辆路径规划问题、考虑载重的车辆路径规划问题以及电动车路径规划问题的基础模型,分析各自约束条件差异性。另外,从精确算法、传统启发式算法、现代启发式算法这三个方面总结出求解各种车辆路径规划问题的求解算法,简要介绍各自的优缺点等,最终选择自适应大规模邻域搜索算法求解本文的模型。（2）深入研究前人对上述四种问题的研究结果,再结合本文的相应背景,重点分析与时间窗、车辆载重以及电动车等因素有关的约束条件,归纳、总结出符合本文要求的考虑载重的带时间窗电动车路径规划问题的模型假设和约束条件,建立相应混合整数规划模型。（3）以自适应大规模邻域搜索算法为主要框架,使用贪婪算法获得初始解、使用模拟退火算法的退火机制跳出局部最优,重点考虑时间窗因素和车辆载重因素,建立符合本文要求的算法,基于python实现该算法。其次,本文从Desaulniers等人论文中选取部分顾客点为25、50和100的案例,验证本文算法的有效性。最终证明,本文算法可以在较短时间内获得较优的结果。（4）结合J公司的相关数据,应用本文所设计出的模型和算法,计算出考虑了载重和时间窗的配送路径。然后研究了充电站数量、电池容量、配送车辆数量、载重等因素对电动车配送方案设计产生的影响。