Nicholas D Kullman

Martin Cousineau

Justin C Goodson

Jorge E Mendoza

Dynamic Ridehailing with Electric Vehicles

We consider the problem of an operator controlling a fleet of electric vehicles for use in a ridehailing service. The operator, seeking to maximize profit, must assign vehicles to requests as they arise as well as recharge and reposition vehicles in anticipation of future requests. To solve this problem, we employ deep reinforcement learning, developing policies whose decision making uses Q-value approximations learned by deep neural networks. We compare these policies against a reoptimizationbased policy and against dual bounds on the value of an optimal policy, including the value of an optimal policy with perfect information which we establish using a Benders-based decomposition.

We assess performance on instances derived from real data for the island of Manhattan in New York City. We find that, across instances of varying size, our best policy trained with deep reinforcement learning outperforms the reoptimization approach. We also provide evidence that this policy may be effectively scaled and deployed on larger instances without retraining.

. For brevity, we refer to this problem as the Electric Ridehail Problem with Centralized control, or E-RPC.

Our contributions in this work are as follows: 1) We offer the first application of deep reinforcement learning (RL) to the E-RPC, developing policies that respond in real time to serve customer requests and anticipate uncertain future demand under the additional constraints of fleet electrification. The policies are model-free, meaning they learn to anticipate this demand without any prior knowledge of its shape.

We compare these deep RL-based policies to a reoptimization-based policy from the ridehailing literature.

2) We evaluate these policies on instances constructed with real data reflecting ridehailing operations from New York City in 2018. 3) We establish a dual bound for the dynamic policies using a perfect information relaxation that we solve using a Benders-like decomposition. We compare this complex dual bound against a simpler dual bound and provide an analysis of when the additional complexity of the perfect information bound is valuable. 4) We show that our best deep RL-based solution significantly outperforms the benchmark reoptimization policy. 5) We further demonstrate that the best-performing deep RL-based policy can be scaled to larger problem instances without additional training. This is encouraging for operators of ridehail companies, as it suggests robustness to changes in the scale of operations: in the event of atypical demand or a change in the number of vehicles (e.g., due to fleet maintenance), the policy should still provide reliable service.

We begin by reviewing related literature in §2, then provide a formal problem and model definition in §3. We describe our solution methods in §4, the bounds established to gauge the effectiveness of these methods in §5, and demonstrate their application in computational experiments in §6. We offer brief concluding remarks in §7.

Related Literature

.

. Hyland and Mahmassani (2018) introduce a

Introduction

Governmental regulations as well as a growing population of environmentally conscious consumers have led to increased pressure for firms to act sustainably. This pressure is particularly high in the logistics domain, which accounts for about one third of emissions in the United States (Office of Transportation and Air Quality 2019). Ridehailing services offer a means to more sustainable transportation, promising to reduce the need for vehicle ownership, offering higher vehicle utilization [START_REF] Lyft | Why 130,000[END_REF], allowing transit authorities to streamline services [START_REF] Bahrami | Flexbus: Improving public transit with ride-hailing technology[END_REF], and stimulating the adoption of new vehicle technologies (Jones and Leibowicz 2019). In recent years, ridehailing services have seen rapid and widespread adoption, with the number of daily ridehailing trips more than quadrupling in New York City from November 2015 to November 2019 (New York City Taxi & Limousine Commission 2018).

Simultaneously, electric vehicles (EVs) are beginning to replace internal-combustion engine (ICE) vehicles, commanding increasingly more market share (Edison Electric Institute 2019). Coupling the pressures to act sustainably with EVs' promise of lower operating costs, ridehail companies are likely to be among the largest and earliest adopters of EV technology. Indeed most major ridehail companies have made public commitments to significant EV adoption [START_REF] Slowik | Assessing ride-hailing company commitments to electrification[END_REF]. However, EVs pose technological challenges to which their ICE counterparts are immune, such as long recharging times and limited recharging infrastructure [START_REF] Pelletier | 50th anniversary invited article -goods distribution with electric vehicles: Review and research perspectives[END_REF].

In this work, we consider these challenges as posed to an operator of a ridehail company whose fleet consists of EVs. We further assume that the EVs in the fleet are centrally controlled and coordinated. suite of optimization-based assignment strategies and show that they outperform heuristics that do not employ optimization. Following suit, [START_REF] Bertsimas | Online vehicle routing: The edge of optimization in large-scale applications[END_REF] describe ways to reduce the complexity of optimization-based approaches for problems with large fleets and many customers. They demonstrate their proposed methods on realistically-sized problem instances that reflect ridehailing operations in New York City.

The aforementioned studies largely ignore the task of repositioning idle vehicles in anticipation of future demand. This is in contrast to studies such as [START_REF] Miao | Taxi dispatch with real-time sensing data in metropolitan areas: A receding horizon control approach[END_REF], [START_REF] Zhang | Control of robotic mobility-on-demand systems: A queueing-theoretical perspective[END_REF], and [START_REF] Braverman | Empty-car routing in ridesharing systems[END_REF] who address their RP from the opposing perspective of the fleet repositioning problem. [START_REF] Miao | Taxi dispatch with real-time sensing data in metropolitan areas: A receding horizon control approach[END_REF] do so using learned demand data with a receding horizon control approach. [START_REF] Braverman | Empty-car routing in ridesharing systems[END_REF] use fluid-based optimization methods for the repositioning of idle vehicles to maximize the expected value of requests served. They establish the optimal static policy and prove that it serves as a dual bound for all (static or dynamic) policies under certain conditions. Other studies consider strategies for both the assignment and repositioning tasks. [START_REF] Daniel | The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios[END_REF] propose rule-based heuristic strategies while most others (such as [START_REF] Alonso-Mora | On-demand highcapacity ride-sharing via dynamic trip-vehicle assignment[END_REF][START_REF] Dandl | Evaluating the impact of spatiotemporal demand forecast aggregation on the operational performance of shared autonomous mobility fleets[END_REF][START_REF] Hörl | Fleet operational policies for automated mobility: A simulation assessment for zurich[END_REF]) employ various optimization-based methods. Because it is scalable and wellsuited for adaptation to our problem model, we implement the approach from Alonso-Mora et al. (2017) here as a benchmark against which to compare our proposed solution methods.

A recent competing method to address ridehail problems is reinforcement learning (RL), predominantly deep reinforcement learning. As it is better-positioned to address problems with larger fleet sizes, many studies employing RL take a multi-agent RL (MARL) approach [START_REF] Oda | Distributed fleet control with maximum entropy deep reinforcement learning[END_REF][START_REF] Oda | Movi: A model-free approach to dynamic fleet management[END_REF][START_REF] Holler | Deep reinforcement learning for multi-driver vehicle dispatching and repositioning problem[END_REF][START_REF] Li | Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning[END_REF], Singh et al. 2019). In work sharing many similarities to ours, [START_REF] Holler | Deep reinforcement learning for multi-driver vehicle dispatching and repositioning problem[END_REF] use deep MARL with an attention mechanism to address both the assignment and repositioning tasks. They compare performance under two different MARL approaches: one in which a system-level agent coordinates vehicle actions to maximize total reward; and one in which vehicle-level agents act individually, each maximizing its own reward. [START_REF] Oda | Movi: A model-free approach to dynamic fleet management[END_REF] use a deep MARL approach to tackle fleet repositioning, but rely on a myopic heuristic to perform assignment. [START_REF] Oda | Distributed fleet control with maximum entropy deep reinforcement learning[END_REF] do so as well, but employ special network architectures with soft-Q learning which they argue better accommodates the inherent complexities in road networks and traffic conditions. [START_REF] Li | Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning[END_REF] employ a multi-agent RL framework, comparing two approaches that vary in what individual vehicles know regarding the remainder of the fleet; however, in contrast to most MARL applications to RPs, they address only the assignment problem, assuming that the vehicles are de-centralized and therefore not repositioned by the operator. Similarly assuming de-centralized vehicles and addressing only the assignment problem, [START_REF] Xu | Large-scale order dispatch in on-demand ride-hailing platforms: A learning and planning approach[END_REF] combine deep RL with the optimization-based methods used in, e.g., [START_REF] Alonso-Mora | On-demand highcapacity ride-sharing via dynamic trip-vehicle assignment[END_REF], [START_REF] Zhang | A taxi order dispatch model based on combinatorial optimization[END_REF], and [START_REF] Hyland | Dynamic autonomous vehicle fleet operations: Optimization-based strategies to assign avs to immediate traveler demand requests[END_REF]. In their work, Xu et al. use deep RL to learn the objective coefficients in a math program that is used in an optimization framework to assign vehicles to requests.

