Site Selection and Best Path using Optimization Techniques — Canada Post Example

Source — https://developers.google.com/maps/solutions/images/storelocator_clothing.png

In this article, we’ll focus on the courier delivery services industry (Canada). There is always a need to reduce operational costs in this industry. And to do this, companies often face challenges while selecting the location for a new site and finding the best path for the delivery van to reduce costs related to fuel and time.

About the Industry

The Courier Delivery Services Industry includes two major segments, that include large couriers and small-scale delivery companies. The total revenue for 2019 in Canada was $12.8 bn with 5-year annual growth of 3.5%. The industry is projected to grow over the next five years as improvements in disposable incomes have made consumers increasingly willing to purchase commercial goods, the majority of which are e-commerce related. The projected upswing in the price of crude oil will also allow the companies to generate more profit by optimizing their delivery performance.

Supply Chain and Major Players

In the market ecosystem, courier delivery companies in Canada form the bridge between first-tier buyers and suppliers. Please see the below figure to understand the supply chain.

Figure 1: Supply Chain Process of Courier Services in Canada

Table 1 below shows the major players in Canada (2019). The overall market share concentration within the industry has decreased despite mergers and acquisitions to increase the scope of operations.

Table 1: Market Share of Major Players in Courier Delivery Services (Canada — 2019)

Canada Post and United Parcel Service (UPS) are the two largest players in the industry. Canada Post that has 33.5% of the market, has powerful collaborations with other entities like Canada Border Services Agency and China Post, and this has allowed the company to grow parcel revenue and volume significantly. Due to labor disruption, the company has experienced a decline in growth and hence needs to come up with efficient cost planning models to reduce their operating costs.

UPS, on the other hand, has relied on the fleets of aircraft to transport parcels over long distances. Air Transit does expedite the process, but in turn, results in customers paying high charges. UPS has over 14% of the total market in Canada and is expected to see a decline in operating profit due to costs of bringing new facilities and technology on-line and hence there is a need to optimize the operating costs for UPS as well.

Challenges in Supply Chain for Courier Delivery Industry

From now on, I will narrow down my scope to focus on the optimization of delivery performance in the industry.

Operational Challenges

The common challenges that courier delivery companies face are time windows between stops to deliver parcels, storage capacity of vehicles, fuel capacity and recharge requirements, lane driving rules, driver’s lunch break and customer’s preference for order receiving time. There are other constraints like labor laws and weekend delivery, but those are outside the scope of this article.

Formulation of Constraints using Linear Programming

The delivery performance problems are a part of the Vehicle Routing Problem family. To explain the problem clearly, I used a linear programming model and the simple versions of such problems include the target of the company to reduce the fuel charge/distance covered. In the real scenario, the target also includes minimizing the number of vehicles used and balancing the workload. To simplify the model, I have considered just one delivery van for Canada Post in the city of Montreal.

The objective function is:

Min(Σ distance covered/fuel cost)

subject to constraints:

1. start and end position of the van is the same
2. The van travels to a location just once

Note: Sometimes, the constraints do not allow the problem to form a convex space for the optimization algorithm to converge to a point. Hence, we should use a forced constraint as per the problem statement. Solving methods like Evolutionary perform better than GRG Non-Linear and Simplex.

Canada Post Problem Illustration

I selected 10 locations in the City of Montreal, considering they have high demand. Table 2 shown below lists the location names with the address and other location information.

Table 2: Locations selected for problem illustration

You can see these locations on a map below:

Figure 2: Locations selected for problem illustration on map (Source — Google Maps)

Problem 1: Find the Optimal Location

Refer to the sheet ‘Optimal location’ for the problem (download link at the end).

In this problem, the target (objective function) is to minimize the fuel cost for delivery. There are 9 customer locations given that are the ones with high demand. The location data (latitude and longitude are also provided). The task is to find the optimal location to open the store so that the trips taken by van (two trips for each location — going and coming back to the store) cost the lowest for the business. Note that this problem does not consider the road path to a location. The optimal solution for this problem is based on the distance calculated geometrically in terms of radian distance of earth.
The optimal location is found by using the GRG Nonlinear method in Excel Solver using a forced constraint to allow the algorithm to converge at a minima. The optimal solution found for this problem is highlighted below:

Figure 3: Optimal location to open a new store based on locations given in red (Source — Google Maps)

Problem 2: Traveling Salesman Problem — Find the optimal path

Refer to the sheet ‘Optimal route’ for this problem (download link at the end).

In this problem, the target (objective function) is to minimize the total distance traveled (in meters). Table 3 shows the data taken from Google Maps that gives the distance rounded up to the nearest hundredth of a meter. Note that this problem considers the shortest road path as measured using google maps. Due to lane restrictions, the numbers will not be mathematically related. There are 2 scenarios for this problem: First, the delivery van can start from anywhere and second, the van should start from the Canada Post location. For this problem, I took location data for an existing store of Canada Post in Montreal. Figures 4 and 5 show the result for the two scenarios

Table 3: Location codes

Table 4: Distance between locations (distance in meters)

Scenario 1 results:

Figure 4: Optimal Path for Scenario 1 — The van can start from anywhere (Source — Google Maps)

Scenario 2 results:

Figure 5: Optimal Path for Scenario 2 — The van starts from Canada Post (Source — Google Maps)

One interesting finding from this analysis is that if the van must start from Canada Post, the algorithm suggests that it should first go to Desautels Faculty of Management and not La Marq. In reality, La Marq is just 700 meters away from Canada Post but since we are taking into account the lane driving laws, the algorithm suggests the best route which otherwise would seem absurd.

My Take on Courier Delivery Industry

Courier delivery companies need to focus on reducing their operating costs as their profits are linked to fluctuations in forces that are outside their reach, such as government policies. The only thing that they can control is optimizing their costs. In the fierce industry competition, there is an ever-growing need to find better algorithms to implement the best practices to reduce costs. The majority of these problems statements fall in the bucket of Vehicle Routing Problems (VRP) and Vehicle Routing Problems with Time Window (VRPTW). These problems sometimes become NP-Hard and require heavy computation to reach the optimum solution. Companies that are data-driven are the ones that are going to dominate the market in the coming years.

Parting Notes

There are advanced algorithms like Balanced Clustering Algorithms with Greedy Insertion and Route Improvement by Extended-Insertion Algorithm, and sometimes using heuristics to reach the optimum minima in convex-shaped problems. However, such problems require high resources both in terms of computation and skill set. There are no publicly available benchmarks and sometimes the solutions are not favorable. Sometimes, we also go for the ‘visually attractive’ solutions which consider how the stops are grouped into routes. Solutions that have overlap in routes for multiple vehicles are often termed to be less visually attractive than others.

References

1. IBIS World Report | 49222CA Couriers & Local Delivery Services in Canada | October 2019
2. Routing Optimization for Waste Management: Surya Sahoo, Seongbae Kim, Byung-In Kim, Bob Kraas and Alexander Popov Jr.
3. A STRATEGIC ANALYSIS OF CANADA POST’S PARCEL ECOMMERCE GROWTH STRATEGY: Kerry Brock

File to refer (Download the excel file)

chandravenky/Optimization

Connect with me on LinkedIn/ GitHub