Optimizing Food Delivery Routes with Ant Colony Optimization: A Solution for Thriving Delivery Markets

By Youngsup(Billy) Shin, Yunru(Ellen) Pan, and Yu(Ray) Gu as part of course project of ECE1724H: Bio-inspired Algorithms for Smart Mobility. Dr. Alaa Khamis, University of Toronto, 2023.

Image Source: The Guardian

Abstract

The rapid growth of urban food delivery services poses significant challenges for efficient route planning and optimization. One of the main challenges is effectively managing pickups in busy urban areas. To address this issue, our study focuses on urban food delivery optimization using the Vehicle Routing Problem with Time Windows (VRPTW) and incorporates the concept of business circles for efficient pickups. To tackle the routing issues associated with VRPTW, we propose implementing the Ant Colony Optimization (ACO) algorithm. This algorithm is designed to optimize delivery routes by considering factors such as cost efficiency, timely delivery, and customer satisfaction. It simulates the process of pheromone-laying and path-finding to identify the most optimal routes for food delivery. To evaluate the performance of the ACO algorithm, we conduct extensive performance evaluations against various benchmark scenarios. These scenarios are carefully designed to mimic real-world application data and provide insights into the practical viability of the algorithm. By comparing the results with real-world application data, we can analyze the effectiveness of the ACO algorithm in addressing the challenges of urban food delivery.

Overall, this project highlights the potential of ACO-based optimization in managing the complexities and challenges that arise during food delivery in urban areas. It provides valuable insights into the scalability and adaptability of the algorithm to meet the increasing demand for efficient and timely food delivery services.

Introduction

In the thriving global food delivery market, valued at 770 billion USD in 2022 and projected to double by 2027, optimizing delivery routes emerges as a pivotal challenge. (Bhati, 2023) Our project, “Food Delivery Optimization using Ant Colony Optimization (ACO),” was born out of a need to enhance the efficiency and effectiveness of food delivery services in densely populated urban areas. The project was driven by the overarching goal of improving customer satisfaction through timely deliveries while also maximizing corporate profitability and driver efficiency.

The problem we aimed to solve is rooted in the complexities of the food delivery landscape, particularly in managing delivery costs, handling orders from multiple restaurants, and ensuring prompt deliveries to maintain food freshness. Our approach to this challenge was to apply the Ant Colony Optimization algorithm, a nature-inspired, probabilistic optimization technique that emulates the foraging behaviour of ants to find the most efficient paths in complex environments.

The objectives of this project were multi-dimensional: to develop a robust model for food delivery optimization using ACO, to address the unique challenges posed by urban delivery scenarios, and to evaluate the performance of our solution against various metrics. The structure of this article reflects this journey, beginning with a literature review to contextualize our approach within existing solutions. This is followed by a detailed exposition of the problem formulation and modelling, showcasing the mathematical underpinnings of our approach. The proposed solution section delves into the specifics of the ACO algorithm and its application in our context. In the performance evaluation, we critically assess our solution through a series of experiments, highlighting both its strengths and limitations. The article concludes with a summary of our findings, recommendations for future improvement, and reflections on the project’s alignment with its initial objectives.

By walking through this structured approach, the article aims to offer a comprehensive insight into the process of optimizing food delivery routes using ACO, from conception to evaluation.

Literature Review

We explore several studies that have utilized Ant Colony Optimization (ACO) and its modifications to tackle delivery challenges. Our goal is to comprehend the progress in this field and determine how our proposed solution builds upon these existing methods.

In the article Research on Task Allocation Model of Takeaway Platform Based on RWS-ACO Optimization Algorithm, the study introduces the Roulette Ant Colony Optimization (RWS-ACO) algorithm (Li et al., 2021). This algorithm enables the efficient selection of the next customer to be visited by balancing exploration and exploitation to avoid local optima in route selection. Unlike traditional ACO, RWS-ACO provides a more dynamic approach to task distribution, which is crucial for high-demand food delivery scenarios. Additionally, the paper divides businesses into different business circles based on region. It proposes a task allocation model that takes into account delivery distance, cost, and overtime in each business circle. This model aims to achieve the best match between consumer orders and couriers. In our solution, we have incorporated this concept and applied it to efficiently manage the logistics of multiple restaurants simultaneously. This ensures that deliveries from various eateries are optimally routed.