Missing from all aforementioned studies is fleet electrification -none take into account the technical challenges associated with electric vehicles, such as long recharging times or limited recharging infrastructure. The number of studies that consider these constraints is limited but growing. Most (e.g., [START_REF] Jung | Shared-taxi operations with electric vehicles[END_REF][START_REF] Chen | Operations of a shared, autonomous, electric vehicle fleet: Implications of vehicle & charging infrastructure decisions[END_REF][START_REF] Kang | Autonomous electric vehicle sharing system design[END_REF][START_REF] Iacobucci | Optimization of shared autonomous electric vehicles operations with charge scheduling and vehicle-to-grid[END_REF][START_REF] Robinson | Heuristics for electric taxi fleet management at teo taxi[END_REF] use the heuristic and optimization methods previously mentioned. We focus here on three works closely related to ours that employ learning-based approaches. First, [START_REF] Al-Kanj | Approximate dynamic programming for planning a ride-sharing system using autonomous fleets of electric vehicles[END_REF] use approximate dynamic programming to learn a hierarchical interpretation of a value function that is used to determine whether or not to recharge vehicles at their current location, in addition to repositioning decisions to neighboring grid cells and the assignment of vehicles to nearby requests. The study examines the possi-bility for riders or the operator to reject a trip assignment at various costs; it also studies the problem of fleet sizing. Second, Pettit et al. (2019) use deep RL to learn a policy determining when an EV should recharge its battery and when it should serve a new request. The study includes time-dependent energy costs. However, it only considers a single vehicle, and it ignores the task of repositioning the vehicle in anticipation of future requests. Finally, [START_REF] Shi | Operating electric vehicle fleet for ridehailing services with reinforcement learning[END_REF] apply deep reinforcement learning to the RP with a community-owned fleet, in which they seek to minimize customer waiting times and electricity and operating costs. Similar to many of the RL studies cited previously, the study employs a multi-agent RL framework that produces actions for each vehicle individually which are then used in a centralized decision-making mechanism to produce a joint action for the fleet. The joint actions assign vehicles to requests and specify when vehicles should recharge; however the study also ignores repositioning actions.

Thus, ours marks the first application of deep reinforcement learning to the E-RPC in consideration of EV constraints alongside both fleet repositioning and assignment tasks. We also argue that we consider a more realistic problem environment than in most RL-based approaches to ridehail problems. Indeed, the vast majority of studies (e.g., [START_REF] Al-Kanj | Approximate dynamic programming for planning a ride-sharing system using autonomous fleets of electric vehicles[END_REF][START_REF] Oda | Distributed fleet control with maximum entropy deep reinforcement learning[END_REF][START_REF] Holler | Deep reinforcement learning for multi-driver vehicle dispatching and repositioning problem[END_REF][START_REF] Shi | Operating electric vehicle fleet for ridehailing services with reinforcement learning[END_REF][START_REF] Singh | A distributed model-free algorithm for multi-hop ridesharing using deep reinforcement learning[END_REF] rely on a coarse grid-like discretization to describe the underlying service region. This serves as the basis for their repositioning actions, which are often restricted to only the adjacent grid cells. This is in contrast to the current work, in which we allow repositioning to non-adjacent sites that correspond to real charging station locations. Time discretization can also be overly coarse. Many studies choose one minute between decision epochs, as in, for example, [START_REF] Oda | Movi: A model-free approach to dynamic fleet management[END_REF]; but some choose far longer between decision epochs, such as six minutes in [START_REF] Shi | Operating electric vehicle fleet for ridehailing services with reinforcement learning[END_REF] and 15 minutes in [START_REF] Al-Kanj | Approximate dynamic programming for planning a ride-sharing system using autonomous fleets of electric vehicles[END_REF]. Given that current ridehailing applications provide fast, sub-minute responses, such an arrangement would likely lead to customer dissatisfaction. We are free of such a discretization here, allowing agents to respond to customer requests immediately.

Problem Definition and Model

We consider a central operator controlling a homogeneous fleet of electric vehicles V = {1, 2, . . . , V } that serve trip requests arising randomly across a given geographical region and over an operating horizon T . Across the region are uncapacitated charging stations (CSs, or simply stations) C = {1, 2, . . . , C} at which vehicles may recharge or idle when not in service. The operator assigns vehicles to requests as they arise. Additionally, the operator manages recharging and repositioning operations in anticipation of future requests. The objective is to maximize expected profit across the operating horizon.

Several assumptions and conditions connect the problem to real-world operations. When a new request arises, the operator responds immediately, either rejecting the request or assigning it to a vehicle.

A vehicle is eligible to serve a new request if it can pickup within w * time units, the amount of time customers are willing to wait. Each vehicle maintains at most one pending trip request. Thus, a vehicle either serves a newly assigned request immediately or does so after completing the service of a request to which it is already assigned ("work-in-process"). Assignments of requests to vehicles cannot be canceled, rescheduled, or reassigned. Each vehicle has a maximum battery capacity Q and known charging rate, energy consumption rate, and speed. The operator ensures assignments and repositioning movements are energy feasible.

We formulate the problem as a Markov decision process (MDP) whose components are defined as follows.

States.

A decision epoch k ∈ {0, 1, . . . , K} begins with a new trip request or when a vehicle finishes its work-inprocess, whichever occurs first. The system state is captured by the tuple s = (s t , s r , s V ).

( (1) m , j

(1) o , j

(1) d , j

(2) m , j

(2) o , j

(2) d , j

(3) m , j

(3) o , j

(3) d ), consisting of the Cartesian coordinates of the vehicle's current position x, y; its charge q ∈ [0, Q]; and a description of its current activity (or job) j (1) , as well as potential subsequent jobs j (2) and j (3) , which may or may not exist, as determined by the operator. The description of a job j (i) consists of its type j (i) m ∈ {idle, charge, reposition, preprocess, serve, ∅} (equivalently, {0, 1, 2, 3, 4, ∅}; "preprocess" refers to when a vehicle is en route to pickup a customer), as well as the coordinates of the job's origin

j (i) o = (j (i) o,x , j (i)
o,y ) and destination j

(i) d = (j (i) d,x , j (i)
d,y ). We limit the number of tracked jobs in the state to three, because this is the maximum number of scheduled jobs a vehicle can have given the constraint that a vehicle may have at most one pending trip request: if a vehicle is currently serving a request and has a pending request, then it will have jobs of type j

(1) m = 4, j

(2) m = 3, and j

(3) m = 4. Note that we do not allow vehicles currently preprocessing for one request to be assigned a second (this would indeed require tracking a fourth job). With a sufficiently strict customer service requirement (i.e., the time between receipt of a customer's request and a vehicle's arrival to the customer), the number of opportunities to meet that requirement after undergoing the necessary (preprocessing, serving, preprocessing) sequence is small enough as to warrant the situation's exclusion. If a vehicle has n < 3 scheduled jobs, then we set j

(i) m = j (i) o = j (i) d = ∅ for n < i ≤ 3. We note that a null job j (i) m = ∅ is distinct from an idle job j (i) m = 0.
A null job is the absence of an assignment, whereas an idle job reflects an assignment to reside at a particular location.

An episode begins with the system initialized in state s 0 in epoch 0 at time 0 on some day d with no new request (s r = ∅) and all vehicles idling with some charge at a station (v ∈ C, q ∈ [0, Q], j

(1)

m = idle, j (2) m = j (3) m = ∅ for all v ∈ V).
The episode terminates at some epoch K in state s K when the time horizon T has been reached.

Actions.

When the process occupies state s, the set of actions A(s) defines feasible assignments of vehicles to a new request as well as potential repositioning and recharging movements. An action a = (a r , a 1 , . . . , a v , . . . , a V ) is a vector comprised of components a r ∈ V ∪ {∅} denoting which vehicle serves new request s r as well as a repositioning/recharging assignment a v for each vehicle v indicating the station to which it should be repositioned and begin recharging a v ∈ C ∪ {∅}. a r = ∅ denotes rejection of the new request (if it exists) and a v = ∅ denotes the "no operation" (NOOP) action for vehicle v, meaning it proceeds to carry out its currently assigned jobs. We refer to the vehicle-specific repositioning/recharging/NOOP actions a v as RNR actions. Jobs of type idle (0), charge (1), reposition (2), and ∅ are preemptable, meaning they can be interrupted by a new assignment from the operator, whereas jobs of type preprocess (3) and serve (4) are non-preemptable.

The following conditions characterize A(s). If there is no new request (s r = ∅), then a r = ∅. If there is a new request, then a vehicle is eligible for assignment if it can be dispatched immediately

m = ∅) (j (1)
m ∈ {0, 1, 2, ∅}) or if it is currently servicing a customer (j

(1) m = 4) and can then be dispatched (j

(2) m / ∈ {3, 4}). Further, a vehicle-request assignment must be energy feasible and must arrive to the customer within w * time units, the maximum amount of time a customer is willing to wait. Let f q (s v , s r ) be the charge with which vehicle v will reach a station after serving request s r . f q (s v , s r ) is equal to the current charge of vehicle v, minus the charge required for the vehicle to travel to the origin of the new request (minus the charge needed to first drop off its current customer, if j

(1) m = 4), to the destination of the new request, and then to the nearest c ∈ C from the destination. Let f t (s v , s r ) be the duration of time required for vehicle v to arrive at the customer. f t (s v , s r ) is equal to the time for vehicle v to travel to the origin of the new request from its current location (plus the time to first drop off its current customer, if j

(1) m = 4). An assignment of vehicle v to request s r is feasible if f q (s v , s r ) ≥ 0 and f t (s v , s r ) ≤ w * . Repositioning and recharging movements must also be energy feasible and may not preempt existing service assignments. If a vehicle is currently serving or preparing to serve a request (j

(1) m ∈ {3, 4}), or if the vehicle has been selected to serve the new request (a r = v), then we only allow the NOOP action a v = ∅. Otherwise, we allow repositioning to any station c ∈ C that can be reached given the vehicle's current charge level. Lastly, if a vehicle completes a trip request, triggering a new epoch, and that vehicle has not been assigned a subsequent trip request (j (1) m = ∅), then it must receive a repositioning action (a v = ∅). This condition forces vehicles to idle only at stations. While this may seem restrictive, we note (i) that the instances in our computational experiments ( §6) contain a high density of stations, (ii) that cities would likely prefer that idling ridehail vehicles do so only at dedicated locations, and (iii) that non-CS idling locations can easily be included in our model as CSs at which energy is replenished at a sufficiently small rate. We summarize the eligible actions for an EV in Table 1.

Reward Function.

When the process occupies state s and action a is selected, we earn the reward C(s, a). This reward is equal to the revenue generated by serving a new request (if a r = ∅), minus any traveling costs incurred during the subsequent epoch. Specifically, the revenue earned by serving new request s r consists of a base fare C B and a fare proportional to the distance of the request C D • d(s r ), where C D is the per-distance revenue and d(s r ) is the distance from the request's origin to its destination. The traveling costs incurred are C T • δ(s, a), where C T is a per-distance travel cost incurred by the operator and δ(s, a) is the total distance traveled by the fleet in the subsequent epoch, including all repositioning and service-related travel. We note that this value is stochastic, since the time of the next epoch is unknown and equal to either the time of the arrival of the next request, or the next time at which a vehicle completes work-in-process, whichever comes first. This yields the following reward function:

C(s, a) =    -C T • δ(s, a) a r = ∅ C B + C D d(s r ) -C T • δ(s, a) otherwise, (2)
Transition Function.

The transition from one state to the next is a function of the selected action and the event triggering the next epoch. The subsequent state s is constructed by updating the current state s to reflect changes to vehicles' job descriptions based on selected action a. Then, at time s t , we observe either a new request s r or a vehicle completing its work-in-process. At that time, we update the vehicle states s V to reflect new positions and charges. We also update vehicles' job descriptions: if a vehicle has completed n jobs between time s t and s t , we left-shift vehicles' job descriptions by n (j (i) ← j (i+n) for 1 ≤ i ≤ 3 -n) and backfill the vacated entries with null jobs (j

(i) m = j (i) o = j (i) d = ∅ for 3 -n < i ≤ 3).
See Appendix A for a more detailed description.

