Model-Based Rolling Matching Strategy for Crowdsourced Drivers and Delivery Tasks Considering Uncertain Transportation Duration

Abstract

The matching of crowdsourced drivers and delivery tasks is an important decision problem for the crowdsourced delivery platform. Although the existence of uncertainty of transportation duration in logistics delivery has been verified, uncertain transportation duration has not been considered in previous studies on the matching of crowdsourced drivers and delivery tasks. This would lead to the limitation that the results of the existing methods cannot meet the time requirements of senders. In this case, the profit and customer satisfaction of the crowdsourced delivery platform would decrease. In this paper, a model-based rolling matching strategy to match crowdsourced drivers and delivery tasks considering uncertain transportation duration is proposed. In addition, it is assumed that the crowdsourced delivery platform also has some dedicated drivers to implement the delivery tasks that cannot be implemented by crowdsourced drivers. First, a simpler problem is described, which is to match crowdsourced drivers and delivery tasks considering uncertain transportation duration in a static data environment. Then, a model is proposed to solve the above problem. Based on the proposed model, this paper further proposes a rolling procedure to solve the problem in a data refreshing environment. Moreover, a heuristic algorithm is presented for combining multiple delivery tasks to solve the one-to-many matching. Finally, a case study and comparison are given to illustrate the validity and the contribution of the proposed matching strategy. The results show that the proposed matching strategy has a distinct advantage of cost savings.

Crowdsourced delivery is a logistics delivery service that is coordinated by a technology platform and designates the delivery tasks to the public to achieve benefits for all stakeholders (1 –6). It is an important part of the sharing economy that provides people with the chance to share and redistribute the excess transportation capacity (7 –9). Compared with traditional logistics, crowdsourced delivery can reduce the cost and time of delivery, improve the performance of delivery, and enhance the social resource utilization (10 –16). In recent years, crowdsourced delivery has been adopted by some platforms and logistics service companies. For example, in 2015, Amazon launched the Flex service in Seattle and outsourced delivery tasks to private drivers (17, 18); the U.S. crowdsourced logistics platforms, Postmates, Deliv and DoorDash outsource the delivery tasks to part-time couriers to provide customers with fast delivery services (19 –23).

When applying for a delivery task, the crowdsourced driver will provide the platform with their relevant information, including their earliest departure time and latest arrival time from the origin to the destination; when announcing the delivery task, the sender will provide the platform with their relevant information, including the earliest and the latest pickup time and delivery time of the package from the origin to the destination. According to the information provided by crowdsourced drivers and senders, the crowdsourced delivery platform needs to determine rational matching between crowdsourced drivers and delivery tasks to implement the delivery tasks and make a profit. It is important to highlight that the determination of rational matching between crowdsourced drivers and delivery tasks is usually complex, since multiple factors need to be considered, including each crowdsourced driver’s origin, destination, earliest departure time and latest arrival time, and each delivery task’s origin, destination, earliest pickup time and latest delivery time, and so forth (2, 24). Therefore, the determination of rational matching between crowdsourced drivers and delivery tasks is an important research problem with a realistic background in the operations of crowdsourced delivery platforms.

In recent years, some researchers have conducted related studies on the determination of matching between crowdsourced drivers and delivery tasks. With regard to the last mile delivery of online orders, Devari et al. proposed a method for crowdsourced delivery matching between social network friends and customers, considering the advantages of social networks ( 25 ). In their study, based on the results of an online survey, a logistic regression model was built to estimate the probabilities that social network friends agree to deliver customers’ online orders. Then, data about the city of Alexandria, Virginia, was used to conduct a simulation study of crowdsourced delivery matching between social network friends and customers according to the probabilities that social network friends would deliver online orders. The performance of the proposed method was evaluated by comparing the scenarios of traditional truck delivery and customers picking up orders at the local store. Results show that the proposed method of crowdsourced last mile delivery using social network friends can effectively improve the efficiency of the last mile delivery, reduce the privacy concerns of consumers and ensure the reliability of the crowdsourced delivery. Soto Setzke et al. proposed an algorithm model for matching crowdsourced drivers and transportation requests considering the transportation routes and time constraints ( 26 ). In the algorithm model, a directed graph is first constructed where the time constraints of departure and pickup are not violated. Then, the matching degrees between the travel routes of the crowdsourced drivers and the delivery routes are measured by computing the additional time of the driver carrying out a transportation request. The maximum matching with minimum cost can be obtained by solving the algorithm model. The effectiveness of the proposed algorithm model was evaluated based on traffic data from a city in Germany. Arslan et al. studied the dynamic pickup and delivery problem ( 7 ). They proposed a rolling horizon framework and developed an exact solution approach to obtain the real-time matching result based on the updated information. In their study, delivery tasks were implemented by either a crowdsourced driver or a dedicated driver. The feasibility and effectiveness of the method was illustrated by computational experiments. The experimental results suggested that the use of crowdsourced drivers can save vehicle-miles by 37% compared with the traditional delivery using only dedicated vehicles. Paskalathis and Azhari solved the multiple pickup and delivery problem in crowdsourced delivery ( 27 ). They proposed an exact algorithm to optimize the transportation path for crowdsourced drivers to implement multiple delivery tasks at one time. In their study, the situations of crowdsourced drivers implementing multiple pickups and deliveries during one trip were considered. Then, the proposed method was evaluated from the number of trips, total distance, total duration and security concerns based on case study data from Yogyakarta, Indonesia. The results show that, compared with direct delivery, the proposed method can effectively save distance and time. Chen et al. focused on the matching problem of multiple crowdsourced drivers and multiple delivery tasks ( 28 ). To solve the matching problem, they proposed a general integer linear programming formulation and developed two heuristic algorithms based on the time compatibility heuristic and the time-expanded graph heuristic, respectively. They synthetically considered the maximum detour, the capacity limits and the selection of transferring delivery tasks between crowdsourced drivers. The numerical study results show that the senders can gain more benefits, and traffic congestion can be alleviated, when the number of crowdsourced drivers increases.

Previous studies have made significant contributions to the determination of rational matching between crowdsourced drivers and delivery tasks considering the different problem characteristics, and have provided valuable decision supports to the practical operation of the crowdsourced delivery platform. It is necessary to point out, however, that the logistics of delivery is generally faced with the uncertainty of transportation duration because of the impact of traffic congestion, weather conditions and other factors (29 –31). Uncertain transportation duration (as it is termed in this paper) should be considered in the determination of matching between crowdsourced drivers and delivery tasks. This is because, on the one hand, serious traffic congestion and uncertain transportation duration cause substantial increase of the cost of last mile delivery, which is an important real-life background for the emergence of crowdsourced delivery. On the other hand, senders usually have delivery time requirements (pickup time, delivery time, etc.) ( 32 ). If the time requirements are not satisfied, then the platform would need to pay compensation to senders and the customer satisfaction would decrease. However, uncertain transportation duration has not been considered in previous studies on the determination of matching between crowdsourced drivers and delivery tasks. This would lead to the limitation that the results of the existing methods cannot meet the time requirements of some senders in practice. In this case, the profit and customer satisfaction of the crowdsourced delivery platform would decrease. Therefore, it is necessary to further develop the method for matching crowdsourced drivers and delivery tasks considering uncertain transportation duration.

In this paper, a new model-based rolling matching strategy is proposed to match crowdsourced drivers and delivery tasks considering uncertain transportation duration. To describe the rolling matching strategy easily and clearly, a model for matching crowdsourced drivers and delivery tasks considering uncertain transportation duration in a static data environment is first proposed. On this basis, a procedure is given to solve the problem in the data refreshing environment based on the model for a static data environment. Moreover, a heuristic algorithm is presented to solve the one-to-many matching by combining multiple delivery tasks. Finally, a case study and comparison are demonstrated to illustrate the implementation procedure and validity of the proposed matching strategy.

Problem of Matching Crowdsourced Drivers and Delivery Tasks

The problem of matching crowdsourced drivers and delivery tasks is shown in Figure 1. In Figure 1, an online crowdsourced delivery platform is considered. When applying for the delivery task, each crowdsourced driver will provide the platform with their relevant information, including their earliest departure time from the origin and latest arrival time to the destination; when announcing the delivery task, each sender will provide the platform with their relevant information, including the earliest and the latest pickup time and delivery time of the packages from the origin to the destination. According to the information provided by the crowdsourced drivers and the senders, the crowdsourced delivery platform needs to determine the rational matching between the crowdsourced drivers and delivery tasks to implement delivery tasks and make a profit. It should be noted that the matching between crowdsourced drivers and delivery tasks is determined in a data refreshing environment. In other words, the crowdsourced delivery platform may receive new delivery applications and new delivery tasks from crowdsourced drivers and senders at any time.

Figure 1.

The problem of matching crowdsourced drivers and delivery tasks.

To solve the problem in a data refreshing environment, this paper proposes a model-based rolling matching strategy. To describe the rolling matching strategy easily and clearly, a model is first given to match crowdsourced drivers and delivery tasks considering uncertain transportation duration in a static data environment. On this basis, a procedure is given to solve the problem in a data refreshing environment based on the proposed model. For this, the problem of matching crowdsourced drivers and delivery tasks considering uncertain transportation duration in a static data environment is described in this section.

Considering a time point during the operation of the crowdsourced delivery platform, there are $m_{1}$ crowdsourced drivers who have sent delivery applications and $n$ delivery tasks announced by senders. To model the problem, following the study of Arslan et al. ( 7 ), it is assumed that the crowdsourced delivery platform has $m_{2}$ dedicated drivers, and that the crowdsourced drivers and dedicated drivers cannot reject a delivery task matched by the crowdsourced delivery platform. Let $D = {d_{1}, d_{2}, \dots, d_{m_{1}}, d_{m_{1} + 1}, d_{m_{1} + 2}, \dots, d_{m_{1} + m_{2}}}$ be the set of $m_{1} + m_{2}$ drivers, where $d_{i}$ , $i \in {1, 2, \dots, m_{1}}$ , denotes the crowdsourced driver and $d_{i}$ , $i \in {m_{1} + 1, m_{1} + 2, \dots, m_{1} + m_{2}}$ , denotes the dedicated driver. Let $o_{i}$ and $b_{i}$ denote the origin and destination of driver $d_{i}$ , $i \in {1, 2, \dots, m_{1} + m_{2}}$ . For the convenience of analysis, it is assumed that all of the dedicated drivers will depart from the dedicated depot and come back to the dedicated depot after completing the delivery tasks, that is, the $o_{i}$ and $b_{i}$ of the dedicated drivers are all the dedicated depot, $i \in {m_{1} + 1, m_{1} + 2, \dots, m_{1} + m_{2}}$ . Let $e_{i}$ and $l'_{i}$ denote the expected earliest departure time and latest arrival time of driver $d_{i}$ from the origin $o_{i}$ to the destination $b_{i}$ , $e_{i} < l'_{i}$ . For the dedicated drivers, it is considered that there are no limits on the departure time and arrival time. Thus, $e_{i}$ can be any time from now, and $l'_{i}$ can be a very long time later, $i \in {m_{1} + 1, m_{1} + 2, \dots, m_{1} + m_{2}}$ . These assumptions are consistent with the study of Arslan et al. ( 7 ). Let $P = {p_{1}, p_{2}, \dots, p_{n}}$ be the set of $n$ delivery tasks announced by senders, where $p_{j}$ denotes the $j$ th delivery task, $j = 1, 2, \dots, n$ . Let $o_{j}^{p}$ and $b_{j}^{p}$ denote the origin and destination of delivery task $p_{j}$ , $j = 1, 2, \dots, n$ . The senders may have time requirements for the delivery tasks. Therefore, let $e_{j}^{p}$ and $l_{j}^{p}$ denote the earliest and latest pickup time of delivery task $p_{j}$ , $e_{j}^{p} < l_{j}^{p}$ ; let $e_{j}'^{p}$ and $l_{j}'^{p}$ denote the earliest and latest delivery time of delivery task $p_{j}$ , $e_{j}'^{p} < l_{j}'^{p}$ .

