{'fraction_non_alphanumeric': 0.031061079841567647, 'fraction_numerical': 0.009464248488638733, 'mean_word_length': 4.478757423481041, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Crowd Sourcing Dynamic Pickup & Delivery Problem considering Task Buffering and Drivers’ Rejection -Application of Multi-agent Reinforcement Learning-

In the last decade, dynamic and pickup delivery problem with crowd sourcing has been focused on as a means of securing employment opportunities in the field of last mile delivery. However, only a few studies consider both the driver's refusal right and the buffering strategy. This paper aims at improving the performance involving both of the above. We propose a driver-task matching algorithm that complies with the delivery time constraints using multiagent reinforcement learning. Numerical experiments on the model show that the proposed MARL method could be more effective than the FIFO and the RANK allocation methods.


Background
Recently, the EC market has been growing year by year, and the importance of Last Mile Delivery (LMD) has been increasing accordingly [1]. On the other hand, it was predicted that the aging rate in Japan will increase every year and reach 39.9% in 2060. The logistics industry will face a serious labor shortage crisis in the future [2]. Therefore, improving the efficiency of LMD will be one of the most important social issues.
LMD can be broadly classified into two types: Delivery problem and Pickup & Delivery problem. The characteristics of each are described in Table 1. These delivery efficiencies have been studied academically as Vehicle Routing Problem (VRP) and Dynamic Pickup & Delivery Problem (DPDP) respectively. In this article, we focus on the Pickup & Delivery Problem, which has drawn attention in the food delivery industry. In the case of Pickup & Delivery Problem, the demand is dynamic and the Time Windows (TW) is short. In order to solve the problem of the labor crisis of LMD in logistic, Crowd Sourcing (CS) LMD has been is considered as a promising approach. CS is a process of outsourcing work to an unspecified number of people. In this article, CS type DPDP is specifically defined as CSDPDP.
Food delivery operations are described in Figure 1 below. Customers access and search dishes on an operator's (server's) application, such as Uber Eats, and pay for orders. The operator then sends a cooking request to the restaurant. Once the restaurant accepts the order, the operator asks the driver to deliver. After the delivery is completed, final payment is sent the operator and the operator pays the restaurant and the driver for the food and the delivery. It should be paid attention that the delivery fee paid to the driver is calculated on the basis of the delivery distance but not on the pickup distance. Therefore, assigning a task with a long pickup distance to a driver may be rejected.

Fig. 1 Food delivery operations
Unlike normal employment, CS allows for shorter periods of engagement, making it easier to secure more labors. However, there are two difficulties with CSDPDP: firstly, unlike normal employment, the number of drivers and their working hours are unknown in advance in the server and are therefore probabilistic. This means that the decisions made at any time may not be optimal. The second difficulty is that drivers have the right to refuse the tasks allocated to them. So, it is necessary to allocate the tasks in such a way that the driver will not reject the task.
There are few previous related works which deal with the above two difficulties. The mentioned waiting for task assignment is known as Buffering Strategy in the field of DPDP, but it is mainly used to verify the effect on the uncertainty of tasks' arrival. The effect on the uncertainty of driver's arrival, which is a characteristic of CS Problem, has not been clarified yet. Matsueda has hypothesized three types of decision criteria for rejection for CSDPDP [3]. That work proposed a task allocation method called RANK, which assigns the task that is least likely to be rejected in order based on the type for each driver. Though, it is difficult to apply this method because it is hard to know the driver's type in advance in practice. In addition, Buffering Strategy is not considered in this paper.

