Let’s talk about Sam, a warehouse manager who is losing his sleep these days, literally and figuratively.

He wakes up sharp at 3 am daily, to plan delivery routes for 50000 consignments from his warehouse. With a team of 60 riders and simple geo-coding software, he is able to complete the job by 6:30 am.

Even after diligent planning, he is unable to plan efficient trips that save money, time, and fuel. He is unable to find the most cost and time-efficient routes or vehicles for the largest savings.

So, he is planning to wake up at 2 am tomorrow morning. But, he is still unsure whether he will be able to save more money than yesterday, or not.

Route planning in logistics can be challenging for large enterprises. This is because constraints make it hard to optimize the transit of millions of orders per day.

Now, these constraints can be anything:

• Number of deliveries every vehicle is allowed to make
• Number of vehicles serving a specific area
• Cost of vehicles, fuel, and fulfillment
• Time or any other SLA

Optimizing routes is a challenging constraint programming problem. It involves analyzing and optimizing specific business use cases at multiple levels.

Some businesses might focus on quick deliveries, while others might prefer vehicle optimization.

This means unlocking economies at scale requires much more than a simple geo-coding engine or TSP.

Scaling your route planning software involves two things:

• Solving business-specific constraints at scale
• Generating intuitive and optimized trips even when the constraints increase

So, as we expanded, we were routing millions of consignments per day, and the standard “one-size-fits-all” approach crumbled down.

We required a DIY Smart Route Planning Optimizer, and here is a walkthrough of how we built one.

What makes this entire endeavor more rewarding is the fact that this DIY worked for both - the developers and the clients. Both the stakeholders can customize and configure the routing software by Shipsy.

They can generate optimized routes by choosing the set of trip constraints from a given list.

So, the routing software allows Sam, the warehouse manager, and all his friends in the industry to generate trips with the greatest profits.

Ultimately, this means that he and his friends can now enjoy a peaceful sleep.

Building a smart route optimizer for multiple constraints

We aimed at building a smart, efficient, and scalable route optimizer that could:

• Distribute consignment (orders) among riders and take care of all the constraints
• Optimize the route (Cost)
• Suggest the best non-overlapping routes (quality and efficiency by plying only one vehicle to a specific area)
• Doesn’t require developer involvement for configuration every time (We have to make it easier for Sam, remember?)

This optimizer would help us in:

• Asset allocation
• Creating route plans, loading sequences, delivery ETAs
• Market vehicle requirements

It would consider the existing resources to suggest a relevant optimization strategy. It would consider the asset configuration, cost function, and consignment constraints.

This would help us deliver or transport consignments from a hub to desired locations (delivery location or another hub) while:

• Optimizing the use of existing resources
• Avoiding breaching any vehicle or consignment constraints

Add operational costs and distance traveled and we had a Pandora’s Box gawking at us!

At first glance, this might seem like a simple K-means or Travelling Salesman problem.

But, here is the catch!

To extract the global optimum, the only possible way would be to generate all the arrangements of trips possible. Only those arrangements which satisfy all arrangements should then be filtered in.

Finally, we should pick the most optimum of the filtered.

Since we’re trying every permutation of the trip, the time complexity of this would be of O(n!).

To put things into perspective, consider the following scenario:

Consider we have three letters {A, B, and C}.

How many permutations of it are possible?

We can start by fixing A, then choosing between {B, C}. This can be done in two ways: {A, B, C} or {A, C, B}. The same can be extended to B and C.

Wherein the results would be: {A, B, C}, {A, C, B}, {B, A, C}, {B, C, A}, {C, A, B}, {C, B, A}.

Take a look at the following image for a visual idea:

Source

Thus, the number of permutations => 6 = 3! We have established that the time complexity for global optimum is n!.

The growth rate of n! is worse than exponential:

Source

We can see n! is a “terrible” time complexity. Thus we needed ways to optimize this process.

So, we started with the strategies we had and began a smart DIY for Shipsy’s Smart Route Optimizer.

What did we do

We had different routing algorithms that fit in different use cases

• Balanced K-Means and Concorde K means algorithm helps distribute the consignments among the workers. Concorde provides the optimal path within the cluster.
• Constraint programming solver
• Shipsy's Routing Algorithm

