{'fraction_non_alphanumeric': 0.03595556222789371, 'fraction_numerical': 0.008744933193214233, 'mean_word_length': 4.752374784110535, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Reinforcement Learning Approach for Electric Vehicle Routing Problem with Vehicle-to-Grid Supply

The use of electric vehicles (EV) in the last mile is appealing from both sustainability and operational cost perspectives. In addition to the inherent cost efficiency of EVs, selling energy back to the grid during peak grid demand, is a potential source of additional revenue to a fleet operator. To achieve this, EVs have to be at specific locations (discharge points) during specific points in time (peak period), even while meeting their core purpose of delivering goods to customers. In this work, we consider the problem of EV routing with constraints on loading capacity; time window; vehicle-to-grid energy supply (CEVRPTW-D); which not only satisfy multiple system objectives, but also scale efficiently to large problem sizes involving hundreds of customers and discharge stations. We present QuikRouteFinder that uses reinforcement learning (RL) for EV routing to overcome these challenges. Using Solomon datasets, results from RL are compared against exact formulations based on mixed-integer linear program (MILP) and genetic algorithm (GA) metaheuristics. On an average, the results show that RL is 24 times faster than MILP and GA, while being close in quality (within 20%) to the optimal.


INTRODUCTION
Last-mile delivery is the most expensive part of the logistic and e-commerce process, often accounting for more than 50% of the overall shipping expenses [3]. To address this major pain-point, most players in this space are exploring the use of newer technologies that can help in reducing the cost. Electric vehicles (EV) are a reasonable choice for this application, as they offer many cost benefits that come naturally from electrification such as high fuel efficiency; low maintenance overhead; compliance to emission regulations. Therefore, there is an increasing adoption of EVs in last-mile delivery operations; expected to grow to 8 million by 2030 [1,13]. While these developments are promising, the benefit of using last-mile delivery EVs extend beyond this present scope. In fact, they can be used to provide other ancillary services within the city ecosystem. Such multi-service operation models open up alternate revenue channels for the logistics provider, which can lead to further cost reduction of the last-mile segment. Motivated by this observation, we explore an alternate delivery model using EVs; where the scope is not only limited to delivery of goods to customers, but extends to the delivery (or selling) of energy to the grid during its periods of peak energy demand. Due to the virtue of the on-board battery (which provide fuel to move the vehicle) EVs can potentially use the same energy reserve to sell power back to the grid at higher tariff rates. The key question, however, is whether or not last-mile EVs can perform this additional task without deviating from the primary business objective.
We approach the problem of delivery of goods (to customers) and delivery of energy (to the grid through discharging stations) as an electric vehicle routing problem (VRP) with the goal of finding the most cost effective routes that guarantee order fulfillment. This problem is non-trivial for the following two reasons. First, the delivery demand (i.e., goods/energy) is present at specific time periods and locations, and therefore, the supply (i.e., delivery EVs) needs to match that demand (both in space and time) for making a successful transaction. Second, the computationally difficult VRP problem becomes even harder with the introduction of new constraints related to EVs and energy discharge (that will happen both implicitly due to travel and explicitly due to energy sale at discharging stations). A number of solutions exist for solving VRP and its different variations. They range from mixed-integer linear programs (MILP) providing exact solutions to metaheuristics involving either neighborhood search, tabu search, genetic algorithms, simulated annealing, or ant colony optimization that provide near exact solutions with faster convergence [6]. However, none of these approaches scale to large problem instances that involve hundreds of customers and discharging stations with multiple operational constraints in quick time [9,16] with reasonable solution accuracy.
We present QuikRouteFinder that uses reinforcement learning (RL) to address the problem of routing for EVs with multi-service delivery by overcoming the above challenges. In RL, a controller agent observes a system state and decides a control action. The system implements the action and provides a reward to the agent. In our case, the RL agent acts as an aggregator to a fleet of delivery EVs. The state of the system at every time step includes information about individual (vehicle-customer) or (vehicle-discharging station) pairs. The action taken is to decide the visit location of vehicles in the system. The reward to the agent would be the trip cost obtained in that timestep of the control action. The RL agent algorithmically learns to map actions to the observed system state in a way that maximizes the rewards earned over the training period. This offline training helps the agent to make faster decisions in real-time with efficient scaling to large problem sizes.
In this paper, our specific contributions include the following.
(1) We model the electric vehicle routing problem (CEVRPTW-D) with constraints on loading capacity; time window; vehicle-to-grid energy supply; and formulate the multi-objective optimization problem to minimize the trip cost of the fleet.
(2) We design QuikRouteFinder : a value-based reinforcement learning algorithm by defining the (state, action) space, and engineer the reward signal for the RL agent to find the cost effective delivery routes. We design and implement a genetic algorithm (GA) metaheuristic to derive optimal results for CEVRPTW-D.
(3) Using Solomon datasets, we evaluate and compare the computation speed and solution accuracy of the proposed RL model against GA and MILP. Preliminary results from our study show that QuikRouteFinder (based on RL) is 24 times faster than the GA and MILP baselines in terms of solutioning speed, but with ≈ 20% decrease in solution quality.
The rest of the paper is organized as follows. The system overview is outlined in Section 2. Section 3 presents the evaluation studies. We review existing literature in Section 4, and conclude by summarizing the work in Section 5.

SYSTEM OVERVIEW
The last-mile logistics system for CEVRPTW-D consists of four primary stakeholders. First, the goods demand-side, consisting of customers who are expecting the delivery of ordered items within a certain time window. Second, the energy demand-side, consisting of discharging stations willing to purchase power during peak energy demand periods of the grid. Third, the supply-side, comprising of last-mile delivery EVs. The final stakeholder is the fleet manager that connects the demand and the supply; but in a manner that ensures that the demand for goods is met without failure, and demand for energy is served if there is an opportunity. Our perspective is that of the fleet manager with an aim to minimize trip cost of the fleet by finding cost effective routes; which reduces the overall travel distance and vehicles used for delivery, while generating revenue from energy sale to the grid.
The fleet manager needs to plan the delivery schedule and vehicle routes in advance. All requisite information is known a priori since the fulfilment center shares the customer order list for delivery purpose, while the grid announces its peak energy demand periods, normally, a day before the requirement. We consider an operational setup where a fleet of last-mile EVs leave the base depot at a given time with a starting state-of-charge (SoC) of . Their target is to complete all deliveries and return back to the same depot. During this delivery period, EVs could also visit a discharging station and sell power back to the grid in a time defined manner that does not impact the delivery of customer orders. We assume that is sufficient to complete the delivery trip without recharging and, in addition, may allow V2G discharging where possible. This setup does not allow recharging halts during the trip as it would increase the vehicle idle time, and subsequently, the trip cost.  indicates, if edge is traversed by an EV (binary) service time at discharging station node time-of-arrival at node remaining battery capacity on arrival at node remaining cargo on arrival at node time of ; and travel energy of . The battery of the EV is depleted at (kWh/km) on the road (while traveling between two nodes); and (kWh) during the discharge operation (while giving back power back to the grid during the peak demand time periods between 1 and 2 at discharging station node ) (see Table 1).

Optimization Problem
The objective of CEVRPTW-D is to minimize the trip cost: M is taken as the combined weighted 1 cost of the total distance travelled by the EVs and the number of such EVs used in a trip; minus the reward gained due to the time spent at discharging stations and selling power back to the grid. Eq.
(1) is subject to the following constraints: ∑︁

RL Agent
Mapped u -> i ?

UNASSIGNED Vehicles
Feasible i for u?

Last-mile Delivery Environment
Local Update

YES NO
Depot

Choose (u,i) pair
State Generator

INFO (u) : Vehicles Find STATE: S t (u,i) feasible (u,i) pairs
Constraint (2) ensures that every customer is visited exactly once, while making it optional to visit any of the discharging stations. Constraint (3) establishes flow conservation, wherein the the number of incoming arcs is equal to the number of outgoing arcs at each node. Constraints (4) and (5) guarantee time feasibility of arcs leaving customers, discharging stations, and the depot. The condition that each node must be visited within its time window is ensured by constraint (6). Constraints (7) and (8) enforce remaining charge (energy) feasibility for arcs leaving customers, discharging stations, and the depot. The demand fulfillment of all customers awaiting order delivery is guaranteed by constraint (9). Constraints (10) and (11) ensure that the discharge service time aligns with the grid peak demand period, if discharging stations are visited. Note that all nodes are given a time window ranging between the starting time of service and the total time horizon. Therefore, by ensuring that the time window constraints for individual customers and discharging stations are met, it can also be ensured that the entire operation happens within the specified time horizon.

RL Representation
The optimization problem is formulated in the RL framework by defining the (state, action) space and engineering the reward function. The algorithm builds the solution by mapping vehicles to a (customer or discharging station) node at every decision epoch, eventually leading to an optimized route.
States: The information about individual (vehicle-node) pairs are given as input to the RL agent. The definition used for the observed system state ( , ) (for vehicle ; at time ; for proposed node ) is shown in Table 2. In our system model, vehicles spend energy under two conditions: first, if they are traveling between two nodes; and second, if they are participating in energy (discharge) transactions at discharging stations. These two aspects are captured by , and , respectively. , also serves as a proxy variable to ascertain the distance travelled between nodes. There are two supporting binary variables and that, respectively, help to capture if the vehicle has left the depot, and the location of the proposed node (customer or discharging station). The final variable captures the wait time of a vehicle at the proposed node before it can start service. The following constants are used for normalizing non-binary state variables: (i) (that denotes the energy required to travel the diagonal length of the graph) is used for , and ; (ii) (that denotes the decision time horizon) is used for .
Action: The action ( , ) is the (vehicle, node) pair at decision time . It is selected either at the start of an episode when all vehicles are available, or when any vehicle becomes available post completing the assigned service. This action is derived in the following manner. The agent computes the respective value for each ( , ) pair (irrespective of their availability status), and chooses the pair with the maximum value. If the chosen ( ↦ → ) mapping includes a vehicle that is currently in-service, a local state update is made to capture this assignment. This update includes removing the chosen node from the service list, and making changes to the distance and time factors. The process is repeated either until all available vehicles or nodes get assigned; post which the global environment is updated along with the reward for the assignment action.
Reward: For each chosen (vehicle, node) pair, the reward ( , ) is taken as the total cost of vehicle visiting node at time . It is defined as: Here, a positive reward is given for visiting either a customer node or a discharging station node; while a negative reward is given for choosing longer route segments; for assignments that lead to waiting time at nodes; and for sending new vehicles from the depot. We chose 1 = 0.15, 2 = 0.001, 3 = 0.15, 4 = 0.15, 5 = 0.55 since they gave the best solutions on the training data. In the reward function, since the weight 3 (given for serving a customer node) is much greater than the weight 2 (given for discharging station visit), the agent learns to prefer customer service more than discharge operation whenever presented with an option of both. In a bid to maximize the reward received, this preference of the agent of putting customers over discharge operation can be seen in the learning curve as the fulfilment ratio slowly becoming equal to 1 (indicating that all the customers were serviced).
Handling workflow: Once the reward is given for the corresponding (state, action) pair, the tuple [ ( , ); ( , ); ( , )] is added to the replay buffer. At the end of each episode, samples are drawn randomly from the replay buffer ; and the value network weights are updated by minimizing the mean squared error (MSE) between ( , ) and ( , ). This makes the agent learn the (state, action) mapping.
(Vehicle ↦ → Node) masking scheme: At each decision step , the RL agent produces a scalar output for all feasible ( , ) pairs. We designed a masking scheme to derive these pairs. Let us suppose that proposed next node of vehicle , currently at node , is node . In such a case, pair ( , ) is considered infeasible if it satisfies any of the following conditions: • Node is a customer with unfulfilled demand that is either nil or exceeds the remaining carrying load of vehicle (refer Eq. (9)).
• Node is a customer and the current SoC of the vehicle cannot support the complete trip from node to node and back to the depot (refer Eq. (7)).
• Node is a discharging station and the current SoC of the vehicle cannot support the complete trip from node to node and back to the depot; as well as the discharge operation at node refer Eq. (8)).
Neural network architecture: The architecture details and the hyperparameters used in the learning and testing are as follows: (i) architecture: (5, 12, 6, 3, 1) consisting of 1 input and 1 output layer, and 3 hidden layers; (ii) optimizer: Adam; (iii) learning rate: 0.001; (iv) batch size ( ): 16; (v) replay buffer size ( ): 5000; (vi) exploration policy: -greedy with exploration factor decaying linearly from 1 to 0 over 75 episodes. The training consisted of 200 episodes where each episode is a different instance (i.e., a random combination of customers, discharge stations, vehicles). The neural network is realised using Pytorch library in Python 3.6. The detailed training procedure is described in Algorithm 1.  1 unit). For each training episode, a new random instance is generated using these parameters. The same parameters are then used for testing.
Solution improvement: After a candidate solution is generated by the RL, it is further refined by a random insertion heuristic. The heuristic works by breaking up routes with the least number of customers, and each node in these routes is checked for feasibility by inserting them between various nodes in the remaining routes. Whenever such feasible locations are found, the one with the least marginal increase in the overall cost is chosen and the node is inserted to form a new route. This insertion heuristic, therefore, refines the solution by reducing the number of vehicles used; without having an adverse effect on the total cost of the trip.

