How to Solve Vehicle Routing Problems: Route Optimization Software and Their APIs

What connects businesses as different as a moving company, meal delivery service, and a laundry service company? Simply, the need to plan daily routes with multiple stops. Unfortunately, many businesses don’t realize how drastically route optimization can increase their operational efficiency.Do you know the logistics problems you’re dealing with? We’ll help you pinpoint them by describing the most common ones.
You may actually recognize your concerns in one or more of them. And we’ll cap it off by referencing the key route optimization providers and their integration APIs.What’s Your Vehicle Routing Problem? Understanding the Route Optimization TasksRoute optimization is the process of determining the most cost-efficient route.

You may think that it means finding the shortest path between two points, but it’s rarely that simple: You must account for all relevant factors involved such as the number and location of all stops on the route, arrival/departure time gap, effective loading, etc. Route optimization is a solution for so-called vehicle routing problems (VRPs).The Vehicle Routing Problem or VRP is the challenge of designing optimal routes from a depot to a set of destinations each with business-specific constraints, such as vehicle limitations, cost controls, time windows, resource limitations concerning the loading process at the depot, etc.

The first classic VRP is known as the traveling salesman problem (TSP), which originated in the early 1800s and became widespread in the days when door-to-door salesmen peddled vacuum cleaners and encyclopedias. With time, VRP was categorized into much more sophisticated tasks involving large chunks of data.Let’s have a closer look at the most common VRPs and software that you can apply to unravel them.

Disclaimer: Real-world VRPs comprise of hundreds or thousands of nodes. The time required to solve them is growing relative to the size of the problem. For sufficiently large problems, it could take years to find the optimal solution.
CTO at OptimoRoute, confirms that point: “Exact methods like integer linear programming (ILP) are rarely used in practice because they are extremely slow and can solve only very small problems with a few orders”. Hence, routing solutions often rely on heuristics to be able to quickly return good enough but not necessarily optimal solutions.Capacitated Vehicle Routing Problem (CVRP)Since each vehicle has a maximum load capacity, you must always consider the weight and volume of what’s being transported.

The challenge is to save costs by transporting more goods in one trip without exceeding the vehicle’s capacity. There might be additional complications like:multiple depotslimited subset of vehicles that have a specific facility in demand (e.g. a freezer compartment)different dimensions of cargo to deliver/pick updifferent capacity of each vehiclemulti-compartment vehiclesReal-life scenario: Tesco Company, a global groceries and general merchandise retailer, uses over-the-road vehicles for goods distribution.

The goods are transported on pallets.
One vehicle can hold a limited number of pallets, while each business unit (BU) demands a different number of them. For instance, large department stores need several times more pallets than the vehicle can fit.Approach to solution: Assign the shortest routes to vehicles so that the total amount of units for the vehicle meets its capacity limitations.

Vehicle Routing Problem with Time Windows (VRPTW)Often customers are available during a specific period of time only. This places limitations on delivery/pick-up time, as now a vehicle has to reach a customer within a prioritized timeframe. When a time window opens, a vehicle should serve the customer.

It may arrive beforehand, but, by no means, outside the set time window. Falling behind schedule can significantly drop customer satisfaction level leading to profit loss in the long run. This dictates the need to schedule rides, but do it in the most cost-efficient way.

That's what VRPTW is all about.
Time windows can be:multiple time windows: a set of non-overlapping time windows with different lengthsdisjoint time windows: arriving between two time windows, a vehicle must wait until the next time window openssoft time windows: serving outside the time window is allowed, but it entails penaltieshard time windows: no time violations are permitted. If a vehicle arrives too early, it must wait until the time window opens; and it is not allowed to arrive late.Real-life scenario: Let’s take FedEx. A package has arrived at the destination country and is accepted by a last-mile carrier.

Now it needs to be efficiently transported to the distribution center. From there, a courier will receive the package and deliver it to a customer who will be waiting for their package on Tuesday from 9 to 10 in the morning. Doesn’t seem like a soft time window, right? So a courier mustn’t be late.
But there are other 11 packages on the agenda, ea