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

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