GA Formulation
In this section, we will describe a GA metaheuristic constructed to solve the CEVRPTW-D problem. We will define a chromosome as a collection of routes of individual vehicles (also known as tour) [? ]. Each chromosome ℎ is assigned a fitness score using the following: Here ( ℎ), 1 ( ℎ), 1 ( ℎ), 1 ( ℎ) and ( ℎ) denote the fitness score, total distance travelled, number of vehicles used, charge penalty, and total energy discharged back to the grid for a chromosome ℎ respectively. The fitness score is chosen to align with Eq.(1) with the exception of the term related to charge penalty 1 (·). This term ensures that the resulting solution does not violate the total charge constraints which ensures that vehicles don't get discharged before the end of the trip. Consequently, the weight 1 ( ℎ) is chosen to be a very high quantity ( 1 ( ℎ) = 1000. 1 ( ℎ)). This guarantees that all chromosomes that violate the total charge constraints are not chosen in the next generation. In addition, for every chromosome, we delete all routes that comprise of only discharging station visits with zero customer visits. The objective is to minimize the fitness score; and hence, chromosomes with lower fitness score are considered "better". The GA proceeds according to the following steps.
• Initial Population Generation: It is done via the nearest neighbor rule starting from random initial nodes, and respecting the total distance and time window constraints.
• Initial Solution Improvement: An insertion heuristic is used in this step. It involves breaking up routes with least volume utilization; putting their nodes in an unreserved pool; trying to insert these nodes into existing routes respecting constraints; and finally choosing the newly formed route with the smallest increment in fitness score. This reduces the number of vehicles in the solution.
• Selection of Parents: A binary tournament procedure is followed for parent selection wherein two chromosomes are selected at random; and the one with lower fitness score is chosen.
• Crossover and Mutation: Two parents are crossed over either using a common nodes crossover or a common arcs crossover approach to produce new offsprings. Once the new offsprings are created, they undergo two stages of mutation. The first stage involves creation of new members by removing routes with only discharging stations (and no customer visits). The second stage involves a mutation with 10% probability (in this case, the type of mutation is chosen to be one among several with equal likelihood; for e.g., random note/route removal, nearest node removal).
• Progression and Termination: The size of the population at the beginning of each generation is a fixed quantity (e.g., 200). Once the parents and offsprings are created and added to the population of current generation; we follow an elitist procedure to select the population for the next generation. In this method, we retain the top 10% of the current population; while the others are randomly sampled. This procedure is terminated if there is no improvement in the solution, or a generation count limit is reached.

