Same-day delivery (SDD) is a type service that enables customers to order and receive goods on the same day. It mimics the immediate product availability of a brick-and-mortar store with the convenience of ordering from electronic devices and home delivery Hausmann et al. (2014) . These services have gained particular attention during the ongoing COVID-19 pandemic. Online retailers and third-party delivery service providers such as Instacart have faced a rapidly increasing demand for deliveries Perez (2020) , Repko (2020) .
An SDD problem considers a fleet of vehicles serving some area, where customers make requests for same-day delivery over the course of a day. The dispatcher decides whether to accept the requests and then dynamically assigns vehicles to complete the delivery. Existing research in SDD focuses on maximizing the utility, which is the total number of expected requests served Chen et al. (2019) , Voccia et al. (2019) , Klapp et al. (2016 Klapp et al. ( , 2018 , . While such an objective can maximize profit for a given day, Chen et al. (2019) shows that the optimal solution often refuses to serve requests that consume most resources, notably driving time, which are generally those that are furthest away from the depot or from other customers. However, in the long run, such a strategy will alienate customers, who will become less likely to request service in the future, reducing the long-term utility. During a pandemic like COVID-19, arXiv:2007.09541v1 [cs. LG] 19 Jul 2020 this unfair system has an especially negative societal impact: customers who do not live in the "right place" do not have an equal chance to receive deliveries from online shopping. For the immuno-compromised and elderly, such a scenario is particularly problematic as these populations are most at risk during in-person shopping.
The industry has been aware of these arising concerns. In 2016, after being accused of excluding some minority neighborhoods from its SDD map, Amazon promised to offer SSD to all urban neighborhoods in the cities that were applicable Howland (2016) . However, no academic research has studied how to achieve fairness among customers from different geographic locations. Particularly, no research considers geographies that are more likely to see rejected service requests, either due to the location being too far away from the dispatch center or too far away from the high-density area. There is also an imperative need to quantify the trade-off between utility and fairness for practitioners to weigh the two considerations when designing a system.
In this paper, we study the SDD problem with the goal of achieving a balance between fairness and utility. We model the problem as a constrained Markov Decision Process in which decisions are made upon receiving a new request. The decision is whether to accept the request and which vehicle to assign it to. We implement deep reinforcement learning to learn the optimal policy. To incorporate fairness, we modify the value function by augmenting the utility with a fairness reward. The fairness considers the difference between the maximum service acceptance rate and the minimum acceptance rate across different regions.
To test the model, we design three customer geographies in which some customers are adversely located, requiring more driving time than others. Results show that our solution effectively trades-off utility (the expected number of served requests) and fairness. While our approach relies on discretizing the service area into a couple of regions and only pursuing fairness across these regions, our analysis shows that our solution exhibits a finer-grained level fairness. In addition, we simulate a scenario to mimic the real-world situation of a pandemic, where there is a dramatic increase in the volume of customer requests while the dispatcher algorithm remains the same. We find that our model is very robust under this sudden systematic pressure and can still obtain fairness at very low cost of utility.
We provide an overview of fairness in machine learning and fairness related work on same-day delivery problems.
Fairness in machine learning has received extended interest in recent years. Research in this area has focused on combating the biases in the decision-making process, caused by bias in the training data or the algorithm. Interested readers can refer to Mehrabi et al. (2019) , Barocas et al. (2019) for more information.
Various definitions of fairness have been proposed in different contexts. For example, demographic parity states that the proportion of each segment of a protected class (e.g., gender) should receive a positive outcome at equal rates. Alternatively, equal opportunity states that each group should get a positive outcome at equal rates, assuming that people in this group qualify for it. The fairness measure in our work is derived from the previous definitions. We require equity in the request acceptance probability, regardless of the locations of the customers.
To achieve fairness, existing works fall into three categories, pre-processing, in-process mechanisms, and post-processing. Pre-processing Zemel et al. (2013) , Calmon et al. (2017) , Madras et al. (2018) , Wang et al. (2019) refers to learning a fair representation of the training data to remove the bias before training a model, and post-processing Hardt et al. (2016) , Lohia et al. (2019) means making posthoc corrections to a biased pre-trained model. Our method here falls into the second category, in-process Berk et al. (2017) . Unlike the previous in-process approaches that build supervised learning models, we incorporate a fairness constraint in a reinforcement learning model, modifying the value function to directly optimize for a fair policy. Our work is related to , which requires that an algorithm never prefers one action over another if the long-term (discounted) reward of choosing the latter action is higher. The paper finds that learning algorithms satisfying fairness must take time exponential in the number of states to achieve non-trivial approximation to the optimal policy. Our work here, instead, focuses on a specific real-world problem and provides a complete solution to achieve a balance between fairness and the original domain-specific goal.
Same-Day delivery falls into the category of dynamic and stochastic routing problems. Reviews of dynamic routing problems can be found in Ulmer et al. (to appeara) . In the domain of same-day delivery, we are not aware of any existing literature that studies fairness. In studying dynamic delivery problems, Soeffker et al. (2017) , Ulmer et al. (2018) and Ulmer et al. (to appearb) consider fairness as an evaluation metric, but do not optimize for it. Our work directly considers fairness in the optimization.
The concept of fairness has been explored in other vehicle routing problems, particularly in ride-sharing systems, where a fleet of vehicles picks up and drops off customers. Lesmana et al. (2019) investigate the fairness on the drivers' side and defines fairness as the minimum profit (utility) of a driver. However, the algorithm proposed in Lesmana et al. (2019) can only improve from an existing assigning mechanism and is, therefore, not an optimized solution. In Nanda et al. (2019) , the authors define fairness as the minimum ratio of the number of matches for a type of requests to the number of arriving requests and then develop an LP-based algorithm that optimizes the profit and fairness. Chen and Wang (2018) consider a (deterministic) last-mile transportation system that consists of passengers of regular-type or special-type. They define two notions of fairness that consider the fare and the order of service for the two types of passengers. Then they solve the problem with optimization techniques.
The problem is related but different from the vehicle routing problems discussed above. In a standard SDD problem, there is one dispatcher and a group of customers; therefore, the fairness needs to be defined at the customers' side. The geographic fairness we define is the first to address the fairness issue in same-day delivery, directly echoing with societal problems that neighborhoods that are financially advantageous or geographically closer to facilities receive more public or private resources, while the vulnerable with a disadvantage of location do not have equal access. The problem is especially timely during the pandemic.
We consider a same-day delivery problem with fairness (SDDF) in some service area Z, where customers can make requests for goods to be delivered from a depot to them within timeδ. To provide the delivery service, a dispatcher manages a fleet of M vehicles V = {v 1 , v 2 , . . . , v M } that operate during [0, t max ] each day. We assume all vehicles must start from the depot at time 0 with no pre-assigned requests and return to the depot by time t max . Upon receiving a request, a dispatcher needs to decide whether to offer service, and if it does, which vehicle to assign this request to. The goal of an intelligent dispatcher algorithm in the existing literature is usually to maximize the total number of accepted requests per day, called utility.
Vehicles perform repeated trips from the depot to a set of customers. For every vehicle, there are two types of routes in this problem. We define the route being undertaken by a vehicle an ongoing route. Each vehicle must complete all deliveries on an ongoing route before it returns to the depot. The dispatcher is not allowed to integrate new customers to ongoing routes. While vehicles are en route, the dispatcher keeps receiving new requests and forming new routes for each vehicle, which we call planned routes. Due to the small size of most delivery items and the relatively low number of packages on most delivery routes Guglielmo (2013) , we assume vehicles are uncapacitated. Thus, the dispatcher only needs to consider route efficiency when forming planned routes. In this paper, we assume planned routes are formed using the insertion heuristic 1 from the literature Azi et al. (2012) , Chen et al. (2019) . A planned route may be updated until the vehicle leaves the depot to execute the route, when a planned route becomes an ongoing route and a new planned route is set to empty.
We describe how a customer's request is processed by the dispatcher.
1. Receiving request: Some customer c k from area Z submits a request to the dispatcher at time t k , where t ∈ [0, t max ], for delivering a package to the customer by the deadline min{t max , t k +δ}. Here we assume the requests are stochastic and dynamic so both the time of the request and the location of the customer are known only when the request is received.
2. Evaluating request: The dispatcher uses the insertion heuristic mentioned above to check which vehicles can feasibly complete the delivery. Here, a vehicle is feasible for this request if it can insert the request to its current planned route while completing all requests on the planned route before their corresponding deadlines. Thus, different requests may cause infeasibility of different vehicles. The infeasibility often happens when the coming customer is located far away from customers already added to the planned route. Therefore, a customer request is deemed eligible for the SDD service if at least one of the vehicles can feasibly serve it. The request is otherwise ineligible. Ineligible requests are automatically denied service and ignored thereafter. Eligible requests, on the other hand, await for future decisions.
3. Assigning request Given an eligible request, the dispatcher needs to determine whether to offer the service and, if so, which vehicle to assign it to. Once a request is assigned to a vehicle, it will be added to the planned route via the insertion heuristic.
The primary source of bias we aim to mitigate in this paper exists in the stage of assigning requests. An eligible request can still be rejected on this stage. This is because the objective of a same-day delivery problem is usually to maximize the total number of accepted requests, and requests that are considered consuming too many resources could hurt the overall objective. For example, if the customer is located far away from other customers, then it will take a lot of time on route to travel to and from. Or if the customer is located far from the depot, it also takes longer to travel to the customer and then return to the depot. In either situation, a utility-driven dispatcher algorithm is encouraged not to offer service to a request from these locations. Therefore, we aim to achieve fairness in service opportunities for customers from different geographic locations. To this end, we partition the service area Z to J regions, i.e., Z = ∪ J j=1 Z j . Our goal is to achieve equity or close the gap in the acceptance probabilities in the partitioned regions.
We first formulate a constrained Markov process and then solve it with a deep Q-learning model.
We present the main elements in the constrained Markov Decision Process (CMDP) for the problem.
• State space S: A state summarizes the information needed to make a decision when receiving a request from a customer c k . The state S k includes time t k at which the request is made, Euclidean distance between the customer and the depot, region the customer is located in, feasibilities of vehicles serving the customer, marginal increase in each vehicle's tour time if the customer is assigned to it, and times at which vehicles will return to the depot from their ongoing tours.
• Action space A: The action A k made at decision point t k reflects whether to offer service to the request c k and, if so, which vehicle will make the delivery. The action space consists of M + 1 actions, i.e., A = {0, 1, · · · , M }, where m ∈ A, ∀m > 0, represents assigning the request to vehicle m and 0 represents not offering service. As introduced, the insertion heuristic first determines if vehicles can feasibly serve request c k . Thus, each action A k is selected from a set of feasible actions feasA k ⊂ A. To define feasA k , we denote the feasibility of vehicle v m serving customer c k as an indicator variable α m,k . The value of α m,k = 1 if vehicle m is feasible for request c k and α m,k = 0 otherwise. Given the feasibilities, a feasibility set feasA k is defined as:
The dispatcher then selects an action A k ∈ feasA k .
• Reward R: Given the state S k at decision point t k , the (immediate) reward of an action A k is 1 if the service if offered, since maximizing the total number of the served requests is the primary goal of the model. Therefore,
After the action A k is made, the dispatcher updates the planned routes for all vehicles using the insertion heuristic and the CMDP proceeds. The CMDP terminates at time t max with all the vehicles back in the depot.
Fairness Constraint To achieve fairness in acceptance rates across different regions, we partition the state space S according to geographic districts. Thus,
where S j represents the state space of requests from region Z j . We seek to learn a policy π that achieves equal service acceptance rates across different regions in the service area. Formally, we constrain the MDP by
where A π (S) represents the action taken for a state S under policy π.
We denote the optimal policy as π * such that it maximizes the total expected reward while satisfying constraint 4. The π * can be expressed by
In the SDDF, decisions now impact immediate utility and fairness evaluated over a certain period in the future, which requires a solution to anticipate the future. To this end, we propose a deep Q-learning (DQL) approach to solve the CMDP. Q-learning is a technique to solve MDPs that learns the expected value of state-action pairs. We relax the constraint into the training objective.
Empirical Fairness Due to the stochasticity and the dynamism of the problem, it is impractical to calculate the exact probabilities introduced in constraint (4). To overcome the issue, our relaxation of the constraint relies on computing the empirical acceptance rate r [d] j for each region Z j over a certain period of T (≥ 1) episodes, where each episode d represents a day. Let S [d] k represent the k th request made in episode d. Starting from any episode d, we can compute the empirical service acceptance rate over the period
where the indicator function 1(·) on requests is 1 if the inside argument is true, and 0 otherwise. Using the definition above, we translate Constraint (4) into the empirical constraint
In this paper, to simplify the computation and make each day an independent episode, we set T = 1, which means we demand the service acceptance to be equal across regions in every episode. Thus the empirical fairness is computed based on every episode. Our model, however, can be easily extended to different values of T .
To include fairness in the training objective, we augment the immediate reward for an action with a non-immediate reward for fairness. For a state S [d] k and the action taken A
[d]
k during day d, the value function can be expressed as
where
The r
[d] max and r [d] min represent the maximum and minimum acceptance rates across regions on day d. In Equation (8), the first term on the right hand side is the reward-to-go, commonly used in utility-driven algorithms. It is the cumulative number of requests accepted from t k to t max , i.e., the future reward. The second term is the reward for fairness. The smaller the difference is between r min (more fair), the larger the second term is, resulting in a higher reward. The coefficient α indicates the extent to which the fairness is considered. Larger α means more emphasis is placed on the fairness than the utility.
We build a neural network to learn the Q-values for the SDDF. The neural network is defined by a set of weights w and denoted as w (n) in the n th training epoch. The input layer takes the state as features. The neural net consists of two hidden layers, each of which consists of 50 neurons. We use ReLU as the activation function to both the input and hidden layers. The output layer consists of M + 1 nodes, where M of them correspond to the acceptance and assignment to each vehicle, and the additional node represents the action of not offering service. We implement an -greedy strategy for selecting actions during training, where exponentially decays from 1 to 0.01 during training.
We apply experience replay introduced in Lin (1993) to overcome the correlations in consecutive states. Before each update of the weights, we randomly sample a batch of (state, action, reward) tuples from the experience memory. Due to the randomness, we drop the superscript d after they are sampled from the experience memory. Let B (n) represent the batch used in the n th training epoch. The neural net is trained by minimizing the loss function
where the summation is performed over the tuples in the batch. The first Q is the computed reward by Equation 8, and the second Q(·, ·|w (n−1) ) represents the value approximated by the neural net after the last update.
Below we describe the generation of customer requests, the vehicle fleet, and the geographic settings where the location of one region is inferior to the other, creating geographic unfairness. In this paper, we consider two or three regions only, but our solution approach allows the number of regions J to be any value.
Requests All customer requests are generated according to a Poisson process, and requests are distributed normally within the regions. Vehicles To explore the effect of resource availability, we consider two different fleet sizes, 3 and 5 vehicles in the fleet. In both cases, we assume vehicle drivers work eight hours. The dispatcher stops receiving requests an hour earlier than t max = 8. We assume that accepted requests must be serviced withinδ = 4 hours. The vehicles travel at a speed of 30km/h. To reflect the effect of road distances and traffic, we transform Euclidean distances to travel times using the method introduced in Boscoe et al. (2012) . Unfair Geographic Settings We describe three geographic settings (see Figure 1 ). In these settings, Region 1 is always the more adverse one. Region 1 and Region 2 are separated by a non-service area, which mimics the river, factories, etc. in the real world. (S1): Region 1 and Region 2 are both represented by rectangles of width d and height 2d. The depot is located in the center of Region 2. Region 1 is located far away with its center 2d away from the depot. The arrival rate of customer requests in both regions are λ 1 = λ 2 = 250.
(S2): The relative distance between Region 1 and Region 2 is the same as in (S1). The depot is located in the middle between the two regions. The arrival rates of customer requests are λ 1 = 100 and λ 2 = 400.
(S3): Region 1 is evenly divided into Region 1a and Region 1b, and have arrival rate λ 1a = 100, λ 1b = 150 and λ 2 = 250. The rest of the setting is the same as in (S1).
In summary, (S1) represents geographic bias where Region 1 is located far away from the depot, (S2) represents population bias where Region 1 is located far away from the majority of customers, and (S3) represents the need for finer-resolution fairness. The three unfair geographies are paired with 3 and 5 vehicles, resulting in 6 scenarios.
We conduct the experiments on a training set of 1500 instances and a testing set of 500 instances. Here, an instance is a set of customer requests (request time and location) for one day. For each geographyfleet combination, we test α ∈ {0, 25, 50, 75, 100, 125, 150, 175, 200, 400, 600 , 800, 1000}. The value α = 0 represents the benchmark policy where the fairness is not considered. Larger α represents more emphasis placed on fairness. We record the utility and the acceptance rates under the ongoing policy every 500 epochs and terminate the training after 450 recordings. After the training terminates, we evaluate the last ten policies on the testing set and calculate the expected utility and acceptance rates.
We quantify the trade-off between fairness and utility in Figure 2 . In each plot, the horizontal axis is ln(r max /r min ), where r max and r min represent the maximum and minimum service acceptance rates of the regions, respectively. The smaller x-value indicates a more fair policy in terms of the service opportunity for regions. The vertical axis represents utility measured by the number of accepted requests. Different colors indicate different α values. Figure 2 shows that, the more vehicles there are, the higher utility. Yet, for both the 3-and 5-vehicle cases, as α increases, the policies become more fair at some cost to the utility. When α is less than about 400, this cost is initially small. After that point, as more emphasis is placed on fairness, the utility experiences a much steeper drop as fairness continues to increase.
Our analysis so far shows our model obtains fairness on a coarse level when we discretize the service area into a few regions. In this section, we evaluate the same model with a more granular fairness measure to test if our solution has benefits beyond the original scope. Figure 3 : Heatmap of acceptance rates for setting S1 with 3 vehicles.
To do this, we further discretize each region into 6 by 12 grids, yielding a total of 72 grids in each region. We then evaluate the acceptance rate for each grid over the course of 500 testing days. Figure 3 presents a heatmap for the acceptance rate for S1, 3 vehicles, and α = 0 and 400. The figure shows that, although the overall acceptance probability is high in the baseline α = 0, the variance across the grids within a region is notably high: customers located closer to the depot has larger acceptance probabilities. This indicates large inequality in customers' opportunities of receiving service. On the other hand, when α = 400, the grids are more homogeneous in the acceptance rates. To quantify the variation, we report the standard deviation of the acceptance rates within each region, when α = 0 and α = 400 and present the results in Figure 4 . Smaller standard deviation represents higher fairness in the region. Heatmaps of other settings are enclosed in the supplementary material.
In all six settings, the standard deviations of service acceptance rate are significantly smaller in for a non-zero α. This indicates that our model can mitigate unfairness at a finer-grained level even when trained at a coarser discretization. One explanation of this effect is that our model learns to weaken the impact of geographic location when processing a request.
As reported in Perez (2020) and Repko (2020) , the need for same-day and faster deliveries has increased rapidly during the COVID-19, flooding the system with a surge of requests. This surge leads to increasing service rejection rates across the country as the resources become more constrained. Motivated by this timely problem, we seek to understand how our policies perform under the stress caused by the surging number of requests. To test this effect, we double the arrival rate in the previous experiments. At the same, we continue using the model trained on 500 customers with α = 0 and 400, to test whether our model is robust to this sudden shock. Figure 5 : Heatmap of acceptance rates for setting S1 with 3 vehicles (1000 requests).
Results demonstrate our model maintains fairness when the volume of requests rapidly increases. Unsurprisingly, we find that the overall utility increases, albeit slightly, due to the higher arrival rate, but the overall acceptance rate for the two regions decreases because we did not increase the available delivery resources. We then investigate whether our model can still maintain fairness across and within the regions. The model with α = 400 shows a smaller difference of 4.2% in the overall acceptance rate between the regions, compared to the benchmark 18.2% (see Figure 5 ). Within each region, our model also shows the ability to maintain fairness on finer-grained grids (see Figure 6 ). We notice the standard deviation of Region 1 slightly exceeds that of Region 2 in S3 with 5 vehicles. However, it is still lower than that in Figure 4 . One explanation is that, when the arrival rate is higher, the benchmark has more requests to choose from without considering fairness, so it distributes even more resources in Region 2. That results in low acceptance rates in all the 72 grids in Region 1.
In this work, we provide a holistic solution to achieve geographic fairness in the same-day delivery problem using reinforcement learning. Our method directly modifies the Q-value in reinforcement learning, incorporating a reward for equal service opportunity across regions. We quantify the trade-off between fairness and utility by varying the coefficient for the fairness reward. We design different unfair settings where one region is adversely located and quantify the trade-off under different resource constraints. Results show that our model can effectively achieve fairness, at both a coarser and a finer-grained level and with little compromise to the utility. The approach is also robust to a sudden surge of requests during unusual occasions like a pandemic.
The proposed model and the results in our work are of interest to both public and private sectors facing delivery problems or seeking fairness in resource allocation. Additional real-world applications of our work include the school bus pick-up, mail delivery, and public services that naturally demand fairness in resource allocation. Our approach offers companies the opportunity to explore strategic decisions about depot location by balancing profitability and fairness.
Future Work Immediate future work is to replace the group-level fairness in this paper with individual-level fairness that does not discretize the service area to regions. Additional future work should include a long-term effect of unfairness to customers, such as reduced arrival rate in certain regions due to consistently low service rates.
In this section, we present the details for how the insertion heuristic works when the dispatcher receives a request.
Before the action A k is made, the dispatcher needs to check for each vehicle the feasibility of serving the customer c k .
Let v m represent a vehicle, and θ m,k (θ m,k ) represent the vehicle's planned route before (after) the action A k is made. For every planned route, the dispatcher checks all the possible insertions of c k into the planned route θ m,k and takes the one that minimizes the increase in the travel time into further consideration. Then, dispatcher checks if this cheapest insertion is feasible for vehicle v m . It is feasible to serve customer c k by vehicle v m if there exists an updated θ m,k satisfying the following six conditions:
1. The updated θ m,k contains c k and all the customers in θ m,k .
2. For every customer in θ m,k , the planned arrival time is not later than its deadline.
3. If the vehicle v m is currently out for deliveries, the start time of θ m,k is not earlier than the time at which v m returns to the depot.
4. The difference between the start time of loading for θ m,k and the arrival time at the next customer is the sum of travel time and loading time. 5. The difference between the arrival times of two consecutive customers is equal to the sum of travel time and service time. 6. The vehicle v m must return to the depot not later than the end of the day t max .
After the action A k is made, the dispatcher updates the planned routes for all vehicles. If request c k is not accepted, all planned routes remain the same. If request c k is accepted and assigned to vehicle v m , the corresponding planned route θ m,k is updated to θ m,k , and the planned routes for other vehicles remain the same. After the update of planned routes, the MDP proceeds until a new customer C k+1 makes a request at t k+1 . The use of feasA k guarantees the action taken is feasible, and thus t k+1 exists. The MDP terminates in state S k : t K = t max with all the vehicles back in the depot.
Heatmaps for 500 requests In addition to the overall acceptance rate, we also compute the temporal acceptance rates throughout the day. We divide the day into four quarters and present the acceptance rate for each quarter in the figures below.
With respect to the acceptance rates throughout the day, there is an interesting difference between the benchmark and fair policies. During the second and third quarters, the benchmark provides the service to a very low percentage of customers located in Region 1. This is because the dispatcher accepts most requests in the first quarter, and then vehicles proceed to deliver for the accepted requests. Thus, the delivering resources become limited in the second and third quarters. With limited resources, the benchmark chooses to reject most of the requests made from Region 1 and distribute the most resources to Region 2. As seen in the last quarter, when the resources become less constrained, the dispatcher considers to serve a relatively higher percentage of the requests made from Region 1, but it is still lower than that for the other region. Figure 7 : Heatmap of acceptance rates for setting S1 with 3 vehicles. Mimicking Crisis with 1000 requests Figure 13 : Heatmap of acceptance rates for setting S1 with 3 vehicles (1000 requests). Figure 14 : Heatmap of acceptance rates for setting S1 with 5 vehicles (1000 requests). 