Abstract: In recent years, with the increasing emphasis on environmental protection and the continuous improvement of relevant policies, the adoption of electric vehicles (EV) in last-mile delivery has received extensive attention. However, using EV faces challenges such as uncertain travel time due to traffic congestion and random waiting time at charging stations. These factors not only affect the efficiency of last-mile delivery but also increase the uncertainty of vehicle energy consumption and charging needs. Thus, this study investigates a stochastic electric vehicle routing problem in which the traffic congestion condition is uncertain and there is a stochastic queueing process at each charging station.
The stochastic electric vehicle routing problem is formulated as a Markov decision process. The state of the system at each decision epoch includes information on EV and unvisited customers, real-time traffic conditions, and the queueing status of charging stations. The information on EV includes the vehicle’s current location and remaining energy level. The decision epoch is triggered by the arrival of EV at a customer location. The action taken at a decision epoch indicates the next location that EV should visit. The candidate locations for EV to visit could be a customer, a charging station, or the depot. The objective is to maximize the expected total rewards that can be collected by EV.
Due to the notorious three curses of dimensionality, this problem cannot be solved exactly using forward dynamic programming. Instead, we propose two algorithms to solve the problem. One is an a priori offline approach and the other is a rollout algorithm. In the a priori offline approach, an a priori route is developed to visit customers. The route is pre-determined before EV leave the depot. However, when there are uncertain traffic congestion conditions, the travel time between locations is uncertain, so is the energy consumption of EV. Therefore, with time windows associated with each customer, EV may not be able to arrive at where customers are within their time windows. In such a case, the a priori route needs to be modified. The modifications of the pre-designed a priori route are named recourse actions. Specifically, when executing an a priori route, before leaving the current location, based on the currently observed traffic condition, if EV cannot arrive at the next customer schedule in the a priori route, the customer will be removed from the planned route and EV will head for the next location after it. In this study, a variable neighborhood search algorithm is proposed to obtain a good quality a priori route.
In the rollout algorithm, we dynamically determine which location to head for at each decision epoch. There are two types of decisions in the rollout algorithm. One is the routing decision and the other is the charging decision. When making a routing decision, an a priori route with recourse actions is adopted to estimate the expected reward-to-go and help to choose the next customer to visit. Future possible traffic conditions are considered when developing the a priori route. When making a charging decision, we adopt a threshold charging policy, so that EV will head for a charging station if its current energy level is below the threshold. If EV need to be charged, the charging decision chooses a charging station, so that the traveling time to the station plus the queueing time at the station is minimal out of all candidate charging stations.
To evaluate the performance of the above two algorithms, we conduct computational experiments using benchmark datasets. We use 56 data instances, each containing 20 customers and 8 charging stations. There are R, C, and RC instance sets. The instance set R corresponds to randomly relocated customers, while instance set C corresponds to clustered customers, and instance set RC corresponds to a mix of randomly relocated and clustered customers. For the R instance set, the rollout algorithm can collect 2. 33% more expected rewards from serving customers than the a priori offline algorithm. For the C instance set, the rollout algorithm collects 10.16% more expected rewards than the a priori offline algorithm, while for the RC instance set, it collects 5.74% more expected rewards than the a priori algorithm. The computational results indicate that the rollout algorithm performs the best when customers are clustered. In terms of computational time, we restrict the computational time for the rollout algorithm to make a decision at each decision epoch to one minute. Thus, the computational time of the rollout algorithm is comparable to the a priori offline algorithm.
In this study, we consider a stochastic electric vehicle routing problem. A priori and dynamic solution algorithms are proposed to solve the problem. The computational experiments demonstrate that the rollout algorithm is in general better than the a priori offline algorithm. To extent this study in the future, we may consider non-linear charging and recharging functions of EV, in which it is more challenging to make dynamic routing and charging decisions.

Key words: electric vehicle, traffic congestion, charging decision, Markov decision process, a priori solution, rollout algorithm

摘要： 在相关政策的支持下,将纯电动轻卡车辆用于城市物流配送成为物流行业发展的新趋势。现实中,由于交通拥堵引起旅行时间的不确定性,以及由此导致的电量消耗不确定性,使得电动车辆需要访问充电站,而充电时的排队等待时间可能是随机的。鉴于此,本研究考虑交通拥堵和充电站排队的纯电动车辆路径规划问题,在尽可能满足顾客时间窗的基础上,求解期望总收益最大的动态路径方案。通过构建马尔可夫决策过程模型并设计离线算法和滚动算法进行模型求解。求解过程中采用先验路径策略近似估计每个决策阶段的期望收益,并通过变邻域搜索算法搜索每个决策阶段的先验路径解。在数值实验中,将滚动算法提供的动态解与离线算法提供的先验解进行对比,验证了研究中采用的滚动算法的有效性和可行性。

关键词: 纯电动车辆, 交通拥堵, 充电决策, 马尔可夫决策过程, 先验路径, 滚动算法