Purpose
The main objective of this paper is to develop a method for CSDPPD that takes (1) the Buffering Strategy and (2) the driver's right of rejection into account, which has not been sufficiently considered in previous works.
We propose a task allocation algorithm built on multiagent reinforcement learning. It allows for autonomous decentralized decision-making for each agent and thus can cope with situations when the arrivals of tasks and drivers are uncertain. Moreover, by learning how the current actions will affect the future ones, appropriate actions such as waiting or rejecting task allocation could be executed, depending on the state of the system. In recent years, due to the development of the computational resource, the solution of the DPDP can be applied in practice. Basic solution strategies, algorithmic performance assessment and prediction of future task information have been studied as solutions to the DPDP. Further study are worthy such as the optimal Waiting Strategy and the improvement of the objective function using the Rolling-horizon algorithm. The fields of dynamic many-to-many and one-to-many-to-one PDPs have also been highlighted as potential research areas.
Berbeglia et al. surveyed the topic of DPDP and summarized it in the paper [4]. Sayarshad et al. proposed to incorporate non-myopic pricing into the non-myopic dynamic dial a ride problem [5]. Muñoz-Carpintero et al. proposed a solution scheme which is designed to support the dispatcher of a dial-a-ride service [6]. The scheme considers different configurations of particle swarm optimization and genetic algorithms within a proposed ad-hoc methodology to solve in real time the nonlinear mixed-integer optimization problem related with the hybrid predictive control approach. Hyytiä, Penttinen and Sulonen defined a new problem Flexible Two-sided Online task Assignment to guide idle workers based on the prediction of tasks and workers so as to increase the total number of assigned worker-task pairs [12].

Crowd Sourcing Dynamic Pickup & Delivery Problem (CSDPDP)
In the study of CSDPDP, Arslan et al. proposed the Rolling Horizon method, which is a framework for solving route planning problems with dynamic ondemand deliveries using both occasional and fixed drivers [7]. As represented in Figure 2, the proposed method solves the task and driver matching problem by converting the online problem to an offline problem. In this paper, an accurate solution method based on the matching formulation is developed to solve various versions of the offline problem repeatedly. It also addresses the lack of control over the supply of drivers by considering the use of normal dedicated vehicles. The proposed technique is a hybrid platform that allows the use of conventional dedicated vehicles to carry out specific tasks.
However, this study does not consider the refusal of the driver and the Buffering Strategy.

CSDPDP with drivers' refusal right
Matsueda studied LMD with drivers' refusal right [3]. When drivers have the refusal right, the solution would be more complicated because the number of arrival of events increases. She defined 0-1 constant to indicate whether a driver accepts a task or not.
In order to reduce the rate of driver rejection, she proposed to divide the types of drivers who have the right to reject into three categories. The specifics are as follows: Type 1 The higher reward the better Type 2 Reward ≥ F: Only do those tasks for which the reward is relatively high (F = average reward of all tasks) Type 3 Pre-processing time ≤ R: Unwilling to do much that is unrewarding (R = average of all pre-processing time) In this study, she proposed a model to rank priorities to tasks based on drivers' preferences and compared the RANK algorithm and FIFO algorithm. However, since we could not know which type the driver belongs to before assigning the task, the type of the driver is random and there is not a uniform criterion to rank the task to the drivers, which causes problems to assign in reality. In addition, both RANK and FIFO do not take Buffering Strategy into account.

Dynamic delivery considering future rewards
Ulmer et al. integrated dynamic requests into delivery routes by taking advantage of preemptive depot returns [8]. And their approximation procedure captures both the current value of a subset selection decision and its impact on future rewards. Voccia et al. introduced a multi-vehicle dynamic pickup and delivery problem with time constraints that incorporates key features associated with same-day delivery logistics [9]. Their solution approach incorporates information about future requests into routing decisions. Klapp et al. introduced the same-day delivery problem that represents a current trend in business practice [10]. They presented a formal Markov decision process model and introduce an analytical result that identifies when it is beneficial for vehicles to wait at the depot. Tong, Wang and Zimu et al. provided a solid motivation for a class of non-myopic policies that take into account the unknown future requests [13]. They mentioned that customers (or items in a parcel service) are flexible in the sense that they tolerate (small) delays in their pick-up and delivery times.  [9]. and Klapp et al. [10] have taken account of future rewards and buffering strategy while others are not. And most related works are not applied to refusal right of drivers except for Matsueda's paper [3]. So the contribution in our study is mainly considering the both.