Objective Function.

Define a policy π to be a sequence of decision rules (X π 0 , X π 1 , . . . , X π K ), where X π k is a function mapping state s in epoch k to an action a in A(s). We seek to provide the fleet operator with a policy π that maximizes the expected total rewards earned during the time horizon, conditional on the initial state:

τ (π ) = max π∈Π E K k=0 C(s k , X π k (s k )) s 0 , ( 3
)
where Π is the set of all policies. As is common in reinforcement learning, we will often refer to the user or implementer of a policy as an agent.

Solution Methods

We consider four policies for solving the E-RPC (to which we will often refer synonymously as "agents").

These include two policies developed using deep reinforcement learning, which we describe in §4.1, and two benchmark policies, which we describe in §4.2.

Deep Reinforcement Learning Policies

Our two primary policies of interest leverage deep reinforcement learning (RL). The first of these uses deep RL to determine which vehicle to assign to new trip requests and relies on optimization-based logic for RNR decisions. We refer to this agent as deep ART (for "Assigns Requests To vehicles") or just Dart.

Our second agent we dub deep RAFTR ("Request Assignments and FleeT Repositioning") or Drafter.

Drafter uses deep RL both to assign vehicles to requests and to reposition vehicles in the fleet.

Before describing these policies in §4.1.3 and §4.1.4, we provide an overview of the basic method of deep reinforcement learning in §4.1.1 and a discussion of extensions to this basic method in §4.1.2.

Overview.

As defined in [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], reinforcement learning refers to the process through which an agent, sequentially interacting with some environment, learns what to do so as to maximize a numerical reward signal from the environment; that is, learns a policy satisfying equation (3). In practice, the agent often achieves this by learning the value of choosing an action a from some state s, known as the state-action pair's Q-value (Q(s, a)), equal to the immediate reward plus the expected sum of future rewards earned by taking action a from state s. We can express this relationship recursively following from the Bellman equation:

Q(s, a) = C(s, a) + γE max a ∈A(s ) Q(s , a ) s, a , ( 4
)
where s is the subsequent state reached by taking action a from state s and γ ∈ [0, 1) is a discount factor applied to the value of future rewards. With knowledge of Q-values for all state-action pairs it may encounter, the agent's policy is then to choose the action with the largest Q-value. However, as the number of unique state-action pairs is too large to learn and store a value for each, a functional approximation of these Q-values is learned. When deep artificial neural networks are used for this approximation, the method is called deep reinforcement learning or, more specifically, deep Q-learning (we use the terms interchangeably here). The neural network used in this process is referred to as the

deep Q-network (DQN).
Beginning with arbitrary Q-value approximations, the agent's DQN improves through its interactions with the environment, remembering observed rewards and state transitions, and drawing on these memories to update the set of weights that define the DQN, conventionally denoted by θ. Specifically, with each step (completion of an epoch) in the environment, the agent stores a memory which is a tuple of the form (s, a, r, s ), consisting of a state s, the action a taken from s, the reward earned r = C(s, a), and the subsequent state reached s . Once a sufficient number of memories (defined by the hyperparameter M start ) have been accumulated, the agent begins undergoing experience replay every M freq steps [START_REF] Lin | Self-improving reactive agents based on reinforcement learning, planning and teaching[END_REF]. In experience replay, the agent draws a random sample (of size M batch ) from its accumulated memories and uses them to update its DQN via stochastic gradient descent (SGD) on its weights θ using a loss function based on the difference

r + γ max a ∈A(s ) Q(s , a ) -Q(s, a) (5)
(or simply r -Q(s, a) if s is terminal), where the Q-values in equation ( 5) are estimated using the agent's DQN. The specific loss function and SGD optimizer used to update the weights may vary -we provide the specific implementations chosen for this work in §B.

We utilize the learned Q-values via an -greedy policy, wherein the agent chooses actions randomly with some probability and chooses the action with the highest predicted Q-value with probability 1 -.

The value of is decayed from some initially large value i at the beginning of training to some small final value f over the course of some number N of training steps. This encourages exploration when Q-values are unknown and exploitation as its predictions improve.

Implemented extensions to deep RL.

We adopt several well established extensions that improve the standard deep RL process just described.

First, we utilize a more sophisticated sampling method during experience replay known as prioritized experience replay (PER) [START_REF] Schaul | Prioritized experience replay[END_REF]. In PER, memories are more likely to be sampled if they are deemed more important, i.e., if the loss associated with a memory is not yet known (because the memory

has not yet been sampled during replay) or if the loss is large (if the agent was more "surprised" by the memory). Second, we use the double DQN (DDQN) architecture [START_REF] Hasselt | Deep reinforcement learning with double q-learning[END_REF], which employs a "target" DQN for action evaluation and a "primary" DQN for action selection. The target DQN is a clone of the primary DQN that gets updated less often (every M update steps), which helps break the tendency for DQNs to overestimate Q-values. Third, we employ dueling DDQN (D3QN) architecture [START_REF] Wang | Dueling network architectures for deep reinforcement learning[END_REF], in which the DQN produces an estimate both of the value of the state and of the relative advantage of each action. By producing these values independently (which together combine to yield Q-values), dueling architecture allows the agent to forgo the learning of action-specific values in states in which its decision-making is largely irrelevant. Finally, we use n-step learning [START_REF] Richard S Sutton | Learning to predict by the methods of temporal differences[END_REF], which helps to reduce error in learned Q-values. With n-step learning, the rewards r and subsequent states s stored in an agent's memories are modified: rather than using the state encountered one step into the future from s (s ), the subsequent state stored in the memory is that encountered n-steps into the future (s (n) ). Similarly, the reward r is replaced by the (properly discounted) sum of the next n rewards, i.e., those accumulated between s and s (n) .