As we onboarded more clients, the nature of consignments changed, adding more constraints:

• Consignments’ weight, volume, height, etc., needed to be considered in the planning
• Fuel Type - Certain areas in India especially in the NCR region have constraints on the type of fuel you can use. For example, in the national capital, only CNG vehicles can serve particular pin codes.
• Delivery, Pickup, and Pickup Delivery in different time windows
• Area Partitioning
• Vehicle Priority (Self-owned vehicles should get priority)
• Order Priority (Certain high-value orders need to be prioritized)
• Soft constraints, such as overlapping of delivery routes, clustering, and vehicle use

Hence, we needed something better than K-means.

After all, Sam’s friend Ray might be looking for a way to create profitable and intuitive trips with a specific set of vehicles or riders. This is the whole idea behind DIY software.

It assumes the configuration that a specific user finds “the best or relevant”.

So, we opted for solving constraint programming using Google OR-tools.

Using Google OR-Tools for Linear Programming

The basic idea was to define "what a particular solution should look like", instead of defining the exact solution.

We converted constraints into equations of the Linear Optimization problem. Then we solved those equations keeping the constraints in mind.

An example of a Linear Optimization problem is shown below:

Source

In our case, the constraints were:

• Consignment constraints: Weight, volume, time, nature, etc.
• Resource: Fixed cost, vehicle shift, vehicle location, weight capacity, volume capacity, etc.
• Cost Function, Speed factor, etc.

(Before we proceed further, it is important to mention that this list of constraints is ever-expanding. This is because as we scaled and onboarded more clients, the problems and criteria for determining the “profitability and optimization” of the trips changed vastly.

Currently, we are offering three different types of routing algorithm options. Each one of them has 30 to 40 constraints.)

Now, to suggest a solution, we were:

• Defining the properties of the solution (optimized routes)
• Not defining the steps (which vehicles for which route, etc) to come to a solution

For constraint programming, we used Google OR-Tools Routing Solver. It is a fast, memory-efficient, and numerically stable solution.

For example, its solution for the problem shown above looks like this:

Source

So, using the Routing Solver by Google, we solved the vehicle routing optimization. Now, we could find the best routes for a fleet of vehicles visiting a set of locations.

Usually, "best" means routes with the least total distance or cost.

Look at the following example where “0” denotes hub and other numbers as nodes for vehicles to visit:

Source

When we used Google OR-tools without constraints, the trip looked something like that:

Source

Okay, so we had amazingly intuitive trips with a single constraint.

But this is not the case in the real world, right?

Because, remember Sam’s friend Ray, his manager has been looking for ways to cut down the operational costs.

So, here comes another set of constraints, such as vehicle capacity.

Now, when we added even one more constraint (resources, consignments, and cost functions), the trip became:

• Non-intuitive
• Complex

So, with constraints, the Routing Solver presented the following trip:

Source

The trip shown above became even worse as we kept on adding constraints. The routes were overlapping, and the trips were no longer intuitive.

So, even though the trips were optimal, they were extremely complex and non-intuitive.

They looked something like this:

Source

Now, not every customer applies all the constraints on every delivery or transit. So, we needed our trips to be intuitive as well as optimal.

Thus, we created Shipsy’s Clustering Algorithm from scratch.

Shipsy’s Clustering Algorithm

Shipsy’s Clustering Algorithm is easy to use and fast. It helps us create intuitive trips with simple constraints.

It first segregates customers into clusters based on the partition they belong to.

Usually, partition_id is set by users to restrict vehicles serving multiple locations and minimize overlaps.

This is followed by collecting all the feasible nodes greedily. The greedy aspect denotes choosing the closest feasible consignment.

Finally, a TSP algorithm is applied to each cluster to get an optimal route per cluster.

So, the trips that initially looked something like this:

Source

Were now extremely intuitive and looked like this:

Source

While we solved the “intuitiveness” challenge, the product required configuration for every client.

This means that every time Sam or Ray or any other person required a change or started using the software, they had to sit with the developer for backend configuration.

This is because every optimization strategy had different optimization parameters as per:

• Business requirements
• Use cases

Now, this doesn’t look like a very good DIY; does it?

Thus began our journey to create an extremely scalable and configurable routing software that would:

• Assume the configuration as per a specific business
• Scale efficiently
• Require minimum to zero developer involvement for backend configuration
• Allow change at any particular period of time
• Come with a negligible learning curve
• Suggest highly optimized and intuitive trips every time (irrespective of the type and number of constraints)

Let us have a quick walkthrough in the next section.

Shipsy’s DIY Routing Playground

Shipsy boasts of a plethora of cutting-edge algorithms for vehicle routing problems. We wanted our clients to get a “feel” of how each algorithm fares in a real-world scenario.

Enter: Routing Playground.

It is one of our hallmark products, and allows users to set up dummy customers, and vehicles, and install their required constraints.

The end user can configure the software and try numerous constraints for creating their version of “the best” trips.

So, they can “play around” with the wide range of options we offer, which makes the name “Routing Playground” apt.

The user can choose any of the routing algorithms they want. The software would generate an optimized routing path within moments.

So, the trips were now optimized and intuitive, as shown below:

Source

They can save the most satisfactory configuration as the default backend engine. This engine keeps on suggesting optimized routes effortlessly and can be configured also.

Also, we were left with another problem - Area Partitioning. This would ensure efficient optimization as no two vehicles served the same area.

Solving area partitioning

It is often the case that the user wants vehicles to serve in select locations only.

For instance: A vehicle serving in the Noida region should not go to Delhi, and vice-versa.

It helped us in two ways:

• Quality of trip: Reduced overlap between vehicle trips.
• Vehicle region restriction: Restricting a vehicle to serve a specific region.

Our intuition here is to assign a “partition_id” to each vehicle and consignment.

Now, only the matching ids may be used to form a trip. We allow users to manually define a boundary in the map itself.

Thus, consignments that fall under that region would be assigned that partition_id.

Take a look at the following screenshot for a better understanding:

Source

Results: Benefits We Unlocked With Our DIY Route Optimizations

1. DIY Routing for Every Stakeholder

We started with Sam, who aimed at creating the most profitable trips. According to Sam, the trips that help him save the most money are the best ones.

However, the logistics and supply chain industry has a lot of Sams, Rays and stakeholders.

So, the definition of “optimized or best” trips varies from person to person.

Creating a DIY routing software allowed our solution to be as versatile as all our customers.

They no longer have to rely on the developers for small configuration changes.

Likewise, at the organizational level, we are able to use the DIY nature of the software for our requirements.

So, Shipsy’s Routing Playground is a DIY-hit with all the stakeholders.

2. Ease of Use and Speed of Processing

Google’s Routing Solver is complex to use and comes with a learning curve. Also, we have to define constraints and create equations for each one of them.

Shipsy’s clustering algorithm offers quick planning and creates intuitive-looking trips. It is easy to use

When we used Google’s Routing Solver, the trip planning for 1000 consignments took 10 to 15 minutes. Shipsy’s clustering algorithm can plan trips for 20, 000 to 30, 000 consignments in a few minutes.

3. OSRM for More Realistic Distance Function

Our routing optimizer uses OSRM (Open Source Routing Machine). So, every trip suggestion examines the geography between two points, such as dead ends, etc.

The trips appear as polylines on OSM (Open Source Maps) and are highly precise.

They also consider the real-world road conditions for smart decisions.

4. Cost Efficiency

Using OSM helped us reduce our dependence on Google Maps which comes with subscription fees. Also, OSRM offers blazing-fast speed because of its C++ backend.

5. Versatile Strategizing

Shipsy’s clustering algorithm offers a large number of options. For example, it offers 100+ consignment parameters and constraints for route planning.

So, strategizing can be as versatile as a client wants. For example, they can opt for Geo-fence partitioning, to map a rider to a specific geo-fence partition for zonal consignments.

At Shipsy, we aim to keep our products, operations, and performance razor-sharp. This ensures that our products scale well and stay relevant to the evolving client needs.

To be a part of our developer community, please visit our Careers Page.

Acknowledgments and Contributions

As an effort towards learning and skill development, we have regular “Tech-A-Break” sessions at Shipsy. In these sessions, our team members exchange notes on ongoing innovation and optimizations.

This write-up stems from a recent Tech-A-Break session on Routing Playground.

Contributions: Sahil Arora, Aman Ruhela, Rajat Kumar, Krishna Yadav, and Nanubala Gnana Sai.