Bio-Inspired Approach to Optimal Placement of Public Parcel Lockers for Last-Mile Delivery
By Tianwei Zhang and Shiuan-Wen Chen as part of course project of ECE1724H: Bio-inspired Algorithms for Smart Mobility. Dr. Alaa Khamis, University of Toronto, 2023.
Abstract
This study presents an application of Simulated Annealing (SA) for finding the optimal placement of public parcel lockers in Toronto. As the demand for efficient, cost-effective delivery solutions grows, this research addresses the critical challenge of balancing customer satisfaction with operational costs. The study utilizes a comprehensive dataset, including population distribution and location of existing infrastructure like bike share stations, for the modeling of this problem. The objective function incorporates factors such as locker placement, base net profit per capita, satisfaction coefficient, and installation costs. By employing the SA algorithm, the study explores various hyper-parameter settings, demonstrating its ability to effectively navigate complex solution spaces and reach near-optimal locker placements. The final outcome suggests a strategic placement of 31 lockers, achieving an estimated net profit of CAD 3,101,136.17. This research aims to serve as an contribution to the smart mobility domain by providing a practical solution for the city and advocating the employment of bio-inspired algorithms in urban planning and logistics.
Introduction
Background: Last-Mile Delivery
In the context of supply chain management, Last Mile is a term used to describe the last leg of the delivery, where the goods are transported from a local region distribution hub/warehouse to the customers. This is often considered the most critical and complex stage, as it directly affects customer satisfaction, as opposed to the first-mile segment and middle-mile segment.
The key challenges in last-mile delivery stem from its significant impact on customer satisfaction, as mentioned above. It is crucial to keep the reliability, flexibility, and security in the delivery process at a high level in order to meet the growing standard from the customers. On top of that, it is important yet challenging to maintain a good cost-effectiveness. For example, a faster, more reliable delivery (enabled through the application of larger, more advanced vehicles and an increased dispatch frequency, etc.) admittedly improves customer satisfaction, but sacrifices in terms of higher operational cost. Likewise, focusing solely on cost-cutting measures would negatively impact delivery speed and reliability as well, potentially leading to dissatisfaction and hence loss of business. Finding a balance between these two aspects often involves a tradeoff and has proven to be a challenging task.
Public Parcel Lockers
With the goal of addressing these issues, Public Parcel Locker has emerged as a safe and convenient package delivery and retrieval solution.
Public parcel lockers directly address the main aspects the aforementioned challenges in last-mile delivery by offering an alternative to traditional delivery solutions that is reliable (deliveries are less prone to unexpected delay and misdelivery because they only need to reach the lockers instead of individuals), flexible (customers can pick up their parcels at any time), and secure (lockers serve as a safe storage for the packages before the collection). Moreover, public parcel lockers significantly reduce the labor and operational cost of last-mile delivery because they eliminate the need for the courier to deliver the packages to individual clients: with the parcel locker as a mini distribution hub, the delivering party will be able to save a large amount of time, money, and effort.
However, public parcel lockers as a last-mile delivery solution is certainly not perfect, and comes with its own problems and challenges too. Primarily, the lack of door-to-door delivery may deter customers if the lockers are located too far away from their residence. On top of that, the installation plus ongoing rent and maintenance can quickly become a major cost in the long run.
It presents a similar tradeoff: if lockers are too sparse or poorly located, customers would not see too much value in them and therefore be disinclined to choose the service. On the other hand, installing too many lockers can lead to overlapping service areas and unsustainable costs, which damaging the cost-effectiveness of this solution.
There has been various proposals to tackle the problem of finding effective locker placements. Among them, bio-inspired algorithms have started to be explored by people as powerful tools for problems like this. These algorithms are based on natural phenomena and biological processes, and they excel in navigating through complex solution spaces and finding near-optimal solutions with great efficiency.
In light of this, we are specifically inclined towards employing Simulated Annealing (SA) as our primary exploration method to find effective locker placements, for its unique set of characteristics that align well with the demands of our problem. Its implementation and execution is relatively straightforward and intuitive, while also offering the ability to fine-tune between Exploration and Exploitation. Considering the nature and scale of solving for the optimal parcel locker placement in a certain area, we believe SA serves as an effective approach of choice.
In later parts of this article, we will do a brief comparison on Simulated Annealing against some other proposed algorithms, showcasing some of its main strengths and weaknesses. Then, we will take Toronto as an example, make a model over the behavior of setting up parcel lockers in the city as a last-mile delivery solution, and attempt to use Simulated Annealing to solve for the optimal placement for these lockers. We will go through different hyper-parameters values, compare the results and discuss the best choice for our specific problem. Lastly, we will evaluate the result we come up with by comparing it against some of the existing solutions that have already been applied in real world.
Literature Review
Many of the existing attempts to tackle the optimal placement of public parcel lockers incorporate Mixed-Integer Linear Programming as the main planning algorithm. For instance, Kahr introduced their approach in [1], while Lin et al. presented their proposal in [2], as some notable examples. Mixed-integer linear programming is a mathematical optimization technique in which the objective function and all the constraints are linear, but either some or all of the decision variables are required to take on integer values. The primary advantage of mixed-integer linear programming as a solution is that it targets the exact optimal solution given the constraints. However, this comes at a cost of significantly more expensive computation when compared to most bio-inspired heuristic algorithms, which could potentially lead to problematic performance issues in some scenarios, especially when dealing with large dataset and complex modeling, making it less practical due to the excessive resources spending on the optimization.
Another kind of alternative strategy involves utilizing some bio-inspired algorithms other than SA. We can see such kind of approach being highlighted in [3], which targets a similar problem related to the optimal placement of bus stops. In this context, Li et al. advocate for the use of Particle Swarm Optimization (PSO). PSO is generally good at exploring the solution space due to the collective learning process: the particles share information, leading to a robust search of the space. However, the limitation in its modeling leads to its lack of ability to generalize in some ways compared to Simulated Annealing. For instance, in our locker placement scenario, we want to evaluate placements with different number of lockers. As opposed to being able to directly incorporate the increase/decrease of the number into the iterations of the solution with SA, PSO necessitates a fresh run of the algorithm for each different locker number. Other than that, in terms of the ability to escape local optima, PSO and SA both have strong ability to obtain a globally optimal solution. While PSO does so by relying on population-based search strategies for a strong solution, SA achieves similar results by utilizing a unique scheduled cooling mechanism. In our case where the search space is not too complex, SA’s single-solution approach provides more benefits by simplifying the process and reducing computational overhead, making this approach more practical to carry out.
Problem Formulation and Modeling
Data
To facilitate the modeling of the task and our solution, we have collected and compiled data regarding the population within the city of Toronto and its geospatial distribution.
- Population Distribution in City of Toronto, by Neighborhood
We used ArcGIS API to retrieve a dataset over the population distribution throughout the city of Toronto. Here is a preview of this dataset in the form of heat map and density choropleth map:
This dataset offers a comprehensive overview of Toronto’s population distribution, serving as a robust foundation. Yet, when delving into the specifics of public parcel locker placement, there’s a need for finer granularity, emphasizing smaller, more localized population segments.
- Location of Bike Share Stations in City of Toronto
In light of this, we sourced another set of geospatial data from City of Toronto implicitly representing the population distribution, at a more fine-grained level. Here is a preview of this dataset in the form of scatter map:
This particular dataset illustrates the distribution of bike share stations across the city of Toronto. While it doesn’t directly reflect the population density, the geospatial distribution of these stations should present a very strong correlation to the residency of the citizens. Considering the large quantity of data points in this dataset and their precise locations, this should add an additional layer of granularity to the population distribution, and, in combination with the first dataset, serves as a strong and effective reference for our modeling objectives.
Modeling
With data mentioned above, we model our problem as the following:
- C : Set of clusters representing population distribution.
- p(c) : Population size of cluster c where c ∈ C.
- L : Set of locker coordinates representing their placement in the city.
- d(c, l) : Walking distance between cluster c and locker at location l where c ∈ C and l ∈ L.
- cc(c) : Compensation coefficient for a certain cluster. This depends on the numbers of bike share stations nearby, and directly affects customer satisfaction. When the number of bike share stations nearby is high, it means the population here is less likely to have a car thus more sensitive about the location of the nearest locker.
- s(d) : Customer satisfaction function based on distance d.
- cost(l) : Cost of building a locker at location l where l ∈ L.
- w_s, w_c : The importance(weight) for customer satisfaction and cost respectively.
To calculate the actual value of this model with the data we have, we need to substantiate the function with actual implementations and coefficients with reasonable parameters.
For the walking distance between two points, we use osmnx package to map these two point into street points on the map, and calculate the length of the shortest path between them.
For the satisfaction function, we consider a number of different factors:
- Satisfaction Coefficient: this coefficient obtain its maximum value at 1 (100% satisfaction) when the distance of the nearest locker is 0 (ideal situation when a locker is located exactly where people live). It will decay exponentially as the distance of the nearest locker goes higher, with the rate of decay depending on how likely for people living here to possess a vehicle, which is reflected by the compensation coefficient mentioned above. We count the number of bike share stations within 1km radius for each cluster, and rank them in the form of percentile. People with highest (100th) percentile will be 2x more sensitive to how far the nearest locker is, and people with lowest (0th) percentile will be 0.5x as sensitive to such distance. For people ranked in between, we will do a linear interpolation to determine their sensitivity value.
- Base net profit per capita: this was estimated by real world statistics we collected to reflect how much net profit will be contributed by one person if they are fully satisfied with the addition of lockers. We take Amazon as our target — according to Statista [4], Amazon.ca had an e-commerce net sales of 11,510 million USD in 2022 generated in Canada. That equals to about 14,963 million CAD per year. Then, according to macrotrends [5], Amazon’s net profit margin as of September 30, 2023 was 3.62%. Consider that Amazon has business in many other fields with significantly higher net profit margin (e.g. AWS, Amazon Pay, Prime Video, etc.), we estimate the net profit margin in e-commerce retail to be halved at around 1.5%. We are also going to consider the profit over the course of 5 years. As for the population, we refer to Statista [6] that there are 38.85 million resident in Canada as of 2022. We also estimate the people in Toronto (which is the biggest city in Canada) to be 1.5x more likely to spend on Amazon compared to nationwide average. Once we have the overall profit contributed to Amazon by one person in Toronto over 5 years by putting these numbers together, we again estimate a 30% expected growth to be generated on top of that by introducing public parcel lockers to enhance their shopping experience, provided they are fully satisfied.
Multiply the base net profit per capita with their satisfaction coefficient, we will have the net profit per capita. If we add up this number for the entire population in Toronto, we will have the overall net profit, a.k.a. the customer satisfaction term in our objective function.
For the cost term, it is hard to find data directly reflecting the cost of public parcel lockers. However, according to this article from Zhihu [7], the manufacturing cost of a smart parcel locker deployed in China is around 60,000 CNY, which is equivalent to around 12,000 CAD. Notice that the market of smart public parcel lockers in China has been considerably more saturated and competitive, plus their material, manufacturing, and labor costs are all significantly lower compared to Canada. Based on these facts, we think it’s reasonable to estimate the manufacturing cost of one smart public parcel locker to be around 50,000 CAD. These parcel lockers also come with inevitable ongoing rent and maintenance costs, and we estimate them to add up to 30,000 CAD per year. Therefore, the cost of building and servicing a public parcel locker over the course of 5 years will fall at around 200,000 CAD.
Since the profit and cost are both estimated in CAD, their respective weights will be the same at 1. With all the above, we will be able to retrieve the objective function value by subtracting the cost from the overall net profit.
Proposed Solution
As stated above, we propose to use Simulated Annealing algorithm to find a locker placement that maximizes the value of our objective function. The core of this algorithm is to choose an ideal set of hyper-parameters that translates to a cooling schedule which ensures the temperature to be high enough at first, in order to allow a comprehensive search and avoid getting trapped in a local optima. As the temperature cools down later on into the process, the temperature will end up low enough for the algorithm to be able to focus on exploiting and refining known good solutions.
We start from an initial state (each “state” of locker placement represents a “solution”) with some lockers scattered around the city at random locations. In each iteration, our algorithm will choose between three options: adding a new locker to our fleet, removing an existing locker from the fleet, or moving one of existing lockers to a new location. After one of these three operations being implemented, we compare the objective value of our new solution to the objective value of the old one. If we arrive at a better result, we will gladly accept it; if the outcome does not see any improvement, we will refer to the current temperature as the probability for the “worse” solution to be accepted or not. If the temperature is high, we are more likely to accept it, and vice versa. Lastly, we lower the temperature, move to the next iteration and repeat the same process. If the parameters are set up correctly, we should expect to see our solution continue to improve as a result.
For the code implementation, we build our algorithm using simanneal package as a starting point. Here is a quick look at a part of our algorithm implementation:
class LockerPlacementAnnealer(Annealer):
def __init__(self, initial_state, index):
super().__init__(initial_state)
self.index = index
self.history = [] # storing the history of metrics at each update
def move(self):
move_type = random.choice(['add', 'remove', 'move'])
if move_type == 'add':
new_location = self.state.street_points.nearest_street_point(
(np.random.uniform(min(self.state.clusters_df['lat']), max(self.state.clusters_df['lat'])),
np.random.uniform(min(self.state.clusters_df['lon']), max(self.state.clusters_df['lon'])))
)
self.state.add_locker(new_location)
elif move_type == 'remove':
if self.state.number_of_lockers() > 1:
self.state.remove_random_locker()
else:
if self.state.number_of_lockers() > 0:
locker_index = random.randint(0, self.state.number_of_lockers() - 1)
new_location = self.state.street_points.nearest_street_point(
(np.random.uniform(min(self.state.clusters_df['lat']), max(self.state.clusters_df['lat'])),
np.random.uniform(min(self.state.clusters_df['lon']), max(self.state.clusters_df['lon'])))
)
self.state.move_locker(locker_index, new_location)
def energy(self):
total_satisfaction = 0
total_cost = 0
for index, cluster in self.state.clusters_df.iterrows():
# Find the nearest locker to this cluster
nearest_locker_distance = min(
calculate_distance((cluster['lat'], cluster['lon']), locker) for locker in self.state.get_locations()
)
# Calculate satisfaction for this cluster
total_satisfaction += cluster['population'] * satisfaction_function((cluster['lat'], cluster['lon']), nearest_locker_distance)
# Sum the cost for all lockers
total_cost = self.state.number_of_lockers() * cost_function()
# Energy is the negative of the obj value
e = -1 * (total_satisfaction - total_cost)
return e
def update(self, step, T, E, acceptance, improvement):
obj_value = -E
# Record the objective function value
metrics = {
'obj_value': obj_value,
'num_lockers': self.state.number_of_lockers(),
}
self.history.append(metrics)The algorithm can be further tuned and customized by changing the cooling schedule with a custom Tmax and Tmin value.
# Initialize a list to store the results
SA_results_all_setups = []
# Parameter values to examine
Tmax_0 = 25_000.0
Tmin_0 = 2.5
Tmax_plus = 50_000.0
Tmin_plus = 5
Tmax_minus = 5_000.0
Tmin_minus = 1e-5
arr_Tmax = [Tmax_0, Tmax_plus, Tmax_minus, Tmax_0, Tmax_plus, Tmax_minus, Tmax_0, Tmax_plus, Tmax_minus]
arr_Tmin = [Tmin_0, Tmin_0, Tmin_0, Tmin_plus, Tmin_plus, Tmin_plus, Tmin_minus, Tmin_minus, Tmin_minus]
num_runs_all_setups = 4
num_steps_all_setups = 4000
# Schedule
def run_SA_all_setups():
# Repeat for 3*3 = 9 configurations
for idx_setup in range(len(arr_Tmax)):
SA_results_per_setup = []
# Repeat for 8 runs
for idx_run in range(num_runs_all_setups):
# Configure the annealer with a random starting state
annealer = LockerPlacementAnnealer(LockersPlacementState(clusters_df, toronto_street_points), idx_run)
# Set the annealer parameters
annealer.Tmax = arr_Tmax[idx_setup]
annealer.Tmin = arr_Tmin[idx_setup]
annealer.steps = num_steps_all_setups
annealer.updates = num_steps_all_setups
# Perform the annealing process
state, e = annealer.anneal()
# Extract the objective function values into a list
obj_values = [metrics['obj_value'] for metrics in annealer.history]
nums_lockers = [metrics['num_lockers'] for metrics in annealer.history]
# Store the result for a single run
SA_results_per_setup.append({
'final_state': state,
'final_energy': e,
'final_obj_value': obj_values[-1],
'obj_values': obj_values,
'nums_lockers': nums_lockers
})
# Store the results for all runs from current configuration
SA_results_all_setups.append(SA_results_per_setup)
# Run!
run_SA_all_setups()In the code above, we examine and try out three candidate Tmax values: 25,000, 50,000, and 5,000 ; as well as three candidate Tmin values: 2.5, 5, and 1e-4. There is a total of 3x3 = 9 combinations — we use each combination of parameters to search for a solution for 4000 iterations, and repeat each combination for 4 times, which gives us 4 different runs to compare with thus reducing the risk of false conclusion due to an outlier run. The results are as follows:
By selecting the runs with the highest ending objective value, we have another graph to compare the best runs for each parameter configuration directly:
We can clearly tell that all combination of parameters yield a positive, improving result. However, upon closer inspection, we have some interesting observations that lead to a better understanding on how these parameters affect the performance of our algorithm:
- For the configurations with
Tmax = 5000, we observe that none of the runs out of the 12 reaches a solution with objective value of2e6or higher. We think this is due to the fact that 5000 is too low of a starting temperature for this particular problem, which prevents the algorithm from accepting worse solutions and conducting a comprehensive exploration across the solution space. - Similarly, for the configurations with
Tmax = 50000, we notice the objective values in early iterations to be highly unstable. They bounce back and forth very frequently since that high temperature allows solutions to get accepted more easily. This is supposed to be a good thing in the early stage of the run, but by comparing them against the ones withTmax = 25000, we notice that they lead to a slower convergence in general and worse final result. This is a sign thatTmax = 50000is higher than the optimal value of our algorithm. - For the configurations with
Tmax = 25000, we observe that they all produce solid results, with the combinationTmax = 25000, Tmin = 1e-4scoring the best solution overall. From the second graph we can confirm that this solution has even stayed at the best among all as early as iteration 1000 all the way till the end at iteration 4000. This result convinces us that this configuration strikes a good balance between Exploration and Exploitation, and if we were to add more runs and increase the number of iterations, its capability to converge on the optimal solution will only become more pronounced.
(By the way, here is another graph of the number of lockers from the best run across all configurations — it does not provide as much useful information, but it’s fun to look at — see how they are ping-ponging at the early stage!)
Performance Evaluation
Final Result
After this analysis on the set of parameters best suited for our problem, we apply these parameters to a final set of runs with 10,000 iterations per run and 8 runs in total to solve for the real optimal placement of parcel lockers. The result is as follows:
Finally, the best solution across all runs suggests building lockers at the following locations:
We can conclude that with our Simulated Annealing algorithm, we eventually reach at a solution bringing us a net profit of CAD 3,101,136.17, with 31 new public parcel lockers set up around Toronto, providing as an additional solution to the last-mile delivery problem for the city.
Evaluation — Quantitative Analysis
In our evaluation setup, three baseline scenarios were established, all utilizing the same number of containers as the best result for comparative purposes. The first baseline involved randomly selecting locations within the Toronto area for container placement, resulting in a final object value of 4915934.93, which is inferior to the best result. The accompanying graph illustrates a downward trend in the final object value as the number of containers increases, indicating the dominance of the cost function over the total reward.
The second baseline, involving the random selection of the center of the population distribution area, led to a final object value of approximately 2470654.10, still falling short of the best result. This baseline, being random, may vary, and infrequently, its final object value might surpass that of the best result. The final object value generally increases with the number of containers.
The last baseline, selecting the center of the population distribution area based on population rank. Choosing the center of the 31st most populated area resulted in a higher final object value of 7480120.57 than the best result. Moreover, the final object value peaked at 71 containers and declined thereafter. However, this baseline, starting in the most populated areas, possessed more information than the SA, which initiated container placement entirely randomly during initialization.
An attempt to benchmark the project results against Amazon’s last-mile delivery system was made. However, the available data only covered a portion of downtown Toronto, and the final object value was considerably worse than the baselines. This discrepancy can be attributed to the complexity of Amazon’s solution, incorporating numerous stores and collaboration with Canada Post. The cost function in this project, emphasizing cost, surpassed satisfaction in the case of Amazon. Furthermore, the project’s data collection, representing the population in the given area, was less dense compared to the concentrated location of Amazon stations. Due to the inherent unfairness in this comparison, it has not been included in the Google Colab.
Evaluation — Qualitative Analysis
In this project, SA took around 14 minutes per iteration to reach saturation which is long considering the fast pace of nowadays world, and more iterations might be required. However, the location SA calculated is not far from the Amazon locker project in Toronto though Amazon locker is slowly retiring from service now. This indicates that SA still provides a reasonable and close-to-optimal solution. If more detailed population data is acquired with individual inhabitants, it is not possible to use the third baseline anymore. Instead, SA could be a great starting point to figure out the number and the location of the container.
Conclusions & Recommendations
This project applied simulated annealing to optimize last-mile delivery in Toronto, leveraging estimated population distribution data. The algorithm aimed to minimize cost and maximize satisfaction while adapting to varying population densities. Results demonstrated effective resource allocation, but reliance on estimated data poses limitations.
Future work should focus on a few points. The first is to refine data accuracy and incorporate individual population distribution with more personal detail to obtain better optimization. Second, based on the data collected on the first point, the satisfaction and cost function should include more factors in the formula, such as age and vehicle ownership. The price of the location and the crime rate can be taken into consideration to fit more into the real-life scenario. Last is to collect data from online retailers or delivery services such as Post Canada or Purolator to acquire the actual need for delivery in each area or, even better, each household.
Since the third baseline has a better result in this project, if individual population distribution map can be obtained, one can use KNN to group the population to the population distribution area map, and from there, using the centres of the most populated areas as the initial value to start an SA experiment to improve the result.
References
[1] M. Kahr, ‘Determining locations and layouts for parcel lockers to support supply chain viability at the last mile’, Omega, vol. 113, p. 102721, 2022.
[2] Y. H. Lin, Y. Wang, D. He, and L. H. Lee, ‘Last-mile delivery: Optimal locker location under multinomial logit choice model’, Transportation Research Part E: Logistics and Transportation Review, vol. 142, p. 102059, 2020.
[3] C. Li, R. Ge, X. Wu, and A. Khamis, ‘Optimal Placement of Bus Stops using Particle Swarm Optimization’, in 2023 IEEE International Conference on Smart Mobility (SM), 2023, pp. 15–20.
[4] ‘Top online stores in Canada in 2022, by e-commerce net sales’, statista.com. https://www.statista.com/forecasts/871090/canada-top-online-stores-canada-ecommercedb
[5] ‘Amazon Profit Margin 2010–2023 | AMZN’, macrotrends.net. https://www.macrotrends.net/stocks/charts/AMZN/amazon/profit-margins
[6] ‘Total population of Canada from 2018 to 2028’, statista.com. https://www.statista.com/statistics/263742/total-population-in-canada/
[7] ‘智能快递柜成本，价格是多少？’, zhuanlan.zhihu.com. https://zhuanlan.zhihu.com/p/130374107