The process of choosing which deep RL extensions to implement and values for associated hyperparameters is not unlike traditional heuristic approaches in transportation optimization. While simple heuristics may suffice in simpler problems (see, e.g., [START_REF] Clarke | Scheduling of vehicles from a central depot to a number of delivery points[END_REF], more complex problems often demand more complex (meta)heuristics specifically tuned for a particular application (see, e.g., [START_REF] Gendreau | Metaheuristics for the capacitated VRP[END_REF]. Analogously, off-the-shelf deep RL may be successful in simpler problems (e.g., [START_REF] Karpathy | Deep reinforcement learning: Pong from pixels[END_REF]), but success in more complex problems requires enhancements (e.g., [START_REF] Hessel | Rainbow: Combining improvements in deep reinforcement learning[END_REF] and is dependent on hyperparameter values [START_REF] Henderson | Deep reinforcement learning that matters[END_REF]. The suite of deep RL extensions adopted here and our selection of hyperparameter values (described in §B) are guided by standard values, where available, and ultimately chosen empirically over the course of the work.

Dart.

Our first proposed agent, Dart uses a combination of deep Q-learning and optimization-based logic to choose an action a = (a r , (a v ) v∈V ) from state s = (s t , s r , s V ).

Assigning vehicles to requests. The action a r pairing a vehicle with the new request employs a deep Q-network. We denote by A Dart = V ∪ {∅} the action space for Dart's DQN. The DQN takes as input the concatenation of a subset of features from the state s which we represent by x Dart = x t ⊕x r ⊕x V ("⊕" is the concatenation operator). These components are defined as follows:

x t System time : the concatenation of the relative time elapsed t/T and a one-hot vector indicating the day of the week d (e.g., for zero-indexed d with d = 0 corresponding to Monday, d = 6 corresponding to Sunday, and d currently equal to Thursday (d = 3), the vector (0, 0, 0, 1, 0, 0, 0)).

x r Request information : the concatenation of a binary indicator for whether there is a new request 1 sr =∅ ; a one-hot vector indicating the location of the request's origin; a one-hot vector indicating the request's destination; and for each vehicle v, the distance v would have to travel to reach the request's origin (scaled by the maximum such distance so values are in [0, 1] (ineligible vehicles are given value 1)).

x V Vehicle information : the concatenation of

x v for all vehicles v ∈ V (x V = x 1 ⊕ • • • ⊕ x V )
, where the vehicle-specific x v is itself the concatenation of the time at which its last non-preemptable job ends (scaled by 1/T ), the charge with which it will finish its last non-preemptable job (scaled by 1/Q), and a one-hot vector indicating its current location.

One-hot vectors in x Dart that indicate location rely on a discretization of the fleet's operating region, as is common in other dynamic ridehail problems in the literature (e.g., [START_REF] Al-Kanj | Approximate dynamic programming for planning a ride-sharing system using autonomous fleets of electric vehicles[END_REF][START_REF] Holler | Deep reinforcement learning for multi-driver vehicle dispatching and repositioning problem[END_REF]). We denote the set of discrete locations (taxi zones (TZs)) constituting the region by L.

x Dart is passed to the agent's DQN to produce Q-value predictions. It then uses an -greedy policy as described in §4.1.1 to choose an a r ∈ A Dart (infeasible vehicles are ignored). A schematic of Dart's DQN is shown at left in Figure 1. RNR Actions. For RNR actions, whenever a request has been missed (s r = ∅ ∧ a r = ∅), Dart repositions a stationary vehicle to the CS nearest the origin of the missed request, choosing the vehicle that is closest to this CS. Let c * r be the CS nearest the origin of the request; V ⊆ V be the subset of the vehicles that are either idling or charging at a CS (j

(1) m ∈ {0, 1}); f t (s v , s r ) be the time for vehicle v to reach the origin of the request; and c * v be the CS nearest vehicle v. Then Dart's setting of RNR actions can be stated as

a v =          c * r s r = ∅ ∧ a r = ∅ ∧ v = arg min v∈ V f t (s v , s r ) ∅ j (1) m = ∅ c * v otherwise. (6)
In equation ( 6), the first case specifies the repositioning of the nearest eligible vehicle to the CS nearest the origin of a missed request. The second case specifies the NOOP action for all vehicles for which it is feasible (i.e., those with a valid current job), and the third case specifies that the remaining vehicles (which do not have a valid current job) are assigned to reposition to the nearest CS.

Drafter.

From a state s, the Drafter agent uses a DQN to choose a vehicle to serve new requests a r and to provide RNR instructions a v for each vehicle v ∈ V. Whereas the number of unique actions under the control of Dart's DQN is V + 1, for Drafter it is (V + 1) × (C + 1) V . For non-trivial fleet sizes V , this is intractably large. In response, we employ a multi-agent reinforcement learning (MARL) framework which avoids this intractability by making separate, de-centralized Q-value predictions for each vehicle. This reduces the number of actions under the control of Drafter's DQN to C + 2, corresponding to the vehicle-specific actions of relocating to each station c ∈ C, serving the request, and doing nothing. We further reduce the number of actions by using the discretization into TZs L described in §4.1.3, yielding the action space A Drafter = {serve, ∅} ∪ L for Drafter's DQN. These actions correspond respectively to serving the request, doing nothing, and relocating to each TZ λ ∈ L. For vehicle v, we define its DQN input by

x v Drafter = (x t , x r , x v , x V ),
-value predictions Q(x v
Drafter , a) for a ∈ A Drafter . These predictions are collected for all vehicles and used to make a centralized decision. A schematic of Drafter's DQN is shown at right in Figure 1.

DQN and attention mechanism. Let us consider the prediction of Q-values for a vehicle v . In the example in Figure 1, v = v 1 . We now also incorporate into the DQN an attention mechanism [START_REF] Mnih | Recurrent models of visual attention[END_REF] to improve the agent's ability to distinguish the most relevant vehicles in the current state.

We expand on the attention mechanism used in [START_REF] Holler | Deep reinforcement learning for multi-driver vehicle dispatching and repositioning problem[END_REF] by incorporating information about the current request, which is likely to influence vehicles' relevancy. Details of our attention mechanism can be found in the appendix, §B. The attention is used to provide an alternative representation (an embedding) of each vehicle g v ∈ R l and the request h ∈ R m , as well as a description of the fleet C F ∈ R n known as the fleet context (here l = n = 128, m = 64; see §B). These components are used to form the

vector C v = C F ⊕ g v ⊕ h ⊕ x t
which is fed to an inner DQN. This inner DQN, which has a structure

similar to Dart's DQN, outputs Q-values Q(x v
Drafter , a) for a ∈ A Drafter . The process is repeated for each v ∈ V, with each vehicle using the same attention mechanism and inner DQN (i.e., all weights are shared).

Drafter is made scalable both through its use of an MARL approach as described above, and also by the attention mechanism. While the MARL approach ensures that the output of the DQN does not depend on the size of the fleet, the attention mechanism ensures the same for the input. More specifically, the attention mechanism makes it possible to predict Q-values (via the inner DQN) using a representation of the fleet C F whose size is not determined by the number of vehicles in the fleet. This structure allows Drafter to be applied to instances of a different size than those on which it was trained.

For example, given a Drafter agent trained to operate a fleet of size V , if a new vehicle is purchased and added to the fleet, or if a vehicle malfunctions and must be temporarily removed, Drafter is capable of continuing to provide service for this modified fleet of size V = V . We assess the scalability of the Drafter agent in our computational experiments, described in §6.

Centralized decision-making. Given Q-value predictions for all vehicles, Drafter's centralized decisionmaking proceeds as follows. Let VDrafter be the set of vehicles for whom the service action has the largest Q-value. To serve the request, we choose the vehicle in VDrafter with the largest such Q-value; this vehicle then receives NOOP for its RNR action. The remaining vehicles perform the RNR action with the largest Q-value, with NOOP prioritized in the event of a tie (ties between repositioning actions are broken arbitrarily). Some consideration must be given to repositioning assignments a v , as the DQN produces outputs in L (TZs), while actions a v take values in C (stations). Given a repositioning instruction to some TZ λ ∈ L for vehicle v, we set a v to the station in λ that is nearest to the vehicle.

Given an action a = (a r , (a v ) v∈V ), define a v Drafter to be the action in Drafter's action space A Drafter assigned to vehicle v:

a v Drafter =    serve a r = v L(a v ) otherwise, (7)
where L(a v ) represents the TZ that contains station a v .

Experience Replay. As described in §4.1.2, Drafter saves state-transition memories (s, a, r, s (n) ) at each step which are later used to train its DQN via prioritized experience replay. Let

x v(n)
Drafter be the DQN input for vehicle v from state s (n) . Because Drafter makes V predictions at each step, our sample of M batch memories leads to an effective sample size of V * M batch , where each memory (s, a, r, s

(n) ) = (x v Drafter , a v Drafter , r, x v(n)
Drafter ) v∈V . Note that the reward r is shared equally among all vehicles during training, with each vehicle receiving the full amount. This was chosen to encourage cooperation among the fleet. Thus, for Drafter, the difference that forms the basis of its loss function (c.f. equation ( 5)) is

r + γ max a ∈A Drafter Q(x v(n) Drafter , a ) -Q(x v
Drafter , a v Drafter ). ( 8)

Benchmark Policies

We implement two policies as benchmarks against which to assess the performance of our Dart and Drafter agents. First, in §4.2.1 we describe the Random policy that chooses actions randomly, effectively serving as a lower bound. Then in §4.2.2 we describe the Reopt policy, a competitive benchmark from the ridehailing literature that leverages reoptimization to assign vehicles to requests and to reposition the vehicles in the fleet (Alonso-Mora et al. 2017).

Random.

The Random policy chooses a vehicle to serve new requests (a r ) uniformly from the eligible vehicles in V ∪ {∅} and chooses repositioning assignments a v uniformly from the eligible locations in C ∪ {∅} for each v ∈ V.

Reopt.

Our Reopt agent employs the reoptimization approach introduced in Alonso-Mora et al. ( 2017

Required model modifications.

The RNR actions from which the Reopt agent may choose are identical to those for the other agents. However, the service action a r now takes a different form. Because the Reopt agent pools requests for T reopt time in between decision epochs, there may now be more than one request to which the agent must respond. Thus, a r is now a set of tuples (v, r), corresponding to matchings between a vehicle v ∈ V ∪ ∅ with a request r ∈ s R , where s R is the set of requests that arrived in the last T reopt time. A rejected request is denoted by the matching (∅, r). Each request r ∈ s R has origin and destination attributes as described in §3, however, we now also include the time at which it was received t r .

Assigning vehicles to requests. To determine how to assign vehicles to requests, Reopt solves a MIP minimizing the total customer waiting time. Let ω v,r be the waiting time of customer r if vehicle v is assigned to serve it. If the current time is s t , the vehicle's state is s v , the request's arrival time is t r , and (as in §3) the time for the vehicle to arrive to the origin of the request from its current position is f t (s v , r); then we have ω v,r = (s t -t r ) + f t (s v , r). We define two sets of binary variables: m v,r , which take value 1 if request r is served by vehicle v; and ψ r , which take value 1 if request r is served by any vehicle (is not rejected). These variables are otherwise 0. Let M be the set of (v, r) matchings that are either energy-or time-infeasible, as defined in §3. The MIP to determine the assignment of vehicles to new requests is then

minimize r∈s R v∈V ω v,r m v,r - r∈s R Bψ r (9) subject to r∈s R m v,r ≤ 1, ∀v ∈ V (10) v∈V m v,r = ψ r , ∀r ∈ s R (11) m v,r = 0, ∀(v, r) ∈ M (12) ψ r , m v,r ∈ {0, 1} (13)
The second term in the objective, equation ( 9), contains the large positive constant B ensuring that the model does not unnecessarily ignore requests. Constraints (10) ensure that each vehicle is assigned to at most one request. Constraints (11) serve both to ensure that at most one vehicle is assigned to serve each request and to fix the ψ r variables, denoting whether requests will be served. Constraints (12) disallow infeasible matchings, and constraints (13) provide variable definitions.

Following the solution to this MIP, we build the set of vehicle-request matchings a r as follows. Any request r for which ψ r = 0 is unserved and receives the matching (∅, r). For the remaining requests (with ψ r = 1), we have matchings (v, r) corresponding to the non-zero m v,r variables.

RNR actions.

Per the approach in Alonso-Mora et al. ( 2017), after assigning vehicles to requests, Reopt then solves another MIP to reposition the vehicles in the fleet. This MIP minimizes the time to reposition idling vehicles so as to be close to the origin of any missed requests. Alonso-Mora et al.

motivate this approach with the assumptions that missed requests may request again, that more requests are likely to occur in the same area where not all requests can be satisfied, and that idling vehicles are in areas with insufficient demand. We note that our Dart agent uses a modified version of this approach for its RNR actions as well.

Let V ⊆ V be the subset of the fleet that is either idling or charging at a station (j

(1) m ∈ {0, 1}) and was not just assigned to serve a new request in the assignment MIP (equations ( 9)-( 13)), and let s R ⊆ s R be the subset of the new requests which were rejected (received a matching (∅, r)). For each request r ∈ s R , define c * r to be the station nearest its origin. Define analogous coefficients ω v,r to be the travel time for vehicle v ∈ V to reach c * r , and let M be the analogous set of energy-infeasible repositioning assignments. We define binary variables m v,r which take value 1 if vehicle v is repositioned to station c * r and are 0 otherwise. Then the MIP to determine fleet repositioning is as follows:

minimize r∈ s R v∈ V ω v,r m v,r (14) subject to r∈ s R v∈ V m v,r = min V , | s R | (15) r∈ s R m v,r ≤ 1, ∀v ∈ V (16) v∈ V m v,r ≤ 1, ∀r ∈ s R (17) m v,r = 0, ∀(v, r) ∈ M (18) m v,r ∈ {0, 1} (19)
Constraint ( 15) ensures that we provide the maximum number of repositioning assignments: either we provide an assignment for all eligible vehicles, or we provide an assignment for all missed requests.

Constraint set ( 16) ensures that each eligible vehicle is given at most one repositioning assignment, and constraint set (17) ensures that each missed request is assigned to be the repositioning destination for at most one vehicle. Constraints (18) disallow infeasible matchings, and constraints (19) provide variable definitions.

Given a solution to this MIP, Reopt makes vehicle assignments a v = c * r for any non-zero variable assignments m v,r . Any vehicle without such an assignment simply receives the NOOP action a v = ∅ unless not allowed, in which case the vehicle is instructed to reposition to its nearest station. Formally,

a v =          c * r m v,r = 1 ∅ j (1) m = ∅ c * v otherwise, (20)
where c * v is the closest station to vehicle v. We offer Reopt agent as a benchmark for a good, scalable dynamic policy. In general, reoptimization approaches offer several potential advantages, foremost among them the ability to consolidate multiple customer requests into a single decision-making epoch. This effectively increases the amount of information with which the fleet operator can make decisions. As such, a good policy that pools requests should be at least as good as a policy that serves requests immediately.

Dual Bounds

Assessing policy quality is hampered by the lack of a strong bound on the value of an optimal policy, a dual bound. Without an absolute performance benchmark it is difficult to know if a policy's performance is "good enough" for practice or if additional research is required. Here, we offer two dual bounds. First is a bound on the value of a policy that serves all requests ( §5.1), and the second is the value of an optimal policy with perfect information, i.e., the performance achieved via a clairvoyant decision maker ( §5.2).

Serve-All Bound.

We first consider the Serve-all (SA) dual bound, which is a bound on the value of a policy that serves all requests. To establish this bound, we assume that the policy is able to serve all requests without incurring any setup travel costs. That is, we can simply sum the value of all observed requests, minus the travel costs incurred to serve them:

C B + (C D -C T ) • d(s r )
, where, as in §3, C B is the base revenue earned when serving a request, C D is the per-distance revenue earned when serving a request, C T is the per-distance travel costs incurred, and d(s r ) is the distance traveled serving the request s r . We know that, given a fleet of sufficient size (and assuming C D ≥ C T and C B ≥ 0), an optimal policy would choose to serve all requests, because policies seek to maximize the sum of rewards, which here are non-negative and incurred only by serving requests. The gap between the SA dual bound and the best policy is a reflection of vehicles' extraneous traveling and the adequacy of fleet size relative to demand and can serve as justification for a ridehailing company to invest (or not) in additional vehicles.

Perfect Information Bound.

In practice, setup and some additional travel costs are unavoidable, and it is likely that not all requests can be feasibly served. As a result, the SA bound is expected to be loose. In an attempt to establish a tighter dual bound, we consider the value of an optimal policy under a perfect information (PI) relaxation.

Under the PI relaxation, the agent is clairvoyant, aware of all uncertainty a priori. In the E-RPC, to have access to PI is to know in advance all details regarding requests: their origins, destinations, and when they will arise. Denote such a set of known requests by R ∈ P, where P is the set of all request sets.

In the absence of uncertainty, we can rewrite the objective function as

max π∈Π E K k=0 C(s k , X π k (s k )) s 0 = E max π∈Π K k=0 C(s k , X π k (s k )) s 0 . ( 21
)
Notice that the perfect information problem (right-hand side of equation ( 21)) can be solved with the aid of simulation. We may rely on the law of large numbers -drawing random realizations of uncertainty (request sets R ∈ P), solving the inner maximization for each, and computing a sample averageto achieve an unbiased and consistent estimate of the true objective value. This value is the perfect information bound. It remains to solve the inner maximization.

In the absence of uncertainty that results from having access to PI, the inner maximization can be solved deterministically: with all information known upfront, no information is revealed to an agent during the execution of a policy. As a result, there is no advantage in making decisions dynamically (step by step) rather than statically (making all decisions at time 0). This permits the use of an exact solution via math programming, which we pursue using a Benders-based branch-and-cut algorithm in which at each integer node of the branch-and-bound tree of the master problem, the solution is sent to the subproblem for the generation of Benders cuts. Here, the master problem is responsible for assigning vehicles to requests in a time-feasible manner, and the subproblem is responsible for ensuring the energy feasibility of these assignments. Additionally, the master problem produces an estimate of the total costs incurred through a particular assignment, and the subproblem refines this cost estimate. The use of the Benders-based decomposition enables the solution of larger PI problems than would otherwise be feasible. We discuss the master problem in more detail in §5.2.1, the subproblem and the generation of cuts in §5.2.2, and comment on the bound's tractability in §5.2.3.

Master problem.

The master problem, responsible for time-feasible assignments of customer requests to vehicles and providing an estimate of the total profit earned, is the MIP defined by equations ( 22)-( 28). In it, requests are represented as nodes in a directed graph G. Request nodes i and j are connected by a directed arc (i, j) when a vehicle can feasibly serve request j after request i (ignoring energy requirements). The graph G also contains a dummy node for each vehicle, representing the location from which it initially departs. These dummy nodes are connected to request nodes for which the initial assignment of vehicles to requests is time-feasible. The problem involves choosing arcs in G, starting from vehicles' dummy nodes, that form (non-overlapping) paths for the vehicles which indicate the sequence of requests that vehicles will serve. If a request i is a member of some vehicle's path, it contributes c i to the objective function, the revenue that its service generates. Our objective also includes the travel costs incurred along the paths that the vehicles travel in serving their assigned requests.

In the master problem, R is the set of all requests (known a priori given PI), V is the set of vehicles, is the time at which request i begins requesting service, w * is the maximum amount of time a customer may wait between when they submit their request and when a vehicle arrives, t p i (d p i ) is the travel time (distance) between the origin and destination of request i, and t s ij (d s ij ) is the travel time (distance) between the destination of request i and the origin of request j. For vehicles, t p v is equal to the earliest time at which they can depart from their initial locations, and t s vi (d s vi ) is equal to the travel (distance) time between their initial locations and the origin of request i. We formally define the master problem as maximize

c
i∈R c i h i -C T   v∈V i∈R d s vi y vi + i∈R j∈R\{i} d s ij x ij + i∈R d p i h i   -θ m (22) subject to v∈V y vi + j∈R\{i} x ji ≥ h i , ∀i ∈ R (23) j∈R\{i} x ij ≤ h i , ∀i ∈ R (24) j∈R y vj ≤ 1, ∀v ∈ V (25) z i ≥ t r i + (t p v + t s vi -t r i )y vi , ∀i ∈ R, ∀v ∈ V (26) z i -z j ≥ t r i -t r j -w * + (t p j + t s ji -t r i + t r j + w * )x ji , ∀i, j ∈ R (i = j) (27) h i , x ij , y vi ∈ {0, 1}; t r i ≤ z i ≤ t r i + w * ; θ m ≥ 0 (28)
The objective ( 22) maximizes profit: its first term captures the revenue earned, while the remaining terms account for costs. In the objective, the first two terms in parentheses capture the distance the vehicles travel in setting up for (traveling between) requests, and the third term in parentheses captures the distance traveled by the vehicles while serving the requests. In its last term, the objective also includes the continuous variable θ m . This variable is controlled by optimality cuts generated in the subproblem, effectively serving to correct the master problem's underestimation of travel costs. While the master problem's objective accounts for the minimum incurred travel costs (those incurred by traveling request sequences directly), there will likely be additional costs incurred as vehicles travel to and from stations.

These station visits are required both for vehicles to restore their charge and to idle between requests, since they are not allowed to do so at request locations. Thus, intuitively, θ m represents the costs incurred during these required station detours.

While θ m is ultimately controlled by the subproblem, we can facilitate the solution of the PI problem by improving the master problem's estimation of these costs. To do so, we consider the minimum required detours between pairs of requests. For requests i and j, let k be the station requiring the minimum detour between i's destination and j's origin, and let t d ij (d d ij ) be the time (distance) required to travel from the destination of request i to station k to the origin of request j. Then we define the minimum detour

distances between requests ij =    d d ij t r i + w * + t p i + t d ij ≤ t r j 0 otherwise, ( 29
)
and then apply the following condition on θ m :

θ m ≥ i∈R j∈R\{i} C T ij x ij . ( 30
)
In equation ( 29) we specify that if there is sufficient time for a vehicle to perform a detour between requests i and j then it must do so, and in equation ( 30) we account for these additional travel costs by raising the lower bound on θ m .

For the remainder of the master problem, equation ( 23) manages the binary assignment variable h i , requiring that it be included in some vehicle's path to take value 1. Similarly, equation ( 24) manages the variables for the outgoing arcs from request i, forcing them to take value 0 if the request has not been assigned to a vehicle. Equation ( 25) ensures that each vehicle has at most one request assigned to be its first. Equation ( 26) sets a lower bound for the time at which vehicles can arrive to their initial requests, and equation ( 27) sets a lower bound for the time at which vehicles' can arrive to subsequent requests.

Finally, equation ( 28) defines variables scopes' and bounds the earliest and latest possible start times for requests z i .

As mentioned, we only connect request nodes i and j via directed arc (i, j) if it is time-feasible to serve request j after request i; that is, if t r i + t p i + t s ij ≤ t r j + w. While energy-feasibility is ultimately ensured by the subproblem, we can again facilitate in the master problem by eliminating additional arcs in G using known energy consumptions to perform stronger feasibility checks. Let ρ be the maximum rate at which vehicles acquire energy when recharging, q p i be the energy required to travel from the origin to the destination of request i, q s ij be the energy required to travel from the destination of request i to the origin of request j, q d i be the energy required to travel from the destination of request i to the nearest charging station, and q o i be the energy required to travel to the origin of request i from its nearest charging station. Then for arc (i, j) to exist, we require that t r j + w -

(t r i + t p i + t s ij ) ≥ 1 ρ max{0, (q p j + q d j -(Q -q o i -q p i ))
}, which states that the maximum down time between i and j (left-hand side) be sufficient to accommodate any recharging that must occur between these requests (right-hand side). We provide similar feasibility checks for the arcs (v, i) connecting vehicle dummy nodes to requests. Specifically, the simpler timefeasible check requires that vehicle v can arrive to request i in time:

t p v + t s vi ≤ t r i + w * . In consideration of energy requirements, we ensure t r i + w * -(t p v + t s vi ) ≥ 1 ρ max{0, q s vi + q p i + q d i -q p v
}, which states that the time for the vehicle to perform any required charging (right-hand side) cannot be greater than the available time before it must arrive to request i. Finally, we force the underlying graph to be acyclic, meaning we prohibit pairs of requests i, j such that (t r i + t p i + t s ij < t r j + w * ) ∧ (t r j + t p j + t s ji < t r i + w * ).

Subproblem.

A solution to the master problem is a sequence of request assignments

r v = (r 1 v , r 2 v , . . .) for each vehicle v ∈ V. r 1
v is taken to be the element in the singleton {j| y vj = 1} ∪ ∅; subsequent entries r i v are similarly elements in singletons {j|x r i-1 v j = 1} ∪ ∅ (r v terminates with the first null element). Given sequences for each vehicle, the subproblem must ensure they are energy feasible. To do so, we use a modified version of frvcpy [START_REF] Kullman | frvcpy: An open-source solver for the fixed route vehicle charging problem[END_REF], which implements the labeling algorithm developed by [START_REF] Froger | Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions[END_REF] to solve the Fixed Route Vehicle Charging Problem (FRVCP) [START_REF] Montoya | The electric vehicle routing problem with nonlinear charging function[END_REF]. The FRVCP entails providing charging instructions (where to charge and to what amount) for an electric vehicle traversing a fixed sequence of customers. The algorithm takes as input a sequence like r v and, if successful, terminates with the minimum duration path through the sequence that includes instructions specifying at which charging stations to recharge and to what amount. When unsuccessful, the labeling algorithm returns the first unreachable node in the sequence. In the original implementation customers did not have time constraints as they do here, where vehicles are required to arrive to requests in the window [t r i , t r i + w * ]. We further discuss the algorithm and our modifications to it to accommodate this difference in the appendix, §C.

Unsuccessful termination of the algorithm for a sequence r v indicates that the sequence cannot be traversed energy-feasibly. To remove it from the search space, we add the following feasibility cut to the master problem:

y v,r 1 v + j -1 i=1 x r i-1 v ,r i v < j , (31)
where j ≤ |r v | is the index of the first unreachable request node in r v to which the algorithm was unable to feasibly extend a label. This cut (31) enforces that not all variables defining the subsequence (r 1 v , . . . , r j v ) be selected. When the algorithm terminates successfully, we add optimality cuts that correct the master problem's estimation of the costs incurred in serving the sequence r v . Specifically, let C(r v ) represent the master problem's estimation of the costs incurred by traveling sequence r v ,

C(r v ) = C T   d s v,r 1 v + |rv|-1 i=1 d s r i v ,r i+1 v + |rv| i=1 d p i   , ( 32
)
and let C * (r v ) represent the actual total cost of traveling sequence r v , as determined by the solution of the labeling algorithm. Then we add optimality cuts to the master problem that account for the difference:

θ m ≥ (C * (r v ) -C(r v ))     y v,r 1 v + |rv|-1 i=1 x r i-1 v ,r i v   (|r v | -1)   . ( 33
)
These cuts work by ensuring that if the master problem selects sequence r v , then it must account for its true travel costs by setting

θ m ≥ C * (r v ) -C(r v ).
Otherwise, the right-hand side of equation ( 33) is at most 0, which is redundant given the non-negativity constraint on θ m , equation (28).

Tractability of the PI Bound.

The PI bound is often computationally intractable to obtain. This is because the estimation of the expected value with perfect information entails repeated solutions to the inner maximization of equation (21), a challenging problem despite the absence of uncertainty. Even if the Benders-based method of §5.2.1 and 5.2.2 does not return an optimal solution for a given realization of uncertainty, we may still get a valid bound by using the best (upper) bound produced by the solver (Gurobi v8.1.1). The solver's bound serves as a bound on the value of an optimal policy with PI, and therefore also as a bound on an optimal policy. This mixed bound, effectively combining both the solver's relaxation and an information relaxation, is weaker than a bound based on the information relaxation alone. However, we show in computational experiments that it still provides value.

0 0  0 0 0 4  0 0 0 8  0 0 1 2  0 0 1 6  0 0 2 0  0 0 0 K 1 0 K 2 0 K 3 0 K

Computational Experiments

To test the solution methods proposed in §4, we perform computational experiments modeled after business-day ridehailing operations on the island of Manhattan in New York City. We describe the experimental setup in §6.1, present our results in §6.2, and offer a brief discussion of the results in §6.3.

Experimental Setup

We generate problem instances (equivalently, episodes over which the agents act) using data publicly available for the island of Manhattan in New York City. New York City Taxi & Limousine Commission (2018) provide a dataset consisting of all ridehail, Yellow Taxi, and Green Taxi trips taken in 2018.

We filter the data to only those trips that originate and terminate in Manhattan and those that occur on business days (d ∈ {0, 1, 2, 3, 4} = {Mon, Tues, Weds, Thurs, Fri}, excluding public holidays). The average daily profile for these data is shown in Figure 2. Based on this profile, we set the episode length T to 24 hours, with episodes beginning and ending at 3:00 am, as this time corresponds to a natural lull in demand from the previous day and gives agents time to perform proactive recharging before the morning demand begins. Data for each trip includes the request's pickup time as well as the location of its origin and destination. Requests' origins and destinations are given by their corresponding taxi zones, an official division of New York City provided by the city government (NYC OpenData 2019) that roughly divides the city into neighborhoods. We use this as the basis for our geographical discretization L as described in §4, resulting in |L| = 61 TZs for Manhattan (see Figure 3). Coordinates ((o x , o y ), (d x , d y ))

for requests' exact origins and destinations are drawn randomly from inside their corresponding TZs.

We fix the set of stations C to all CSs currently available or under construction in Manhattan at the time of writing, as listed by National Renewable Energy Laboratory (2019), yielding a set of |C| = 302 CSs (blue marks in left map of Figure 3). We assume that all CSs dispense energy at a constant rate of 72kW, equal to that of a Tesla urban supercharger [START_REF] Tesla | Supercharging cities[END_REF]. Vehicles' batteries have similar traits to that of a mid-range Tesla Model 3, with a capacity of 62 kWh and an energy consumption of 0.15 kWh/km. Further, we assume vehicles travel at a speed of approximately 13 km/hr (8 mi/hr), incur 2.

Vehicles' initial locations are determined by drawing a TZ randomly according to the distribution of drop-off locations during the final hour of the previous day's operation (2:00-3:00am). See right map in Figure 3. We then choose a charging station uniformly from within the TZ (TZs without CSs are excluded). Vehicles' initial charges are drawn uniformly from [0, Q]. To randomly generate a set of R requests for an instance, we first sample a business day from 2018 then draw R requests that occurred on that day. We consider a primary set of problem instances with R = 1400 requests and V = 14 vehicles (we will often refer to these instances by their R/V ratio, 1400/14). The number of requests was chosen such that the mean number of requests per hour during the busiest time of day (between 6:00-7:00pm, see Figure 2) is approximately 100. The number of vehicles in this set was then derived from a scaling of the ratio R /V , where R = 449, 121 is the total number of trip requests (taxi and ridehail) served on an average business day in Manhattan in 2018, and V = 4, 400 is an approximation of the number of simultaneously active Yellow Taxis in Manhattan at any given time in 2018 (see data aggregations in, e.g., [START_REF] Schneider | Taxi and ridehailing usage in new york city[END_REF]. Experiments on our 1400/14 instances include results for all agents as well as the SA and PI bounds. The agents are evaluated over a set of 200 episodes, while the bounds -given the high computational demand for the PI bound -are established using an average over 30 episodes. Prior to evaluation, the Dart and Drafter agents are first trained on a separate set of 750 episodes. We note that the PI bound cannot be solved to optimality for these instances, so the values reported correspond to the mixed version of the bound as described in §5.2.3.

In addition to the 1400/14 instances, we also consider instances two, five, and ten times larger (2800/28, 7000/70, and 14000/140) to assess Drafter's ability to scale and generalize. That is, we

Results

We begin with a comparison of our proposed dual bounds in §6.2.1. We then describe agents' performance on the instance sets, first discussing the results on our primary 1400/14 instances in §6.2.2, followed by scalability tests in §6.2.3.

Comparison of Dual Bounds.

The first proposed dual bound, SA, is simple to compute but may be loose when not all requests can be feasibly served. In contrast, the PI bound promises to be tighter, but it is significantly more challenging to compute. Here, we aim to quantify the improvement in the bound afforded by the additional computation for the PI bound.

Intuitively, with a larger fleet size V , more requests can be served. At some V , a policy with PI should be able to serve all requests, so the PI and SA bounds should converge. Conversely, with decreasing fleet size, even with PI, it should become impossible to serve all requests, so the bounds will diverge. We test this intuition in an experiment comparing the value of these two bounds as a function of fleet size. The results are summarized in Figure 4. We begin with instances of size 1400/14, for which (as shown in §6.2.2) the gap between the PI and SA bounds is large. We then increment the fleet size by 2 (V + = 2), and resolve 15 episodes of the 1400/V instances. We find that the results confirm intuition -the gap between the bounds decreases exponentially with increasing fleet size, reaching near equivalence (2% , where SA and P I are (upper bounds on) the profit earned by a policy that serves all requests and an optimal policy with perfect information, respectively.

gap between the bounds) at a fleet size of 38. Because the SA bound does not include the travel costs incurred outside of serving requests, the gap between the SA and PI bounds will generally be greater than zero. We note that the PI values here reflect the mixed PI bound discussed in §5.2.3, implying that the gaps may actually be larger than these results suggest. only 41 episodes. Both agents' objective performance is stable after 250 episodes. In Figure 6 we compare agents' performance on the 30 evaluation episodes for which the PI and SA dual bounds are available.

Primary

We find that the Drafter agent is the best performing with a mean daily profit of $10,898, although there remains a large gap between this policy and the PI dual bound, and an even larger gap between the PI and SA dual bounds (as expected from the experiments in §6.2.1). We note that the reported PI bound is a mixed bound (see §5.2.3), as we are not able to solve any of the 30 episodes to optimality.

After Drafter, Dart is the second-best performing agent, earning a mean daily profit of $9,627. Dart's performance is not significantly different from Reopt, which has a mean profit of $9,067. On this set of 30 instances, Drafter outperforms Reopt by 20.2%.

Scalability Tests.

After training on the 1400/14 instances, we then apply Drafter directly to instances two, five and ten times larger. With the primary instances of size 1400/14 being the basis with an Instance Scale of 1, we refer to these larger instances as having Instance Scales of 2, 5, and 10, which respectively correspond I n s t a n c e S c a l e 1 2 5 1 0 $ 0 $ 4 0 , 0 0 0 $ 8 0 , 0 0 0 $ 1 2 0 , 0 0 0 $ 1 6 0 , 0 0 0 $ 1 0 , 9 3 7 $ 6 , 7 9 4 $ 9 , 2 5 0 $ 1 6 , 3 5 3 $ 2 3 , 7 5 4 $ 2 7 , 1 8 7 $ 4 6 , 3 4 1 $ 7 4 , 3 1 3 $ 8 0 , 3 4 5 $ 1 6 9 , 3 9 1 $ 1 6 6 , 5 4 0 $ 9 9 , 2 3 2 to V /R ratios of 2800/28, 7000/70, and 14000/140 (all other instance parameters remain the same). Across all scales, Drafter is the best performing agent. Its advantage over Reopt is largest in the 1400/14 instances, with an objective 18.2% better on average over the 200 evaluation episodes. This edge over Reopt decreases with increasing instance scale, to 14.5% for the 2800/28 instances, 8.1% for the 7000/70 instances, and 1.7% in the 14000/140 instances. This relationship is shown in Figures 7 and8.

We provide further comparison between the agents in Figure 9 which shows three metrics of interest for a fleet operator: as measures of customer service, we consider average customer waiting time and number of requests served; and as a measure of efficiency, we consider the proportion of productive travel (the percentage of the total distance traveled by the fleet with a customer on board). We find that Drafter serves the greatest percentage of customer requests across all instances sizes, serving 44% of requests in the 1400/14 instances (compared to 34% for Reopt), 54% in the 2800/28 instances (44% for Reopt), and 66% in the 14000/140 instances (61% for Reopt). Although serving fewer requests, Reopt does achieve the lowest waiting time for the customers that it does serve. This is true across all instance scales. Reopt serves customers 10 s faster than Drafter in the 1400/14 instances, 15.6 s faster in the 2800/28 instances, 23.9 s faster in the 7000/70 instances, and 27.2 s faster in the 14000/140 instances.

Lastly, we observe that Reopt also has a greater proportion of productive travel than Drafter, achieving an average of 74% across instance scales, compared to an average of 50% for Drafter.

Discussion

While often in dynamic optimization no dual bound is available against which to compare policy performance, we offer two here. Although the gaps from these bounds to our agents are large, the results still serve to illustrate that even a loose bound has utility. For example, comparative analysis of the PI and SA bounds suggests that access to perfect information is of significant value in the E-RPC: for instances with a V/R ratio of 1400/38 and greater, the bounds are nearly equivalent, indicating that an optimal policy with PI is consistently able to serve all requests.

Our computational experiments primarily set out to compare the Reopt and Drafter agents. In the experiments posed here, Drafter is the apparent winner as it consistently achieves both the best objective values and the greatest percent of customer requests served. These are arguably the most important criteria to an operator of a ridehail fleet. That Drafter consistently serves more requests, when taken alongside its higher waiting times (207 s on average, compared to 187 s for Reopt), suggests that Drafter is able to position the fleet so as to better cover the demand. Notably, Drafter requires no prior knowledge or assumptions about the shape of this demand to learn to do so -in the language of reinforcement learning, it is model-free. Rather than relying on, e.g., historical data or domain knowledge regarding parameters describing the demand's spatial and temporal distributions, Drafter garners sufficient working knowledge of the demand during its training to determine which actions best allow it to serve future requests and ultimately achieve greater objective values. Being model-free also implies that Drafter is flexible to various relationships between actions and rewards, because this relationship is learned by the agent.

That is, while we trained and evaluated Drafter on the reward function defined by equation ( 2), we could have equally used, e.g., a deterministic reward function or one which incorporated additional revenue or cost metrics. Although displaying inferior performance than Drafter and lacking its scalability, Dart is also model-free and therefore enjoys these same benefits. Drafter's scalability should be encouraging for operators of ridehail companies, as it suggests robustness to changes in problem instances. That is, in the event that demand is slow on a particular day or one or more vehicles are unavailable (e.g., due to repairs), Drafter should still provide reliable service.

We note the encroaching objective performance of Reopt with increasing Instance Scales relative to Drafter, with Drafter's advantage shrinking from 18.2% in the 1400/14 instances to 1.7% in the 14000/140 instances. This result is not surprising. First, Drafter is acting in an environment that is increasingly different from the one in which it was trained. Additionally, with more requests pooled in a single decision-making epoch, Reopt is armed with increasing information with which to make decisions. This ability to wait-and-see is an innate advantage possessed by reoptimization-style agents. Future research should investigate these two points in more detail. For example, for the former, while we lacked the computational resources to do so here, it would be interesting to compare the performance of a scaled Drafter agent (like the one used here) against a Drafter agent that was trained directly on instances of the larger size. This would answer the question as to how much of Drafter's relative decline was due to the difference in its evaluation and training environments, rather than Reopt simply performing better at scale. In the event that, under this comparison, the gap between Drafter and Reopt continues to be smaller for larger instances, then it would suggest that Reopt-style agents may simply have an advantage at larger instance scales, due to their ability to more completely observe demand before making decisions.

Regardless, it would be a worthy endeavor to create an MDP problem model that would accommodate a deep-RL agent that could similarly pool requests for some amount of time before making a decision.

Lastly, we comment on the proportion of productive travel. This metric is primarily of interest to cities, as they aim to reduce congestion on roadways. Our results suggest that fleet operation costs alone may not be ample motivation for ridehail operators to minimize nonproductive travel: in the presence of realistic revenues and prices, Drafter found that it was still in its financial interest to pursue nonproductive vehicle movements (in order to serve future requests). To combat such behavior, cities may wish to implement congestion pricing (see, e.g., the review in [START_REF] Gu | Congestion pricing practices and public acceptance: A review of evidence[END_REF]. Future research may investigate how learned agent behavior varies under different pricing schemes, as one would expect that nonproductive travel would decrease with increased congestion pricing.

Concluding Remarks

We considered the E-RPC, the problem faced by an operator of a ridehail service with a fleet composed of centrally-controlled electric vehicles. To solve the E-RPC, we developed two policies, Dart and Drafter, derived with deep reinforcement learning. To serve as a comparison, we consider a reoptimization policy from the ridehailing literature, as well as a randomly-acting policy that serves as a lower bound. We develop two dual bounds on the value of an optimal policy, including the value of an optimal policy with perfect information. To establish this bound, we decompose a relaxed version of the E-RPC into time-and energy-feasibility subproblems, and solve them via a Benders-like decomposition. We offer an analysis of when this more complex dual bound offers value beyond that of a simpler proposed dual bound.

We perform computational experiments on instances derived from real world data for ridehail operations in New York City in 2018. Across instances of varying scales, we consistently find the deep RL-based Drafter agent to be the best performing. On instance scales for which it was specifically trained, it achieved an objective 18.2% better than the reoptimization policy. We further show that Drafter is scalable, finding that, on instances two, five, and ten times larger than any on which it was trained, it outperforms other policies by 14.5%, 8.1%, and 1.7%, respectively. These results ultimately suggest there are opportunities for deep reinforcement learning in solving problems like the E-RPC. By more efficiently utilizing finite resources, these methods have the potential to promote greater sustainability in the domain of transportation and logistics. ** For the inner DQN (see Figure 1).

to produce joint embeddings j v = g v ⊕ h. The j v s and g v s are then used to perform attention over the vehicles, creating a fleet context vector C F ∈ R 128 via (34) where α v = σ(w • tanh(W • j v )) is a scalar weighting vehicle v, σ is the sigmoid activation function, w is a trainable vector of weights, and W is a trainable matrix of weights (the summation in equation ( 34) is performed element-wise). This attention mechanism is similar to the one used to produce the fleet context in [START_REF] Holler | Deep reinforcement learning for multi-driver vehicle dispatching and repositioning problem[END_REF], with the notable difference that here we also incorporate the request.

C F = v∈V α v g v ,
As the request s r is likely to influence which vehicles are relevant in a given state, its inclusion in the attention mechanism should yield a more descriptive fleet context C F . The fleet context vector is then used in the production of Q-values for each vehicle as described in §4.1.4.

C Froger et al. (2019) FRVCP Labeling Algorithm

We provide here additional details on the labeling algorithm from [START_REF] Froger | Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions[END_REF] and our modifications to accommodate time constraints on the customers. We will refer to the sequence of requests to be served by vehicle v, as determined by the master problem ( §5.2), by r v = (r 1 v , r 2 v , . . .).

C.1 Algorithm Overview

To find the optimal recharging instructions given a request sequence r v , the FRVCP is reformulated as a resource-constrained shortest path problem. The algorithm then works by setting labels at nodes on a graph G v (see example in Figure 10) that reflects the vehicle's assigned request sequence r v and possible charging station visits. Labels are defined by state-of-charge (SoC) functions. SoC functions are piecewise-linear functions comprised of supporting points z = (z t , z q ) that describe a state of departure from a node in G v in terms of time z t and battery level z q . See Figure 11

C.2 Algorithm Modifications

We modify the algorithm to accommodate time constraints for the requests in r v , which are not considered in the original implementation. We assume that the vehicle is eligible to depart its initial location, denoted

  1) The current time s t = (t, d) is the time of day in seconds t and the day of week d. If the epoch was triggered by a new request, then s r = ((o x , o y ), (d x , d y )) consists of the Cartesian coordinates for the request's origin and destination, otherwise s r = ∅. The vector s V = (s v ) v∈V describes the state of each vehicle in the fleet. For a vehicle v, s v = (x, y, q, j

Figure 1 :

 1 Figure1: Schematics of the Dart and Drafter agents in the case of three vehicles and three TZs (V = 3, L = 3). Elements are concatenated at intersections marked with ⊕. The Drafter schematic shows the case where Q-values are being predicted for vehicle 1 (in yellow). Note: in practice, a single forward pass with x Drafter can be used to generate Q-values for all vehicles. We depict the process for a single vehicle here for the sake of clarity.

  ), solving two mixed integer programs (MIPs) in every epoch to inform its decisions. This agent is inherently different from the other three proposed in this section. Whereas decision epochs for Dart, Drafter, and Random are triggered by the arrival and completion of requests, the Reopt agent is afforded a decision epoch at regular intervals (governed by the parameter T reopt ; e.g., every 30 seconds). This difference requires modifications to the problem model defined in §3.

Figure 2 :

 2 Figure 2: Mean number of requests by hour in Manhattan on a business day in 2018. The dashed vertical line indicates episodes' 03:00 start time.

Figure 3

 3 Figure 3: (Left) The island of Manhattan divided into taxi zones with charging station locations shown in blue. (Right) Distribution of requests' desintations by taxi zone during episodes' last hour (02:00-03:00).

  is in contrast to Drafter, for which the size of its DQN output (A Drafter ) is indifferent to the size of the fleet. Details on the hyperparameters used in the training of the Dart and Drafter agents for all instance size classes are provided in §B. We use a reoptimization period of T reopt = 30 seconds for the Reopt agent.

Figure 4 :

 4 Figure 4: The mean percent difference of the SA bound relative to the PI bound over 15 episodes of an instance with 1400 requests for varying fleet sizes. Note: computed as SA-P I P I

  1400/14 Instance Set. The Dart and Drafter training curves, showing their increasing objective performance over the 750 training episodes, are provided in Figure 5. Dashed horizontal lines in the figure indicate the mean objective performance of Reopt and Random, and thin vertical lines indicate the points at which the Dart and Drafter agents surpass the mean performance of the Reopt agent. We see that learning happens quickly for both agents, with Dart surpassing Reopt after 96 training episodes and Drafter doing so after

Figure 5 :Figure 6 :

 56 Figure 5: Training curves for the Dart and Drafter agents, showing two-week performance averages (the average objective over an episode and the previous 13 episodes). Dashed horizontal lines depict mean objective values for the Random and Reopt agents. Vertical lines indicate where Dart and Drafter surpass Reopt's mean objective achievement.

Figure 7 :

 7 Figure 7: Agents' objective performance over 200 evaluation episodes of various instance scales.

Figure 8 :Figure 9 :

 89 Figure 8: The improvement in objective offered by Drafter over Reopt over 200 evaluation episodes of instances of varying scales.

  for an example.During the algorithm's execution, labels are extended along nodes in G v . When extending labels, SoC functions are shifted by the travel time and energy between nodes, and supporting points resulting in infeasible (negative) charges are pruned. When extending a label to a charging station node, we create new supporting points that correspond to the breakpoints in the charging curve at that station -energy levels at which the charging rate changes. (Note that here, we assume linear charging until the vehicle reaches full battery, at which point it begins idling. This breakpoint corresponds to z 2 in the left graph of Figure11.) We continue to extend labels along nodes in G v until either the destination node r |rv| v is reached or there are no feasible label extensions. If the destination node is reached, the algorithm returns the earliest arrival time to that node based on the label's SoC function and the sequence is deemed to be energy feasible; if the destination node cannot be reached, the sequence is deemed energy-infeasible and the algorithm returns the first request node to which it could not extend a label. Bounds on energy and time are established in pre-processing and are used alongside dominance rules during the algorithm's execution in order to improve its efficiency. For complete details on the algorithm, we refer the reader to[START_REF] Froger | Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions[END_REF].

Table 1 :

 1 Eligible actions for an EV v.

	Action	Eligibility conditions
	Serve request	Request exists, no pending service (j	(2) m < 3), energy feasible, time feasible
	Reposition to a v	No active or pending service (j	(1) m < 3), energy feasible
	NOOP	Always, unless just finished serving and no pending service (j	(1)

  where components are as defined for Dart in §4.1.3 and the redundant x v is included just to indicate the vehicle for which we are generating Q-values. With vehicle input x v Drafter , the DQN makes Q

  i is the revenue earned by serving request i, h i is a binary variable taking value 1 if request i is assigned to any vehicle, y vi is a binary variable taking value 1 if job i is the first request assigned to vehicle v, x ij is a binary variable taking value 1 if a vehicle is assigned serve request j immediately after request i, z i is a continuous non-negative variable equal to the time at which a vehicle arrives to pick up request i, t r i

Table 2 :

 2 Instance parameters. Drafter agent directly on 200 instances of each size without any additional training on these instances -it simply uses its DQN as trained on the 1400/14 instances. We compare the Drafter agent to the Random and Reopt agents. Dart is absent from this analysis as its scalability is inherently handicapped, with its DQN's output (A Dart ) dependent on the number of vehicles in the instance. This

	Parameter	Value
	Episode length T	24 hrs
	Episode start time	3:00 am
	Number of Taxi Zones |L|	61
	Number of charging stations |C|	302
	CS charging rate	72 kW
	Vehicle battery capacty	62 kWh
	Vehicle energy consumption	0.15 kWh/km
	Vehicle speed	13 km/hr
	Travel costs C T	$0.53/km
	Base fare C B	$10.75
	Per-distance fare C D	$4.02/km
	Max customer waiting time w *	5 minutes
	evaluate the

Table 3 :

 3 Agents' hyperparameters.

	Parameter

* With the exception of the layers in the attention mechanism as described in §B.

Acknowledgements

Nicholas Kullman is grateful for support from the Société des Professeurs Français et Francophones d'Amérique. Justin Goodson wishes to express appreciation for the support from the Center for Supply Chain Excellence at the Richard A. Chaifetz School of Business. Martin Cousineau and Jorge Mendoza would like to thank HEC Montréal and the Institute for Data Valorization (IVADO) for funding that contributed to this project; Jorge Mendoza is additionally grateful for funding from HEC Montréal's Professorship on Clean Transportation Analytics. This research was also partly funded by the French Agence Nationale de la Recherche through project e-VRO (ANR-15-CE22-0005-01).

A Updating Vehicles' Job Descriptions

Upon choosing action a from state s, we immediately update vehicles' job descriptions. We describe this process here. For the following discussion, let the current location of vehicle v be (v x , v y ).

NOOP.

Vehicles receiving the NOOP instruction (a v = ∅) see no change to their existing job descriptions.

Repositioning/Recharging.

Let the location to which the vehicle is instructed to reposition be a v = c with location (c x , c y ). We set the first job's type to repositioning (j (1) m = 2), its origin to the vehicle's current location (j

and its destination to c (j

We then set the second job type to charging (j

(2) m = 0) which begins and ends at c (j

After recharging, the vehicle then idles at the station:

Serving Request.

Let the new request have origin (o x , o y ) and destination (d x , d y ).

No work-in-process. If the vehicle is not already serving a request (j (1) m = 4), then its first job is updated to type preprocess (j

B Agent Details: Hyperparameters & Attention Mechanism

We provide here additional details about the training and implementation of the Dart and Drafter agents. Hyperparameters, chosen based on empirical results, are given in Table 3. The rest of this section describes the attention mechanism used in Drafter's DQN.

The attention mechanism used by the Drafter agent is depicted in Figure 1. We begin by creating an embedding g v of each vehicle's representation x v using a single dense layer called the "vehicle embedder." An embedding of some input is simply an alternative representation of that input. For example, for

, where W a is a 128 × (2 + |L|) matrix of trainable weights, b is a 128-length vector of trainable weights, and f is the activation function (here a rectified linear unit, ReLU ). Similar to vehicle embeddings g v , we create an embedding h ∈ R 64 of the request x r using another single dense layer (the "request embedder"). We then concatenate each vehicle's embedding g v with the request embedding h 0 v , at time t p v with charge q p v . Moving between locations a and b requires energy q s a,b and time t s a,b (if b is a request, the values reflect the time and energy to reach its destination via its origin). For this discussion, additional information about the algorithm beyond the overview in §C.1 may be necessary, for which we refer the reader to the description of Algorithm 3 in §5.3 and Appendix E of [START_REF] Froger | Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions[END_REF].

The first modification serves to include the option of idling at charging stations. We add a point in the charging function at (∞, Q) as shown in Figure 11. This allows the vehicle to idle at a CS after it has fully charged its battery. Second, when extending a label to a request, we prune supporting points at the request node based on the request's time constraints. Specifically, all supporting points that are too early are shifted later in time. This may result in multiple supporting points with the same time but different energy levels, in which case we keep only the supporting point with maximum energy.

Supporting points whose times are too late are eliminated, and a new supporting point is established where the SoC function intersects the end of the customer's time window. These processes are shown in Figure 11. Finally, when extending a label from one request node directly to another, if a supporting point has been shifted later in time by some amount ∆t (like z 1 in Figure 11), then the point incurs a charge penalty ∆q. This reflects the constraint that vehicles may not idle at request nodes, so we assume that the vehicle has continued driving (e.g., "circling the block") during the time ∆t and has thus drained its battery by the amount ∆q. Note that such penalties are not incurred when extending to or from charging station nodes in G v as these nodes have no time constraints. ) as we extend a label to r 1 v , resulting in points z 1 , z 2 , z 3 . (Right) Supporting points must lie within customer r 1 v 's time window w * . Point z 1 is eliminated since it is dominated after this shift (indicated by the "x"), having less charge than the new point z 1 . Point z 3 is eliminated and the new point z 2 is created where the SoC function intersects the end of the time window.

Note that there is no charge penalty incurred here, as the label is being extended from a charging station.