The above problem is how to determine an optimal matching between drivers and delivery tasks according to the delivery application information $o_{i}$ , $b_{i}$ , $e_{i}$ , $l'_{i}$ and delivery task information $o_{j}^{p}$ , $b_{j}^{p}$ , $e_{j}^{p}$ , $l_{j}^{p}$ , $e_{j}'^{p}$ , $l_{j}'^{p}$ . To solve this problem, the model for matching drivers and delivery tasks in a static data environment is given in the next section.

Model for Matching Crowdsourced Drivers and Delivery Tasks Considering Uncertain Transportation Duration in a Static Data Environment

In this section, to solve the above problem shown in the previous section, a model is proposed to match crowdsourced drivers and delivery tasks considering uncertain transportation duration in a static data environment. First, a framework of the proposed model is given, then detailed description of the model is given according to the framework.

Framework of the Proposed Model

It can be seen in the existing studies (7, 24, 33, 34) that the results of one-to-one matching are the basis of one-to-many matching between drivers and delivery tasks. Usually, the model for one-to-many matching can be obtained according to the transformation of the model for one-to-one matching. Since the main contribution of this paper is the consideration of uncertain transportation duration in crowdsourced delivery, first a model is proposed for one-to-one matching between drivers and delivery tasks, that is, each driver implements one delivery task on a trip. Then, a heuristic algorithm is proposed to solve the one-to-many matching problem based on the model for one-to-one matching by combining multiple delivery tasks.

The framework of the proposed model is shown in Figure 2. It can be seen from Figure 2 that the construction of the model includes three parts. A brief description of each part is given below.

Determination of the transportation cost matrix of drivers concerning different delivery tasks. According to the origins and destinations of drivers (including both crowdsourced drivers and dedicated drivers) and delivery tasks, the transportation routes that each driver implements mean that different delivery tasks can be determined. Then, the pickup distance matrix, delivery distance matrix and arriving destination distance matrix of drivers concerning different delivery tasks can be constructed according to the transportation routes. According to the obtained distance matrices and the unit transportation costs of different drivers, the transportation cost matrix of drivers concerning different delivery tasks can be determined.

Determination of the expected penalty cost matrix of drivers concerning different delivery tasks. According to the obtained pickup, delivery and arriving destination distance matrices, the uncertain transportation duration intervals of drivers concerning different delivery tasks can be determined, and the relevant expected times (expected pickup time, expected delivery time and expected arrival at destination time) in the form of interval numbers can be estimated. Then, the penalty probability matrices on pickup, delivery and arrival at destination stages can be estimated based on the time requirements of delivery tasks and the relevant expected times of drivers concerning different delivery tasks. Further, the expected penalty cost matrix of drivers concerning different delivery tasks can be determined according to the penalties of delay concerning different stages.

Constructing and solving the optimization matching model. According to the obtained transportation cost matrix and the expected penalty cost matrix of drivers concerning different delivery tasks, an optimization matching model is constructed to minimize the total cost of the crowdsourced delivery platform. The solution of the optimization matching model can be obtained by the Hungarian method ( 35 ) and the optimal matching between drivers and delivery tasks can be determined.

Figure 2.

Framework of the proposed model.

Detailed Description of Construction of the Model

Determination of the Transportation Cost Matrix of Drivers Concerning Different Delivery Tasks

Following the study of Arslan et al. ( 7 ), there are four possible position relationships between the origins and destinations of drivers (including crowdsourced drivers and dedicated drivers) and delivery tasks, as shown in Figure 3. In Figure 3a, the driver and the delivery task have the same origin and destination. In this case, the routes of the driver and the delivery task are exactly the same. The idle resources of the drivers are effectively used and there is no waste of additional transportation cost to implement the delivery task. It is the most efficient situation in the crowdsourced delivery. In Figure 3b, the driver and the delivery task have different origins and the same destination. In this case, the driver should arrive at the origin of the delivery task first, then pick up and deliver the package to the destination of the delivery task and their own destination. In Figure 3c, the driver and the delivery task have the same origin and different destinations. In this case, the driver can pick up the package directly and deliver the package to the destination, and then travel to their own destination. In Figure 3d, the driver and the delivery task both have different origins and different destinations. In this case, the driver should first arrive at the origin of the delivery task, and then pick up the package and deliver it to its destination. After completing the delivery task, the driver needs to travel to their own destination.

Figure 3.

The four possible position relationships between drivers and delivery tasks: (a) same origin and destination, (b) different origins and same destination, (c) same origin and different destinations, and (d) different origins and destinations.

Based on the above analysis, the process by which drivers (including crowdsourcing drivers and dedicated drivers) implement the delivery tasks can be divided into three transportation stages. The first one is the pickup stage, in which the driver travel from their own origin to the origin of the delivery task. If the origin of the driver is the same as the origin of the delivery task (as shown in Figure 3, a and c ), then the transportation distance in the pickup stage is zero. The second is the delivery stage, in which the driver travels from their origin to the destination of the delivery task. The third is the arrival the destination stage, in which the driver moves to their own destination after completing the delivery task. If the destination of the driver is the same as the destination of the delivery task (as shown in Figure 3, a and b ), then the transportation distance in the arrival at destination stage is zero. By using the three transportation stages, the four possible position relationships can be unified into one. Thereafter, the calculation procedure and equations can be given with respect to the unified driver/delivery task relationship.

According to the origin and destination of each driver and each delivery task, the transportation distance of each driver completing each delivery task in each transportation stage can be obtained. Let $S_{ij}^{dp}$ , $S_{j}^{pp}$ and $S_{ij}^{pd}$ denote the transportation distances that driver $d_{i}$ implements for the delivery task $p_{j}$ in the pickup stage, delivery stage and arrival at destination stage respectively, $i = 1, 2, \dots, m_{1} + m_{2}$ , $j = 1, 2, \dots, n$ . According to the obtained $S_{ij}^{dp}$ , $S_{j}^{pp}$ and $S_{ij}^{pd}$ , $i = 1, 2, \dots, m_{1} + m_{2}$ , $j = 1, 2, \dots, n$ , three transportation distance matrices $S^{dp} = [S_{ij}^{dp}]_{(m_{1} + m_{2}) \times n}$ , $S^{pp} = [S_{j}^{pp}]_{(m_{1} + m_{2}) \times n}$ and $S^{pd} = [S_{ij}^{pd}]_{(m_{1} + m_{2}) \times n}$ with respect to the pickup stage, delivery stage and arrival at destination stage can be constructed.

In this study, it is assumed that the transportation costs of implementing the delivery tasks are proportional to the transportation distance. Let $ϕ_{1}$ denote the transportation cost that the platform pays to crowdsourced drivers for their per unit distance traveling for the platform. Let $ϕ_{2}$ denote the transportation cost that the platform pays to dedicated drivers for their per unit distance traveling for the platform. Since the crowdsourced drivers use their own vehicles and fuel, we suppose $ϕ_{1} < ϕ_{2}$ . Thus, the transportation cost that the platform pays to crowdsourced driver $d_{i}$ for implementing the delivery task $p_{j}$ can be represented by:

c_{ij} = c_{0} + ϕ_{1} [S_{ij}^{dp} + S_{j}^{pp} + S_{ij}^{pd}], i = 1, 2, \dots, m_{1}, j = 1, 2, \dots, n,

(1)

where $c_{0}$ is the basic cost per delivery.

Similarly, the transportation cost that the platform pays to dedicated driver $d_{i}$ for implementing the delivery task $p_{j}$ can be represented by:

c_{ij} = c_{0} + ϕ_{2} [S_{ij}^{dp} + S_{j}^{pp} + S_{ij}^{pd}], i = m_{1} + 1, m_{1} + 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n .

(2)

According to $c_{ij}$ , the transportation cost matrix of drivers concerning different delivery tasks $C = [c_{ij}]_{(m_{1} + m_{2}) \times n}$ can be constructed, $i = 1, 2, \dots, m_{1} + m_{2}$ , $j = 1, 2, \dots, n$ .

Determination of the Expected Penalty Cost Matrix of Drivers Concerning Different Delivery Tasks

In the daily operation of the crowdsourced platform, senders may provide time requirements for the pickup and delivery time of delivery tasks, such as the earliest and latest pickup time, and the earliest and latest delivery time. Meanwhile, crowdsourced drivers may also provide their time requirements, such as the earliest departure time and latest arrival time. Because of the uncertain transportation duration caused by traffic congestion, weather conditions and other factors, a crowdsourced driver may not complete their delivery tasks on time (29 –31). If the delivery tasks are not completed meeting the time requirements, then the platform needs to pay compensation to the senders and the senders’ customer satisfaction will also decrease. To analyze the possible loss caused by the delay of delivery tasks under uncertain transportation duration, the penalty probabilities of each driver concerning different delivery tasks are first estimated, and then the expected penalty cost matrix of drivers concerning different delivery tasks can be constructed.

Based on the above analysis, the process by which drivers implement the delivery tasks can be divided into three transportation stages, that is, pickup stage, delivery stage and arrival at destination stage. The uncertain transportation time intervals concerning the three transportation stages by which a driver implements different delivery tasks can be obtained according to the origins and destinations of the driver and the delivery tasks. Let ${\hat{t}}_{ij}^{dp} = [t_{ij}^{dpf}, t_{ij}^{dps}]$ , ${\hat{t}}_{j}^{pp} = [t_{j}^{ppf}, t_{j}^{pps}]$ and ${\hat{t}}_{ij}^{pd} = [t_{ij}^{pdf}, t_{ij}^{pds}]$ denote the uncertain transportation time intervals of pickup stage, delivery stage and arrival at destination stage by which the driver $d_{i}$ implements the delivery task $p_{j}$ , $i = 1, 2, \dots, m_{1} + m_{2}$ , $j = 1, 2, \dots, n$ . The values of ${\hat{t}}_{ij}^{dp} = [t_{ij}^{dpf}, t_{ij}^{dps}]$ , ${\hat{t}}_{j}^{pp} = [t_{j}^{ppf}, t_{j}^{pps}]$ and ${\hat{t}}_{ij}^{pd} = [t_{ij}^{pdf}, t_{ij}^{pds}]$ can be determined by considering the related factors (such as traffic congestion, weather condition and so on). Let $t_{ij}$ denote the departure time at which driver $d_{i}$ implements the delivery task $p_{j}$ , $i = 1, 2, \dots, m_{1} + m_{2}$ , $j = 1, 2, \dots, n$ . Let ${\hat{T}}_{ij}^{dp} = [T_{ij}^{dpf}, T_{ij}^{dps}]$ , ${\hat{T}}_{j}^{pp} = [T_{j}^{ppf}, T_{j}^{pps}]$ and ${\hat{T}}_{ij}^{pd} = [T_{ij}^{pdf}, T_{ij}^{pds}]$ denote the expected pickup time, expected delivery time and expected arrival at destination time ay which driver $d_{i}$ implements delivery task $p_{j}$ , $i = 1, 2, \dots, m_{1} + m_{2}$ , $j = 1, 2, \dots, n$ .

