# Two-Stage Solution for Meal Delivery Routing Optimization on Time-Sensitive Customer Satisfaction

Authors: Wenjie Wang; Li Jiang
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

The online-to-offline (O2O) meal delivery mode in which takeout meals are ordered online and delivered offline is recently emerging. The fast delivery of huge meal orders for time-sensitive customers imposes great challenges on O2O meal delivery platforms. This study establishes a two-stage solution for meal delivery routing optimization with the objective of maximizing time-sensitive customer satisfaction. In the first stage, a large number of meal orders are hierarchically classified and merged into delivery bundles based on the nearest pickup location rule by applying the hierarchical agglomerative clustering (HAC) algorithm, to increase fast meal delivery efficiency. In the second stage, a genetic algorithm (GA) is applied to solve the cluster-based delivery routing optimization model to find an optimal delivery route for meal orders in each delivery bundle. The numerical simulation results verify that the two-stage routing optimization solution is effective to schedule timely meal delivery and improve customer time satisfaction. The comparison of the results indicates the superiority of the proposed two-stage solution with HAC and GA on customer satisfaction while ensuring the delivery of all orders within 60 minutes. The sensitivity analysis shows the impact of time-sensitive customer heterogeneity on meal delivery satisfaction. This research has significant managerial insights for fast delivery services of O2O meal delivery platforms.


---

## Body

## 1. Introduction