There are studies that provide insights on how to handle problems with multi-pickups and deliveries with time windows. For instance, Tran et al. (2021) introduce the Smooth Max-Min Ant System, an approach that utilizes Ant Colony Optimization to manage complex delivery schedules and time-sensitive deliveries. This approach is more comprehensive compared to single-destination models. Another article by Ratanavilisagul (2022) proposes an improved Ant Colony Optimization algorithm that addresses infeasible routes and local optima by introducing route elimination and pheromone reset techniques. This advancement over traditional ACO methods is particularly helpful in handling complex delivery scenarios.

In our study, we focus on optimizing food delivery in urban areas like Toronto’s Bloor/Yonge area. The challenges posed by intense traffic and a crowded population include managing costs, handling multi-restaurant pickups, and ensuring timely deliveries. Inspired by the time-sensitive approaches mentioned above, we employ the Ant Colony Optimization (ACO) algorithm to efficiently manage urban food delivery logistics. This approach prioritizes cost-efficiency, timeliness, and customer satisfaction while effectively handling the intricate variables and constraints of the Vehicle Routing Problem with Time Windows (VRPTW).

Exploratory Spatial Data Analysis:

For ESDA, the visualized concepts of food delivery are shown as the street map, point of interest, heat map, cluster map, and cartogram map. The final map concluded the limited amount of restaurant locations user x can access within a limited range.

Problem Datasets

Our primary dataset encompasses the map of the Bloor-Yonge area in Toronto, sourced from OpenStreetMap.

