Introduction
-
We present a problem of takeaway order selection and delivery path planning for deliverymen, which utilizes store and customer habit data to better estimate order ready time and customer satisfaction level;
-
We propose a hybrid evolutionary algorithm to efficiently solve the problem;
-
We demonstrate the performance of the proposed method on test instances constructed based on real-world data of online takeaway platforms.
Related work
Problem formulation
Basic inputs
-
If the overdue time is shorter than 15 min, the basic delivery fee will be deducted by a percent \(e_1\);
-
If the overdue time is between [15, 30] min, the basic delivery fee will be deducted by a percent \(e_2\);
-
If the overdue time is longer than 30 min, no delivery fee will be paid, and an additional penalty fee which is a percent \(e_3\) of the basic delivery fee will be deducted.
-
If \(n_p\) is less than the lower limit \(\underline{n}_a\), there is an additional penalty of \(\epsilon _1(\underline{n}_a-n_p)\) yuan;
-
If \(n_p\) is between \([n^\dag _a,n^\ddag _a)\), there is an additional reward of \(\epsilon _2\) yuan per order;
-
If \(n_p\) reaches or exceeds \(n^\ddag _a\), there is an additional reward of \(\epsilon _3\) yuan per order.
Variable | Description |
---|---|
n
| Number of the candidate orders |
O
| Set of candidate orders |
\(p_o\)
| Pickup point of order o (\(\forall o\in O\)) |
\(s_o\)
| Service point of order o (\(\forall o\in O\)) |
\(v_o\)
| Basic delivery fee of order o (\(\forall o\in O\)) |
\(\widehat{t}_o\)
| Delivery deadline of order o (\(\forall o\in O\)) |
\(r_o\)
| Expected ready time of order o (\(\forall o\in O\)) |
\(p_0\)
| Initial location of the deliveryman |
P
| Set of all involved points |
\(\varDelta t(i,j)\)
| Travel time from point i to point j (\(\forall i,j\in P\)) |
\(\widehat{T}\)
| Maximum travel time of the delivery path |
\(e_1\)
| First-level overtime penalty |
\(e_2\)
| Second-level overtime penalty |
\(e_3\)
| Third-level overtime penalty |
\(\underline{n}_a\)
| Lower limit of the number of orders per hour |
\(n^\dag _a\)
| First threshold of the number of orders per hour |
\(n^\ddag _a\)
| Second threshold of the number of orders per hour |
\(\epsilon _1\)
| Additional penalty on the number of orders per hour |
\(\epsilon _2\)
| First-level award on the number of orders per hour |
\(\epsilon _3\)
| Second-level award on the number of orders per hour |
e
| Additional award per five-star score |
\(\widehat{r}(o)\)
| Ready time of order o calculated using machine learning |
\(\rho (o)\)
| Probability of five-star scoring calculated using machine learning |
Uncertain factors
Decision variables
-
An n-dimensional vector \(\mathbf {x}=\{x_1,x_2,\dots ,x_n\}\), where \(x_k=1\) denotes that \(o_k\) is selected and \(x_k= 0\) otherwise (\(1\le k\le n\)); then the subset of selected orders is \(O_{{\mathbf {x}}}=\{o_k|o_k\in O \wedge x_k=1\}\).
-
A sequence \(\mathbf {y}=\{y_1,y_2,\dots ,y_{l(\mathbf {y})}\}\) of the set of all pickup points and service points of the orders in \(O_{{\mathbf {x}}}\), where \(l(\mathbf {y})\) denotes the length of \(\mathbf {y}\). In other words, \(\mathbf {y}\) represents the delivery path of the deliveryman. For each \(y_j\) in \(\mathbf {y}\), if \(y_j\) is a pickup point, we let \(O(y_j)= \{o|o\in O_{\mathbf {x}}\wedge p_o=y_j\}\) be the set of orders from store \(y_j\), and suppose that the orders in \(O(y_j)\) are sorted in increasing order of ready time; if \(y_j\) is a service point, we let \(O'(y_j)= \{o|o\in O_{\mathbf {x}}\wedge s_o=y_j\}\) be the set of orders for customer \(y_j\).
-
For each pickup point \(y_j\) in \(\mathbf {y}\), an integer \(z(y_j)\) that denotes the deliveryman’s decision on how many orders the deliveryman will pick up from \(y_j\) at this time. That is, if \(|O(y_j)|=1\), then \(z(y_j)\) is 1; else, \(z(y_j)\) is an integer in \([1,|O(y_j)|]\), indicating that the deliveryman will pick up the first \(z(y_j)\) of these \(|O(y_j)|\) orders and then leave (and will go back for the remaining orders if exist).
Calculation of delivery time and revenue
Constraints
-
For each selected order o, the delivery path must contain its pickup point \(p_o\) and service point \(s_o\), and the (first) occurrence of \(p_o\) should be before that of \(s_o\):where \(\textit{ind}(i, \mathbf {y})\) denotes the index of element i in sequence \(\mathbf {y}\) (if the element occurs multiple time, it returns the first index).$$\begin{aligned} p_o\in \mathbf {y}\wedge s_o\in \mathbf {y} \wedge \textit{ind}(p_o,\mathbf {y})\!<\! \textit{ind}(s_o,\mathbf {y}), \quad \forall o\in O_{{\mathbf {x}}}\nonumber \\ \end{aligned}$$(12)
-
The decision \(z(y_j)\) at each pickup point is not larger than the cardinality of \(O(y_j)\):$$\begin{aligned} 1\le z(y_j)\le |O(y_j)|, \quad \forall \text { pickup point }y_j\text { in }\mathbf {y} \end{aligned}$$(13)
-
The total travel time cannot exceed the maximum travel time \(\widehat{T}\):$$\begin{aligned} \varDelta t(p_0,y_1)+\sum _{j=1}^{l(\mathbf {y})\!-\!1} \varDelta t(y_j,y_{j+1})\le \widehat{T} \end{aligned}$$(14)
Data-driven machine learning for estimating order ready time and customer satisfaction level
-
Expected ready time \(r_o\) of the current order given by the store;
-
Number of orders whose ready times are overdue in the recent month;
-
Percentage of orders whose ready times are overdue in the recent month;
-
Maximum, minimum, median, and standard deviations of the overdue time of the overdue orders in the recent month;
-
Number of orders whose ready times are overdue in the recent 3 days;
-
Percentage of orders whose ready times are overdue in the recent 3 days;
-
Maximum, minimum, median, and standard deviations of the overdue time of the overdue orders in the recent 3 days;
-
Number of orders that are accepted by the store and to be delivered in the next hour.
-
Calculated delivery time d(o) of the current order;
-
Number of orders placed by the customer in the recent 3 months, recent week, and recent day;
-
Percentage of orders receiving five-star scores to all orders that are not overdue in the recent 3 months, recent week, and recent day;
-
Number of orders received or to be received by the customer 1 h before and after.
A hybrid evolutionary algorithm for the problem
Tabu search for path planning
Water wave optimization for order selection
Computational experiments
Experimental results of machine learning
Experimental results of evolutionary optimization
No. instance | n | \(n_p\) | \(n_s\) |
---|---|---|---|
#1 | 25 | 3 | 8 |
#2 | 25 | 6 | 17 |
#3 | 25 | 9 | 26 |
#4 | 50 | 9 | 26 |
#5 | 50 | 12 | 35 |
#6 | 50 | 20 | 59 |
#7 | 75 | 20 | 59 |
#8 | 75 | 27 | 81 |
#9 | 100 | 20 | 59 |
#10 | 100 | 32 | 95 |
#11 | 100 | 36 | 121 |
# | Metric | GA | ACO | PSO | DE | BBO | EBO | AAA | WWO | WWO-AB |
---|---|---|---|---|---|---|---|---|---|---|
1 | med | \(^\dag \)10.91 | \(^\dag \)10.27 | \(^\dag \)9.84 | \(^\dag \)11.00 | \(^\dag \)11.25 | 11.25 | 11.25 | \(^\dag \)10.87 | 11.25 |
std | 0.51 | 0.82 | 0.92 | 0.77 | 0.10 | 0.41 | 0.79 | 0.51 | 0.20 | |
2 | med | \(^\dag \)7.12 | \(^\dag \)7.24 | \(^\dag \)5.75 | \(^\dag \)5.82 | 8.73 | \(^\dag \)8.73 | \(^\dag \)8.25 | \(^\dag \)8.25 | 8.73 |
std | 1.15 | 1.01 | 1.08 | 0.51 | 0.24 | 0.42 | 0.67 | 0.71 | 0.00 | |
3 | med | \(^\dag \)6.46 | \(^\dag \)5.91 | \(^\dag \)5.56 | \(^\dag \)4.80 | 7.18 | 7.16 | \(^\dag \)6.72 | \(^\dag \)6.86 | 7.21 |
std | 0.77 | 0.64 | 0.67 | 0.67 | 0.38 | 0.46 | 0.49 | 0.44 | 0.33 | |
4 | med | \(^\dag \)7.05 | \(^\dag \)6.85 | \(^\dag \)6.16 | \(^\dag \)7.20 | \(^\dag \)8.45 | 8.82 | \(^\dag \)7.83 | \(^\dag \)7.77 | 8.85 |
std | 0.63 | 0.59 | 0.67 | 0.48 | 0.29 | 0.39 | 0.56 | 0.53 | 0.35 | |
5 | med | \(^\dag \)5.53 | \(^\dag \)5.62 | \(^\dag \)4.29 | \(^\dag \)4.35 | 7.33 | \(^\dag \)6.88 | \(^\dag \)6.59 | \(^\dag \)5.90 | 7.31 |
std | 0.57 | 0.60 | 0.55 | 0.26 | 0.82 | 1.03 | 0.70 | 0.73 | 0.99 | |
6 | med | \(^\dag \)4.37 | \(^\dag \)4.50 | \(^\dag \)3.85 | \(^\dag \)3.86 | \(^\dag \)5.64 | \(^\dag \)5.68 | 5.73 | \(^\dag \)4.74 | 5.82 |
std | 0.41 | 0.45 | 0.42 | 0.21 | 0.29 | 0.35 | 0.35 | 0.41 | 0.32 | |
7 | med | \(^\dag \)5.40 | \(^\dag \)5.63 | \(^\dag \)4.97 | \(^\dag \)5.35 | \(^\dag \)7.00 | \(^\dag \)7.17 | \(^\dag \)8.15 | \(^\dag \)7.99 | 8.56 |
std | 0.68 | 0.85 | 0.96 | 0.49 | 0.72 | 0.74 | 0.52 | 0.36 | 0.30 | |
8 | med | \(^\dag \)5.96 | \(^\dag \)5.96 | \(^\dag \)5.19 | \(^\dag \)5.45 | \(^\dag \)8.02 | \(^\dag \)7.77 | \(^\dag \)7.04 | \(^\dag \)9.60 | 10.43 |
std | 0.78 | 0.97 | 0.90 | 0.48 | 0.41 | 0.84 | 0.51 | 0.81 | 0.36 | |
9 | med | \(^\dag \)5.19 | \(^\dag \)5.33 | \(^\dag \)3.93 | \(^\dag \)4.55 | \(^\dag \)7.24 | \(^\dag \)6.73 | \(^\dag \)6.91 | \(^\dag \)5.70 | 7.89 |
std | 0.70 | 0.85 | 0.51 | 0.34 | 0.67 | 0.67 | 0.65 | 0.66 | 0.62 | |
10 | med | \(^\dag \)4.39 | \(^\dag \)4.61 | \(^\dag \)3.79 | \(^\dag \)3.39 | \(^\dag \)5.32 | \(^\dag \)5.24 | \(^\dag \)5.22 | \(^\dag \)4.55 | 5.64 |
std | 0.44 | 0.54 | 0.36 | 0.31 | 0.16 | 0.28 | 0.30 | 0.39 | 0.17 | |
11 | med | \(^\dag \)5.64 | \(^\dag \)5.95 | \(^\dag \)5.21 | \(^\dag \)5.9 | \(^\dag \)7.45 | \(^\dag \)7.58 | \(^\dag \)7.50 | \(^\dag \)7.37 | 8.70 |
std | 0.46 | 0.52 | 0.38 | 0.40 | 0.28 | 0.37 | 0.45 | 0.26 | 0.21 |