The emerging O2O meal delivery mode in which takeout meals ordered by customers online are delivered offline within a certain time window has been experiencing rapid growth [1]. The O2O meal delivery platform Uber Eats (https://www.ubereats.com), which provides meal delivery services for customers to get great meals from customers’ favorite local restaurants, increased revenues by over 200 percent in 2020. One of the largest China O2O meal delivery platforms Meituan (https://www.meituan.com) has a turnover of 20.575 billion in the first quarter of 2021, with a growth of 116.8% compared with the first quarter of 2020. At the end of July 2021, O2O meal delivery platforms in China have nearly 469 million customers with an annual increase of 15% [1].However, the emerging O2O meal delivery mode is facing huge challenges on fast delivery service provision due to the huge volume of online takeout meal orders for time-sensitive customers. Three major aspects of challenging problems of the O2O meal delivery mode are presented in this study. Firstly, the fast delivery services are required to maintain the freshness of the takeout meals for the customers. Customer satisfaction with delivery time is normally used to evaluate the service quality of fast meal delivery [2]. The customers with heterogeneous time sensitivity degrees have different expectations in terms of service experience and satisfaction [3]. Therefore, how to improve time-sensitive customer satisfaction with fast meal delivery is an extremely important issue for O2O takeout meal delivery platforms. The second aspect is that the large volume of takeout meal orders, especially during peak hours, makes it very difficult and complicated for meal delivery platforms to schedule meal delivery. For example, there are nearly ten thousand real-time orders per second placed on the China Eleme meal delivery platform during peak hours. Hence, the research on the scheduling of a large volume of takeout meal orders has critical importance for O2O takeout meal delivery platforms, which are devoted to timely delivering meal orders for customers. Thirdly, the meal delivery routing problem (MDRP) [4] has a unique feature that the delivery riders pick up meals from restaurants in different locations and then deliver them to customers in different locations, in contrast to the conventional vehicle routing problem (VRP), in which the goods are picked up in a fixed distribution center. Therefore, research on meal delivery routing optimization with dynamic pickup and delivery for large volume takeout meal orders of time-sensitive customers has both practical significance and academic significance for O2O meal delivery platforms to increase customer satisfaction with fast meal delivery services.The focus of this study was to construct a meal delivery routing optimization model with the objective of maximizing the time-sensitive customer satisfaction with meal delivery services. Moreover, the heterogeneous time-sensitive customers who have different time sensitivity degrees on delayed meal delivery have been taken into consideration in meal delivery routing optimization modelling [3, 5]. A two-stage solution with HAC and GA is proposed for fast meal delivery routing optimization. The HAC algorithm is firstly employed to cluster several meal orders into delivery bundles for delivery riders to improve the performance of fast meal delivery by delivering a large volume of meal orders on time. Accounting for the characteristic of the MDRP, the nearest pickup location rule is adopted to cluster meal orders. Furthermore, a GA is applied to solve optimal meal delivery route for meal orders clustered in each delivery bundle in the first stage so that meal orders are delivered within the delivery time window to increase customer satisfaction.Our study in this paper generates several main contributions. Firstly, we proposed a meal delivery routing optimization model with the objective of optimizing time-sensitive customer satisfaction extending prior works on MDRP [6, 7]. Secondly, a two-stage solution is proposed to combine HAC and GA for meal delivery routing optimization in order to improve fast meal delivery performance. Based on the cluster first-route second philosophy [8], the meal orders are clustered into delivery bundles by the HAC algorithm in the first stage. Then, the delivery route for each delivery bundle is optimized by GA in the second stage. Thirdly, we compare the impact of time-sensitive customer heterogeneity on meal delivery satisfaction. From a practical perspective, the meal delivery routing optimization solution in our research contributes to improving order data processing and delivery efficiency and customer satisfaction for O2O meal delivery platforms.The remaining parts of this study are organized as follows. Section2 reviews the existing literature on the research of MDRP, customer satisfaction and time-sensitive customer, clustering algorithm, and heuristic algorithm. Section 3 describes the MDRP and proposes a two-stage meal delivery routing optimization solution. Section 4 designs the HAC and GA method. Section 5 details the comparative study of the two-stage meal delivery routing optimization solution versus the standard GA and the particle swarm optimization (PSO) algorithm using actual data. The impact of time-sensitive customer heterogeneity on meal delivery satisfaction is thoroughly discussed. Section 6 summarizes our research results and discusses the future research direction.


## 2. Literature Review

This study investigates the meal delivery routing optimization on time-sensitive customer satisfaction by applying the clustering method and heuristic algorithm. Therefore, our work is closely related to three streams of literature: the MDRP, customer satisfaction and time-sensitive customer, and clustering and heuristic algorithm.The MDRP [4] has attracted attention from researchers. The MDRP is most similar to the dynamic pickup and delivery problem (DPDP) that arises when goods must be transported from unique pickup locations to unique drop-off locations [6]. The MDRP is a dynamic problem with deadlines at customers, a customer service-focused objective function, and a large number of vehicles serving a large number of orders [6]. Ulmer et al. [6] studied a stochastic dynamic pickup and delivery problem (DPDP) with the objective to dynamically control a fleet of drivers in a way that avoids delays with respect to customers’ deadlines. An anticipatory customer assignment (ACA) policy is proposed relying on a time buffer and postponement to account for the dynamism and uncertainty of the problem. Yildiz and Savelsbergh [4] introduced a model for a meal delivery routing problem assuming perfect information about order arrivals and develop a simultaneous column- and row-generation algorithm for its solution. Rey et al. [9] proposed an approach for rescuing perishable food delivery problems to find an exact solution with the least travel cost routes. A heuristic algorithm that combines greedy and local search is introduced to efficiently provide envy-free and cost-effective solutions. Wang [10] studies a meal delivery problem that needs to route vehicles on multiple trips to pick up meals from multiple suppliers and deliver them to customers. Two mainstream heuristic algorithms, iterated local search and adaptive large neighborhood search, are developed for multi-trip routing with soft time windows and multiple refill locations. Xue et al. [11] established a two-stage model with mixed-integer programming and large neighborhood search algorithms to optimize the scheduling of riders for food delivery services in the O2O business.Customer satisfaction with delivery time that could be employed to evaluate the quality of the fast services is receiving increasing attention [12, 13]. Kuppelwieser and Maggard [14] analyzed customer satisfaction with wait time in a two-stage service process. Sarstedt and Sarstedt [15] studied the influence of individuals’ future time perspective on customer satisfaction. Homburg et al. [16] examined the influence of customer satisfaction and elapsed time on the price knowledge of drivers. Several papers consider customer satisfaction in MDRP. Liao et al. [7] described customer satisfaction of delivery time with fuzzy membership function in multi-objective green meal delivery routing problem. Teng et al. [12] constructed a VRP model for takeaway delivery by transforming the satisfaction of merchants and customers into a penalty function and aiming to minimize the total delivery cost.The time-sensitive customers on wait time and delay time have been taken into consideration in pricing, capacity, and routing research literature. Abouee-Mehrizi et al. [17] discussed a pricing policy of a service queuing system with a nonlinear waiting cost function of customers who are sensitive to the wait time (delay) and strategic regarding their balking and abandonment decisions. Wang et al. [18] investigated service capacity competition with seasonal arrival rates and time-sensitive customers who may leave if the service is delayed. Vodopivec and Miller-Hooks [19] studied the dynamic vehicle routing with time-sensitive customer pickup for a stochastic dial-a-ride application. A two-stage stochastic optimization approach is developed to integrate dynamic recourse into a priori scheduling and routing. Considering the heterogeneity of time-sensitive customers, Sainathan [3] examined the competition between two service providers by applying a three-stage game. The customers are heterogeneous in their delay sensitivities and belong to one of two types: impatient and patient. Golrezaei et al. [20] studied dynamic pricing with strategic customers who are heterogeneous with respect to their initial valuations for the goods and their time sensitivities. The customers are heterogeneous in their decreasing valuation distribution. They constructed a multiplicative model with different valuation decay rates changing over time. However, the research on heterogeneous time-sensitive customers that are important for fast services of meal delivery platforms has been rarely found in the existing MDRP literature. In this study, we study meal delivery routing optimization with the objective of time-sensitive customer satisfaction with fast meal delivery services as the customers have heterogeneous sensitivity to delayed meal delivery time.The clustering method including K-means and hierarchical algorithm has been applied to classify and merge orders into delivery bundles in several research works in the existing literature. Hsieh and Huang [21] merged online shopping orders using the K-means algorithm and optimized the performance of order picking systems by applying the self-organized map batching heuristics. Ishizaka et al. [22] designed a multi-criteria divisive hierarchical clustering algorithm that tackles the problems with uncertainty and imprecision, and it has been used to cluster financial institutions for US banks with improved performance. Tumpa et al. [23] used the hierarchical clustering method to analyze common key obstacles encountered in adopting the green supply chain of the textile industry. Xu et al. [24] proposed a unified validity index for the agglomerative hierarchical clustering, which demonstrated the efficiency of identifying the optimal number of clusters.There is abundant literature on heuristic algorithms for optimization problems [25–30]. For example, Homsi et al. [31] proposed an exact branch-and-price algorithm and a hybrid genetic search to study industrial and tramp ship routing and scheduling problems. Vidal et al. [32] proposed an efficient hybrid genetic algorithm with advanced diversity control for a large class of vehicle routing problems with time windows. Zhou et al. [33] designed a hybrid multi-population genetic algorithm to solve a real-world territory design problem of a major dairy company with the objective of minimizing the total operational cost. A variety of heuristic algorithms including the genetic algorithm and the greedy adaptive neighborhood heuristic [7, 9–12] have been applied in meal delivery routing optimization.Researchers often combine the clustering method with other heuristics, mate-heuristics, and approximate or exact solution approaches to solve the optimization problem [34, 35]. For example, Dondo and Cerdá [8] proposed a three-phase cluster-based optimization approach for the heterogeneous fleet vehicle routing problem based on the cluster first-route second philosophy. After grouping nodes into a few clusters during phase I, such clusters are assigned to vehicles and sequenced on the related tours in phase II. In the last phase III, the detailed routing and scheduling for each tour found in phase II are determined by solving a small cluster-based mixed-integer linear (MILP) model in phase III. Wang and Vidal [36] introduce a hybrid genetic algorithm that uses K-means as a local search in combination with problem-tailored genetic operators. Wang and Lin [37] developed a scenario-based heuristic algorithm in which an index of “intimacy degree” is defined for grouping customers into different clusters. Mendes et al. [38] used a Pearson’s and τ-Kendall hierarchical cluster approach to reduce the dimensionality of the multi-objective vehicle routing problem solved by the MOEA/D evolutionary approach. Oezdamar and Demir [39] described a hierarchical clustering and heuristic routing procedure to coordinate vehicle routing in large-scale disaster distribution planning. Liao et al. [7] applied K-means order combination and GA routing optimization solution in a green meal delivery routing problem (GMDRP). Two-stage strategy with Tabu search (TS) and GA is developed to optimize the number of riders, reduce carbon emissions in distribution, and ensure high customer satisfaction.We compare this study with previous research work to show the differences in Table1. Firstly, we propose a meal delivery routing optimization model with the objective of time-sensitive customer satisfaction extending the prior work of Liao et al. [7] and Teng et al. [12], unlike the cost minimization objective in most existing MDRP literature [6]. Secondly, we are differently taking into consideration of heterogeneous time-sensitive customers by introducing the time sensitivity coefficient in the customer time satisfaction function of the MDRP model. Similar to Sainathan [3] and Golrezaei et al. [20], we consider that the customers are heterogeneously sensitive to the delay time. Differently, we focus on the heterogeneity of time-sensitive customers on delayed delivery time of fast meal delivery services. Thirdly, we proposed a two-stage solution with HAC and GA based on the cluster first-route second philosophy [8] for meal delivery routing optimization in this study. The meal orders are clustered into delivery bundles by the HAC algorithm in the first stage. Then, the order delivery route for each bundle is optimized by the GA heuristic method in the second stage. In contrast to previous studies [7] using K-means clustering, we apply the HAC method, which does not give the numbers of clustering groups in advanced [40] to cluster meal orders into delivery bundles in our research.Table 1
Comparison between the existing literature and this study.
ReferenceMDRPCustomer satisfactionTime sensitiveHeuristic algorithmOrder clusteringTwo-stage solutionUlmer et al. [6]√Savelsbergh and Savelsbergh [4]√Rey et al. [9]√√Wang [10]√√Xue et al. [11]√√√Teng et al. [12]√√√Liao et al. [7]√√GAK-means√Sainathan [3]√√Abouee-Mehrizi et al. [17]√Golrezaei et al. [20]√Vodopivec and Miller-Hooks [19]√√Gribel and Vidal [36]GAK-meansWang and Lin [37]√K-means√Zhu et al. [34]√K-linksMendes et al. [38]√HACOezdamar and Demir [39]√HACDondo and Cerdá [8]√Heuristic√This study√√√GAHAC√In summary, this study introduces a meal delivery routing optimization model with the objective of maximizing time-sensitive customer satisfaction, for which the two-stage solution is proposed by combining HAC and GA. The takeout meal orders placed online by customers are clustered into delivery bundles for riders with the HAC algorithm by the closest pickup locations criterion, to increase delivery efficiency for fast delivery services. Then, a GA is designed to optimize the meal delivery route in delivery bundles with the fitness function of customer time satisfaction, to improve customer satisfaction with fast delivery services. The numerical simulation is implemented on actual data to verify the performance of the two-stage solution for meal delivery routing optimization. Finally, we investigate the influence of time-sensitive customer heterogeneity on satisfaction with fast meal delivery services provided by O2O meal delivery platforms.


## 3. Meal Delivery Routing Optimization Modelling

### 3.1. Problem Description

The emerging O2O meal delivery platforms accept customers’ meal orders online at any time and delivery the orders quickly offline. Different from traditional commodity delivery mode, O2O meal delivery mode has its unique characteristics, including (1) the fast service requirement for meal delivery to keep the food fresh and warm; (2) the huge volume of meal orders on online takeout meal delivery platforms, especially during peak hours; and (3) different meal pickup locations of restaurants and different delivery locations of customers with no fixed distribution center.Considering the fast delivery requirement of takeout meal customers, we established the meal delivery routing optimization model aiming to maximize customer time satisfaction, which is expressed as the function related to the delivery time window and delayed delivery time. The time sensitivity coefficient is also factored into the customer time satisfaction function accounting for the impact of time-sensitive customer heterogeneity. To improve the delivery time efficiency for the huge order volume of O2O meal delivery platforms, a two-stage solution for meal delivery routing optimization model is proposed with HAC and GA as shown in Figure1. Based on the cluster first-route second philosophy [8], the takeout meal orders are clustered into delivery bundles for riders with the nearest pickup location rule by the HAC algorithm in the first stage. In the second stage, the optimal delivery route for meal orders in each clustered bundle is deducted out with GA to maximize customer time satisfaction.Figure 1
Meal order cluster first-route second process.The takeout meal delivery orders have different meal pickup locations of restaurants and different delivery locations of customers with no fixed distribution center. To improve the time efficiency of meal order clustering, the nearest pickup locations rule is applied to hierarchically cluster meal orders into delivery bundles while saving the pickup time for delivery riders. For example, meal orders 1, 2, and 3 are clustered into one delivery bundle 1 on the nearest pickup location rule as shown in Figure1. The delivery rider assigned for the delivery bundle 1 picks up meals from restaurants 1, 2, and 3 and then deliveries them in an optimized delivery route.Considering heterogeneous time-sensitive customer satisfaction with fast delivery services, the routing optimization model for meal orders in clustered bundles is built on the following assumptions: (1) the delivery time of the meal orderi is restricted within the delivery time window [Ei, Fi]. (2) Each meal order is picked up and delivered by the same delivery rider. (3) The vehicle of delivery rider k has the maximum capacity Qk for meal order load. (4) The food preparation time and delivery vehicle charging time are neglected in the model.The MDRP can be described by graph theory,G = (I, N) , where I=A∪B=1,…,n is a group of nodes including restaurants and customers, where n represents the number of meal orders. A = {ai} is the set of pickup restaurant locations of the meal order i, where i = 1, 2, 3, …, n. B = {bi} is the set of customer location of the meal order i, where i = 1, 2, 3, …, n.N=i,j|i∈I,j∈I is the set of delivery route arcs from meal order i to meal order j, where i, j = 1, 2, 3, …, n. K is the number of available riders in a certain designated delivery area, which is normally within a three- to five-kilometer living circle. The O2O meal delivery platform clusters mk meal orders into the delivery bundle k, which is assigned to the delivery rider k with the optimized delivery route, where ∀k ∈ K and mk denotes the number of meal orders clustered into the delivery bundle k.Throughout this study, two decisions are to be made: the number of bundles (riders) and deliver route of meal orders in each bundle for the delivery rider. Firstly, the number of delivery bundles that is equal to the number of delivery riders is determined by the HAC algorithm in the first stage of the proposed two-stage solution. We use the decision variablezik=1 to denote that the meal order i is assigned to rider k. Secondly, the delivery route of meal orders in each bundle for the rider is optimized by GA to offer fast delivery service in the second stage. We use decision variable xijk = 1 to denote that the rider k travels from the order i location to the order j location. The variables and parameters applied in the modelling are listed in Table 2.Table 2
Notations used in modelling.
NotationDescriptionnThe number of meal ordersKThe number of available riders in a certain designated delivery areaQkThe delivery capacity constraint of riderk, ∀k ∈ K, k = 1, 2, 3, …, KmkThe number of meal orders clustered in the delivery bundlek, ∀k ∈ K, k = 1, 2, 3, …, KSiCustomer time satisfaction of meal orderi, i = 1, 2, 3, …, nfk(Si)Average customer time satisfaction of meal orders in the delivery bundlek, i = 1, 2, 3, …., mkβTime sensitivity coefficient of heterogeneous time-sensitive customersEiThe earliest arrival time of meal orderi, i = 1, 2, 3, …, nFiThe latest arrival time of meal orderi, i = 1, 2, 3, …, nLiThe acceptable delayed arrival time of meal orderi, i = 1, 2, 3, …, nTaikThe arrival time of the orderi delivered by rider kTlikThe departure time of riderk leaving the customer location of order itijkThe travel time of the riderk from the order i location to the order j locationzikBinary decision variable equals to 1 if orderi is assigned to rider k; otherwise 0xijkBinary decision variable equals to 1 if riderk travels from order i location to the order j location; otherwise 0


### 3.2. Mathematical Formulation

Based on the cluster first-route second philosophy [8], a two-stage solution with HAC and GA is proposed for meal delivery routing optimization in this study. To improve the delivery efficiency of huge volume meal orders, the takeout meal orders are clustered into delivery bundles by the HAC algorithm in the first stage. In the second stage, a cluster-based [8] meal delivery routing optimization model is established for fast delivery services of meal orders inside each delivery bundle with the objective of maximizing the time-sensitive customer satisfaction. The cluster-based meal delivery routing optimization model for clustered delivery bundle k with time sensitivity coefficient and the objective of maximizing the average customer time satisfaction is as follows.(1)maxfkSi=1mk∑i=1mkSi,subject to(2)Si=1,Ei≤Taik≤Fi,Li−TaikLi−Fiβ,Ei≤Taik≤Fi,0,Taik≥Li,(3)mk≤Qk,∀k∈K,(4)Tajk=Tlik+tij,i,j=1,2,3,…,n,(5)Tlik<Tajk,i,j=1,2,3,…,n,(6)∑k=1Kzik=1,∀k∈K,i=1,2,3,…,n,(7)∑i=1mkxihk−∑j=1mkxhjk=0,∀k∈K,h=1,2,3,…,mk,(8)∑i=1mkxijk=1,∀k∈K,j=1,2,3,…,mk,(9)∑j=1mkxijk=1,∀k∈K,i=1,2,3,…,mk,(10)∑k=1K∑j=1mkxijk≤K,i=1,2,3,…,mk,(11)zik=0,1,∀k∈K,i=1,2,3,…,n,(12)xijk=0,1,∀k∈K,i,j=1,2,3,…,n.The objective function (1) aims to maximize average time-sensitive customer satisfaction ofmk meal orders inside the delivery bundle k for the rider k. The time-sensitive customer satisfaction function Si [12] of meal order i with the time sensitivity coefficient β is shown in equation (2). The average time-sensitive customer satisfaction in equation (1) is calculated by dividing the sum of mk meal orders’ satisfaction by the number of meal orders mk in the delivery bundle k.The time-sensitive customer satisfaction function, as shown in equation (2), is applied to measure customer satisfaction with the considerations of heterogeneous time sensitivity to delayed meal delivery. Taik is the arrival time of the meal order i delivered to the customer by the rider k. The customer time satisfaction is equal to 1 when the meal orders are delivered within the given delivery time window [Ei, Fi], which indicates that the customers are satisfied with the on-time meal delivery. The customers will have dissatisfied experiences on the delayed meal delivery when the arrival time of meal orders Taik exceeds the latest arrival time of meal orders Fi. Li is the acceptable delayed arrival time of the meal order i delivered to the customer. The customer time satisfaction will be reduced to be less than 1 when meal orders are delivered within the acceptable delayed delivery time period [Fi, Li] as the arrival time of meal orders Taik does not exceed the acceptable delayed arrival time Li. However, the value of customer time satisfaction will be reduced to zero as the arrival time of meal orders Taik exceeds the acceptable delayed arrival time Li.We introduce time sensitivity coefficientβ in the time-sensitive customer satisfaction function to measure the impact of time-sensitive customer heterogeneity on meal delivery satisfaction [3]. We divide the customers into three groups [20] based on their time sensitivity to delayed meal delivery. The time sensitivity coefficient β is set as 0 < β < 1, β = 1, and β > 1 to indicate low, medium, and high time sensitivity of the customers, respectively. The first group consists of the customers with low time sensitivity as they are less sensitive to delayed meal delivery. The second group includes the customers with medium time sensitivity as they are sensitive to delayed meal delivery in the medium sensitivity degree. The third group comprises the customers with high time sensitivity as they are more sensitive to delayed meal delivery. As shown in Figure 2, the satisfaction of the customers with medium time sensitivity is linearly decreased with the arrival time of meal orders Tai within the delayed delivery time period [Fi, Li]. The satisfaction of the customers with low time sensitivity is higher than the medium group. In contrast, the satisfaction of the customers with high time sensitivity is lower than the medium group.Figure 2
Customer time satisfaction function with different time sensitivity coefficients.Equations (3) to (12) are the constraints of this cluster-based meal delivery routing optimization model. Equation (3) restricts the number of meal orders mk clustered in the delivery bundle k, which cannot exceed the delivery capacity Qk provided by the rider’s vehicle. Equation (4) defines the arrival time of the meal order j delivered by rider k that is the sum of the departure time of rider k leaving the customer location of order i and the travel time of the rider k from the order i delivery location to the order j delivery location. Equation (5) gives the restriction on the delivery sequence of meal orders. Equation (6) restricts to avoid the duplicated assignment to a delivery rider with the same meal order. Equation (7) gives the requirement on the delivery rider k who should leave the order h location after he arrives at the order h location. Equations (8) and (9) restrain that the delivery rider must travel to each meal order delivery location once and only once in the delivery bundle. Equation (10) gives the restriction on the number of clustered bundles that cannot be more than the number of available delivery riders. Equations (11) and (12) are the value ranges of the decision variables, which are the rider assignment for meal order zik and the rider travel route xijk.


## 3.1. Problem Description

The emerging O2O meal delivery platforms accept customers’ meal orders online at any time and delivery the orders quickly offline. Different from traditional commodity delivery mode, O2O meal delivery mode has its unique characteristics, including (1) the fast service requirement for meal delivery to keep the food fresh and warm; (2) the huge volume of meal orders on online takeout meal delivery platforms, especially during peak hours; and (3) different meal pickup locations of restaurants and different delivery locations of customers with no fixed distribution center.Considering the fast delivery requirement of takeout meal customers, we established the meal delivery routing optimization model aiming to maximize customer time satisfaction, which is expressed as the function related to the delivery time window and delayed delivery time. The time sensitivity coefficient is also factored into the customer time satisfaction function accounting for the impact of time-sensitive customer heterogeneity. To improve the delivery time efficiency for the huge order volume of O2O meal delivery platforms, a two-stage solution for meal delivery routing optimization model is proposed with HAC and GA as shown in Figure1. Based on the cluster first-route second philosophy [8], the takeout meal orders are clustered into delivery bundles for riders with the nearest pickup location rule by the HAC algorithm in the first stage. In the second stage, the optimal delivery route for meal orders in each clustered bundle is deducted out with GA to maximize customer time satisfaction.Figure 1
Meal order cluster first-route second process.The takeout meal delivery orders have different meal pickup locations of restaurants and different delivery locations of customers with no fixed distribution center. To improve the time efficiency of meal order clustering, the nearest pickup locations rule is applied to hierarchically cluster meal orders into delivery bundles while saving the pickup time for delivery riders. For example, meal orders 1, 2, and 3 are clustered into one delivery bundle 1 on the nearest pickup location rule as shown in Figure1. The delivery rider assigned for the delivery bundle 1 picks up meals from restaurants 1, 2, and 3 and then deliveries them in an optimized delivery route.Considering heterogeneous time-sensitive customer satisfaction with fast delivery services, the routing optimization model for meal orders in clustered bundles is built on the following assumptions: (1) the delivery time of the meal orderi is restricted within the delivery time window [Ei, Fi]. (2) Each meal order is picked up and delivered by the same delivery rider. (3) The vehicle of delivery rider k has the maximum capacity Qk for meal order load. (4) The food preparation time and delivery vehicle charging time are neglected in the model.The MDRP can be described by graph theory,G = (I, N) , where I=A∪B=1,…,n is a group of nodes including restaurants and customers, where n represents the number of meal orders. A = {ai} is the set of pickup restaurant locations of the meal order i, where i = 1, 2, 3, …, n. B = {bi} is the set of customer location of the meal order i, where i = 1, 2, 3, …, n.N=i,j|i∈I,j∈I is the set of delivery route arcs from meal order i to meal order j, where i, j = 1, 2, 3, …, n. K is the number of available riders in a certain designated delivery area, which is normally within a three- to five-kilometer living circle. The O2O meal delivery platform clusters mk meal orders into the delivery bundle k, which is assigned to the delivery rider k with the optimized delivery route, where ∀k ∈ K and mk denotes the number of meal orders clustered into the delivery bundle k.Throughout this study, two decisions are to be made: the number of bundles (riders) and deliver route of meal orders in each bundle for the delivery rider. Firstly, the number of delivery bundles that is equal to the number of delivery riders is determined by the HAC algorithm in the first stage of the proposed two-stage solution. We use the decision variablezik=1 to denote that the meal order i is assigned to rider k. Secondly, the delivery route of meal orders in each bundle for the rider is optimized by GA to offer fast delivery service in the second stage. We use decision variable xijk = 1 to denote that the rider k travels from the order i location to the order j location. The variables and parameters applied in the modelling are listed in Table 2.Table 2
Notations used in modelling.
NotationDescriptionnThe number of meal ordersKThe number of available riders in a certain designated delivery areaQkThe delivery capacity constraint of riderk, ∀k ∈ K, k = 1, 2, 3, …, KmkThe number of meal orders clustered in the delivery bundlek, ∀k ∈ K, k = 1, 2, 3, …, KSiCustomer time satisfaction of meal orderi, i = 1, 2, 3, …, nfk(Si)Average customer time satisfaction of meal orders in the delivery bundlek, i = 1, 2, 3, …., mkβTime sensitivity coefficient of heterogeneous time-sensitive customersEiThe earliest arrival time of meal orderi, i = 1, 2, 3, …, nFiThe latest arrival time of meal orderi, i = 1, 2, 3, …, nLiThe acceptable delayed arrival time of meal orderi, i = 1, 2, 3, …, nTaikThe arrival time of the orderi delivered by rider kTlikThe departure time of riderk leaving the customer location of order itijkThe travel time of the riderk from the order i location to the order j locationzikBinary decision variable equals to 1 if orderi is assigned to rider k; otherwise 0xijkBinary decision variable equals to 1 if riderk travels from order i location to the order j location; otherwise 0


## 3.2. Mathematical Formulation

Based on the cluster first-route second philosophy [8], a two-stage solution with HAC and GA is proposed for meal delivery routing optimization in this study. To improve the delivery efficiency of huge volume meal orders, the takeout meal orders are clustered into delivery bundles by the HAC algorithm in the first stage. In the second stage, a cluster-based [8] meal delivery routing optimization model is established for fast delivery services of meal orders inside each delivery bundle with the objective of maximizing the time-sensitive customer satisfaction. The cluster-based meal delivery routing optimization model for clustered delivery bundle k with time sensitivity coefficient and the objective of maximizing the average customer time satisfaction is as follows.(1)maxfkSi=1mk∑i=1mkSi,subject to(2)Si=1,Ei≤Taik≤Fi,Li−TaikLi−Fiβ,Ei≤Taik≤Fi,0,Taik≥Li,(3)mk≤Qk,∀k∈K,(4)Tajk=Tlik+tij,i,j=1,2,3,…,n,(5)Tlik<Tajk,i,j=1,2,3,…,n,(6)∑k=1Kzik=1,∀k∈K,i=1,2,3,…,n,(7)∑i=1mkxihk−∑j=1mkxhjk=0,∀k∈K,h=1,2,3,…,mk,(8)∑i=1mkxijk=1,∀k∈K,j=1,2,3,…,mk,(9)∑j=1mkxijk=1,∀k∈K,i=1,2,3,…,mk,(10)∑k=1K∑j=1mkxijk≤K,i=1,2,3,…,mk,(11)zik=0,1,∀k∈K,i=1,2,3,…,n,(12)xijk=0,1,∀k∈K,i,j=1,2,3,…,n.The objective function (1) aims to maximize average time-sensitive customer satisfaction ofmk meal orders inside the delivery bundle k for the rider k. The time-sensitive customer satisfaction function Si [12] of meal order i with the time sensitivity coefficient β is shown in equation (2). The average time-sensitive customer satisfaction in equation (1) is calculated by dividing the sum of mk meal orders’ satisfaction by the number of meal orders mk in the delivery bundle k.The time-sensitive customer satisfaction function, as shown in equation (2), is applied to measure customer satisfaction with the considerations of heterogeneous time sensitivity to delayed meal delivery. Taik is the arrival time of the meal order i delivered to the customer by the rider k. The customer time satisfaction is equal to 1 when the meal orders are delivered within the given delivery time window [Ei, Fi], which indicates that the customers are satisfied with the on-time meal delivery. The customers will have dissatisfied experiences on the delayed meal delivery when the arrival time of meal orders Taik exceeds the latest arrival time of meal orders Fi. Li is the acceptable delayed arrival time of the meal order i delivered to the customer. The customer time satisfaction will be reduced to be less than 1 when meal orders are delivered within the acceptable delayed delivery time period [Fi, Li] as the arrival time of meal orders Taik does not exceed the acceptable delayed arrival time Li. However, the value of customer time satisfaction will be reduced to zero as the arrival time of meal orders Taik exceeds the acceptable delayed arrival time Li.We introduce time sensitivity coefficientβ in the time-sensitive customer satisfaction function to measure the impact of time-sensitive customer heterogeneity on meal delivery satisfaction [3]. We divide the customers into three groups [20] based on their time sensitivity to delayed meal delivery. The time sensitivity coefficient β is set as 0 < β < 1, β = 1, and β > 1 to indicate low, medium, and high time sensitivity of the customers, respectively. The first group consists of the customers with low time sensitivity as they are less sensitive to delayed meal delivery. The second group includes the customers with medium time sensitivity as they are sensitive to delayed meal delivery in the medium sensitivity degree. The third group comprises the customers with high time sensitivity as they are more sensitive to delayed meal delivery. As shown in Figure 2, the satisfaction of the customers with medium time sensitivity is linearly decreased with the arrival time of meal orders Tai within the delayed delivery time period [Fi, Li]. The satisfaction of the customers with low time sensitivity is higher than the medium group. In contrast, the satisfaction of the customers with high time sensitivity is lower than the medium group.Figure 2
Customer time satisfaction function with different time sensitivity coefficients.Equations (3) to (12) are the constraints of this cluster-based meal delivery routing optimization model. Equation (3) restricts the number of meal orders mk clustered in the delivery bundle k, which cannot exceed the delivery capacity Qk provided by the rider’s vehicle. Equation (4) defines the arrival time of the meal order j delivered by rider k that is the sum of the departure time of rider k leaving the customer location of order i and the travel time of the rider k from the order i delivery location to the order j delivery location. Equation (5) gives the restriction on the delivery sequence of meal orders. Equation (6) restricts to avoid the duplicated assignment to a delivery rider with the same meal order. Equation (7) gives the requirement on the delivery rider k who should leave the order h location after he arrives at the order h location. Equations (8) and (9) restrain that the delivery rider must travel to each meal order delivery location once and only once in the delivery bundle. Equation (10) gives the restriction on the number of clustered bundles that cannot be more than the number of available delivery riders. Equations (11) and (12) are the value ranges of the decision variables, which are the rider assignment for meal order zik and the rider travel route xijk.


## 4. Two-Stage Solution Design

The two-stage solution with HAC and GA is designed to cluster high-volume meal orders into delivery bundles and optimize the delivery route for meal orders in each bundle. The framework of the two-stage solution on cluster first-route second philosophy [8] is shown in Figure 3. In the first stage, a large number of meal orders are clustered into delivery bundles on the nearest pickup location rule applying the HAC algorithm. Then, clustered bundles are assigned to the delivery riders. In the second stage, a GA is designed to optimize the delivery route for each assigned rider to deliver meal orders in the delivery bundle clustered in the first stage with the objective of time-sensitive customer satisfaction maximization. The two-stage solution combined HAC and GA could provide a highly effective and feasible strategy to timely deliver high-volume meal orders for O2O meal delivery platforms.Figure 3
Two-stage solution design flowchart on HAC clustering and GA route optimization.


### 4.1. The HAC Meal Order Clustering

In the first stage of the two-stage solution for O2O meal delivery routing optimization, the HAC algorithm is applied to classify and merge meal orders into delivery bundles on the nearest pickup location rule. The HAC algorithm gradually agglomerates single meal order into delivery bundles. Firstly, the meal orderi, which has pickup location ai, is classified as one delivery bundle Ck. The delivery bundle set C = {C1, C2, C3, …, Ck} = {a1, a2, a3, …, an}. The Euclidean distance is adopted to measure the location distance dij from the meal order i with location axis (axi, ayi) to the meal order j with location axis (axj, ayj), as follows:(13)dij=axi−axj2+ayi−ayj2.The distance between different delivery bundles is calculated with the sum of deviation squares, which is also called the ward linkage method. It is assumed that there arei and j meal orders inside the delivery bundle Ci and the delivery bundle Cj, respectively. The bundle distance between the delivery bundle Ci and the delivery bundle Cj is defined as the increment of deviation square sum Dij2, as follows:(14)Dij2=Sr2−Si2−Sj2,where Sr2 is the sum of deviation squares of meal order locations inside the clustered bundle Cr, which is agglomerated from the delivery bundle Ci and the delivery bundle Cj. Two bundles that have the shortest bundle distance are clustered into a new delivery bundle Ck. The distance recursion formula for the sum of deviation squares is as follows:(15)Drk2=k+ir+kDik2+k+jr+kDjk2−kr+kDij2.The bundle merging process mentioned above is repeated and ended until alln meal orders are agglomerated into only one delivery bundle. The bundle agglomerating results could be represented in a tree diagram. Then, the O2O meal delivery platforms could determine the numbers of delivery bundles and assign them to the nearest delivery riders by referring to available delivery riders and fast meal delivery time requirement.


### 4.2. The Cluster-Based GA Routing Optimization

In the second stage, the cluster-based [8] meal delivery routing optimization model is solved by GA. As shown in Figure 3, GA is applied to search for the optimal delivery route for mk meal orders in the delivery bundle k assigned to the rider k in the first stage. The simplified Python pseudocode of the algorithm linking the delivery bundles (clusters) clustered by HAC for assigned riders with cluster-based GA route optimization is shown in Algorithm 1.Algorithm 1: GA routing optimization for assigned rider of clustered bundle.
for rider:for mealOrder in route:if mealOrder in clusters[rider]:MealOrders_rider[rider].append(mealOrder)end ifend forend forfor rider, mealOrder in MealOrders_rider.items():For mealOrder:If delivery_time in [E,L] and load ≤ maxCapacity:calculate time satisfaction and route append mealOrderelsenew_route append DNA(rider)end forend forConsidering the fast service characteristics of meal delivery, customer time satisfaction related to the time sensitivity of heterogeneous customers is taken as the objective of the meal delivery routing optimization model, in contrast with the cost minimization objective in conventional MDRP. In the GA design, we take the customer time satisfaction as the fitness function to maximize the objective of the above-mentioned MDRP optimization model. The optimal chromosome with the highest fitness has the highest customer time satisfaction. The fitness function could be obtained in the following equation:(16)FiS=fiS.The optimal solution for meal delivery routes would be found from the solution space, which consists of a population of chromosomes. Each chromosome is one solution that can be evaluated by the fitness function. The meal orders in the delivery bundle are encoded using the integer encoding method. Suppose that there are six orders in a delivery bundle. The delivery sequence of these six meal orders in one route solution is encoded and represented as one chromosome (1 2 3 4 5 6). The initial solution would be randomly selected. A new population is generated by the selection operation, which selects the better chromosome with higher fitness into the new population. The selected probability of each chromosome could be calculated as follows:(17)Pi=Fi∑i=1mkFi.The crossover operator is usually applied in the genetic algorithm to obtain the new child chromosome, which could inherit the good fitness of the parent chromosome. The randomly selected gene sections highlighted in green background in Figure4 are crossed in two-parent chromosomes. The partial mapped method is used to exchange repeated order numbers in the conflict positions indicated in an asterisk of the new child chromosomes.Figure 4
GA Crossover operation.The mutation operator that exchanges the genes in the chromosome is applied to enhance the diversity of the population. The mutation operation is shown in Figure5.Figure 5
GA mutation operation.To improve the local search ability of the genetic algorithm, the inver-over operator is induced multiple times after selection, crossover, and mutation operations. The child chromosomes with increased fitness in the inver-over operation could be evolved into the next procedure. The inver-over evolutionary operation [7] is shown in Figure 6.Figure 6
GA inver-over operation.


## 4.1. The HAC Meal Order Clustering

In the first stage of the two-stage solution for O2O meal delivery routing optimization, the HAC algorithm is applied to classify and merge meal orders into delivery bundles on the nearest pickup location rule. The HAC algorithm gradually agglomerates single meal order into delivery bundles. Firstly, the meal orderi, which has pickup location ai, is classified as one delivery bundle Ck. The delivery bundle set C = {C1, C2, C3, …, Ck} = {a1, a2, a3, …, an}. The Euclidean distance is adopted to measure the location distance dij from the meal order i with location axis (axi, ayi) to the meal order j with location axis (axj, ayj), as follows:(13)dij=axi−axj2+ayi−ayj2.The distance between different delivery bundles is calculated with the sum of deviation squares, which is also called the ward linkage method. It is assumed that there arei and j meal orders inside the delivery bundle Ci and the delivery bundle Cj, respectively. The bundle distance between the delivery bundle Ci and the delivery bundle Cj is defined as the increment of deviation square sum Dij2, as follows:(14)Dij2=Sr2−Si2−Sj2,where Sr2 is the sum of deviation squares of meal order locations inside the clustered bundle Cr, which is agglomerated from the delivery bundle Ci and the delivery bundle Cj. Two bundles that have the shortest bundle distance are clustered into a new delivery bundle Ck. The distance recursion formula for the sum of deviation squares is as follows:(15)Drk2=k+ir+kDik2+k+jr+kDjk2−kr+kDij2.The bundle merging process mentioned above is repeated and ended until alln meal orders are agglomerated into only one delivery bundle. The bundle agglomerating results could be represented in a tree diagram. Then, the O2O meal delivery platforms could determine the numbers of delivery bundles and assign them to the nearest delivery riders by referring to available delivery riders and fast meal delivery time requirement.


## 4.2. The Cluster-Based GA Routing Optimization

In the second stage, the cluster-based [8] meal delivery routing optimization model is solved by GA. As shown in Figure 3, GA is applied to search for the optimal delivery route for mk meal orders in the delivery bundle k assigned to the rider k in the first stage. The simplified Python pseudocode of the algorithm linking the delivery bundles (clusters) clustered by HAC for assigned riders with cluster-based GA route optimization is shown in Algorithm 1.Algorithm 1: GA routing optimization for assigned rider of clustered bundle.
for rider:for mealOrder in route:if mealOrder in clusters[rider]:MealOrders_rider[rider].append(mealOrder)end ifend forend forfor rider, mealOrder in MealOrders_rider.items():For mealOrder:If delivery_time in [E,L] and load ≤ maxCapacity:calculate time satisfaction and route append mealOrderelsenew_route append DNA(rider)end forend forConsidering the fast service characteristics of meal delivery, customer time satisfaction related to the time sensitivity of heterogeneous customers is taken as the objective of the meal delivery routing optimization model, in contrast with the cost minimization objective in conventional MDRP. In the GA design, we take the customer time satisfaction as the fitness function to maximize the objective of the above-mentioned MDRP optimization model. The optimal chromosome with the highest fitness has the highest customer time satisfaction. The fitness function could be obtained in the following equation:(16)FiS=fiS.The optimal solution for meal delivery routes would be found from the solution space, which consists of a population of chromosomes. Each chromosome is one solution that can be evaluated by the fitness function. The meal orders in the delivery bundle are encoded using the integer encoding method. Suppose that there are six orders in a delivery bundle. The delivery sequence of these six meal orders in one route solution is encoded and represented as one chromosome (1 2 3 4 5 6). The initial solution would be randomly selected. A new population is generated by the selection operation, which selects the better chromosome with higher fitness into the new population. The selected probability of each chromosome could be calculated as follows:(17)Pi=Fi∑i=1mkFi.The crossover operator is usually applied in the genetic algorithm to obtain the new child chromosome, which could inherit the good fitness of the parent chromosome. The randomly selected gene sections highlighted in green background in Figure4 are crossed in two-parent chromosomes. The partial mapped method is used to exchange repeated order numbers in the conflict positions indicated in an asterisk of the new child chromosomes.Figure 4
GA Crossover operation.The mutation operator that exchanges the genes in the chromosome is applied to enhance the diversity of the population. The mutation operation is shown in Figure5.Figure 5
GA mutation operation.To improve the local search ability of the genetic algorithm, the inver-over operator is induced multiple times after selection, crossover, and mutation operations. The child chromosomes with increased fitness in the inver-over operation could be evolved into the next procedure. The inver-over evolutionary operation [7] is shown in Figure 6.Figure 6
GA inver-over operation.


## 5. Numerical Simulation

The python programming language is applied to numerically simulate two-stage solution of meal delivery routing optimization with the objective of time-sensitive customer satisfaction. Both MDRP model and algorithms are coded in Python 3.7 and tested on a system with 64 bit Windows 10 OS, Intel i5-8400T CPU (1.7 GHz), and 8 GB RAM. The pickup location coordinates (axi, ayi) and delivery location coordinates (bxi, byi) of forty-one takeout meal orders in the five-kilometer delivery region of a China O2O meal delivery platform [13] are listed in Table 3. Table 3 also lists the delivery time window, which includes the earliest arrival time of meal order Ei, the latest arrival time of meal order Fi, and the acceptable delayed arrival time of meal order Li. It is assumed that the average travel speed of delivery riders is v  = 10 km/h. The average time that the delivery rider k travel to each restaurant is tw  = 2 min. The average pickup time that the delivery rider k waits and picks up a meal in the restaurant is tq = 2 min. The average service time is ts = 0.5 min for each customer. The time sensitivity coefficients are set as βL = 0.5, βM = 1, and βH = 1.5 to represent low, medium, and high time sensitivity of the customers.Table 3
Location and time data of forty-one meal orders.
Order numberPickup locationDelivery locationTime windowaxiayibxibyiEiFiLi12725220019252062.502030215752587.51787.5412.502030316501512.51837.52362.5020304637.51012.51262.5207502030514251887.51687.516500253561262.52137.52000235003040787511251612.52250030408242514501487.5222503040913751850235026000304010137518501837.52362.503040112087.512501862.514250405012145027002400237504050132187.56251437.51362.504050142800232519251887.510354515265022252250217510354516282524252012.5175010354517887.51137.51825205010354518167532523501725206070191512.51362.51462.52387.52060702026252262.5180010502060702126252262.51687.5165020607022912.5687.52175737.52060702319252062.52725220004050241787.5412.5575587.503040251837.52362.516501512.503040261262.52075637.51012.503040271687.5165014251887.50354528200023501262.52637.503040291612.52250875112503040301487.5222572514500304031235026001375185003040321837.52362.51375185003040331862.514252087.512500405034240023751450270004050351437.51362.52187.5625040503619251887.528002325103545372250147526502225103545382012.51750282524251035453918252050887.51137.51035454023507251675132520607041912.51587.5218060004050


### 5.1. Meal Order Clustering

The delivery bundles clustered from these forty-one takeout meal orders using the ward HAC algorithm in the first stage are shown in the hierarchical clustering tree diagram in Figure7. The number of the clustered bundle is varied in different agglomerating layers that are indicated with h1, h2, and h3 horizontal lines in the tree diagram. In the h1 agglomerating layer, eight delivery bundles are clustered out from these forty-one meal orders. There are six delivery bundles clustered out in the h2 agglomerating layer. The h3 agglomerating layer clustered out five delivery bundles.Figure 7
Meal orders clustered into delivery bundles by the ward HAC algorithm.Considering available delivery riders and fast meal delivery requirement, eight delivery bundles in theh1 agglomerating layer are determined as clustering results in the first stage, which are assigned to eight riders. As shown in Figures 8 and 9, these eight delivery bundles include diverse numbers of meal orders. Delivery bundle 1 includes four meal orders, orders 13, 18, 24, and 40. Delivery bundle 2 includes six meal orders, orders 5, 6, 9, 10, 26, and 41. Delivery bundle 3 includes eight meal orders, orders 1, 14, 15, 16, 20, 21, 31, and 34. Delivery bundle 4 includes four meal orders, orders 4, 7, 17, and 22. Delivery bundle 5 includes seven meal orders, orders 2, 12, 25, 28, 29, 30, and 32. Delivery bundle 6 includes four meal orders, orders 8, 11, 33, and 37. Delivery bundle 7 includes four meal orders, orders 23, 36, 38, and 39. Delivery bundle 8 includes four meal orders, orders 3, 19, 27, and 35. The effectiveness of HAC algorithm based on the nearest location is also revealed from the spatial distribution of forty-one meal orders and eight delivery bundles in Figure 8.Figure 8
Spatial distribution of 41 orders and 8 clustered bundles.Figure 9
Delivery routes of 8 clustered bundles.


### 5.2. Clustered Bundle Routing Optimization

The optimal delivery routes for meal orders in eight clustered bundles are numerically calculated by applying the GA heuristic method in the second stage as shown in Figure9. The delivery time of each meal order in eight optimized delivery routes is listed in Table 4. Table 4 also lists the average customer time satisfaction of the meal orders in eight clustered delivery bundles. The average customer time satisfaction for the low, medium, and high time sensitivity of the customers is further compared when time sensitivity coefficient is set as βL = 0.5, βM = 1, and βH = 1.5.Table 4
Meal delivery time and average time satisfaction in clustered bundles.
Bundle (rider) numberOrder numberEiFiLiDelivery time (minutes)Average time satisfactionβL = 0.5βM = 1βH = 1.51130405018.091114020607019.54240304027.521820607040.222100304020.420.7480.6280.56960304021.4090304023.9950253530.97260304038.37410405047.9931410354525.000.9110.8510.81210203026.051510354528.131610354531.062120607033.11310304035.35340405040.492020607050.65440203019.0311170304021.391710354523.152220607031.335250304023.380.5960.5240.336290304028.60300304030.76320304035.36280304040.15120405047.1820203059.57680304018.40111110405023.72330405025.443710354532.227230405017.091113610354517.973810354518.593910354532.6830203017.601111920607019.86270354522.88350405031.77The numerical simulation results indicate that four meal orders in five delivery bundles 1, 4, 6, 7, and 8 could be delivered within the delivery time window. Therefore, the average customer time satisfaction of these five delivery bundles 1, 4, 6, 7, and 8 are equal to 1, which indicates high customer satisfaction with meal delivery time. Moreover, most of the meal orders in these five delivery bundles could be delivered to the customer within around thirty minutes, which demonstrates good performance of fast meal delivery services. Even meal order 18 in delivery bundle 1 could still be delivered before the latest arrival timeF18 = 60 minutes.Some delayed meal orders exceeded the delivery time window in delivery bundles 2, 3, and 5 are shaded in gray in Table4. Three meal orders in delivery bundle 2 could be delivered within the delivery time window, while three delayed meal orders could exceed the delivery time window but within the acceptable delayed arrival time period. There are three delayed meal orders of eight orders in delivery bundle 3 that fall within the acceptable delayed time period. However, two of seven meal orders in delivery bundle 5 could be seriously delayed and could exceed the acceptable delayed arrival time, whereas three meal orders could be delivered within the delivery time window and the other two delayed meal orders could be delivered within the acceptable delayed time period. Therefore, the average customer time satisfaction of these three delayed bundles 2, 3, and 5 are less than 1, which indicates lower customer satisfaction with meal delivery time.The simulation results verify that the two-stage solution on customer time satisfaction with HAC meal order clustering and cluster-based GA routing optimization in this study is an effective strategy with good performance to improve fast services for O2O meal delivery. Customer satisfaction is improved by delivering all meal orders on every delivery route within 60 minutes. In particular, the majority of the meal orders could be delivered to the customers within around thirty minutes, which demonstrated great performance of fast meal delivery services. Appropriate meal orders clustered in the delivery bundle, which are around four meal orders in this instance, are critical to achieving high customer time satisfaction with fast meal delivery services.The proposed two-stage solution with HAC and GA is compared with the standard GA and the PSO algorithm [41] in the same scale simulated instance. The simulation results on delivery time and customer satisfaction of three different algorithms are shown in Table 5. Obviously, the proposed two-stage solution greatly improves customer satisfaction by delivering every single meal order in all cluster-based delivery routes within 60 minutes, which is particularly important for fast meal delivery services. The proposed two-stage solution and the PSO algorithm both have better performance on delivery time and customer satisfaction than the standard GA. Although the PSO algorithm can obtain a slightly shorter average delivery time per order, the delivery time for one of the routes is around 73 minutes, which exceeds the acceptable delayed arrival time. The delayed delivery of the meal orders that exceed the acceptable delayed arrival time reduces customer satisfaction with fast services for meal delivery platforms. Therefore, the proposed two-stage solution with HAC meal order clustering first and cluster-based GA routing optimization second could provide good performance on customer satisfaction improvement of the fast meal delivery services.Table 5
Simulation results obtained by different algorithms.
AlgorithmAverage delivery time per order (unit: min)Delivery completion time (unit: min)Route time over 60 minsNumber of ridersAverage customer satisfactionβL = 0.5βM = 1βH = 1.5Two-stage7.959294.5080.8760.8350.786GA8.239337.7070.6750.6240.600PSO7.368290.1160.7540.7270.713


### 5.3. Impact of Time-Sensitive Customer Heterogeneity

The impact of time-sensitive customer heterogeneity on the satisfaction with fast meal delivery is shown in Table4 and Figure 10. We can conclude that the time sensitivity degrees of heterogeneous customers have the impact on the satisfaction with meal delivery when some meal orders in clustered bundles are delayed. Customer time satisfaction of low time-sensitive customers with a time sensitivity coefficient of βL = 0.5 (0 < β < 1) is higher than medium time-sensitive customers (βM = 1). Therefore, low time-sensitive customers might not feel very dissatisfied when the meal order is delayed within the acceptable time period. The delayed meal delivery in a short time window will not affect the satisfaction of low time-sensitive customers. In contrast, customer time satisfaction of high time-sensitive customers with a time sensitivity coefficient of βH = 1.5 (β > 1) is lower than medium time-sensitive customers (βM = 1). Hence, high time-sensitive customers will feel strongly dissatisfied when the meal order is delayed even if it is within the normal acceptable time period. The delayed meal delivery will give high time-sensitive customers a negative service experience.Figure 10
Comparison on heterogeneous time-sensitive customer satisfaction.Moreover, customer time satisfaction is found to be reduced with the increment in the time sensitivity coefficient in the analysis taking the delayed meal order 32 in delivery bundle 5 as an example in Figure11. Thus, time sensitivity degrees of heterogeneous customers have the negative impact on customer satisfaction with meal delivery. The higher time sensitivity degree the customers have, the lower satisfaction the customers could feel on meal delivery. The time-sensitive customer satisfaction with meal delivery sharply decreases with the increment in the time sensitivity coefficient β, especially when 0 < β < 2. When the time sensitivity coefficient β > 2, customer time satisfaction with meal delivery is gradually reduced to zero. Hence, the high time-sensitive customers who really care about the timely meal delivery (β > 1) will have strong dissatisfaction with delayed meal delivery. The low time-sensitive customers who do not care the delayed meal delivery (β = 0) have the highest time satisfaction.Figure 11
Impact of time sensitivity coefficient on customer time satisfaction.However, time sensitivity degrees of heterogeneous customers will have no impact on the time satisfaction with meal delivery if all meal orders in clustered bundles are timely delivered within the delivery time windows. Customer time satisfaction with meal delivery for orders in clustered bundle 1, bundle 4, bundle 6, bundle 7, and bundle 8 maintains the highest value (Si = 1) no matter what the time sensitivity coefficient is, as shown in Table 4 and Figure 10. Therefore, it is extremely important for O2O meal delivery platforms to design solution for timely delivered orders so that customer time satisfaction with fast meal delivery services can be significantly enhanced.


## 5.1. Meal Order Clustering

The delivery bundles clustered from these forty-one takeout meal orders using the ward HAC algorithm in the first stage are shown in the hierarchical clustering tree diagram in Figure7. The number of the clustered bundle is varied in different agglomerating layers that are indicated with h1, h2, and h3 horizontal lines in the tree diagram. In the h1 agglomerating layer, eight delivery bundles are clustered out from these forty-one meal orders. There are six delivery bundles clustered out in the h2 agglomerating layer. The h3 agglomerating layer clustered out five delivery bundles.Figure 7
Meal orders clustered into delivery bundles by the ward HAC algorithm.Considering available delivery riders and fast meal delivery requirement, eight delivery bundles in theh1 agglomerating layer are determined as clustering results in the first stage, which are assigned to eight riders. As shown in Figures 8 and 9, these eight delivery bundles include diverse numbers of meal orders. Delivery bundle 1 includes four meal orders, orders 13, 18, 24, and 40. Delivery bundle 2 includes six meal orders, orders 5, 6, 9, 10, 26, and 41. Delivery bundle 3 includes eight meal orders, orders 1, 14, 15, 16, 20, 21, 31, and 34. Delivery bundle 4 includes four meal orders, orders 4, 7, 17, and 22. Delivery bundle 5 includes seven meal orders, orders 2, 12, 25, 28, 29, 30, and 32. Delivery bundle 6 includes four meal orders, orders 8, 11, 33, and 37. Delivery bundle 7 includes four meal orders, orders 23, 36, 38, and 39. Delivery bundle 8 includes four meal orders, orders 3, 19, 27, and 35. The effectiveness of HAC algorithm based on the nearest location is also revealed from the spatial distribution of forty-one meal orders and eight delivery bundles in Figure 8.Figure 8
Spatial distribution of 41 orders and 8 clustered bundles.Figure 9
Delivery routes of 8 clustered bundles.


## 5.2. Clustered Bundle Routing Optimization

The optimal delivery routes for meal orders in eight clustered bundles are numerically calculated by applying the GA heuristic method in the second stage as shown in Figure9. The delivery time of each meal order in eight optimized delivery routes is listed in Table 4. Table 4 also lists the average customer time satisfaction of the meal orders in eight clustered delivery bundles. The average customer time satisfaction for the low, medium, and high time sensitivity of the customers is further compared when time sensitivity coefficient is set as βL = 0.5, βM = 1, and βH = 1.5.Table 4
Meal delivery time and average time satisfaction in clustered bundles.
Bundle (rider) numberOrder numberEiFiLiDelivery time (minutes)Average time satisfactionβL = 0.5βM = 1βH = 1.51130405018.091114020607019.54240304027.521820607040.222100304020.420.7480.6280.56960304021.4090304023.9950253530.97260304038.37410405047.9931410354525.000.9110.8510.81210203026.051510354528.131610354531.062120607033.11310304035.35340405040.492020607050.65440203019.0311170304021.391710354523.152220607031.335250304023.380.5960.5240.336290304028.60300304030.76320304035.36280304040.15120405047.1820203059.57680304018.40111110405023.72330405025.443710354532.227230405017.091113610354517.973810354518.593910354532.6830203017.601111920607019.86270354522.88350405031.77The numerical simulation results indicate that four meal orders in five delivery bundles 1, 4, 6, 7, and 8 could be delivered within the delivery time window. Therefore, the average customer time satisfaction of these five delivery bundles 1, 4, 6, 7, and 8 are equal to 1, which indicates high customer satisfaction with meal delivery time. Moreover, most of the meal orders in these five delivery bundles could be delivered to the customer within around thirty minutes, which demonstrates good performance of fast meal delivery services. Even meal order 18 in delivery bundle 1 could still be delivered before the latest arrival timeF18 = 60 minutes.Some delayed meal orders exceeded the delivery time window in delivery bundles 2, 3, and 5 are shaded in gray in Table4. Three meal orders in delivery bundle 2 could be delivered within the delivery time window, while three delayed meal orders could exceed the delivery time window but within the acceptable delayed arrival time period. There are three delayed meal orders of eight orders in delivery bundle 3 that fall within the acceptable delayed time period. However, two of seven meal orders in delivery bundle 5 could be seriously delayed and could exceed the acceptable delayed arrival time, whereas three meal orders could be delivered within the delivery time window and the other two delayed meal orders could be delivered within the acceptable delayed time period. Therefore, the average customer time satisfaction of these three delayed bundles 2, 3, and 5 are less than 1, which indicates lower customer satisfaction with meal delivery time.The simulation results verify that the two-stage solution on customer time satisfaction with HAC meal order clustering and cluster-based GA routing optimization in this study is an effective strategy with good performance to improve fast services for O2O meal delivery. Customer satisfaction is improved by delivering all meal orders on every delivery route within 60 minutes. In particular, the majority of the meal orders could be delivered to the customers within around thirty minutes, which demonstrated great performance of fast meal delivery services. Appropriate meal orders clustered in the delivery bundle, which are around four meal orders in this instance, are critical to achieving high customer time satisfaction with fast meal delivery services.The proposed two-stage solution with HAC and GA is compared with the standard GA and the PSO algorithm [41] in the same scale simulated instance. The simulation results on delivery time and customer satisfaction of three different algorithms are shown in Table 5. Obviously, the proposed two-stage solution greatly improves customer satisfaction by delivering every single meal order in all cluster-based delivery routes within 60 minutes, which is particularly important for fast meal delivery services. The proposed two-stage solution and the PSO algorithm both have better performance on delivery time and customer satisfaction than the standard GA. Although the PSO algorithm can obtain a slightly shorter average delivery time per order, the delivery time for one of the routes is around 73 minutes, which exceeds the acceptable delayed arrival time. The delayed delivery of the meal orders that exceed the acceptable delayed arrival time reduces customer satisfaction with fast services for meal delivery platforms. Therefore, the proposed two-stage solution with HAC meal order clustering first and cluster-based GA routing optimization second could provide good performance on customer satisfaction improvement of the fast meal delivery services.Table 5
Simulation results obtained by different algorithms.
AlgorithmAverage delivery time per order (unit: min)Delivery completion time (unit: min)Route time over 60 minsNumber of ridersAverage customer satisfactionβL = 0.5βM = 1βH = 1.5Two-stage7.959294.5080.8760.8350.786GA8.239337.7070.6750.6240.600PSO7.368290.1160.7540.7270.713


## 5.3. Impact of Time-Sensitive Customer Heterogeneity

The impact of time-sensitive customer heterogeneity on the satisfaction with fast meal delivery is shown in Table4 and Figure 10. We can conclude that the time sensitivity degrees of heterogeneous customers have the impact on the satisfaction with meal delivery when some meal orders in clustered bundles are delayed. Customer time satisfaction of low time-sensitive customers with a time sensitivity coefficient of βL = 0.5 (0 < β < 1) is higher than medium time-sensitive customers (βM = 1). Therefore, low time-sensitive customers might not feel very dissatisfied when the meal order is delayed within the acceptable time period. The delayed meal delivery in a short time window will not affect the satisfaction of low time-sensitive customers. In contrast, customer time satisfaction of high time-sensitive customers with a time sensitivity coefficient of βH = 1.5 (β > 1) is lower than medium time-sensitive customers (βM = 1). Hence, high time-sensitive customers will feel strongly dissatisfied when the meal order is delayed even if it is within the normal acceptable time period. The delayed meal delivery will give high time-sensitive customers a negative service experience.Figure 10
Comparison on heterogeneous time-sensitive customer satisfaction.Moreover, customer time satisfaction is found to be reduced with the increment in the time sensitivity coefficient in the analysis taking the delayed meal order 32 in delivery bundle 5 as an example in Figure11. Thus, time sensitivity degrees of heterogeneous customers have the negative impact on customer satisfaction with meal delivery. The higher time sensitivity degree the customers have, the lower satisfaction the customers could feel on meal delivery. The time-sensitive customer satisfaction with meal delivery sharply decreases with the increment in the time sensitivity coefficient β, especially when 0 < β < 2. When the time sensitivity coefficient β > 2, customer time satisfaction with meal delivery is gradually reduced to zero. Hence, the high time-sensitive customers who really care about the timely meal delivery (β > 1) will have strong dissatisfaction with delayed meal delivery. The low time-sensitive customers who do not care the delayed meal delivery (β = 0) have the highest time satisfaction.Figure 11
Impact of time sensitivity coefficient on customer time satisfaction.However, time sensitivity degrees of heterogeneous customers will have no impact on the time satisfaction with meal delivery if all meal orders in clustered bundles are timely delivered within the delivery time windows. Customer time satisfaction with meal delivery for orders in clustered bundle 1, bundle 4, bundle 6, bundle 7, and bundle 8 maintains the highest value (Si = 1) no matter what the time sensitivity coefficient is, as shown in Table 4 and Figure 10. Therefore, it is extremely important for O2O meal delivery platforms to design solution for timely delivered orders so that customer time satisfaction with fast meal delivery services can be significantly enhanced.


## 6. Conclusion

This study focuses on meal delivery routing optimization with customer time satisfaction and heterogeneous time-sensitive customers. Compared with the conventional objective of delivery cost minimization, we firstly adopt customer satisfaction as the objective to optimize meal delivery routing. The customer time satisfaction function is related to time sensitivity of heterogeneous customers. A two-stage solution with HAC and GA is proposed for meal delivery routing optimization to improve fast services of huge volume meal orders. In the first stage, the HAC algorithm is designed to cluster meal orders into the delivery bundles for riders with the nearest pickup location rule. The ward agglomerating method is adopted to use the sum of deviation squares for measuring the distance between two bundles. In the second stage, the cluster-based meal delivery optimization model is established to obtain the optimal delivery route for meal orders clustered in the delivery bundle in the first stage. The GA is designed to search for the optimal meal delivery route by applying the fitness function of customer time satisfaction.The numerical simulation results showed that the proposed two-stage solution with HAC and GA for meal delivery routing optimization is verified to improve customer satisfaction with fast meal delivery by timely delivering meal orders within the delivery time window. Moreover, the proposed two-stage solution, which firstly clusters meal orders into a delivery bundle and secondly optimizes the cluster-based delivery route for riders, could improve the efficiency of fast meal delivery for O2O meal delivery platforms significantly. All meal orders in every cluster-based delivery route could be delivered to customers within 60 minutes with most of the orders being under thirty minutes. Furthermore, the effectiveness of the proposed two-stage solution is validated by comparing it with the standard GA and the PSO algorithm. The proposed two-stage solution with HAC and GA outperforms the standard GA and the PSO algorithm on customer satisfaction and delivery efficiency.The proper number such as four meal orders clustered into a delivery bundle in this simulation and optimal delivery routes is found to be essential factors for timely delivering all meal orders within the delivery time window in order to achieve the highest customer time satisfaction. The time sensitivity of customers has the negative impact on customer time satisfaction. The delayed meal delivery would be accepted by low time-sensitive customers as it does not have much influence on their satisfaction with meal delivery. In contrast, the delayed meal delivery would cause dissatisfaction with meal delivery for high time-sensitive customers.Our study provides some managerial sights for meal delivery platforms in scheduling optimization and customer satisfaction improvement. Firstly, in the competitive meal catering market, customer satisfaction improvement is becoming the critical key to attracting customers and maintaining customers’ loyalty to the meal delivery platform. Thus, our research offers meal delivery platforms a method to incorporate customer satisfaction factors into delivery routing problems. The proposed solution in our research can effectively improve customer satisfaction and optimize scheduling decisions of meal delivery platforms. Secondly, heterogeneous customers have different experiences with fast meal delivery services. Our research results could help O2O meal delivery platforms to establish time-sensitive customer profiles and integrate time sensitivity factors into delivery routing decisions. Thirdly, our meal order clustering algorithm could highly improve fast delivery efficiency and reduce the delivery cost. Therefore, the meal order clustering algorithm application is valuable to optimize scheduling for practical meal delivery platforms. Finally, the two-stage solution in our study investigated the practical scheduling optimization process for meal delivery platforms.The O2O meal delivery platform is facing complicated scenarios in practice, such as traffic congestion, road complexity, or extreme weather conditions, which may be considered in the routing optimization in future research. Despite that the number of meal orders is fixed in this study, the real demand for O2O takeout meals is changing in real time since the customers could place the online meal through the platforms at anytime and anywhere. Thus, the dynamic insertion of new meal orders may be considered in the realistic research on delivery scheduling optimization in the future. Moreover, both customer satisfaction and delivery cost are critical for O2O meal delivery platforms. Therefore, multiple objectives might be also applied in future studies on meal delivery routing optimization. We set fixed time sensitivity coefficients for meal orders to simplify simulation in this study, and different time sensitivity coefficients might be assigned for each meal order in future realistic studies. Lastly, in-depth studies on algorithms design may be a further improvement in meal delivery optimization.



---

*Source: 9711074-2022-07-07.xml*