EVALUATION
To test the performance of the aforementioned algorithms, we use the Solomon datasets as benchmarks [15], which are modified to suit the EVRPTW-D problem. These datasets are classified into two categories: Type 1, (vehicles with low capacities); and Type 2 (vehicles with larger capacities). Further, within each type the dataset can have customer locations that are either clustered ( ), random ( ), or a combination of both ( ). For each standard dataset, we convert some of the existing customers to charging stations with a pre-specified timing window corresponding to the grid peak demand. For instance, the standard dataset 1 100 comprises of 90 customers and 10 discharging stations. The experiment results are captured in Tables 3 and 4. Each row, respectively, describes the average results obtained for datasets of a specific type (1 or 2); number of customers and discharging stations (25, 50, 100); and location distribution of customers ( , , ). We make comparisons using the objective value M (refer to Eq. 1), which is averaged over all datasets corresponding to a particular row. Table 3 outlines the comparison results between the RL approach of QuikRouteFinder and GA for all the datasets. Table 4 contains specific instances where the MILP formulation (Section 2.1) converges within a reasonable amount of time.
From Table 4, we can observe that GA metaheuristic performs close to an exact formulation approach 2 . Table 3 shows two key aspects: first, GA outperforms RL by an average of 19.8% (range 8.3% − 36.52%) based on M; and second, RL is faster than GA by 24 times (on average). In other words, the RL approach of QuikRouteFinder finds approximately optimal solutions at a much faster rate than the metaheuristic GA. The analysis also reveals that the average optimality gap between GA and RL is consistent with respect to number of nodes: 17.23% (std. dev. of 7.98%) for 25-nodes; 22.38% (std. dev. of 8.35%) for 50-nodes; and 20.02% (std. dev. of 6.58%) for 100-nodes. Therefore, for datasets with higher number of nodes (prevalent in real-world scenarios), QuikRouteFinder can be preferred over GA (if compute time is critical).

