论文部分内容阅读
近几年，伴随着共享经济而来的电动汽车分时租赁业务，因其租车的便利性与能源的清洁性，正在逐渐壮大之中。城市共享电动汽车租赁公司，在积极运营租赁业务的同时，需要面临共享电动汽车的清洁问题，以便提供更好的服务获得更高的满意度。本文研究了城市共享电动汽车清洁排程优化问题，即电动汽车需要在有限的时间窗内进行清洁服务，其中每辆电动汽车都有多个可被清洁的时间窗并对应地点信息。论文的主要工作与创新点：
（1）通过详细了解城市共享电动汽车的清洁流程，抽象出了清洁车排程的车辆路径问题（Vehicle Routing Problem，简称VRP），相比于传统的多时间窗车辆路径问题（ Vehicle Routing Problem with Multiple Time Windows，简称VRPMTW），提出多个时间窗对应多个位置的概念，即多时间窗多位置的车辆路径问题。首先，在离线模式下，基于单辆清洁车情况，以最小化清洁车的行驶成本以及电动汽车的清洁成本为目标，构建了旅行商的多时间窗多位置问题（Traveling Salesman Problem with Multiple Time Windows Corresponding to Multiple Locations，简称TSPMTWML）模型，通过CPLEX验算证明模型正确性；针对大规模问题的情况，使用遗传算法与差分进化算法求解，能够在有限的时间内求得满意解。
（2）在离线模式下，基于多辆清洁车情况，以最小化清洁车总工作时间以及清洁车总数量为目标，构建了多时间窗多位置的车辆路径问题（ Vehicle Routing Problem with Multiple Time Windows Corresponding to Multiple Locations，简称VRPMTWML）模型，使用双目标遗传算法求解，同时设计滚动时域法，对比两种算法结果，得出当停车场数量少，电动汽车时间窗多的情况下，滚动时域法效果优于双目标遗传算法。
（3）针对在线模式下多辆清洁车排程，对清洁车服务排程问题进行刻画。首先，讨论了在线与离线服务器（指代清洁车）相同情况，分析得出在线服务器行驶总路程为离线服务器的正无穷倍。然后，讨论了基于离线2个服务器的在线服务器数量界定，当请求任务数为k时，分析得出最多为?(k+2)/2?个服务器。最后，讨论了直线情况下，在线调度策略的服务器数量，设计了画圆策略，得出当路径直线长度为L=a+b时，服务器数量最多为[log2(a+2)/2]+[log2(b+2)/2]个。
（1）通过详细了解城市共享电动汽车的清洁流程，抽象出了清洁车排程的车辆路径问题（Vehicle Routing Problem，简称VRP），相比于传统的多时间窗车辆路径问题（ Vehicle Routing Problem with Multiple Time Windows，简称VRPMTW），提出多个时间窗对应多个位置的概念，即多时间窗多位置的车辆路径问题。首先，在离线模式下，基于单辆清洁车情况，以最小化清洁车的行驶成本以及电动汽车的清洁成本为目标，构建了旅行商的多时间窗多位置问题（Traveling Salesman Problem with Multiple Time Windows Corresponding to Multiple Locations，简称TSPMTWML）模型，通过CPLEX验算证明模型正确性；针对大规模问题的情况，使用遗传算法与差分进化算法求解，能够在有限的时间内求得满意解。
（2）在离线模式下，基于多辆清洁车情况，以最小化清洁车总工作时间以及清洁车总数量为目标，构建了多时间窗多位置的车辆路径问题（ Vehicle Routing Problem with Multiple Time Windows Corresponding to Multiple Locations，简称VRPMTWML）模型，使用双目标遗传算法求解，同时设计滚动时域法，对比两种算法结果，得出当停车场数量少，电动汽车时间窗多的情况下，滚动时域法效果优于双目标遗传算法。
（3）针对在线模式下多辆清洁车排程，对清洁车服务排程问题进行刻画。首先，讨论了在线与离线服务器（指代清洁车）相同情况，分析得出在线服务器行驶总路程为离线服务器的正无穷倍。然后，讨论了基于离线2个服务器的在线服务器数量界定，当请求任务数为k时，分析得出最多为?(k+2)/2?个服务器。最后，讨论了直线情况下，在线调度策略的服务器数量，设计了画圆策略，得出当路径直线长度为L=a+b时，服务器数量最多为[log2(a+2)/2]+[log2(b+2)/2]个。