In the pickup stage, to implement the delivery task $p_{j}$ , the driver $d_{i}$ will depart at time $t_{ij}$ and the uncertain transportation time is ${\hat{t}}_{ij}^{dp} = [t_{ij}^{dpf}, t_{ij}^{dps}]$ . Thus, the expected pickup time ${\hat{T}}_{ij}^{dp} = [T_{ij}^{dpf}, T_{ij}^{dps}]$ can be represented by:

{\hat{T}}_{ij}^{dp} = [T_{ij}^{dpf}, T_{ij}^{dps}] = [t_{ij} + t_{ij}^{dpf}, t_{ij} + t_{ij}^{dps}], i = 1, 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n,

(3)

In the delivery stage, if the driver arrives at the origin of the delivery task before the earliest pickup time, then the driver cannot pick up the package and begin to deliver it until the earliest pickup time $e_{j}^{p}$ . Therefore, if $T_{ij}^{dpf} < T_{ij}^{dps} < e_{j}^{p}$ , then the expected delivery time ${\hat{T}}_{j}^{pp} = [T_{j}^{ppf}, T_{j}^{pps}]$ can be expressed by $[e_{j}^{p} + t_{j}^{ppf}, e_{j}^{p} + t_{j}^{pps}]$ ; if $T_{ij}^{dpf} < e_{j}^{p} \leq T_{ij}^{dps}$ , then the expected delivery time ${\hat{T}}_{j}^{pp} = [T_{j}^{ppf}, T_{j}^{pps}]$ can be expressed by $[e_{j}^{p} + t_{j}^{ppf}, T_{ij}^{dps} + t_{j}^{pps}]$ ; if $e_{j}^{p} \leq T_{ij}^{dpf} < T_{ij}^{dps}$ , then the driver will not arrive at the origin of the delivery task before the earliest pickup time, and the expected delivery time ${\hat{T}}_{j}^{pp} = [T_{j}^{ppf}, T_{j}^{pps}]$ is the sum of expected pickup time and uncertain transportation time of delivery, that is, $[T_{ij}^{dpf} + t_{j}^{ppf}, T_{ij}^{dps} + t_{j}^{pps}]$ . Thus, the value of ${\hat{T}}_{j}^{pp} = [T_{j}^{ppf}, T_{j}^{pps}]$ can be calculated by:

\begin{matrix} {\hat{T}}_{j}^{pp} = [T_{j}^{ppf}, T_{j}^{pps}] = \\ {\begin{matrix} [e_{j}^{p} + t_{j}^{ppf}, e_{j}^{p} + t_{j}^{pps}], T_{ij}^{dpf} < T_{ij}^{dps} < e_{j}^{p} \\ [e_{j}^{p} + t_{j}^{ppf}, T_{ij}^{dps} + t_{j}^{pps}], T_{ij}^{dpf} < e_{j}^{p} \leq T_{ij}^{dps} \\ [T_{ij}^{dpf} + t_{j}^{ppf}, T_{ij}^{dps} + t_{j}^{pps}], e_{j}^{p} \leq T_{ij}^{dpf} < T_{ij}^{dps} \end{matrix} \\ i = 1, 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n \end{matrix},

(4)

Similar to the analysis of the delivery stage, the analysis of arrival at destination time is given below. If the driver arrives at the destination of the delivery task before earliest delivery time $e_{j}'^{p}$ , then the driver cannot deliver the package and begin to go to their own destination until the earliest delivery time $e_{j}'^{p}$ . Therefore, if $T_{j}^{ppf} < T_{j}^{pps} < e_{j}'^{p}$ , then the expected arriving destination time ${\hat{T}}_{ij}^{pd} = [T_{ij}^{pdf}, T_{ij}^{pds}]$ can be calculated by $[e_{j}'^{p} + t_{ij}^{p d f}, e_{j}'^{p} + t_{ij}^{pds}]$ ; if $T_{j}^{ppf} < e_{j}'^{p} \leq T_{j}^{pps}$ , then the expected arrival at destination time ${\hat{T}}_{ij}^{pd} = [T_{ij}^{pdf}, T_{ij}^{pds}]$ can be calculated by $[e_{j}'^{p} + t_{ij}^{pdf}, T_{j}^{pps} + t_{ij}^{pds}]$ ; if $e_{j}'^{p} \leq T_{j}^{ppf} < T_{j}^{pps}$ , then the driver will not arrive at the destination of the delivery task before the earliest delivery time, and the expected arrival at destination time ${\hat{T}}_{ij}^{pd} = [T_{ij}^{pdf}, T_{ij}^{pds}]$ is the sum of the expected delivery time and the uncertain transportation time of arrival at the destination, that is, $[T_{j}^{ppf} + t_{ij}^{pdf}, T_{j}^{pps} + t_{ij}^{pds}]$ . Thus, the value of ${\hat{T}}_{ij}^{pd} = [T_{ij}^{pdf}, T_{ij}^{pds}]$ can be calculated by:

\begin{matrix} {\hat{T}}_{ij}^{pd} = [T_{ij}^{pdf}, T_{ij}^{pds}] = \\ {\begin{matrix} [e_{j}'^{p} + t_{ij}^{pdf}, e_{j}'^{p} + t_{ij}^{pds}], T_{j}^{ppf} < T_{j}^{pps} < e_{j}'^{p} \\ [e_{j}'^{p} + t_{ij}^{pdf}, T_{j}^{pps} + t_{ij}^{pds}], T_{j}^{ppf} < e_{j}'^{p} \leq T_{j}^{pps} \\ [T_{j}^{ppf} + t_{ij}^{pdf}, T_{j}^{pps} + t_{ij}^{pds}], e_{j}'^{p} \leq T_{j}^{ppf} < T_{j}^{pps} \end{matrix} \\ i = 1, 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n . \end{matrix}

(5)

According to the obtained ${\hat{T}}_{ij}^{dp}$ , ${\hat{T}}_{j}^{pp}$ and ${\hat{T}}_{ij}^{pd}$ , $i = 1, 2, \dots, m_{1} + m_{2}$ , $j = 1, 2, \dots, n$ , the expected pickup time matrix ${\hat{T}}^{dp} = [{\hat{T}}_{ij}^{dp}]_{(m_{1} + m_{2}) \times n}$ , expected delivery time matrix ${\hat{T}}^{pp} = [{\hat{T}}_{j}^{pp}]_{(m_{1} + m_{2}) \times n}$ and expected arrival at destination time matrix ${\hat{T}}^{pd} = [{\hat{T}}_{ij}^{pd}]_{(m_{1} + m_{2}) \times n}$ can be constructed.

Let $ρ_{ij}^{dp}$ , $ρ_{j}^{pp}$ and $ρ_{ij}^{pd}$ denote the penalty probability of driver $d_{i}$ for implementing the delivery task $p_{j}$ in the pickup stage, delivery stage and arrival at destination stage, respectively. To estimate the penalty probabilities $ρ_{ij}^{dp}$ , $ρ_{j}^{pp}$ and $ρ_{ij}^{pd}$ , it is necessary to compare the elements in ${\hat{T}}^{dp} = [{\hat{T}}_{ij}^{dp}]_{(m_{1} + m_{2}) \times n}$ , ${\hat{T}}^{pp} = [{\hat{T}}_{j}^{pp}]_{(m_{1} + m_{2}) \times n}$ and ${\hat{T}}^{pd} = [{\hat{T}}_{ij}^{pd}]_{(m_{1} + m_{2}) \times n}$ with the time requirements of delivery tasks and drivers. Following the studies of Liu et al. ( 36 ) and Fan et al. ( 37 ), there are six position relationships between the expected times and time requirements of delivery tasks. Taking the pickup stage as an example, the six possible position relationships between the expected pickup time and the pickup time requirement of delivery task are shown in Figure 4.

Figure 4.

The six possible position relationships between the expected pickup time and the pickup time requirement of delivery task: (a) $T_{ij}^{dpf} < T_{ij}^{dps} < e_{j}^{p} < l_{j}^{p}$ , (b) $T_{ij}^{dpf} < e_{j}^{p} \leq T_{ij}^{dps} < l_{j}^{p}$ , (c) $e_{j}^{p} \leq T_{ij}^{dpf} < T_{ij}^{dps} \leq l_{j}^{p}$ , (d) $e_{j}^{p} < T_{ij}^{dpf} \leq l_{j}^{p} < T_{ij}^{dps}$ , (e) $T_{ij}^{dpf} < e_{j}^{p} < l_{j}^{p} \leq T_{ij}^{dps}$ , and (f) $e_{j}^{p} < l_{j}^{p} < T_{ij}^{dpf} < T_{ij}^{dps}$ .

In the cases of Figure 4, a–c, that is, $T_{ij}^{dpf} < T_{ij}^{dps} < e_{j}^{p} < l_{j}^{p}$ , $T_{ij}^{dpf} < e_{j}^{p} \leq T_{ij}^{dps} < l_{j}^{p}$ and $e_{j}^{p} \leq T_{ij}^{dpf} < T_{ij}^{dps} \leq l_{j}^{p}$ , the driver can pick the package up before the latest pickup time of the delivery task $l_{j}^{p}$ even if the driver arrives at the origin of the delivery task at the latest possible time $T_{ij}^{dps}$ . Therefore, in the cases of Figure 4, a–c, the penalty probability is zero. In the case of Figure 4, d and e , that is, $e_{j}^{p} < T_{ij}^{dpf} \leq l_{j}^{p} < T_{ij}^{dps}$ and $T_{ij}^{dpf} < e_{j}^{p} < l_{j}^{p} \leq T_{ij}^{dps}$ , if the driver $d_{i}$ arrives at the origin of the delivery task in the time interval $[T_{ij}^{dpf}, l_{j}^{p}]$ , then there is no need for the platform to pay compensation to the sender. But, if the driver $d_{i}$ arrives in the time interval $[l_{j}^{p}, T_{ij}^{dps}]$ , then the platform should pay compensation to the sender. To estimate the penalty probabilities in the cases of Figure 4, d and e , it is assumed that the real time at which driver $d_{i}$ arrives at the origin of delivery task $p_{j}$ uniformly and independently distributes in ${\hat{T}}_{ij}^{dp} = [T_{ij}^{dpf}, T_{ij}^{dps}]$ . Therefore, in the cases of Figure 4, d and e , the penalty probability of the driver can be calculated by $(T_{ij}^{dps} - l_{j}^{p}) / (T_{ij}^{dps} - T_{ij}^{dpf})$ . In the case of Figure 4f, that is, $e_{j}^{p} < l_{j}^{p} < T_{ij}^{dpf} < T_{ij}^{dps}$ , it can be seen that the penalty probability of the driver is one.

Thus, the value of $ρ_{ij}^{dp}$ can be respectively calculated by:

\begin{matrix} ρ_{ij}^{dp} = {\begin{matrix} 0, T_{ij}^{dpf} < T_{ij}^{dps} < l_{j}^{p} \\ (T_{ij}^{dps} - l_{j}^{p}) / (T_{ij}^{dps} - T_{ij}^{dpf}), T_{ij}^{dpf} < l_{j}^{p} \leq T_{ij}^{dps} \\ 1, l_{j}^{p} \leq T_{ij}^{dpf} < T_{ij}^{dps} \end{matrix} \\ i = 1, 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n . \end{matrix},

(6)

Similar to the analysis of the pickup stage, in the delivery stage and arrival at destination stage, there are also six position relationships between the expected time and time requirement of delivery tasks. The values of $ρ_{j}^{pp}$ and $ρ_{ij}^{pd}$ can be estimated by:

\begin{matrix} ρ_{j}^{pp} = {\begin{matrix} 0, T_{j}^{ppf} < T_{j}^{pps} < l_{j}'^{p} \\ (T_{j}^{pps} - l_{j}'^{p}) / (T_{j}^{pps} - T_{j}^{ppf}), T_{j}^{ppf} < l_{j}'^{p} \leq T_{j}^{pps} \\ 1, l_{j}'^{p} \leq T_{j}^{ppf} < T_{j}^{pps} \end{matrix} \\ i = 1, 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n . \end{matrix},

(7)

\begin{matrix} ρ_{ij}^{pd} = {\begin{matrix} 0, T_{ij}^{pdf} < T_{ij}^{pds} < {l'}_{i} \\ (T_{ij}^{pds} - {l'}_{i}) / (T_{ij}^{pds} - T_{ij}^{pdf}), T_{ij}^{pdf} < {l'}_{i} \leq T_{ij}^{pds} \\ 1, {l'}_{i} \leq T_{ij}^{pdf} < T_{ij}^{pds} \end{matrix} \\ i = 1, 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n . \end{matrix},

(8)

According to the penalty probabilities $ρ_{ij}^{dp}$ , $ρ_{j}^{pp}$ and $ρ_{ij}^{pd}$ , the total expected penalty cost by which driver $d_{i}$ implements the delivery tasks $p_{j}$ can be represented by:

g_{ij} = α (ρ_{ij}^{dp} + ρ_{j}^{pp} + ρ_{ij}^{pd}), i = 1, 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n,

(9)

where $g_{ij}$ is the total expected penalty cost by which driver $d_{i}$ implements the delivery task $p_{j}$ ; $α$ is the penalty that the platform should pay if the driver $d_{i}$ does not complete the delivery task $p_{j}$ on time. As for the determination of departure time $t_{ij}$ , an optimization model is set up as follows:

\begin{matrix} min g_{ij} = α (ρ_{ij}^{dp} + ρ_{j}^{pp} + ρ_{ij}^{pd}), \\ i = 1, 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n, \\ s . t . t_{ij} \geq e_{i} \end{matrix},

(10a)

\begin{matrix} ρ_{ij}^{dp} = {\begin{matrix} 0, T_{ij}^{dpf} < T_{ij}^{dps} < l_{j}^{p} \\ (T_{ij}^{dps} - l_{j}^{p}) / (T_{ij}^{dps} - T_{ij}^{dpf}), T_{ij}^{dpf} < l_{j}^{p} \leq T_{ij}^{dps} \\ 1, l_{j}^{p} \leq T_{ij}^{dpf} < T_{ij}^{dps} \end{matrix} \\ i = 1, 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n, \end{matrix},

(10b)

\begin{matrix} ρ_{j}^{pp} = {\begin{matrix} 0, T_{j}^{ppf} < T_{j}^{pps} < l_{j}'^{p} \\ (T_{j}^{pps} - l_{j}'^{p}) / (T_{j}^{pps} - T_{j}^{ppf}), T_{j}^{ppf} < l_{j}'^{p} \leq T_{j}^{pps} \\ 1, l_{j}'^{p} \leq T_{j}^{ppf} < T_{j}^{pps} \end{matrix} \\ i = 1, 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n, \end{matrix},

(10c)

\begin{matrix} ρ_{ij}^{pd} = {\begin{matrix} 0, T_{ij}^{pdf} < T_{ij}^{pds} < {l'}_{i} \\ (T_{ij}^{pds} - {l'}_{i}) / (T_{ij}^{pds} - T_{ij}^{pdf}), T_{ij}^{pdf} < {l'}_{i} \leq T_{ij}^{pds} \\ 1, {l'}_{i} \leq T_{ij}^{pdf} < T_{ij}^{pds} \end{matrix} \\ i = 1, 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n . \end{matrix},

(10d)

According to the model, the optimal $t_{ij}$ can be determined, $i = 1, 2, \dots, m_{1} + m_{2}$ , $j = 1, 2, \dots, n$ . On this basis, the expected penalty cost $g_{ij}$ can be estimated and the expected penalty cost matrix $G = [g_{ij}]_{(m_{1} + m_{2}) \times n}$ can be constructed.

Constructing and Solving the Optimization Matching Model

According to the transportation cost matrix $C = [c_{ij}]_{(m_{1} + m_{2}) \times n}$ and expected penalty cost matrix $G = [g_{ij}]_{(m_{1} + m_{2}) \times n}$ , the optimization matching model of the crowdsourced delivery platform considering uncertain transportation duration can be constructed. Let $X = [x_{ij}]_{(m_{1} + m_{2}) \times n}$ denote the decision matrix for matching drivers and delivery tasks, where $x_{ij} = 1$ represents that the driver $d_{i}$ is matched with the delivery task $p_{j}$ ; otherwise, $x_{ij} = 0$ , $i = 1, 2, \dots, m_{1} + m_{2}$ , $j = 1, 2, \dots, n$ . Then, the optimization matching model considering uncertain transportation duration can be constructed, that is,

min Z = \sum_{i = 1}^{m_{1} + m_{2}} \sum_{j = 1}^{n} c_{ij} x_{ij} + \sum_{i = 1}^{m_{1} + m_{2}} \sum_{j = 1}^{n} g_{ij} x_{ij},

(11a)

s . t . \sum_{j = 1}^{n} x_{ij} \leq 1, i = 1, 2, \dots, m_{1} + m_{2},

(11b)

\sum_{i = 1}^{m_{1} + m_{2}} x_{ij} = 1, j = 1, 2, \dots, n,

(11c)

x_{ij} = 0 or 1, i = 1, 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n, .

(11d)

In the model, Equation 11a is the objective function to minimize the sum of the transportation costs and expected penalty costs of the matching between drivers and delivery tasks. Constraint 11b is to guarantee that no more than one delivery task is completed by each crowdsourced driver and dedicated driver; constraint 11c is to guarantee that each delivery task is matched with one of the crowdsourced drivers or dedicated drivers. Obviously, the optimization matching model, that is, Equation 11, can be solved by the Hungarian method ( 35 ), and the matching between crowdsourced drivers and dedicated drivers can be determined.

Rolling Procedure for Matching Crowdsourced Drivers and Delivery Tasks in Data Refreshing Environment

It should be noted that the matching between crowdsourced drivers and delivery tasks is carried out in a data refreshing environment. In other words, the crowdsourced delivery platform may receive new delivery applications and new delivery tasks from crowdsourced drivers and senders at any time ( 38 ). To solve the problem in a data refreshing environment, this section proposes a rolling procedure to match crowdsourced drivers and delivery tasks in a data refreshing environment based on the proposed model.

The rolling procedure framework has been widely used and has been estimated as an effective method for decision making in dynamic environments (39 –42), such as dynamic pricing (43 –45), dynamic inventory management (46, 47) and the dynamic routing problem (40, 48). By optimizing decisions based on the data at the current time and repeating the optimization process when the data is refreshed, the rolling procedure can reduce the complexity of dynamic problems effectively. Thus, the rolling procedure can also be used to solve the matching between crowdsourced drivers and delivery tasks in a data refreshing environment.

The main idea of the rolling procedure is vividly shown in Figure 5. It can be seen from Figure 5 that the rolling procedure can be divided into six stages. A brief description of each stage is given below.

Stage 1: Confirm the information of present delivery applications and delivery tasks, that is, delivery application information $o_{i}$ , $b_{i}$ , $e_{i}$ , $l'_{i}$ and delivery task information $o_{j}^{p}$ , $b_{j}^{p}$ , $e_{j}^{p}$ , $l_{j}^{p}$ , $e_{j}'^{p}$ , $l_{j}'^{p}$ , $i = 1, 2, \dots, m_{1} + m_{2}$ , $j = 1, 2, \dots, n$ ;

Stage 2: Determine the matching plan between drivers and delivery tasks using the proposed model, that is, $X = [x_{ij}]_{(m_{1} + m_{2}) \times n}$ ;

Stage 3: Determine the first departure time which is the departure time of the first driver to implement the delivery task according to the matching plan determined in Stage 2, that is, $t_{ij}^{min} = min {t_{ij} | x_{ij} = 1, i = 1, 2, \dots, m_{1} + m_{2}, j = 1, 2, \dots, n}$ ;

Stage 4: If the platform receives a new delivery application or delivery task before the first departure time based on the real-time information, then discard the current matching plan and go to Stage 1; otherwise, go to Stage 5;

Stage 5: Let the driver whose departure time is the first departure time implement the corresponding delivery task;

Stage 6: Delete the driver and delivery task that has been implemented, and go to Stage 1.

Figure 5.

Rolling procedure for matching crowdsourced drivers and delivery tasks in a data refreshing environment.

By the proposed procedure, the problem of matching crowdsourced drivers and delivery tasks in a data refreshing environment can be solved based on the proposed model. The obtained matching results can support the operation of the crowdsourced delivery platform.

It is necessary to point out that the above real-time rolling strategy is proposed based on the assumption that the drivers could receive the information about the assigned tasks from the platform at any time. In some practical situations, however, the assumption may not be satisfied since it will need the drivers to keep sustain attentions to the messages or announcements of the platform. In these situations, the periodic rolling strategy can be adopted as a substitute. Some discussion about the differences between the real-time rolling strategy and the periodic rolling strategy is given below.

The frequency of data refreshing and matching plan recalculating.

In the real-time rolling strategy, when the platform receives new delivery applications or delivery tasks, the data is refreshed and the matching plan is recalculated according to the refreshed data. In the periodic review rolling strategy, the data is refreshed and the matching plan is recalculated at the specific time points with regular intervals. Compared with the real-time rolling strategy, although the periodic rolling strategy usually cannot achieve the optimal assignment results theoretically, it is easier for drivers to receive information and query tasks. The specific time points for data refreshing can be determined according to the characteristics of crowdsourced delivery, such as the number of delivery tasks, the number of crowdsourced drivers and the time requirements of the senders.

2. The cut-off time for the assignment.

In the real-time rolling strategy, the platform determines the matching plan based on the real-time information and backward deduces the first departure time. In this case, the cut-off time for the assignment is the first departure time, which means that the platform can continue to receive the new information and refresh the matching plan before the drivers with the first departure time depart. In the periodic rolling strategy, the platform refreshes the data and determines the matching plan at the preset specific time, and then informs the drivers whose departure times are before the next refreshing time about their delivery tasks. Therefore, in the periodic rolling strategy, the cut-off time for the assignment is the preset specific time of data refreshing.

3. Discarding the matching plan

In the real-time rolling strategy, drivers do not receive the related information about the matching plan before the cut-off time (that is, the first departure time). Thus, if the platform receives new information (new delivery applications or new delivery tasks), then the new matching plan is recalculated according to the new information and the original matching plan can be totally discarded. In the periodic rolling strategy, the platform will send the related information to the drivers whose departure times are before the next refreshing time at the time of data refreshing. Therefore, the matching plan about the drivers who have received the delivery information will not be discarded.

Heuristic Algorithm for Combining Multiple Delivery Tasks to Solve the One-to-Many Matching Problem

According to the proposed model and the rolling procedure, the problem of matching crowdsourced drivers and delivery tasks can be solved by determining one-to-one matching. However, in some practical scenarios, to provide service to more senders or gain more profit, the one-to-many matching problem should be considered. To solve the one-to-many matching problem, in this section, a heuristic algorithm is proposed for combining multiple delivery tasks as a new delivery task. Then, the one-to-many matching problem is transformed into the one-to-one matching problem which can be solved by the above proposed model. The flow chart of the heuristic algorithm is shown in Figure 6. The specific description of each step in the heuristic algorithm is given below.

Step 1: Input initial delivery task information

Input the set of initial delivery task, $P = {p_{1}, p_{2}, \dots, p_{n}}$ , and the delivery task information (including the origin and destination of delivery task, the earliest and latest pickup time, the earliest and latest delivery time), that is, $o_{j}^{p}$ , $b_{j}^{p}$ , $e_{j}^{p}$ , $l_{j}^{p}$ , $e_{j}'^{p}$ , $l_{j}'^{p}$ , $j = 1, 2, \dots, n$ .

Step 2: Calculate the time compatibility for combining any two delivery tasks

Let $\tilde{E} = [{\tilde{ε}}_{j j'}]_{n \times n}$ denote the time compatibility matrix, where ${\tilde{ε}}_{j j'}$ denotes the time compatibility for combining delivery tasks $p_{j}$ to $p_{j'}$ . Time compatibility ${\tilde{ε}}_{j j'}$ represents the possibility of simultaneously satisfying the time requirements of tasks $p_{j}$ and $p_{j'}$ when combining the delivery tasks. For calculating ${\tilde{ε}}_{j j'}$ , six possible logical relationships about $o_{j}^{p}$ , $b_{j}^{p}$ , $o_{j'}^{p}$ and $b_{j'}^{p}$ representing six feasible delivery schemes for tasks $p_{j}$ and $p_{j'}$ should be considered, which are shown in Figure 7. It can be seen that for each feasible delivery scheme in Figure 7, three kinds of sub-time compatibilities between origins and destinations need to be considered. Let $k$ denote the index of the kth feasible delivery scheme and $h$ denote the index of the hth sub-time compatibility, $k = 1, 2, \dots, 6$ , $h = 1, 2, 3$ . In Figure 7, the time intervals denote the uncertain transportation time intervals between two positions. For example, ${\overset{⌣}{t}}_{j j^{'}}^{k h} = [{\tilde{t}}_{j j^{'}}^{khf}, {\tilde{t}}_{j j^{'}}^{k h s}]$ denotes the uncertain transportation time interval of the hth sub-time compatibility in the kth feasible delivery scheme, where ${\tilde{t}}_{jj'}^{khf}$ is the fastest transportation time and ${\tilde{t}}_{jj'}^{kh s}$ is the slowest transportation time.

Figure 6.

Flow chart of the heuristic algorithm for combining delivery tasks.

Figure 7.

Six possible logical relationships about $o_{j}^{p}$ , $b_{j}^{p}$ , $o_{j'}^{p}$ and $b_{j'}^{p}$ .

In Figure 7, the solid line indicates the link between the origin and destination of the same delivery task and the dashed line indicates the link between the origin and destination of different delivery tasks. It is the default setting that the time requirements between the origin and destination of the same delivery task are compatible. Thus, the sub-time compatibility between the origin and destination of the same delivery task is one. However, the time compatibility between the origin and destination of the different delivery tasks need to be calculated.

Taking feasible delivery scheme 1 as an example, in feasible delivery scheme 1 there is a sub-time compatibility that needs to be calculated, that is, $k = 1$ and $h = 2$ . For calculating the sub-time compatibility, let ${\overset{⌣}{t}}_{j j^{'}}^{12} = [{\tilde{t}}_{j j^{'}}^{12 f}, {\tilde{t}}_{j j^{'}}^{12 s}]$ denote the uncertain transportation time intervals from $b_{j}^{p}$ to $o_{j'}^{p}$ . Since the earliest and latest departure times from $b_{j}^{p}$ are $e_{j}'^{p}$ and ${l'}_{j}^{p}$ , the expected arrival time of $o_{j'}^{p}$ can be represented by:

{\overset{⌣}{T}}_{j j^{'}}^{12} = [{\tilde{T}}_{j j^{'}}^{12 f}, {\tilde{T}}_{j j^{'}}^{12 s}] = [{e^{'}}_{j}^{p} + {\tilde{t}}_{j j^{'}}^{12 f}, {l^{'}}_{j}^{p} + {\tilde{t}}_{j j^{'}}^{12 s}], j \neq j^{'} .

(12)

Then, let $ρ_{j j'}^{kh}$ denote the penalty probability of the hth sub-time compatibility in the kth feasible delivery scheme, $k = 1, 2, \dots, 6$ , $h = 1, 2, 3$ . To calculate $ρ_{j j'}^{12}$ , according to the expected arrival time ${\overset{⌣}{T}}_{j j^{'}}^{12} = [{\tilde{T}}_{j j^{'}}^{12 f}, {\tilde{T}}_{j j^{'}}^{12 s}]$ and the time requirement $e_{j'}^{p}$ and $l_{j'}^{p}$ , the penalty probability $ρ_{j j'}^{12}$ can be estimated by:

ρ_{j j'}^{12} = {\begin{matrix} 0, {\tilde{T}}_{j j'}^{12 f} < {\tilde{T}}_{j j'}^{12 s} < l_{j'}^{p} \\ ({\tilde{T}}_{j j'}^{12 s} - l_{j'}^{p}) / ({\tilde{T}}_{j j'}^{12 s} - {\tilde{T}}_{j j'}^{12 f}), {\tilde{T}}_{j j'}^{12 f} < l_{j'}^{p} \leq {\tilde{T}}_{j j'}^{12 s} \\ 1, l_{j'}^{p} \leq {\tilde{T}}_{j j'}^{12 f} < {\tilde{T}}_{j j'}^{12 s} \end{matrix}, j \neq j' .

(13)

Therefore, let ${\tilde{ρ}}_{j j'}^{kh}$ denote the hth sub-time compatibility in the kth feasible delivery scheme, the sub-time compatibility ${\tilde{ρ}}_{j j'}^{kh}$ can be represented by:

{\tilde{ρ}}_{j j'}^{kh} = 1 - ρ_{j j'}^{kh}, j \neq j', k = 1, 2, \dots, 6, h = 1, 2, 3 .

(14)

With a similar approach, the sub-time compatibility in the six feasible delivery schemes can be calculated. Let ${\tilde{τ}}_{jj'}^{k}$ denote the time compatibility for combining delivery tasks $p_{j}$ to $p_{j'}$ based on the kth feasible delivery scheme. Then, according to the principle of probability theory, the time compatibility for combining delivery tasks $p_{j}$ to $p_{j'}$ based on different feasible delivery schemes can be estimated, that is,

{\tilde{τ}}_{jj'}^{k} = Π_{h = 1}^{3} {\tilde{ρ}}_{j j'}^{kh}, j \neq j', k = 1, 2, \dots, 6,

(15)

Further, since only one feasible delivery scheme should be selected from the six different feasible delivery schemes, we define ${\tilde{ε}}_{j j'} = max {{\tilde{τ}}_{jj'}^{1}, {\tilde{τ}}_{jj'}^{2}, \dots, {\tilde{τ}}_{jj'}^{6}}$ , $j \neq j'$ . In addition, since the same delivery task cannot be combined to itself, we define ${\tilde{ε}}_{j j} = 0$ . On this basis, the time compatibility matrix $\tilde{E} = [{\tilde{ε}}_{j j'}]_{n \times n}$ for combining any two delivery tasks can be constructed.

Step 3: Judgment (Whether there exists a time compatible task pair?)

If all elements in matrix $\tilde{E}$ are zero, that is, ${\tilde{ε}}_{j j'} = 0$ , then there is no task pair that satisfies the time requirements after they are combined together. In this case, go to Step 8. Otherwise, go to Step 4.

Step 4: Calculate the cost saving for the feasible combining tasks

For ${\tilde{τ}}_{jj'}^{k} > 0$ , let ${\tilde{s}}_{jj'}^{k}$ denote the total distance for completing the delivery tasks $p_{j}$ and $p_{j'}$ based on the kth feasible delivery scheme. It can be seen from Figure 7 that ${\tilde{s}}_{jj'}^{k}$ is composed of three distances. For example, in feasible delivery scheme 1, ${\tilde{s}}_{jj'}^{k}$ is composed of the distance from $o_{j}^{p}$ to $b_{j}^{p}$ , the distance from $b_{j}^{p}$ to $o_{j'}^{p}$ and the distance from $o_{j'}^{p}$ to $b_{j'}^{p}$ . Thus, the transportation cost of the kth feasible delivery scheme for completing the delivery tasks $p_{j}$ and $p_{j'}$ can be represented by:

{\tilde{c}}_{jj'}^{k} = c_{0} + ϕ_{1} {\tilde{s}}_{jj'}^{k}, j \neq j',

(16)

where $c_{0}$ is the basic cost per delivery. Further, the saving cost for completing the delivery tasks $p_{j}$ and $p_{j'}$ based on the kth feasible delivery scheme can be represented by:

{\tilde{Λ}}_{jj'}^{k} = (2 c_{0} + ϕ_{1} S_{j}^{pp} + ϕ_{1} S_{j'}^{pp}) - (c_{0} + {\tilde{c}}_{jj'}^{k} + {\tilde{g}}_{jj'}^{k}), j \neq j',

(17)

In Equation 17, $(2 c_{0} + ϕ_{1} S_{j}^{pp} + ϕ_{1} S_{j'}^{pp})$ represents the total cost for delivering tasks $p_{j}$ and $p_{j'}$ when they are not combined; $(c_{0} + {\tilde{c}}_{jj'}^{k} + {\tilde{g}}_{jj'}^{k})$ represents the total cost for delivering tasks $p_{j}$ and $p_{j'}$ when they are combined, where ${\tilde{g}}_{jj'}^{k}$ is the expected penalty cost for completing the delivery tasks $p_{j}$ and $p_{j'}$ can be estimated by:

{\tilde{g}}_{jj'}^{k} = \sum_{h = 1}^{3} α ρ_{j j'}^{kh}, j \neq j' .

(18)

Step 5: Judgment (Whether the cost savings of all feasible combining tasks are no more than zero?)

For ${\tilde{τ}}_{jj'}^{k} > 0$ , if ${\tilde{Λ}}_{jj'}^{k} \leq 0$ , then there is no task pair that can save the delivery cost after they are combined together. In this case, go to Step 8; otherwise, let ${\tilde{Λ}}_{jj'}^{k^{*}} = max {{\tilde{Λ}}_{jj'}^{k} | p_{j}, p_{j'} \in P}$ , go to Step 6.

Step 6: Determining the combining task and updating the delivery task information

Let $p_{j}$ and $p_{j'}$ denote the delivery tasks with the saving cost ${\tilde{Λ}}_{jj'}^{k^{*}}$ . For combining $p_{j}$ and $p_{j'}$ , let $p^{*}$ denote a new delivery task generated by combining the $p_{j}$ and $p_{j'}$ . Let $o^{p^{*}}$ , $b^{p^{*}}$ , $e^{p^{*}}$ , $l^{p^{*}}$ , ${e'}^{p^{*}}$ , ${l'}^{p^{*}}$ denote the related information of task $p^{*}$ , that is, the origin and destination, the earliest and latest pickup time, the earliest and latest delivery time of task $p^{*}$ , respectively. The delivery task information of $p^{*}$ can be determined according to the delivery information of tasks $p_{j}$ and $p_{j'}$ , and the feasible delivery scheme with the maximum saving cost ${\tilde{Λ}}_{jj'}^{k^{*}}$ . Table 1 shows the delivery information of task $p^{*}$ based on different feasible delivery schemes. For example, if the new delivery task $p^{*}$ is derived by combining $p_{j}$ and $p_{j'}$ based on the first feasible delivery scheme (that is, the second column), then $o^{p^{*}} = o_{j}^{p}$ , $b^{p^{*}} {= b}_{j'}^{p}$ , $e^{p^{*}} = e_{j}^{p}$ , $l^{p^{*}} {= l}_{j}^{p}$ , ${e'}^{p^{*}} = e {'_{j'}}^{p}$ , ${l'}^{p^{*}} {= l'}_{j'}^{p}$ .

Table 1.

Delivery Task Information in Different Feasible Delivery Schemes

	Feasible delivery scheme
Related information of task $p^{*}$	1st	2nd	3rd	4th	5th	6th
$o^{p^{*}}$	$o_{j}^{p}$	$o_{j}^{p}$	$o_{j}^{p}$	$o_{j'}^{p}$	$o_{j'}^{p}$	$o_{j'}^{p}$
$b^{p^{*}}$	$b_{j'}^{p}$	$b_{j'}^{p}$	$b_{j}^{p}$	$b_{j'}^{p}$	$b_{j}^{p}$	$b_{j}^{p}$
$e^{p^{*}}$	$e_{j}^{p}$	$e_{j}^{p}$	$e_{j}^{p}$	$e_{j'}^{p}$	$e_{j'}^{p}$	$e_{j'}^{p}$
$l^{p^{*}}$	$l_{j}^{p}$	$l_{j}^{p}$	$l_{j}^{p}$	$l_{j'}^{p}$	$l_{j'}^{p}$	$l_{j'}^{p}$
$e'^{p^{*}}$	$e {'_{j'}}^{p}$	$e {'_{j'}}^{p}$	$e {'_{j}}^{p}$	$e {'_{j'}}^{p}$	$e {'_{j}}^{p}$	$e {'_{j}}^{p}$
${l'}^{p^{*}}$	${l'}_{j'}^{p}$	${l'}_{j'}^{p}$	${l'}_{j}^{p}$	${l'}_{j'}^{p}$	${l'}_{j}^{p}$	${l'}_{j}^{p}$

Step 7: Judgment (Is the requirement of the decision maker satisfied?)

In the operation of the crowdsourcing platform, the decision maker may formulate different operational requirements. For example, to improve the participation positivity of crowdsourcing drivers and ensure the probability of crowdsourcing drivers receiving delivery tasks, decision makers may require combining only when the number of delivery tasks is greater than the number of crowdsourcing drivers. Therefore, a step for judging whether the requirement of the decision maker is satisfied is necessary. If the requirement of the decision maker is satisfied, go to step 8; otherwise, return to step 2.

Step 8: Stop and output the delivery task information

By the proposed heuristic algorithm, the delivery task information which contains combining delivery tasks can be obtained. The matching between delivery tasks and drivers can then be solved based on the proposed model.

It is necessary to point out that the main idea of the heuristic algorithm is to determine the combining tasks by calculating the time compatibility and the cost saving for feasible combining of delivery tasks. It means that the combining of tasks determined by this algorithm must be feasible and the total cost must be decreased. On the other hand, the problem of the one-to-many matching is very complex even if the transportation duration is certain. In this study, uncertain transportation duration is considered, which makes the problem more complicated. Thus, it is difficult to present an exact algorithm that can obtain the optimal solution of combining tasks. Therefore, the proposed heuristic algorithm can be regarded as an acceptable and effective alternative for combining tasks.

Case Study and Comparison

In this section, to illustrate the implementation procedure and validity of the proposed matching strategy, a case study is conducted for a crowdsourced delivery platform that matches crowdsourced drivers and delivery tasks. Then, to further illustrate the importance of the consideration of uncertain transportation durations and the contribution of the proposed matching strategy, a comparison is given. Since the main focus is on the consideration of uncertain transportation duration in crowdsourced delivery, the case study is mainly conducted for matching crowdsourced drivers and delivery tasks considering uncertain transportation duration in a static data environment based on the proposed model.

Case Study

Consider a time point in the operation of the crowdsourced delivery platform in S city. There are 23 drivers (comprised of 20 crowdsourced drivers and three dedicated drivers) and 20 delivery tasks, which are denoted as $D = {d_{1}, d_{2}, \dots, d_{20}, d_{21}, d_{22}, d_{23}}$ , where $d_{1}, d_{2}, \dots, d_{20}$ are 20 crowdsourced drivers and $d_{21}, d_{22}, d_{23}$ are three dedicated drivers, and $P = {p_{1}, p_{2}, \dots, p_{20}}$ . The origins and destinations of crowdsourced drivers and delivery tasks are shown in Figure 8. The time requirements of crowdsourced drivers and delivery tasks are shown in the supplemental material.

Figure 8.

Map of case study city showing origins and destinations of crowdsourced drivers and delivery tasks.

To determine an optimal match between drivers and delivery tasks, the proposed model for matching drivers and delivery tasks considering uncertain transportation duration in a static data environment is used. The process, in detail, has three parts and which are described as follows.

Determination of the transportation cost matrix of drivers concerning different delivery tasks.

According to the origins and destinations of drivers and delivery tasks, from the transportation routes that each driver implements different delivery tasks can be determined. Then, three transportation distance matrices $S^{dp} = [S_{ij}^{dp}]_{23 \times 20}$ , $S^{pp} = [S_{j}^{pp}]_{23 \times 20}$ and $S^{pd} = [S_{ij}^{pd}]_{23 \times 20}$ with respect to the pickup stage, delivery stage and arrival at destination stage can be constructed, as shown in the supplemental material. Here, $c_{0} = 0$ , $ϕ_{1} = 1$ , $ϕ_{2} = 2$ . According to Equations 1 and 2, the transportation cost matrix $C = [c_{ij}]_{23 \times 20}$ is obtained, as shown in the supplemental material.

2. Determination of the expected penalty cost matrix of drivers concerning different delivery tasks.

According to the obtained pickup, delivery and arrival at destination distance matrices, the uncertain transportation duration intervals with respect to the pickup stage, delivery stage and arrival at destination stage, that is, ${\hat{t}}_{ij}^{dp} = [t_{ij}^{dpf}, t_{ij}^{dps}]$ , ${\hat{t}}_{j}^{pp} = [t_{j}^{ppf}, t_{j}^{pps}]$ and ${\hat{t}}_{ij}^{pd} = [t_{ij}^{pdf}, t_{ij}^{pds}]$ can be determined as shown in the supplemental material: $i = 1, 2, \dots, 23$ , $j = 1, 2, \dots, 20$ . According to Equations 3 to 5, the expected times of drivers to implement delivery tasks in the pickup stage, delivery stage and arrival at destination stage can be estimated. Then, based on the time requirements of crowdsourced drivers and delivery tasks and the above expected times, the penalty probability $ρ_{ij}^{dp}$ , $ρ_{j}^{pp}$ and $ρ_{ij}^{pd}$ can be obtained according to Equations 6 to 8, $i = 1, 2, \dots, 23$ , $j = 1, 2, \dots, 20$ .

Let $α = 10$ . According to Equation 9, the total expected penalty costs when drivers implement the delivery tasks are obtained, and the expected penalty cost matrix $G = [g_{ij}]_{23 \times 20}$ can be determined, which is shown in the supplemental material.

3. Constructing and solving the optimization matching model.

According to the transportation cost matrix of drivers $C = [c_{ij}]_{23 \times 20}$ and the expected penalty cost matrix of drivers $G = [g_{ij}]_{23 \times 20}$ , the optimization matching model can be built, that is,

min Z = \sum_{i = 1}^{23} \sum_{j = 1}^{20} c_{ij} x_{ij} + \sum_{i = 1}^{23} \sum_{j = 1}^{20} g_{ij} x_{ij},

(19a)

s . t . \sum_{j = 1}^{20} x_{ij} \leq 1, i = 1, 2, \dots, 23,

(19b)

\sum_{i = 1}^{23} x_{ij} = 1, j = 1, 2, \dots, 20,

(19c)

x_{ij} = 0 or 1, i = 1, 2, \dots, 23, j = 1, 2, \dots, 20, .

(19d)

The optimization matching model can be solved by the Hungarian method ( 35 ). Table 2 shows the decision matrix $X = [x_{ij}]_{23 \times 20}$ of the optimization matching model. By reference to Table 2, the optimization matching results between drivers and delivery tasks and the departure times of drivers can be determined. According to the decision matrix $X = [x_{ij}]_{23 \times 20}$ , the departure times of drivers are shown in Table 3.

Table 2.

Decision Matrix $X = [x_{ij}]_{23 \times 20}$ of the Optimization Matching Model

	$p_{1}$	$p_{2}$	$p_{3}$	$p_{4}$	$p_{5}$	$p_{6}$	$p_{7}$	$p_{8}$	$p_{9}$	$p_{10}$	$p_{11}$	$p_{12}$	$p_{13}$	$p_{14}$	$p_{15}$	$p_{16}$	$p_{17}$	$p_{18}$	$p_{19}$	$p_{20}$
$d_{1}$	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{2}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
$d_{3}$	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
$d_{4}$	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{5}$	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{6}$	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{7}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
$d_{8}$	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{9}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{10}$	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
$d_{11}$	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
$d_{12}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
$d_{13}$	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{14}$	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{15}$	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
$d_{16}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
$d_{17}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
$d_{18}$	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
$d_{19}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
$d_{20}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{21}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{22}$	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
$d_{23}$	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0

Table 3.

Departure Times of Drivers

d_{i}

d_{1}

d_{2}

d_{3}

d_{4}

d_{5}

d_{6}

d_{7}

d_{8}

d_{9}

d_{10}

d_{11}

d_{12}

t_{ij}

07:30

07:26

07:20

08.08

07:54

08:40

08:14

07:00

08:20

08:40

07:50

d_{i}

d_{13}

d_{14}

d_{15}

d_{16}

d_{17}

d_{18}

d_{19}

d_{20}

d_{21}

d_{22}

d_{23}

t_{ij}

08:00

07:54

08:20

08:30

07:40

07:50

09:00

07:33

07:37

Note: NA = not available.

According to the departure times of drivers, the first departure time is determined, that is, $t_{ij}^{min} = min {t_{ij} | x_{ij} = 1, i = 1, 2, \dots, 23, j = 1, 2, \dots, 20} = 07$ :00. If the platform receives a new delivery application or delivery task before the first departure time, that is, 07:00, then a refreshed matching result between crowdsourced drivers and delivery tasks should be determined according to the refreshed data, and a refreshed first departure time can be obtained; otherwise, the driver $d_{8}$ will implement delivery task $p_{4}$ at the first departure time.

By implementing proposed matching strategy, the matching result of the drivers and delivery tasks in a data refreshing environment can be obtained. Then, according to the matching result, the decision maker of the crowdsourced platform can assign the delivery tasks to the drivers. It is necessary to further illustrate that the proposed method is the first attempt to determine the matching result of the drivers and delivery tasks considering uncertain transportation duration. The proposed method has important significance and availability for guiding the decision maker in operating the crowdsourced platform in cities with serious traffic congestion and delay penalties.

Comparison

To further illustrate the importance of the consideration of uncertain transportation duration in the matching between drivers and delivery tasks, the results of the proposed matching strategy are compared with the matching strategy that does not consider uncertain transportation duration. The matching results that consider uncertain transportation duration are determined by the proposed strategy based on the data about the origins, destinations and time requirements of drivers and delivery tasks provided by drivers and senders. The matching strategy that does not consider uncertain transportation duration is also determined by the similar procedure in the proposed model. In the matching strategy that does not consider uncertain transportation duration, it is assumed that the available times of drivers are no longer the ranges of uncertain transportation time intervals, where the available times of drivers are the expected times for drivers to implement delivery tasks. The available times of drivers are represented by exact numbers. We convert the available times of drivers from the uncertain transportation time interval (that is, [earliest time, latest time]) to an exact number according to the transportation distance obtained in the proposed strategy and the average speed in the transportation that considers uncertain transportation duration.

The expected times (in the form of crisp numbers) of drivers implementing delivery tasks that do not consider uncertain transportation duration in the three transportation stages, ${\bar{t}}_{ij}^{dp}$ , ${\bar{t}}_{ij}^{p p}$ and ${\bar{t}}_{ij}^{pd}$ are shown in the supplemental material, $i = 1, 2, \dots, 23$ , $j = 1, 2, \dots, 20$ . Based on the time requirements of crowdsourced drivers, delivery tasks and expected times that do not consider uncertain transportation duration, the penalty probabilities ${\bar{ρ}}_{ij}^{dp}$ , ${\bar{ρ}}_{j}^{pp}$ and ${\bar{ρ}}_{ij}^{pd}$ in three transportation stages can be obtained respectively. In each of the transportation stages, if a driver can complete the delivery task before the latest time requirement, the penalty probability is zero, otherwise, the penalty probability is one. Specifically, in the pickup stage, if the driver can pick up the package before the latest pickup time, the penalty probability ${\bar{ρ}}_{ij}^{dp} = 0$ , otherwise, the penalty probability ${\bar{ρ}}_{ij}^{dp} = 1$ , $i = 1, 2, \dots, 23$ , $j = 1, 2, \dots, 20$ . Similarly, in the delivery stage and the arrival at destination stage, if the driver can deliver the package and arrive at their own destination before the latest delivery time and latest arrival time, the penalty probability ${\bar{ρ}}_{j}^{pp} = 0$ and ${\bar{ρ}}_{ij}^{pd} = 0$ , otherwise, the penalty probability ${\bar{ρ}}_{j}^{pp} = 1$ and ${\bar{ρ}}_{ij}^{pd} = 1$ , $i = 1, 2, \dots, 23$ , $j = 1, 2, \dots, 20$ . In a similar way to the proposed matching strategy, the expected penalty cost matrix that does not consider uncertain transportation duration $\bar{G} = [{\bar{g}}_{ij}]_{23 \times 20}$ can be determined, as shown in the supplemental material.

According to the transportation cost matrix of drivers, $C = [c_{ij}]_{23 \times 20}$ , and the expected penalty cost matrix of drivers, $\bar{G} = [{\bar{g}}_{ij}]_{23 \times 20}$ , the optimization matching model that does not consider uncertain transportation duration can be built and the optimization matching result can be obtained by the Hungarian method ( 35 ). Table 4 shows the optimization matching result $\bar{X} = [{\bar{x}}_{ij}]_{23 \times 20}$ that does not consider uncertain transportation duration. It can be seen from Tables 2 to 4 that the matching result that does not consider uncertain transportation duration is different from the matching result of the proposed matching strategy.

Table 4.

Decision Matrix $\bar{X} = [{\bar{x}}_{ij}]_{23 \times 20}$ of the Optimization Matching Model

	$p_{1}$	$p_{2}$	$p_{3}$	$p_{4}$	$p_{5}$	$p_{6}$	$p_{7}$	$p_{8}$	$p_{9}$	$p_{10}$	$p_{11}$	$p_{12}$	$p_{13}$	$p_{14}$	$p_{15}$	$p_{16}$	$p_{17}$	$p_{18}$	$p_{19}$	$p_{20}$
$d_{1}$	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{2}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
$d_{3}$	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
$d_{4}$	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{5}$	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{6}$	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{7}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
$d_{8}$	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{9}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{10}$	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
$d_{11}$	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
$d_{12}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
$d_{13}$	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{14}$	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{15}$	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
$d_{16}$	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
$d_{17}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
$d_{18}$	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0
$d_{19}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
$d_{20}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
$d_{21}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{22}$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$d_{23}$	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0

The two strategies were then evaluated by calculating the total costs of the two matching results in which the actual time of the driver implementing the delivery task is randomly selected from the corresponding uncertain transportation time interval. By selecting the actual time of each driver implementing the delivery task 1,000 times repeatedly, 1,000 total costs of the two matching results can be obtained and the moving average total costs of the two results can be obtained. Figure 9 shows the comparison of moving average total costs for the two matching strategies, where $Z^{A}$ denotes the moving average total costs for the proposed matching strategy, and ${\bar{Z}}^{A}$ denotes the moving average total costs for the matching strategy that does not consider uncertain transportation duration. It can be seen that, compared with the matching strategy that does not consider uncertain transportation duration, the proposed matching strategy has a distinct advantage of cost savings.

Figure 9.

Moving average total costs in 1,000 cases.

In Figure 10, the moving average total costs of the two matching strategies in different unit transportation costs are compared. In Figure 10, $Z_{1}^{A}$ and ${\bar{Z}}_{1}^{A}$ denote the moving average total costs of two matching strategies when $ϕ_{1} = 1$ and $ϕ_{2} = 2$ respectively; $Z_{2}^{A}$ and ${\bar{Z}}_{2}^{A}$ denote the moving average total costs of two matching strategies when $ϕ_{1} = 1.2$ and $ϕ_{2} = 2.4$ respectively; $Z_{3}^{A}$ and ${\bar{Z}}_{3}^{A}$ denote the moving average total costs of two matching strategies when $ϕ_{1} = 2$ and $ϕ_{2} = 4$ respectively. It can be seen from Figure 10 that the proposed matching strategy is still significantly superior to the matching strategy that does not consider uncertain transportation duration when the unit transportation costs are different. In addition, the reduction in costs for the proposed matching strategy increases with the unit distance transportation costs. This means that the proposed matching strategy can save more transportation costs by consideration of uncertain transportation duration. Therefore, in the market of high transportation costs, it is more advantageous to consider uncertain transportation duration and implement the proposed matching strategy for the determination of matching between crowdsourced drivers and delivery tasks.

Figure 10.

Moving average total costs in different unit distance transportation costs.

Figure 11 shows the moving average total costs of the two matching strategies in different delay penalties. In Figure 11, $Z_{4}^{A}$ and ${\bar{Z}}_{4}^{A}$ denote the moving average total costs of two matching strategies when $α = 5$ ; $Z_{5}^{A}$ and ${\bar{Z}}_{5}^{A}$ denote the moving average total costs when $α = 7$ ; $Z_{6}^{A}$ and ${\bar{Z}}_{6}^{A}$ denote the total costs when $α = 20$ . It can be seen from Figure 11 that the moving average total costs of the proposed matching strategy are less than the matching strategy that does not consider uncertain transportation duration when the parameter of delay penalty is different. More specifically, the gap between the moving average total costs of the two matching strategies is larger as the delay penalty increases. This suggests that the proposed matching strategy can make a greater cost savings than the matching strategy that does not consider uncertain transportation duration when the delay penalty is high. Therefore, when customers have a high requirement of delivery on time in the market, considering uncertain transportation duration and implementing the proposed matching strategy are more profitable to the platform. Thus, the importance of considering uncertain transportation duration and the contribution of the proposed matching strategy have been verified.

Figure 11.

Moving average total costs in different delay penalties.

In summary, the proposed matching strategy can help the decision maker of the crowdsourced platform save cost and make more profit. The proposed matching strategy can save transportation costs, reduce transportation distances and reduce emissions. Therefore, the implementation of the matching strategy considering uncertain transportation duration should be encouraged. Furthermore, the proposed matching strategy can reduce the penalty cost. Especially in cities with serious traffic congestion and delay penalties, where customers have high requirement of delivery on time, the proposed matching strategy can save penalty cost and increase customer satisfaction more effectively.

Conclusions

The matching of crowdsourced drivers and delivery tasks is an important research topic with practical application background in the operation of crowdsourced delivery platforms. Although several studies on matching crowdsourced drivers and delivery tasks have been conducted, uncertain transportation duration in crowdsourced delivery has not been considered. In this paper, a new model-based rolling matching strategy is proposed to match crowdsourced drivers and delivery tasks considering uncertain transportation duration. First, a model for matching crowdsourced drivers and delivery tasks considering uncertain transportation duration in a static data environment is proposed. On this basis, a procedure is given for solving the problem in a data refreshing environment based on the model in a static data environment. Moreover, a heuristic algorithm is presented for combining multiple delivery tasks to solve the one-to-many matching. The major contributions of this paper are summarized as follows.

First, this paper refines a noteworthy research problem, that is, the problem of matching crowdsourced drivers and delivery tasks considering uncertain transportation duration. Although several studies on matching crowdsourced drivers and delivery tasks have been conducted, uncertain transportation duration in crowdsourced delivery has not been considered. The consideration of uncertain transportation duration overcomes the limitations of the results obtained by the existing methods that cannot meet the time requirements of senders, and lays a good foundation for conducting further studies.

Second, to solve the problem, a model-based rolling matching strategy is proposed, which can be described as three parts, that is: (i) a model for matching crowdsourced drivers and delivery tasks considering uncertain transportation duration in a static data environment; (ii) a rolling procedure for matching crowdsourced drivers and delivery tasks in a data refreshing environment based on the proposed model; (iii) a heuristic algorithm that is presented to solve the one-to-many matching by combining multiple delivery tasks. The proposed rolling strategy and heuristic algorithm provide new ideas for dealing with similar problems in a data refreshing environment.

Third, this paper presents formulas for estimating the penalty probability and expected penalty costs of a crowdsourced delivery platform considering uncertain transportation duration. According to the formulas, the expected penalty costs for each driver implementing different delivery tasks can be estimated. The formulas lay a good foundation to construct the optimization matching model considering uncertain transportation duration.

Fourth, to illustrate the validity and the contribution of the proposed matching strategy, this paper conducts a case study and comparison with the matching strategy that does not consider uncertain transportation duration. The results show that the proposed matching strategy has a distinct advantage of cost savings over the matching strategy that does not consider uncertain transportation duration. In addition, considering uncertain transportation duration and implementing the proposed matching strategy are more profitable to the platform in the market of high transportation costs and delay penalties.

This paper also has some limitations, which may serve as avenues for future research. First, crowdsourced drivers can deliver multiple packages in one trip within the limits of transportation capacity. Therefore, extended studies of the proposed method should be conducted considering the transportation capacity of crowdsourced drivers. Second, the crowdsourced driver may reject the delivery task matched by the crowdsourced delivery platform if the matching degree between the travel route of the crowdsourced driver and the delivery route is low. Thus, the detour preference of the crowdsourced driver can be taken as an effect factor for the matching of the crowdsourced delivery platform.

Supplemental Material

sj-docx-1-trr-10.1177_0361198120974364 – Supplemental material for Model-Based Rolling Matching Strategy for Crowdsourced Drivers and Delivery Tasks Considering Uncertain Transportation Duration

Supplemental material, sj-docx-1-trr-10.1177_0361198120974364 for Model-Based Rolling Matching Strategy for Crowdsourced Drivers and Delivery Tasks Considering Uncertain Transportation Duration by Qi Zhang, Yang Liu, Zhi-Ping Fan and Zong-Lin Li in Transportation Research Record

Footnotes

Acknowledgements

The authors thank the anonymous reviewers for their helpful comments and suggestions that greatly improved the presentation of the paper.

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: Yang Liu, Zhi-Ping Fan, Qi Zhang; data collection: Zong-Lin Li; analysis and interpretation of results: Yang Liu, Qi Zhang, Zhi-Ping Fan; draft manuscript preparation: Qi Zhang, Yang Liu, Zhi-Ping Fan. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was partly supported by the National Natural Science Foundation of China (Project numbers 72031002 and 71771043), the Liaoning BaiQianWan Talents Program (Project number 2016921027), and the Construction Base for Introducing Talents of Discipline Innovation to Chinese Universities 111 project (B16009).

Data Accessibility Statement

No data are made available.

Supplemental Material

Supplemental material for this article is available online.

References

Mehmann

Frehe

Teuteberg

Crowd Logistics—A Literature Review and Maturity Model. Innovations and Strategies for Logistics and Supply Chains, Vol. 20, 2015, pp. 117–145.

Punel

Stathopoulos

Modeling the Acceptability of Crowdsourced Goods Deliveries: Role of Context and Experience Effects. Transportation Research Part E: Logistics and Transportation Review, Vol. 105, 2017, pp. 18–38.

Punel

Ermagun

Stathopoulos

Push and Pull Factors in Adopting a Crowdsourced Delivery System. Transportation Research Record, 2019. 2673: 529–540.

Alnaggar

Gzara

Bookbinder

J. H.

Crowdsourced Delivery: A Review of Platforms and Academic Literature. Omega, Vol. 98, 2019, p. 102139.

Huang

Ardiansyah

M. N.

A Decision Model for Last-Mile Delivery Planning with Crowdsourcing Integration. Computers & Industrial Engineering, Vol. 135, 2019, pp. 898–912.

T. V.

Stathopoulos

Van Woensel

Ukkusuri

S. V.

Supply, Demand, Operations, and Management of Crowd-Shipping Services: A Review and Empirical Evidence. Transportation Research Part C: Emerging Technologies, Vol. 103, 2019, pp. 83–103.

Arslan

A. M.

Agatz

Kroon

Zuidwijk

Crowdsourced Delivery—A Dynamic Pickup and Delivery Problem with Ad Hoc Drivers. Transportation Science, Vol. 53, No. 1, 2019, pp. 222–235.

Guo

Jaramillo

Y. J. L.

Bloemhof-Ruwaard

Claassen

G. D. H.

On Integrating Crowdsourced Delivery in Last-Mile Logistics: A Simulation Study to Quantify Its Feasibility. Journal of Cleaner Production, Vol. 241, No. 20, 2019, p. 118365.

T. V.

Ukkusuri

S. V.

Crowd-Shipping Services for Last Mile Delivery: Analysis from American Survey Data. Transportation Research Interdisciplinary Perspectives, Vol. 1, 2019, p. 100008.

10.

Miller

Nie

Stathopoulos

Crowdsourced Urban Package Delivery: Modeling Traveler Willingness to Work as Crowdshippers. Transportation Research Record, 2017. 2610: 67–75.

11.

Chen

Cheng

S. F.

Gunawan

Misra

Dasgupta

Chander

TRACCS: A Framework for Trajectory-Aware Coordinated Urban Crowd-Sourcing. Proc., 2nd AAAI Conference on Human Computation and Crowdsourcing, Pittsburgh, 2014, pp. 30–40.

12.

Mladenow

Bauer

Strauss

Crowdsourcing in Logistics: Concepts and Applications using the Social Crowd. Proc., 17th International Conference on Information Integration and Web-Based Applications & Services, Brussels, Belgium, 2015, pp. 244–251.

13.

Chen

Pan

Using the Crowd of Taxis to Last Mile Delivery in E-Commerce: A Methodological Research. In Service Orientation in Holonic and Multi-Agent Manufacturing, Springer, Cham, 2016, pp. 61–70.

14.

Paloheimo

Lettenmeier

Waris

Transport Reduction by Crowdsourced Deliveries—A Library Case in Finland. Journal of Cleaner Production, Vol. 132, 2016, pp. 240–251.

15.

Chen

Chankov

S. M.

Crowdsourced Delivery for Last-Mile Distribution: An Agent-Based Modelling and Simulation Approach. Proc., 2017 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), Singapore, 2017, pp. 1271–1275.

16.

Wang

Zhang

Liu

Shen

Lee

L. H.

Towards Enhancing the Last-Mile Delivery: An Effective Crowd-Tasking Model with Scalable Solutions. Transportation Research Part E: Logistics and Transportation Review, Vol. 93, 2016, pp. 279–293.

17.

Carbone

Rouquet

Roussat

The Rise of Crowd Logistics: A New Way to Co-Create Logistics Value. Journal of Business Logistics, Vol. 38, No. 4, 2017, pp. 238–252.

18.

Kang

Lee

Do Chung

Learning-Based Logistics Planning and Scheduling for Crowdsourced Parcel Delivery. Computers & Industrial Engineering, Vol. 132, 2019, pp. 271–279.

19.

Dablanc

Morganti

Arvidsson

Woxenius

Browne

Saidi

The Rise of On-Demand ‘Instant Deliveries’ in European Cities. Supply Chain Forum: An International Journal, Vol. 18, No. 4, 2017, pp. 203–217.

20.

Castillo

V. E.

Bell

J. E.

Rose

W. J.

Rodrigues

A. M.

Crowdsourcing Last Mile Delivery: Strategic Implications and Future Research Directions. Journal of Business Logistics, Vol. 39, No. 1, 2018, pp. 7–25.

21.

Liu

Shen

Z. J. M.

Shared Mobility for Last-Mile Delivery: Design, Operational Prescriptions, and Environmental Impact. Manufacturing & Service Operations Management, Vol. 20, No. 4, 2018, pp. 737–751.

22.

Esper

T. L.

Hofer

A. R.

Designing Crowdsourced Delivery Systems: The Effect of Driver Disclosure and Ethnic Similarity. Journal of Operations Management, Vol. 60, 2018, pp. 19–33.

23.

Yang

Iyer

Frazier

Mean Field Equilibria for Resource Competition in Spatial Settings. Stochastic Systems, Vol. 8, No. 4, 2018, pp. 307–334.

24.

Basık

Gedik

Ferhatosmanoglu

K. L.

Fair Task Allocation in Crowdsourced Delivery. IEEE Transactions on Services Computing, 2018. https://doi.org/10.1109/TSC.2018.2854866

25.

Devari

Nikolaev

A. G.

Crowdsourcing the Last Mile Delivery of Online Orders by Exploiting the Social Networks of Retail Store Customers. Transportation Research Part E: Logistics and Transportation Review, Vol. 105, 2017, pp. 105–122.

26.

Soto Setzke

Pflügler

Schreieck

Fröhlich

Wiesche

Krcmar

Matching Drivers and Transportation Requests in Crowdsourced Delivery Systems. Proc., 23rd Americas Conference on Information Systems, Boston, MA, 2017.

27.

Paskalathis

Azhari

S. N.

Ant Colony Optimization on Crowdsourced Delivery Trip Consolidation. Indonesian Journal of Computing and Cybernetics Systems (IJCCS), Vol. 11, No. 2, 2017, pp. 109–118.

28.

Chen

Mes

Schutten

Multi-Hop Driver-Parcel Matching Problem with Time Windows. Flexible Services and Manufacturing Journal, Vol. 30, No. 3, 2018, pp. 517–553.

29.

Huang

Cui

Yang

Wang

Fourth Party Logistics Routing Problem with Fuzzy Duration Time. International Journal of Production Economics, Vol. 145, No. 1, 2013, pp. 107–116.

30.

Kim

Ong

Y. S.

Cheong

Tan

P. S.

Solving the Dynamic Vehicle Routing Problem under Traffic Congestion. IEEE Transactions on Intelligent Transportation Systems, Vol. 17, No. 8, 2016, pp. 2367–2380.

31.

Savelsbergh

Van Woensel

50th Anniversary Invited Article—City Logistics: Challenges and Opportunities. Transportation Science, Vol. 50, No. 2, 2016, pp. 579–590.

32.

Mahmoudi

Zhou

Finding Optimal Solutions for Vehicle Routing Problem with Pickup and Delivery Services with Time Windows: A Dynamic Programming Approach Based on State–Space–Time Network Representations. Transportation Research Part B: Methodological, Vol. 89, 2016, pp. 19–42.

33.

Zhu

Liu

Zhang

Zhu

Teng

Solving the Many to Many Assignment Problem by Improving the Kuhn–Munkres Algorithm with Backtracking. Theoretical Computer Science, Vol. 618, 2016, pp. 30–41.

34.

Masoud

Jayakrishnan

A Decomposition Algorithm to Solve the Multi-Hop Peer-to-Peer Ride-Matching Problem. Transportation Research Part B: Methodological, Vol. 99, 2017, pp. 1–29.

35.

Kuhn

H. W.

The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, Vol. 2, No. 1–2, 1955, pp. 83–97.

36.

Liu

Fan

Z. P.

Zhang

A Method for Stochastic Multiple Criteria Decision Making Based on Dominance Degrees. Information Sciences, Vol. 181, No. 19, 2011, pp. 4139–4153.

37.

Fan

Z. P.

Zhang

Chen

F. D.

Liu

Multiple Attribute Decision Making Considering Aspiration-Levels: A Method Based on Prospect Theory. Computers & Industrial Engineering, Vol. 65, No. 2, 2013, pp. 341–350.

38.

Tong

She

Ding

Wang

Chen

Online Mobile Micro-Task Allocation in Spatial Crowdsourcing. Proc., 2016 IEEE 32nd International Conference on Data Engineering (ICDE), Helsinki, Finland, 2016, pp. 49–60.

39.

Sethi

Sorger

A Theory of Rolling Horizon Decision Making. Annals of Operations Research, Vol. 29, No. 1, 1991, pp. 387–415.

40.

Chen

Z. L.

Dynamic Column Generation for Dynamic Vehicle Routing with Time Windows. Transportation Science, Vol. 40, No. 1, 2006, pp. 74–88.

41.

Christensen

Erera

Pacino

A Rolling Horizon Heuristic for the Stochastic Cargo Mix Problem. Transportation Research Part E: Logistics and Transportation Review, Vol. 123, 2019, pp. 74–88.

42.

Fukasawa

Ricardez-Sandoval

Bi-Objective Short-Term Scheduling in a Rolling Horizon Framework: A Priori Approaches with Alternative Operational Objectives. Computers & Operations Research, Vol. 111, 2019, pp. 141–154.

43.

Hassan

Abdelghany

Semple

Dynamic Road Pricing for Revenue Maximization: Modeling Framework and Solution Methodology. Transportation Research Record, 2013. 2345: 100–108.

44.

Chen

Z. L.

Pundoor

Acharya

Markdown Optimization at Multiple Stores. IIE Transactions, Vol. 47, No. 1, 2015, pp. 84–108.

45.

Nourinejad

Ramezani

Ride-Sourcing Modeling and Pricing in Non-Equilibrium Two-Sided Markets. Transportation Research Part B: Methodological, Vol. 132, 2020, pp. 340–357.

46.

Chew

E. P.

Lee

Liu

Joint Inventory Allocation and Pricing Decisions for Perishable Products. International Journal of Production Economics, Vol. 120, No. 1, 2009, pp. 139–150.

47.

Coelho

L. C.

Cordeau

J. F.

Laporte

Heuristics for Dynamic and Stochastic Inventory-Routing. Computers & Operations Research, Vol. 52, 2014, pp. 55–67.

48.

Giesen

Mahmassani

H. S.

Jaillet

Coping with Disruptions: Performance Comparison of Strategies for Online Inventory Routing Systems under Demand Surges. Transportation Research Record, 2010. 2168: 63–70.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.61 MB