Assumptions
・The driver delivers only one item at a time.
・The speed of the driver is constant.
・ The driver's assessment is not taken into account when assigning tasks. ・Routing is not taken into account. However, routing can be taken into account by solving the Traveling Salesman Problem (TSP) as a subroutine for the tasks assigned to each driver in this study. ・The waiting time at the pickup point is included in the pickup time.
・Assume a situation where as many tasks as possible are assigned to drivers. Tasks that are not allocated to any driver are handled by special means at an additional cost. : binary constant indicating the rejection of task when it is assigned after task 1, 2, 3 : sufficiently large constants

Coefficient of determination
"#! : A binary variable that is 1 if driver delivers task after task , and 0 otherwise " : Delivery start time for task

Formulations
Referring to Matsueda's paper [3], we define the offline task allocation problem as in (1). (1a) is the maximization of the number of allocated tasks. Equation (1b) is the constraint that each task is delivered at most once. Equation (1c) is the constraint that each driver delivers at most one task a time. Equation (1d) is a flow constraint. Equation (1e) is the compatibility of successive tasks. Equations (1f) and (1g) are the available working time constraints for each driver. Equations (1h) and (1i) are the TW constraints for each task. Equation (1j) is the binary condition of "#! . Equation (1k) is a restriction on the start time of delivery for each task.
Problem (1) can be solved optimally as an off-line problem if the input information about tasks and drivers is known in advance. However, as this information is changing from time to time, it needs to be solved as an online problem.

Application of multi-agent reinforcement learning
Multi-agent reinforcement learning is the learning of optimal policies by means of trial-and-error interactions with the environment by multiple autonomous agents. It is suitable for solving online problems in dynamic situations, because it can learn the policy of what actions to take in uncertain environments and under what conditions. There are two types of agents in our study: task agents and driver agents. Define 1 as the set of uncompleted tasks and 1 as the set of waiting drivers at each time t of the defined event set . is defined by the arrival time " of each task , the start work time ! of each driver , the time when each task must be assigned to driver at the latest time " % − " % − # " " $ , which are three types of time sets. However, we assume that ! is the task that driver has completed immediately before. As shown in Figure 3(a), each task agent observes the state transition: "1 → "(10() , !1 → !(10() Step 7. Time update: → + 1 Step 8. If all events are finished, go to Step 9, otherwise go to Step1. Step 9. The task agent updates the value Q( , ) Step 10. If t=1, go to Step 1. Each agent is assumed to be unaware of the internal states and strategies of other agents. As the system cannot direct the drivers, driver agents do not learn this time. We also assume that each driver is proficient so the speed and the capacity of each driver is the same. On this basis, we model a situation in which the task agent learns a policy in different environments. In order to discretize the state and reward of each agent, we classify each parameter into seven classes which are shown in Table 3. Fig. 3 Examples of agents' determination process Table 3 The classification of arameters

Task agent's condition, action, reward and value update
The task agent chooses its actions based on the state = 4 × 5 , which consists of the combination of the agent's internal state 4 and the environmental state 5 . We define the internal state as the class 4 = {1, ⋯ , 5} of the average urgency of delivery. When task is assigned to driver , the distance "! and the urgency of delivery "! are defined by the following equations (2) and (3).
The environmental state is defined as the class of driver shortage degree 5 = {1, ⋯ ,6}. The driver shortage degree " 5 is defined by the following equation (4). | 1 | is the number of active drivers who can be assigned at time . And | 1 | is the number of incomplete tasks.
The actions of the task agent are assignment and waiting for a driver. When assigning a task to a driver, if we assume that all drivers can be chosen, the number of actions will be too large to learn. Therefore, we set actions 1 ∈ {0,1, ⋯ ,5}, where 1 = 0 means waiting, and 1 = 1, ⋯ ,5 means choosing a driver of reward in class 1, ⋯,5 respectively, as described above. If there is more than one driver of different reward classes, the driver with the highest reward would be chosen. The reward of the task agent is represented in Equation (5) and Figure 4. Arriving at the early arrival time of task's TW is considered to be the most efficient, and the reward is set to a maximum of 1 at " % . Also, we set the reward to be higher the closer to " % in [ " , " % ]. And the absolute value of the gradient of the reward function at [ " , " % ] is set to be lower than [ " % , " % ] as we believe that to arrive during TW is better than to arrive before the early arrival time " % in order to make the best use of the driver's time.