• Map: From OpenStreetMap via osmnx API
• Restaurant locations: From OpenStreetMap via overpass API
• Address points: From Toronto Open Data (https://open.toronto.ca/dataset/address-points-municipal-toronto-one-address-repository/) published by Information & Technology
• Neighbourhoods: From Toronto Open Data (https://open.toronto.ca/dataset/neighbourhoods/) published by Social Development, Finance & Administration
• Benchmark Dataset: From VRPTW Benchmark Problems (http://web.cba.neu.edu/~msolomon/problems.htm) parsed from HTML to text format for processing in Jupyter Notebook

Street and Satellite Maps

To gain a comprehensive understanding of the Bloor-Yonge area’s physical layout and infrastructure, we’ll first analyze both its street map and the corresponding satellite map.

From the street map, we can observe that Bloor-Yonge is essentially segmented into four prominent blocks by the intersection of two major streets: Bloor Street and Yonge Street. These streets likely form the principal transportation arteries for this locale.

The satellite map provides further insights into the area’s characteristics. Bloor-Yonge is evidently a bustling urban zone brimming with buildings. The top-right and top-left quadrants predominantly feature residential housings, while the bottom-right section is characterized by an array of structures, including office buildings and condominiums. Conversely, the bottom-left segment is primarily occupied by the University of Toronto’s campus, marking it as an academic zone.

(Source: Author)

Points of Interest (POIs)

Focusing on food delivery, we’re keen to understand the distribution of cafes and restaurants within the Bloor-Yonge area. By leveraging the overpass API, we can query OpenStreetMap to fetch a comprehensive list of these entities, all within a 2km radius of our map's center. This compilation will constitute our POI map. In the map below, red dots represent the location of either a cafe or a restaurant.

(Source: Author)

Heat Map

Building on our POI map, we can explore deeper into the locations of cafes and restaurants using a heat map. This visualization enables us to pinpoint areas with a higher concentration of these establishments.

(Source: Author)

Cartogram Map

To visually represent potential food delivery demand, we’ve constructed a cartogram map where neighbourhoods are scaled based on the number of address points. Essentially, larger polygons signify higher potential demand, guiding us to prioritize orders from those areas.

(Source: Author)

Cluster Map

After exploring the supply side of food delivery, we’re now shifting our focus to the demand side — pinpointing areas with potential users. Recognizing that food orders aren’t exclusive to homes but can also come from offices, schools, parks, etc., a comprehensive dataset encompassing all address points is crucial.

(Source: Author)

Business Circle Map with Distance Constraint

The business circle map with distance constraint summarized and analyzed the dataset and highlighted the restaurant within a limited range where users can place orders for food delivery.

(Source: Author)

In conclusion, based on the analysis above, it is evident that there is significant potential demand for food delivery services due to the presence of numerous potential customers. However, a challenging aspect of this scenario lies in the widespread distribution of both users and restaurants. Effectively delivering food to these customers, especially when it comes to routing and logistical challenges. In the following sections, we will dive into problem characterization and explore how to optimize food delivery routing to address this challenge.

Problem Characterization

In urban areas like Toronto’s Bloor/Yonge Area, optimizing food delivery poses significant challenges, such as managing costs, handling multi-restaurant pickups, and ensuring timely deliveries. To address these, the focus is on scheduled food delivery, using the Vehicle Routing Problem with Time Windows (VRPTW) model. The introduction of ‘business circles’, inspired by the paper “Research on Task Allocation Model of Takeaway Platform Based on RWS-ACO Optimization Algorithm” [4], centralizes pickups from clustered restaurants, reducing complexity. The solution employs the Ant Colony Optimization (ACO) algorithm, adept at handling the VRPTW’s intricate variables and constraints. This approach aims to efficiently manage urban food delivery logistics, prioritizing cost-efficiency, timeliness, and customer satisfaction.

Assumption

For the effective implementation and interpretation of our ACO-based solution to the VRPTW in scheduled food delivery, several key assumptions have been made. These assumptions are crucial for simplifying the complex real-world problem into a manageable computational model without significantly compromising the practical applicability of the solution. They are as follows:

1. Standardized Business Circles: Restaurants are grouped into predefined business circles, which serve as focal points in our model, although in reality, couriers pick up orders directly from the restaurants. We disregard the minimal distances between restaurants and their business circles in our calculations. The K-Means clustering algorithm is employed to efficiently establish these circles, clustering restaurants based on their locations to identify central points, thereby streamlining our route optimization. Our primary objective is to enhance the ACO-based algorithm, for which we utilize these established business circles.
2. Uniform Courier Speed: All couriers are assumed to travel at a uniform speed. This assumption simplifies the route planning process by standardizing travel time calculations across different routes.
3. Consistent Courier Capacity: Each courier has the same capacity limit in terms of the number of food items or orders they can carry. This uniformity ensures that the capacity constraint is uniformly applied across all couriers, simplifying the optimization process.
4. Flexible Courier Availability: It is assumed that there is a sufficient number of couriers available to meet the demand of scheduled orders. This allows our algorithm to focus on optimizing routes and delivery schedules without the constraint of courier shortage.
5. Fixed Time Windows: Each order comes with a fixed and predetermined time window, set by the customer, within which the delivery must be made. These time windows are strictly adhered to in our route planning.
6. Geographical Service Range: The delivery service is constrained to a certain geographical range from the business circle. This assumption is based on the operational limits typically set by food delivery services.
7. Exclusion of External Factors: External factors such as traffic conditions, weather, and courier-specific variables (like different modes of transportation) are not considered in the model. The focus is on optimizing routes based on distance and time windows.
8. Reliable Demand Forecast: The number and specifics of orders (including their time windows and delivery locations) are known in advance, allowing for pre-planning of routes. This is in line with the nature of scheduled food delivery services.

Problem Formulation and Modeling

The VRPTW-based scheduled food delivery problem can be formulated as follows:

• Let G = (N, A) be a graph where N is the set of nodes including the business circle and customer locations and A is the set of arcs representing possible paths between nodes.
• Each node i ∈ N has a demand q_i, the number of food items to be delivered, and a time window [a_i, b_i] within which the delivery must occur.
• Each arc (i, j) A has an associated travel time t_ij and distance d_ij.
• The objective is to minimize the total distance travelled by all couriers.

The problem can be mathematically represented as:

Subject to the following constraints:

1. Route Continuity and Elimination of Subtours:

2. Time Window Constraints:

3. Capacity Constraints:

4. Binary Decision Variables:

Where x_ij = 1 if the path from node i to node j is used by a courier and 0 otherwise.

Proposed Solution

We’ve implemented our ACO-based VRPTW algorithm with two classes: Ant and AcoSolver.

Ant class:

1. Initialization:

• Each ant explores the route assignments for the ACO algorithm.
• It is initialized with essential components like the map_provider (supplying data on distances, demands, and time windows), capacity (max number of items it can deliver), ACO parameters (alpha, beta, rho), start_time, and speed.

2. State Reset:

• Prepares the ant for a new route search by resetting its capacity, the current time to the start time, and marking all nodes as unvisited.

3. Solution Search:

• The core of the ant’s behavior, is that it repeatedly selects the next node and moves to it until all nodes are visited or no more moves are possible.
• Each route is constructed by starting from the source node, iteratively adding new nodes until no further nodes can be added, and then returning to the source.

4. Travel Time Calculation:

• Determines the time it takes to travel between two nodes, considering the type of coordinates (Euclidean or GPS) and the ant’s speed.

5. Next Node Selection:

1. Selects the next node to visit based on ACO rules: pheromone concentration on the path (influenced by alpha), heuristic desirability (influenced by beta), and prioritization of nodes whose ready times are closer to the current time.
2. If the demand at a node (e.g. the size or number of food items to be delivered) exceeds the ant’s remaining capacity, that node is excluded from consideration.
3. For each potentially available node, the method calculates the expected arrival time at that node, based on the current time and the travel time from the current node to that node. A node is considered available to travel if the ant can arrive at it before or within its closing time window. This means if the expected arrival time at a node is later than the end of its time window, that node is excluded from selection.
4. Each available node is then scored. The score is a product of three components:

• Pheromone trail strength on the path to that node, raised to the power of alpha (the parameter emphasizing the importance of pheromone trails).
• Heuristic desirability (typically the inverse of the distance to that node), is raised to the power of beta (the parameter emphasizing the importance of the heuristic value).
• A time-related factor, which gives higher scores to nodes whose ready times are closer to the current time, to prioritize immediate deliveries.
• These scores are then normalized to form a probability distribution. The next node is selected probabilistically from all available nodes based on these probabilities.

Node Movement: Moves the ant to the selected node, updates the current time by adding travel and service times, and handles the waiting time if the ant arrives before the start of a node’s time window.

Route Initialization: Initializes a new route when the current route is completed or can’t be extended further, starting again from the source node.

AcoSolver class:

1. Initialization:

• Manages the overall ACO process.
• Initializes the map provider, a list of ants with specified capacities, and other relevant parameters.

2. Solving the VRPTW:

• Iteratively runs each ant to find solutions (routes) and applies pheromone updates based on the quality of these solutions.
• Pheromone Management: Involves evaporating pheromones to reduce the influence of past routes and updating pheromones locally and globally to reinforce successful routes.

Adaptation and Tuning

The effective application of the Ant Colony Optimization (ACO) algorithm to the Vehicle Routing Problem with Time Windows (VRPTW) required careful adaptation and tuning of various ACO parameters. To identify the most suitable configuration, we employed a Grid Search methodology, systematically exploring a range of values for key parameters. This section outlines our approach and findings in this crucial phase of the project.

Grid Search Methodology

1. Parameter Selection:

We focused on tuning five critical ACO parameters: max_iterations, alpha (pheromone importance), beta (heuristic importance), rho (pheromone evaporation rate), and num_ants (number of ants in the colony).

2. Defining the Parameter Grid:

A parameter grid was established, specifying a range of plausible values for each parameter. For instance, max_iterations ranged from 100 to 200, alpha from 1.0 to 4.0, beta from 2.0 to 4.0, rho from 0.3 to 0.5, and num_ants from 10 to 100.

Iterative Testing

The Grid Search iteratively tested every combination of parameters within the grid. For each combination, the ACO algorithm was executed, and its performance was measured in terms of the total distance travelled by the couriers.

Performance Evaluation of Grid Search Methodology

The performance of each parameter set was evaluated against Solomon’s VRPTW benchmark (Solomon, 2005) with the objective function being the minimization of the total route distance.

Findings and Adaptations

1. Initial Parameter Set:

Our initial runs, based on estimated parameters (max_iterations: 100, alpha: 1.0, beta: 2.0, rho: 0.3, num_ants: 10), yielded a total distance of 1328.03 units using the Solomon’s VRPTW benchmark’s R101.50 dataset. The benchmark optimal distance is 1044.0 units.

2. Optimized Parameters:

The Grid Search identified an optimized parameter set that significantly improved performance: max_iterations: 200, alpha: 2.0, beta: 2.0, rho: 0.3, num_ants: 100. This configuration achieved a total distance of 1184.70 units.

3. Analysis of Results:

a. The increase in max_iterations and num_ants suggested that allowing for more extensive exploration and greater diversity of solutions led to more efficient route planning.

b. The higher value of alpha indicated that a stronger emphasis on pheromone trails was beneficial, possibly due to the ants’ better exploitation of successful routes discovered in earlier iterations.

c. The constant value of beta maintained the significance of heuristic information (distance), ensuring a balanced approach to path selection.

d. Despite the improvements, there remained a gap compared to the benchmark optimal distance of 1044.0 units, indicating further potential for optimization.

e. The Ant Colony Optimization (ACO) algorithm introduces an element of randomness into its solutions due to its stochastic nature. To evaluate the effectiveness of our optimized ACO parameters, we conducted 20 trials against the Benchmark dataset. These tests consistently yielded distances between 1150 to 1250 units, significantly improving upon the results obtained with our initial parameter estimates. A comparative graph illustrates this enhancement: prior to tuning, the results varied widely, but after adapting and tuning the ACO parameters, the solution distances converged within a much narrower and more efficient range. The “After” graph shows a notable improvement in route efficiency with a reduced total distance and fewer overlapping routes compared to the “Before” graph. The distribution of routes is more balanced post-tuning, indicating a better-optimized network that more closely approaches the benchmark optimal distance.

Adaption and Tuning for Benchmark Dataset with 25 Orders [2](Generated with Dataset Section in Colab)

Adaption and Tuning for Benchmark Dataset with 50 Orders [2](Generated with Dataset Section in Colab)

The “After” graph shows a notable improvement in route efficiency with a reduced total distance and fewer overlapping routes compared to the “Before” graph. The distribution of routes is more balanced post-tuning, indicating a better-optimized network that more closely approaches the benchmark optimal distance.

Real-World Application:

We integrated our Ant Colony Optimization (ACO) based algorithm into a practical real-world scenario, specifically, scheduled food delivery.

Input:

1. Map: We chose a map centered in Yonge-Bloor Area in Toronto
2. Business Circles and Orders: A list of business circles (representing actual restaurants) and a list of orders to be delivered.
3. Start Time and Speed: The start time for the delivery operation and the speed of the delivery couriers. The start time is provided in the “HH: MM” format (e.g., “12:30”). The speed is in kilometers per hour (km/h), aligning with common transportation metrics.
4. Coordinate System: GPS coordinates were used. This specificity caters to the real-world applicability of the solver, where accurate geographical positioning is crucial for efficient route planning. The shortest path on a given map is found using Dijkstra’s algorithm, and its distance is used in the computation.
5. Time Window Handling: For each order, the ready_time (earliest delivery time) and due_time (latest delivery time) within the time window are also expected in the “HH: MM” format.

Steps:

Orders are categorized by their corresponding business circles, ensuring a distinct order list for each. This setup is pivotal as it enables us to iterate through each business circle, applying our ACO-based algorithm to determine the optimal delivery routes for couriers within every individual circle.

Legend:

• Red point: business circle location
• Blue point: customer location
• Coloured Line: path travelled by couriers

Each courier’s route is depicted as a series of interconnected lines, uniformly coloured to represent the individual path taken.

Output of Real-World Application (Source: Author)

ACO Parameters:

• Max Iterations (max_iterations): Determines how many times the algorithm will iterate. More iterations can allow the algorithm to explore more routes but also increase computational time.
• Alpha (alpha): Influences the importance of the pheromone trail. A higher alpha gives more weight to the pheromone, potentially leading to more exploitation of known good paths.
• Beta (beta): Dictates the importance of heuristic information (like distance). A higher beta emphasizes the desirability of shorter paths, promoting exploration.
• Rho (rho): The pheromone evaporation rate. Higher values mean faster pheromone evaporation, which encourages exploration over exploitation by reducing the influence of older paths.
• Number of Ants (num_ants): More ants can explore more routes simultaneously, increasing the diversity of solutions but also computational requirements.

Benchmark Test Analysis for the dataset with 50 orders(Source: Author)

Performance Evaluation

Quantitative Evaluation Methods:

1. Average route length and individual route length for each courier.

(Source: Author)

Benchmark 25 Orders: This scenario has a relatively stable line with fewer fluctuations, indicating a more consistent number of stops across couriers.

Benchmark 50 Orders: The noticeable spike suggests some couriers have a significantly higher number of stops compared to others. The line shows more variability, which means an uneven distribution of stops.

Real-world Application: Most couriers have a low number of stops. This could suggest a more streamlined or efficient route planning.

Overall, the real-world application has the most uniform distribution with the least variation in the number of stops per courier. The Benchmark 50 Orders shows the most variation meaning the imbalanced workload for couriers. The Benchmark 25 Orders fall in between these two, with moderate variation among couriers.

Pros:

1. Counting stops is straightforward and provides a clear, easy-to-understand metric.
2. The method offers a quick estimate of each courier’s workload, which can be crucial for balancing tasks among the workforce.

Cons:

1. The number of stops does not account for the distance between stops, traffic conditions, or the time spent at each stop, which can significantly impact the actual workload.
2. Not all stops are equal — some may involve single parcel deliveries while others may be bulk or require significant time for unloading and processing.
3. Low relevance with cost and profit for courier delivery: The number of stops does not necessarily correlate with the profitability or cost-effectiveness of the routes.

2. Workload Distribution — Evaluate how evenly the tasks (deliveries) are distributed among couriers.

Pros: Ensures a fair distribution of tasks among couriers, which can lead to better job satisfaction and efficiency.

Cons: Equal distribution of tasks may not equate to equal distance or effort due to varying delivery locations and conditions.

1. Benchmark Test with 25 Orders: The average deviation from the mean number of orders per courier is approximately 1.78. This test set indicates a moderate level of unevenness in task distribution, meaning some couriers had significantly more or fewer deliveries than others.
2. Benchmark Test with 50 Orders: The average deviation from the mean number of orders per courier is approximately 1.05. Meaning this test set indicates a more balanced distribution of deliveries among couriers compared to the 25-order benchmark, suggesting a more equitable workload.
3. Real-world Application Test: The average deviation from the mean number of orders per courier is approximately 0.89. This represents the most evenly distributed workload among couriers in the tested scenarios. The lower deviation here suggests that the real-world application has a more efficient and fair distribution system.

Comparison: The analysis shows that the real-world application test exhibits the most balanced distribution of delivery tasks among couriers. This implies an effective allocation strategy, likely contributing to improved courier satisfaction and operational efficiency. In contrast, the 25-order benchmark test shows a higher level of imbalance, indicating potential areas for improvement in task allocation.

(Source: Author)

Qualitative Evaluation Methods:

1. Logical Order

Pros: Evaluating test results based on logical orders is straightforward to model and plan for, making them suitable for benchmarking and testing optimization algorithms.

Cons: Evaluating results based on logical orders may not accurately reflect real-world scenarios that introduce more complexity such as traffic conditions, customer preference and delivery windows.

• Benchmark courier routes with 25 orders: In this dataset, the orders follow a simplified and logical pattern, often connecting a central point to multiple customer locations and returning to the central point.
• Benchmark courier routes with 50 orders: The result is similar to the above one while maintaining a logical structure that connects a central point to various customer locations and back.
• Real-world courier routes with 25 orders: Since the logical order here is influenced by the geographic distribution of customers, it may not always follow a perfectly systematic pattern due to real-world factors.

In summary, the logical orders in the benchmark datasets are more predictable and straightforward to optimize, while the real-world dataset introduces complexity in customer orders.

2. Smoothness

Pros: Smooth routes mean shorter travel times and lower fuel consumption, increasing overall routing efficiency.

Cons: Evaluating smoothness alone may oversimplify complex routing problems, ignoring other factors like traffic etc.

• Real-world courier routes with 25 orders: This dataset is based on real-world data, making it less predictable in terms of route smoothness. The smoothness of routes in this scenario depends on the actual distribution of customers and their locations. Routes with complex customer distributions may result in less smooth paths due to real-world constraints.
• Benchmark courier routes with 25 orders: This dataset consists of shorter routes with fewer stops, making them generally smoother due to their low level of complexity.
• Benchmark courier routes with 50 orders: These routes have more stops compared to the one above but still maintain a relatively straightforward route planning. The route connects a central point to multiple customer locations and returns to the central point. Overall, the routing is slightly less smooth than the previous one due to more stops.

In summary, the benchmark datasets exhibit smoother routes than the real-world scenario, with the benchmark_25 dataset being the smoothest. Due to the complexity introduced by the real-world dataset, we can find less predictable route smoothness. Improvements to the real-world routes could be achieved through enhanced route optimization techniques.

ACO algorithm and Benchmark test result comparison

The benchmark test result is more optimal than the actual test result can be attributed to several factors. Benchmark tests typically represent an ideal or known optimal solution for a given problem, which may not be achievable in practice due to various limitations and challenges in the actual algorithm implementation.

Conclusions & Recommendations

In conclusion, our project tackles the pressing challenge of optimizing food delivery routes in densely populated urban areas. Our proposed solution involves the variation of the ACO algorithm. Throughout the project, we developed an efficient model which addressed urban delivery challenges and evaluated our solution’s performance against various metrics while referring to external literature. While benchmark tests represented optimal solutions, real-world applicability factors and algorithmic complexities influenced our results. Overall, our ACO-based solution offered insights regarding efficient route planning for food delivery services in urban settings, with room for parameter refinement and further enhancements.

Colab Notebook

All Routing Output, Images and Analytical Result Charts were generated from the code implemented by the team, details can be found in Colab Notebook.

Google Colaboratory

References

[1] Bhati, N. (2023, October 4). 10 challenges faced by food delivery app Businesses. Tech Blog | Mobile App, eCommerce, Salesforce Insights. https://www.emizentech.com/blog/food-delivery-mobile-app-business-challenges.html

[2]Reba. (2014, October 20). The Vehicle Routing Problem with Time Windows and Scheduled Departure. PowerPoint Presentation — ID:5641081. SlideServe. https://www.slideserve.com/reba/the-vehicle-routing-problem-with-time-windows-and-scheduled-departure

[3] M. M. Solomon, “VRPTW BENCHMARK PROBLEMS,” Benchmarking problems, http://web.cba.neu.edu/~msolomon/problems.htm (accessed Dec. 15, 2023).

[4] J. Li, X. Xu, Y. Yang, and F. Yang, “Research on task allocation model of takeaway platform based on RWS-ACO Optimization Algorithm,” Business Intelligence and Information Technology, pp. 786–795, 2021. doi:10.1007/978–3–030–92632–8_74

[5] T. Tran and M. A. A. Clariño, “Solving Multi-Pickup and Delivery Problem with Time Windows using Ant Colony Optimization”, JTEC, vol. 13, no. 4, pp. 35–41, Dec. 2021.

[6] C. Ratanavilisagul, “Modified ant colony optimization with route elimination and pheromone reset for multiple pickup and multiple delivery vehicle routing problem with Time Window,” Journal of Advanced Computational Intelligence and Intelligent Informatics, vol. 26, no. 6, pp. 959–964, 2022. doi:10.20965/jaciii.2022.p0959