Solving VRP With a Route Optimization API — An Intro for Developers

The Vehicle Routing Problem (VRP) is an optimization problem that involves finding the most efficient routes for a fleet of vehicles to deliver goods or services to a number of customers at various locations. The goal is to minimize the total distance traveled by the vehicles while also satisfying certain constraints, such as the capacity of each vehicle and the delivery time window for each location.

The VRP is important because it can help businesses reduce costs, increase efficiency and improve customer service with faster deliveries, and can be applied across a spectrum of industries, including delivery logistics, transportation planning and emergency response.

Solving the VRP can be challenging, as it requires accounting for a wide range of factors, including vehicle capacity, travel distances and times between locations, and vehicle/driver availability. There are many algorithms and heuristics that can be used to solve the VRP, including Integer Linear Programming (ILP) and heuristics such as the nearest neighbor, insertion and sweep algorithms.

Numerous variants of the VRP exist, each differing in the specific constraints and requirements of the problem. Some common variations are explained below.

Capacitated VRP (CVRP)

In the capacitated VRP, each vehicle has a limited capacity and cannot exceed it while making deliveries. The objective is to find a set of routes for the vehicles such that the total demand of all customers is satisfied while staying within the capacity constraints of the vehicles.

ILP problem decision variables:

• Binary variables x_ij indicating whether a customer i is served by a vehicle j
• Continuous variables d_ij representing the amount of goods delivered from customer i to customer j

Constraints:

• Flow conservation constraints to ensure that the demands of every customer are met

Time-Window VRP

As the name implies, in the time-window VRP, each customer has a time window within which the delivery must be made. The objective is to find routes that minimize the total travel time while ensuring that all deliveries are made within the required time window.

ILP problem decision variables:

• Binary variables x_ij indicating whether a customer i is served by a vehicle j
• Continuous variables t_ij representing the arrival time at customer i for vehicle j

Constraints:

• Flow conservation constraints to ensure that the demands of every customer are met

Multi-Depot VRP

In the multi-depot VRP, there are multiple depots from which vehicles can start and end their routes. The objective is to find the optimal routes for the vehicles such that the total travel distance is minimized while satisfying the demands of all customers.

ILP problem decision variables:

• Binary variables x_ij indicating whether a customer i is served by a vehicle j
• Continuous variables d_ij representing the amount of goods delivered from customer i to customer j

Constraints:

• Flow conservation constraints to ensure that the demands of every customer are met
• Subtour elimination constraints to prevent the formation of subtours within a route and ensure that each vehicle returns to its starting depot

Mixed VRP

In the mixed VRP, some customers have a fixed delivery location while others can be served from multiple locations. The objective is to find the optimal routes for the vehicles such that the total travel distance is minimized while satisfying the demands of all customers.

ILP problem decision variables:

• Binary variables x_ij indicating whether a customer i is served by a vehicle j
• Continuous variables d_ij representing the amount of goods delivered from customer i to customer j

Constraints:

• Flow conservation constraints to ensure that the demands of every customer are met
• Subtour elimination constraints to prevent the formation of subtours within a route and ensure that each vehicle returns to its starting depot

Vehicle Routing Problem with Time Windows (VRPTW)

In the VRPTW, each customer has a time window within which the delivery must be made and the vehicles have fixed start and end times. The objective is to find the optimal routes for the vehicles such that the total travel time is minimized while ensuring that all deliveries are made within the required time window.

ILP problem decision variables:

• Binary variables x_ij indicating whether a customer i is served by a vehicle j
• Continuous variables t_ij representing the arrival time at customer i for vehicle j

Constraints:

• Flow conservation constraints to ensure that the demands of every customer are met
• Time window constraints to ensure that the arrival of each vehicle at a customer location falls within the required time window

Vehicle Routing Problem with Pickups and Deliveries (VRPPD)

In the VRPPD, each customer has both pickup and delivery requests. The objective is to find the optimal routes for the vehicles such that the total travel distance is minimized while satisfying the pickup and delivery requests of all customers.

ILP problem decision variables:

• Binary variables x_ij indicating whether a customer i is served by a vehicle j
• Continuous variables d_ij representing the amount of goods delivered from customer i to customer j

Constraints:

• Flow conservation constraints to ensure that the demands of every customer are met
• Subtour elimination constraints to prevent the formation of subtours within a route and ensure that each vehicle returns to its starting depot

Route Optimization API for VRP

The key to solving the VRP and its numerous variations for any given use case is a route optimization API. Not just any route optimization API, but a fully featured one that comes with the ability to account for factors like vehicle capacity and driver shift timings in its calculations. Not all of them do.

Why not use a full-fledged packaged routing solution instead of just a route optimization API? Wouldn’t it be easier? Not necessarily. Packaged solutions have some serious limitations. They exist in the proprietary ecosystem of the solution provider and are often incompatible with other external tools. Because of this, these kinds of solutions make most sense when there is no existing infrastructure in place. If the need is to integrate into a pre-existing system architecture, an individual route optimization API is the best bet — it won’t require any costly or time-consuming infrastructure overhaul.

There’s another reason to opt for a route optimization API over a full route optimization solution. Even if there is no pre-existing infrastructure, a packaged solution will limit future options. The lack of modularity and flexibility can prove to be a point of failure when looking to scale up operations or cut costs. A high-performing standalone route optimization API imposes no such restrictions.

With all that said, it’s clear that a high-performance route optimization API is the way to go for solving the VRP. Schedule a call with our team to see if NextBillion.ai’s Route Optimization API is the right fit for your organization.