Routing, Packing, and Clustering - Optimization Fundamentals

December 04, 2020

Delivery planning, cloud resource allocation, inventory management, and portfolio management. What do all of these have in common? Decision modeling and optimization.

With the ongoing explosion of data, businesses across every industry constantly need new ways to make automated decisions. Many of those decisions have roots in three common optimization problems: routing, packing, and clustering.

Hop, our decision modeling & optimization platform, is built around these same principles. 

Routing

The most common routing problem is how to build the shortest, most efficient path possible for a driver or set of drivers. There can be constraints like how much a driver can carry or when a customer expects their food delivery. We usually think of road warriors when we think of routing, but routing optimization, like the Hop route solver, can actually be used on any problem where we want to connect objects across a network.

Let's start by taking a closer look at that most common routing problem -- the capacitated vehicle routing problem, or cvrp. That's a mouthful, so in Hop, we call this Fleet.

Our fleet input is a set of drivers, starting and ending locations for those drivers, how much each driver can carry, and delivery locations with a quantity of packages (apartment buildings get way more than my townhome).  Our fleet output is the order in which each driver will visit different locations such that the total distance traveled by all drivers is minimized. JSON in, JSON out. Pretty straightforward.

hop cvrp

At first glance, this looks pretty specific to cars, bikes and trucks, right?

In fact, the optimization solver doesn't actually care that it's optimizing connections between vans and retail customers. It could connect sales leads to appropriate agents, pickers and packers through a warehouse, or applications across a fiber network.

Contrary to popular robo responses, sometimes calls (or tickets) shouldn't be answered (or addressed) in the order in which they were received. Network optimization can determine whether your service meets expected time and quality benchmarks for your end users or not. It can also save you money ;-)

Packing

The classic Knapsack problem is crucial for your post-COVID world traveling adventure. In its purest form, the knapsack optimizer decides what items to take with you and what items to leave behind. Have you ever tried to pack 3 pairs of boots for a weekend in the mountains? Your pack has a finite carrying capacity and each item has a weight and a value.

Starting again with the classic operations research representation of the problem, our input contains items to pack, their predicted value, their weight or size, and our knapsack's capacity. Our output shows the list of packed items and their aggregate values. Again JSON in, JSON out.

hop knapsack

While it's always fun to think about what stays and what goes when packing for a hike or a mission to the International Space Station, where does this get us in the real world? Pretty far it turns out.

The same solver can allocate limited inventory to projects, build a schedule for employees, and manage investment portfolios. The cost of mistakes for these decisions might be a bit more than an oversized luggage fee.

Clustering

The same strategy you employ for kitchen organization -- grouping like things together such that dry goods are in the pantry, vegetables in the crisper, utensils are stacked in the same drawer, etc. -- also comes into play with optimization. Clustering optimizes groups of things for likeness with a single or multiple parameters.

Here at nextmv, we typically use our capacitated k-means solver to assign groups of similarly destined packages to potential drivers but there's nothing that limits its application to deliveries.

hop clustering

Fundamentally, our cluster models take in a set of things (points or users), a measurer that compares things to each other (distance or quality), and constraints like the total number allowed in a cluster. I'm sure you can guess at this point that Hop clustering solvers can be used in a number of ways. Want to know which product bundle to serve up to which users on an e-commerce site? Clustering. Want to balance your portfolio with different investment strategies? Clustering.

I hope you enjoyed our quick spin through optimization fundamentals and how relevant they are to a variety of industries and problems. There are certainly many more than I touched on today and we'd always love to hear more about how you use decision models in practice.

Happy hopping!

Featured posts