RELATED WORK
Electric VRP or EVRP is one of the latest variations of the extensively studied vehicle routing problem. It was first introduced by Schneider et al. [14] where they explored the possibility of recharging EVs during the trip while considering the capacity constraints of the vehicle and time windows for goods delivery. It was an extension of the work on green VRP by Erdogan and Miller [7], which aimed to find a way to extend the range of alternate fuel vehicles (i.e., those running on biodiesel, liquid natural gas, or CNG) by visiting refueling stations. However, the key difference between these two works is the energy replenishment model; wherein [7] uses a constant replenishment time model, while [14] uses a linear charging time model. Following these two initial studies, there have been multiple investigations on EV route optimization that extend EVRP to include various operational aspects of charging and discharging. Existing work can be broadly categorized as follows: (i) Grid-to-Vehicle (G2V): Since EV charging is time consuming, Felipe et al. [8] and Keskin et al. [10] proposed partial recharging strategies rather than going for full charge. The key challenge in this EVRPTW-PR problem was to estimate the charge levels for a large set of EVs using different types of charging technologies; for which [8] proposed simulated annealing metaheuristic approach combined with a constructive local search mechanism, while [10] developed an adaptive large neighborhood (ALNS) search method. Yang et al. [19] factored in the time-of-use electricity price for estimating the charging cost with the aim to optimize the EV route cost for delivery and pickup services. They solved this model by 2 The MILP approach was solved using the standard Coin-BC (Branch and Cut ) Solver developing a learnable partheno-genetic algorithm with integration of expert knowledge about location of charging stations and their selection probability. Barco et al. [5] extended this problem of route assignment and charging actions to reduce the combined cost of charging and battery degradation, and solved using the differential evolution technique. Yu et al. [20] developed an MILP model to find optimal routes for autonomous EVs in order to make them charge at locations of energy generation.
(ii) Vehicle-to-Grid (V2G) & Grid-to-Vehicle (G2V): Tang et al. [17] proposed a distributed routing and charge scheduling algorithm, which decides the charging station locations and the charge / discharge rates along the optimal route for EVs to complete their trip by incurring the least travel cost. In this problem, they considered two types of stations with time invariant energy price signals: one, providing renewable energy at a low price; and second, regular stations with higher charging cost with rewards for discharging. Trivino et al. [18] extended this work by incorporating intermediate stops for EVs, and considering time-variant electricity prices and battery degradation cost. Abdulaal et al. [4] studied G2V and V2G options in the travel path of EVs with multiple constraints, and developed a GA solver that incorporates Markov decision process and trust region optimization methods. Lin et al. [12] studied the problem of joint optimization of routing and charge/discharge scheduling of multiple EVs under time-variant electricity prices; for which they proposed a MILP solution with hueristic.
The application of RL to EVRP variants is relatively new. Lin et al. [11] proposed a RL framework to solve capacitated EVRP with time window constraints (CEVRPTW). This paper differs from [11], both in terms of the problem definition and RL design. Our multiservice model of delivering goods and energy requires extending CEVRPTW with energy discharge constraints on account of visiting discharging stations during a delivery trip. We use a RL model to find (near) optimal routes by mapping vehicles to customer / discharging station locations; instead of using a RL attention mechanism to handle dynamic changes in the operating constraints.

CONCLUSION
In this paper, we presented an approach for the solving CVRPTW-D (a new EVRP variant) using a RL framework. Using numerical simulations on benchmark datasets, we showed that the RL approach generates solutions 24 times faster than the proposed GA and MILP baselines; although with approximately 20% increase in optimality gap in terms of the cost. We are currently working on designing better RL models to not only close this optimality gap, but also to handle dynamic demands in real-time.