【作者】 杨琳；

【导师】 彭超；

【作者基本信息】 华东师范大学 ， 软件工程， 2017， 硕士

【摘要】 在低碳经济的大背景下,新能源汽车成为未来汽车发展的方向。在新能源汽车的推广过程中,汽车的续航能力是不可忽视的重要环节。由于目前新能源充电站数量有限,在途更换电池将成为一种新的服务模式。根据实际需求,新能源汽车既可以自行前往服务站进行电池更换,也可以请求配送中心对其在行驶路径中直接配送。针对这两种情况,配送中心需要分别对服务站以及请求配送的车辆进行电池配送。由于车辆请求到达配送中心的不可预期性,配送中心的电池配送问题是一个动态车辆路径问题(Dynamic Vehicle Routing Problem,DVRP)。类似于驾驶传统汽车时驾驶员都会在油箱中还有一定油量的情况下寻找加油站加油,我们可以假设新能源汽车的驾驶员也会提前一段时间开始请求更换电池。因此,请求车辆对配送中心电池配送的实时性要求不高,可将一定时间段内收到的请求进行集中配送,将DVRP分解为若干连续的静态车辆路径问题(Static Vehicle Routing Problem,SVRP)。本文从基于服务站的电池配送与基于移动车辆的直接配送两个角度对电池配送问题进行分析:在基于服务站的电池配送问题中,利用服务站可以存放电池的特性,本文提出基于预测的配送算法,在每个配送阶段的初始时刻对下一阶段可能到达的请求车辆所需电池进行配送。在每个配送阶段将配送车辆配送距离最小作为目标,使用禁忌搜索算法来对该问题进行求解。实验显示,在不考虑请求车辆等待时间的情况下,基于预测的配送算法所得到的解在请求车辆等待时间方面是可接受的,可认为该预测算法有效。在基于移动车辆的直接配送问题中,配送中心直接对请求车辆在其行驶路径中的交叉路口处进行电池配送。由于请求车辆在发出请求之后仍处于行驶状态,因此配送车辆在不同时间对其进行配送时配送的地点也是不相同的。本文首先提出先来先服务(First Come First Service,FCFS)算法与最短路径优先(Shortest Path First,SPF)算法对该问题进行求解。其次,使用基于聚类的求解方法对配送初始时刻请求车辆的位置进行聚类,每一辆配送车辆负责一个聚类中请求车辆的配送,之后对每一辆配送车辆的配送问题使用FCFS以及SPF进行求解。但是,聚类算法仅根据请求车辆在配送初始时刻的位置进行聚类,而请求车辆一直处于高速行驶中,初始位于聚类i中的请求车辆可能在配送时更接近聚类j。考虑到这种情况,本文对基于聚类的求解方法做出改进,将其得到的解作为初始解,查找是否存在初始所在聚类与最终接近聚类不同的请求车辆。若存在,考虑将该请求重新分配至最终接近聚类对应的配送车辆,若重新分配后对目标值有所优化,则接受该重新分配。最后,对空闲配送车辆使用重定位等待策略。提出基于预测的等待算法,令已完成本阶段配送任务且有剩余电池的空闲配送车辆前往最近一段时间可能出现请求的交叉路口进行等待。实验显示,基于聚类的求解方法得到的最终解中,存在配送时更接近其他聚类的请求车辆,本文提出的改进算法对其得到的解有一定的优化作用。对于空闲车辆重定位等待问题,本文提出的基于预测的等待算法在绝大多数情况下是优于最后配送位置等待策略的。更多还原

【Abstract】 In the background of low-carbon economy,new energy vehicles have become the direction of the future.Charging problem is the indispensable part of the promotion process of the new energy vehicles.Battery-replacement is a development trend in the future due to the limited number of new energy charging stations.According to the actual demand,the vehicle can either go to the replacement station to replace battery or request distribution center to dispatch battery on the path of the vehicle directly.The distribution center need to dispatch batteries to replacement station and request vehicles respectively.Since the vehicle’s request is unexpected,the battery distribution problem can be seen as a dynamic vehicle routing problem(DVRP).Similar to the driver of the traditional vehicle will looking for gas station while there is a certain amount of oil in the trunk,we suppose that the driver of the new energy vehicle will be in advance for a period of time to request the battery.Therefore,the real-time requirement of battery distribution is not high,distribution center can dispatch the requests which are received in a certain period of time centralized,then the DVRP can be divided into several continuous static vehicle routing problems(SVRP).We analyze the battery distribution problem from two aspects in this paper:battery distribution based on replacement station and direct delivery problem based on the moving vehicle:In the case of battery distribution based on replacement station,we propose the distribution algorithm based on forecast since the replacement station can use to store batteries.In this paper,we propose a forecast-based routing algorithm that distributes the requested vehicle at the next stage.The tabu search algorithm is used to solve the problem in each distribution stage.In the direct delivery problem based on moving vehicle,the distribution center directly carries out the battery distribution at the intersection of the requested vehicle’s route.Since the requested vehicle is still running after the request is made,the distribution location at different times is also different.In this paper,the First Come First Serve algorithm and the shortest distance first algorithm are proposed to solve this problem.Then,the k-means is used to cluster the requested vehicle at the initial time,each distribution vehicle is responsible for a cluster’s requested vehicles,and use FCFS and SPF algorithm for each distribution vehicle.Experiments show that using clustering algorithm is better than those without clustering.However,the k-means algorithm only clustering according to the location of the requested vehicle at the initial time of delivery,while requested vehicle is at high speed,it may initially locate in cluster i and be closer to cluster j at the time of dispatching.We consider to reassign this requested vehicle to the distribution vehicle corresponding to cluster j if it can get better target value.Experiments show that there exist requested vehicles that is closer to the other clusters and the target value can be optimized after the redistribution.Finally,a relocation strategy is proposed to allow the idle vehicle which have the remaining battery to the nearest intersection for a request.更多还原