Fig. 4 Task agent's reward function
We choose -greedy selection as the task selection policy. This policy takes the action with the largest value ( , ) in probability ε and takes random action in probability (1-ε). By setting this ε appropriately, the trade-off between centralization and diversification of search can be considered.
Value update is difficult to apply to bootstrap learning because it is difficult to predict the next state when the task and driver have taken actions. In addition, in the case of sequential updating, the value of waiting cannot be updated correctly because no reward is given when

Driver agent's condition and action
The driver agents' state in class P={1,⋯, 5} is defined by the loaded vehicle ratio of the presented tasks. The loaded vehicle ratio of the task is defined by the following Equation (6).
The driver agent's behavior is to accept or to reject the presented task. The policy is that the driver agent will accept if the class of the loaded vehicle ratio is above a certain threshold , and to rejects if it is below it. Ant the threshold is assumed to be the same for all drivers.

Experiment Design
We have made numerical experiments to verify the effectiveness of the proposed method.
In order to execute the experiment, the following input information is set up. is made from uniform random numbers U(0,3000), and " is made from uniform random numbers U (0,2 ). ・ : 325yen + × 60/1000yen. ・ : made from uniform random numbers U(540,1370). ・ : made from uniform random numbers U( + 10, " + 30). ・ : + 30. ・ Driver's acceptance threshold to assigned task: The execution environment is IntelI Core™ i7-8700CPU (2.40GHz, 2.40GHz), 8.00GB Memory. The image diagram generated by the input information of pickup location and delivery location is shown in Figure  5 below. And the time zone from each task arrival time to late arrival time and the working hours of each driver are shown in Figure 6 below.  Table 4 shows the experimental results of the number of allocations for acceptances with the loaded vehicle ratio of class 3 or higher. ROTAP is the optimal solution for the offline problem (1), where the drivers' working hours and refusal information are known in advance. FIFO is the method of allocating tasks in the order of arrival time at the server. RANK is the method of allocating tasks to the driver with the shortest pickup distance. The proposed MARL method gives a better number of allocations than the FIFO and RANK methods. Since the higher the number of allocations, the lower the cost, the proposed MARL method seems to be more effective than the above two methods.   Table 5 shows the experimental results of the allocation rate for acceptance of class 3 and above actual vehicle rate. We compared the allocation ratio of the proposed MARL method with that of the FIFO and RANK methods. While m = 20, 30 and n = 20, 30, 40, the MARL method's results are close to that of the FIFO and RANK methods, but while m = 10 and n = 20, 30 or m = 20 and n = 10, the allocation ratio of the MARL method is higher than that of the FIFO and RANK methods. These also mean that the proposed MARL method is more effective than the FIFO and RANK methods. Table 6 The competitive ratio of allocation for acceptances (the average of 10 times)  Table 6 shows the experimental results of the competitive ratio for acceptances with the loaded vehicle ratio of class 3 or higher. The competitive ratio is a performance evaluation index of the online algorithm for solving the online scheduling problem. The definition of the competitive ratio is based on Matsueda's paper [3] and is given in Equation (7) below.

