Optimal Allocation of Distribution Points for Delivery Orders
By Hang Li, Yuntai Zeng, Ke Liu as part of course project of ECE1724H: Bio-inspired Algorithms for Smart Mobility. Dr. Alaa Khamis, University of Toronto, 2023.
Abstract:
The escalating demand for prompt and reliable food delivery services in urban landscapes necessitates an enhanced approach to order distribution. This study introduces bio-inspired computational strategies, Simulated Annealing (SA) and Genetic Algorithms (GA) to optimize courier order allocation. By simulating real-time order assignment, this research seeks to develop a mathematical model that reflects complex real-world scenarios, aiming to improve the efficiency and reliability of food delivery systems. Our findings indicate that achieving a more optimal solution often requires an increase in algorithm time, achieved through higher iteration or generation counts or an enlarged population size. However, it is noteworthy that a reasonably good solution can be obtained within real-time constraints. Further discussion suggests that Genetic Algorithms (GA) exhibit superior performance, particularly when implemented with high parallelism on modern equipment.
Introduction:
The burgeoning realm of food delivery services presents an intricate challenge in effectively managing the distribution of orders to couriers. This project was conceived out of a necessity to enhance operational efficiency in urban settings, where the demand for swift and dependable delivery services is continuously escalating. Our research endeavors to tackle the intricate logistics involved in allocating numerous orders to available couriers, aiming to refine the balance between expediency and service reliability.
In order to solve the problem of reasonable distribution of food orders, we seperately use two innovative bio-inspired computational techniques: the Simulated Annealing (SA) and Genetic Algorithm (GA). These methodologies were selected due to their adeptness at finding the optimal solution among mutiple complex choices.
Our experimental design simulates a scenario wherein food orders are systematically assigned to delivery men at five-minute intervals. Each delivery person maintains a dynamic list of orders, subject to periodic updates via our selected algorithms. This procedure is pivotal in refining the order allocation process, ensuring both the optimization of delivery routes and the steadfastness of service once an order is in transit.
Our project mainly contains two aspects. Primarily, it seeks to construct a mathematical model that mirrors the real-world complexities of order distribution. Additionally, the project aspires to rigorously assess the performance of these algorithms under varied operational conditions.
This paper unfolds with a comprehensive review of existing methodologies, followed by an in-depth exposition of our problem formulation and modeling strategy. Subsequent sections will delve into our proposed algorithms, evaluate their effectiveness, synthesize our data to get a relatively optimal solution and make some logical conclusions.
Literature Review:
The exploration of optimization in food delivery order allocation bears similarity to the methodologies applied in the vehicle routing problem with time windows, as explored by Bent and Van Hentenryck [1]. Both problems deal with the efficient assignment of tasks to agents within specified time constraints. However, our approach extends this by focusing on the dynamic nature of food delivery, where decisions must be made in real-time or near-real-time, accommodating rapid changes in customer demand and traffic conditions.
In supply chain network design, Vishnu et al. utilize Genetic Algorithms for strategic planning [2], which aligns with our use of GAs for operational efficiency in food delivery. While both applications employ GAs to optimize logistics, our solution is distinguished by the emphasis on immediate decision-making and frequent re-routing, in contrast to the long-term planning focus in supply chain design.
Torrent-Fontbona et al ’s approach to ILA using Simulated Annealing [3] differs from ours in that it optimizes for service provision rather than location-based logistics. Our solution, while also employing Simulated Annealing, diverges by considering the geographical aspects of order delivery, factoring in the physical movements of delivery personnel.
Overall, while the foundational principles of optimization are shared across these domains, our food delivery order allocation solution is uniquely characterized by its real-time adaptability and responsiveness to the immediate, unpredictable nature of food delivery logistics.
Exploratory Spatial Data Analysis:
Problem dataset:
Although there are many information recorded in the dataset, what we will use is part of them including:
1.Timestamp: the time that order is created.
2. User Information: Information about the users placing the orders, the location that order needed to be delivered which consist of the latitude and longitude coordinates.
3. Information for Restaurants: The location of the restaurant, including the latitude and longitude coordinates.
4. Actual delivery minutes: The time for each order to be delivered.
Also, we will use the OpenStreetMap NetworkX (OSMnx) which is a Python library for acquiring, analyzing, and visualizing urban street network data from OpenStreetMap (OSM) [5]. It allows users to retrieve detailed information about streets, buildings, and other urban features, as well as perform spatial analyses and create visualizations of urban networks.
Cluster map:
Upon this geographic canvas, we apply the DBSCAN clustering algorithm to identify natural groupings of restaurant locations, resulting in our cluster map. This advanced visualization clusters restaurants based on their proximity, highlighting areas with a high density of service providers. Each cluster is marked, providing a visual representation of potential hotspots within the city (Fig. 1).
Order map:
This map can display the new coming orders at a specific time region. (The figure below describes the new orders at 2020 Aug 1st 10:00 AM — 2020 Aug 1st 10:05 AM) Also, there is a popup window for the user location icon to display the estimated time window (Fig. 2).
Running map:
This map shows the delivery person’s location with a user icon, and the pickup coordinate as a starter icon, and the client’s location as pin icon. Also the routes for each delivery person are shown in the map with different colors. Also, there is a popup window for the user location icon to display the estimated delivery time (Fig. 3).
Problem Formulation and Modeling:
Our module requires:
Assumption:
We assume the time_step for each batch of orders to get dispatched is 5 minutes. This means that dispatch_time_step=5 minutes.
We have 2 main Objects:
Initialization of objects:
Our Order Object contains the following attributes:
Our Delivery Person Object contains the following attributes:
Our goal is to minimize the total time cost for completing all orders:
Constraints:
The delivery person’s coordinate will always drive (use drive routes) to the node coordinate with the shortest straight distance.
When the delivery person’s coordinate arrives at the start coordinate of a not_picked order (state = 0) from the orderList, the person has to wait until the order is ready (pick_time arrives) to change the state of the order to “picked/delivering” (state is 1)
When the delivery person’s coordinate arrives at the end coordinate of a picked/delivering order (state = 1), and saves the delivery_time, and changes the order state to “completed” (state 2)
When the orderList of the delivery person is empty, the delivery person’s coordinate will not change until another order is dispatched.
Proposed Solution:
In our implementation, we are trying to solve the problem by using SA (Simulated annealing algorithm) and GA (genetic algorithm).
Simulated annealing:
Simulated annealing draws inspiration from the annealing process in metallurgy, where a material is heated and then gradually cooled to remove defects and optimize its structure.
Similarly, in our algorithm, the system is trying to find the best (global optimal) order dispatching method to minimize the total delivering time.
- Initialization: We used a random dispatching method as an initialized method.
- Temperature: We used the total consumed time as temperature
- Neighbor definition: The neighbor is defined by moving a movable order (not picked order, state = 0) to another delivery person.
- Termination: We are using zero late order as the termination condition. (However, there might be no dispatching solution with zero late order, so we set a maximum recursive value (SA_fireOut = 4) to force the system to terminate.
Genetic algorithm:
Genetic algorithm is chosen for its efficacy in handling complex optimization problems, especially when multiple decision variables and system dynamics are involved.
In our module, we are trying to find the best allocation of distributed delivery orders to minimize the total delivering time.
- Individual definition: a list of orderList (of every delivery person with the same order).
- Initialize population: We used a random dispatching method as an initialized individual, also the picked/delivering orders are set at the corresponding position for each individual permanently.
- Fitness: We calculate the fitness value for each solution based on the total delivery time and the number of late orders times, thereby driving the GA towards more optimized solutions. (fitness = 1 / delivery_time (in sec) + late_order_num * 60 + 1 (in case all 0))
- Selection: We select the fittest individuals as elitism (which has the best fitness score) first, and select individuals with the probability based on the individuals’ fitness scores one by one until the size reaches half of populationSize. (The selection can be duplicate)
- Crossover: We use a random crossover strategy to crossover parents with a given crossoverRate (set as 0.5). For each orderList, there is a probability to be crossover. child1 will use parent1’s orderList if no crossover happens, child1 will use parent2’s orderList if crossover happens. Furthermore, the child1 will remove the duplicate orders from the parent2, and the missing orders will be added back based on the position from parent1. (We generate populationSize next generation individuals in crossover progress. (pop 1 element if the populationSize is odd.))
- Mutation: We randomly move a not picked order (state = 0) from one orderList to another orderList.
- Replacement: We simply replace the population with the new generated population.
Performance Evaluation:
Upon rigorous quantitative and qualitative assessment of the Simulated Annealing (SA) algorithm’s performance for dispatch optimization, we observe the following trends and implications based on Fig. 4:
Quantitatively, a steady decrease as iterations progress underpins a trend toward improved per-order efficiency, with 40 iterations yielding a notable enhancement, and the algorithm runtime is increasing as the iteration increases.
Qualitatively, considering the stability and reliability, the data suggests a consistent improvement in the algorithm’s output up to a certain threshold, beyond which gains are marginal. The iteration 40 is a special case which means that it reaches a good method at “start”.
For algorithm adaptability, the varying performance across different iteration counts indicates the algorithm’s adaptability, with 40 iterations emerging as the most effective balance between operational efficiency and computational demand.
Conclusively, the optimal parameter for the SA algorithm, within the tested range, appears to be at 40 iterations with a cooling factor (SA_k) of 0.95. This setting offers a compelling trade-off between delivery punctuality, efficiency, and computational feasibility, which are pivotal for real-world applicability in dynamic delivery environments.
According to Fig. 5, quantitatively, the delivery time initially decreases as the SA_k value increases from 0.8 to 0.85, suggesting that a higher cooling rate initially helps in finding faster delivery routes. However, as SA_k increases further to 0.9, there’s a noticeable increase in delivery time, indicating a possible over-tuning of the algorithm parameters that could lead to inefficiency.
Qualitatively, the graph (Fig. 5) suggests that there is an optimal range for the cooling factor, around 0.85, where the algorithm achieves better performance in minimizing delivery time. Beyond this range, the effectiveness of the algorithm seems to diminish.
Conclusively, 0.85 should be the best cooling factor, and the algorithm time is not related with this factor.
Based on Fig. 6, the Genetic Algorithm (GA) shows an interesting performance trend over various generations. Quantitatively, the delivery time decreases initially but then plateaus, suggesting that the GA is quickly finding a near-optimal solution but then struggles to make significant further improvements. The running time, however, increases steadily with each generation, indicating a higher computational cost as the GA progresses. Qualitatively, it seems the GA efficiently optimizes delivery routes up to a point, after which additional generations do not yield proportional benefits, potentially due to the algorithm converging on a local minimum or the parameter settings not encouraging enough diversity in the population for further exploration.
From Fig. 7 showing Genetic Algorithm performance with a constant generation count, crossover rate, and mutation rate, we can discern both quantitative and qualitative insights.
Quantitatively, as the population size increases, the delivery time initially decreases, indicating that a larger population size helps the GA to find more efficient solutions. However, after a certain point, the delivery time plateaus, suggesting a diminishing return on increasing population size. The running time of the GA increases almost linearly with the population size, which is expected as a larger population requires more computational resources to evaluate.
Qualitatively, the GA demonstrates an initial improvement in optimizing delivery times as diversity increases with population size. Yet, there seems to be an optimal threshold for the population size, beyond which no significant improvement in delivery time is observed. This indicates that while a larger population provides a richer set of candidates for evolution, beyond a certain point, the additional computational effort does not translate into better solutions. The challenge lies in finding the right balance between a population large enough to ensure diversity and a manageable computational load.
Fig. 8 depicts the Genetic Algorithm (GA)’s performance relative to its crossover rate, given a fixed population size and mutation rate. Quantitatively, the delivery time decreases as the crossover rate increases from 0.3 to 0.5, after which it rises, peaking at a crossover rate of 0.55, then sharply declines at 0.6 and starts to rise again. The running time inversely correlates with the delivery time initially but begins to increase steadily after the crossover rate exceeds 0.55, indicating higher computational effort.
Qualitatively, the performance improvement up to a 0.5 crossover rate may indicate better exploration and exploitation of the solution space, but beyond this point, the GA may be converging too quickly or suffering from premature convergence, leading to suboptimal solutions. The optimal crossover rate seems to balance the exploration of new solutions and the refinement of existing ones without excessive computational cost.
Fig. 9 presents the performance of a Genetic Algorithm (GA) over different mutation rates, given a fixed generation count and crossover rate.
Quantitatively, the delivery time shows a general decreasing trend as the mutation rate increases up to 0.1, suggesting that introducing mutations enhances the algorithm’s ability to escape local optima and find more efficient solutions. However, beyond this point, delivery time increases, implying too much mutation can disrupt the convergence process. The running time remains relatively stable but shows a slight uptick as the mutation rate increases, which is expected due to the additional computational effort required to apply mutations.
Qualitatively, the GA benefits from a moderate level of mutation that introduces variability into the population, fostering exploration of the solution space. Yet, an excessive mutation rate seems to degrade performance, indicating a delicate balance necessary to maintain a constructive search for optimal solutions. The optimal mutation rate, in this case, appears to be around 0.1, where the balance between exploration and exploitation is most effectively achieved.
Conclusions and discussions:
Conclusions:
By viewing the generated result (average consuming time for orders), the Simulated Annealing algorithm improves consistently with increasing iterations, particularly when k is set to 0.85. However, a notable anomaly occurs at iteration 40, possibly due to coincidental random values.
In contrast, the Genetic algorithm demonstrates steady improvement without critical points. Increasing the population size positively influences its performance, while crossover choice has minimal impact. A mutation rate of 10% (0.1) yields optimal results.
After viewing the algorithm time, the algorithm consuming time is increasing with increasing iterations or generations or populationSize. (Clearly) It means the parameters that can make the algorithm perform better will take longer time. However, the mutation rate has positive effects while setting as 10% (0.1) with no algorithm time influence.
By observing these 2 algorithms’ plots, we can see that the GA can produce much better results, but cost more algorithm time. Based on our assumption, we read orders each 5 min and dispatch them, so it makes sense if the algorithm time is less than the real passing time. In addition, we streamlined some processes for a faster experimental workflow. (Loading only 1 core region in the map, and using straight lines for rest regions.)
Discussions:
Why is there a critical point at iteration 40 in the Simulated Annealing algorithm?
There might be a good initialized random dispatching method and the result may change a lot even with a small change (order swap in our algorithm).
Why does the crossover have few influence on the algorithm?
The crossover strategy we are using is a random crossover. It means that the crossover may happen anywhere, and the experiments set the deliveryPersonNum as 3, so there is a high probability that no crossover happens. In addition, the populationSize is not large enough, there might be a lot of same or similar individuals in the parents set.
Why does the SA_k have a critical point at 99%?
In SA, the neighbors are too “far” from each other, which means that a large influence may happen with a small change, so the speed of cooling may be out of control of the SA_k.
References:
- Bent, R., & Van Hentenryck, P. (2004). A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science, 38(4), 515–530. https://doi.org/10.1287/trsc.1030.0049
- Vishnu, C. R., Das, S. P., Sridharan, R., Ram Kumar, P. N., & Narahari, N. S. (2021). Development of a reliable and flexible supply chain network design model: a genetic algorithm based approach. International Journal of Production Research, 59(20), 6185–6209. https://doi.org/10.1080/00207543.2020.1808256 3.
- Torrent-Fontbona, F., Munoz, V., & Lopez, B. (2013). Solving large immobile location–allocation by affinity propagation and simulated annealing. Application to select which sporting event to watch. Expert Systems with Applications, 40(11), 4593–4599. https://doi.org/10.1016/j.eswa.2013.01.065
- Delivery dataset: Jack McMenamin https://www.kaggle.com/datasets/jackmcmenamin/orders-autumn-2020/data
- Osmnx dataset: Boeing, G. 2017. OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks. Computers, Environment and Urban Systems 65, 126–139.