Numerical experiments to verify the proposed method
=>,(?) OPT (L) is the optimal value of the optimal solution to the offline problem (1), where the drivers' working hours and refusal information are known in advance.
A ( ) is the evaluation value of the online algorithm. For a real number ℎ ∈ ℝ , which is established in Equation (7), is the competitive ratio of the online algorithm.
Therefore, from the experimental results of the competitive ratios of the experiments of the methods in Table 6, it can be seen that the competitive ratio of the proposed method MARL is always less different from the best conflict ratio of 1.0 compared to FIFO and RANK methods. So, the MARL method is considered to perform better than the FIFO and RANK methods. Table 7 shows the experimental results of the number of allocations of the actual car acceptance rate class 1 or more to actual car acceptance rate class 5 or more. According to the experimental results of the number of allocations with different accepted loaded vehicle ratio, although the actual loaded vehicle ratio class is 1, 2 and 5, the proposed MARL method is less different from the FIFO method and the RANK method, the MARL method obtains a better number of allocations than the FIFO method and the RANK method. When the accepted loaded vehicle ratio class is 3 and 4, the proposed MARL method is different from the FIFO and RANK methods, and it can obviously obtain a better number of allocations. Therefore, we can say that the MARL method is more effective than the FIFO and RANK methods even when the actual acceptance rate class varies.

Experiment with changing the demand at different times of the day
We experimented with changing the frequency of task arrivals in response to the high number of customers requesting food deliveries during lunch and dinner hours. According to Uber Eats' research, the peak hours for delivery requests are lunch time (11AM-2PM) and dinner time (6PM-9PM) [6]. Therefore, we set the number as shown in Table 8 below. The probability of a task occurring between 11AM -2PM is set to 0.4, the probability of a task occurring between 6PM -9PM is set to 0.4, and the probability of a task occurring at other times is set to 0.2. The time zones for each task and the working hours of each driver, which have been changed are represented in Figure 9. And the results of the experiment are shown in Table 9 below.  From the experimental results in Table 9, it can be seen that the number of allocations for the MARL method is higher than that for the FIFO and RANK methods, even when the frequency of task arrivals is changed during lunch and dinner. It is indicating that the MARL method is more effective than the FIFO and RANK methods.

Conclusion
Improving the efficiency of LMD has become an important social issue, and CS employment have been focused on as a means of securing employment opportunities. So, this article focuses on CSDPDP in order to solve the problem of efficiency improvement of LMD.
Although there have been studies on CSDPDP already, there are few studies that consider both the driver's refusal right and the buffering strategy. Therefore, this article aims to improve the algorithm of CSDPDP by considering both driver's refusal right and buffering strategy. Specifically, we propose a cost-minimizing driver-task matching algorithm that complies with the delivery time constraint using multiagent reinforcement learning. Numerical experiments on the model show that the proposed MARL method is more effective than the FIFO and the RANK allocation methods. Even if the experiments are carried out in the case of changing the accepted loaded vehicle ratio class or in the case of changing the demand in different times of the day, the MARL method remains the most effective.
As a future prospect, simultaneous processing of multiple tasks can be considered in order to further reduce the cost. In addition, since we have trained the task, we can consider building a model that also takes into account the learning of the driver.

Simultaneous processing of multiple tasks
In food delivery, items are comparatively similar and there is little difference between large and small items. So, more than one item can be carried in one delivery. Also, there are cases where items are delivered from shops that are close together, or where items from the same shop are delivered to close destinations. In these situations, if multiple tasks are handled simultaneously, the delivery distance is reduced, and the overall cost is also reduced. Therefore, a future research topic could be the possibility for drivers to accept more than one task each time. Li [14] took a chain supermarket as an example, combined the distance factor and plans the distribution route of vehicle. And the results show heuristic algorithm can effectively solve the optimal solution of vehicle routing problem for single distribution center. In addition, Simultaneous handling of multiple tasks also changes the delivery routing, and it is one of the directions of future research to determine in which situations the costs can be reduced the most.

Learning of drivers
In this case, the task was learned. However, in reality, ad hoc drivers are hard to be controlled. In order to know each driver better, the future model could take the learning of drivers into account.