Vehicle routing problem

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 Tasks

Route 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.

solved traveler salesman problem

The example of a solved traveler salesman problem - the optimal route for Pokémon Go players created by developer Andrew Briz Source: University of Waterloo

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. Frane Saric, 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 depots
  • limited subset of vehicles that have a specific facility in demand (e.g. a freezer compartment)
  • different dimensions of cargo to deliver/pick up
  • different capacity of each vehicle
  • multi-compartment vehicles
Real-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.

CVRP by GoogleOR-Tools solving CVRP where depot is in black, BUs - in blue, and demanded cargo quantity - at the lower right of each BU



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 lengths
  • disjoint time windows: arriving between two time windows, a vehicle must wait until the next time window opens
  • soft time windows: serving outside the time window is allowed, but it entails penalties
  • hard 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, each with a specified timeframe. VRPTWs need to be solved everywhere: from bank, postal, restaurant, or supermarket deliveries, to school bus routing and security patrol services.

Approach to solution: So how to be on time everywhere, while taking the shortest routes? We need to connect the dots: find a set of routes of minimal total traveling cost and maximal customer satisfaction which in this case is reached by complying with the prioritized time windows.

VRPTW visualized

VRPTW visualized: blue - customers to visit with their time windows above, black dot - depot, Source: Google OR-Tools

You can read more about ETA calculations in a separate post.

Pickup and Delivery Vehicle Routing Problem (PDVRP)

Each vehicle picks up items/passengers at location A and drops them off at location B. No depot is involved. Usually with PDVRP, we talk about simultaneous delivery and pickup. A common case is on-demand transportation - supplying services in direct response to customer requests (e.g. taxi, shuttle service, buses, etc.). Associated with origin and destination, routing results in paired pickup and delivery points.

Real-life scenario: This problem concerns transportation requests. Take Uber as an example. The system has to efficiently assign drivers to locations so that it takes them the least time to get there and pick up a customer.

Approach to solution: Assign routes to the vehicles to pick up and deliver passengers. Customer’s request must be met as early as possible by minimizing the total length of vehicles’ paths.

Pickup and delivery locations

Pickup and delivery locations as blue circles and the routes between them. Source: Google OR-Tools

Although, we’ve described the three VRP in isolation, OptimoRoute's Frane Saric points out that in the real world they often overlap exploding the size of the problem.“The placement of both pickup and delivery in a route affects whether you have room in your vehicle for another pickup. It also dramatically affects whether you’ll meet all time window constraints”. Frane illustrates it with an example: “Let’s say you are transporting people, there are only so many seats in your van. Then the problem becomes even worse to manage, as you have to keep track of capacity constraints throughout”.

Please note that there are way more problems and combinations of them. You can find a longer list here.

How to solve routing problems: off-the-shelf route optimization tools

Many fleet management software providers include route optimization functions (e.g. Verizon Connect, Teletrac Navman, and Fleetio). As we’ve already reviewed those jacks-of-all-trades in a dedicated article, we focus now on solutions targeting route planning exclusively.

Before we dive in, let’s overview the factors to note when choosing a route optimization solution. Yael Almog, product manager at Bringg, remarks that in today's market there is a growing demand for speed, cost, and convenience. That’s why among the most important characteristics of a routing software she names flexibility, real-time visibility, customized automation, and usability. Yael adds: “Given the complexity of delivery and logistics operations, deep digital integrations across business and transportation platforms is required”.

So now here’s a brief overview of the key players.

Google Optimization Tools (OR-Tools): open-source toolkit for routing problems

We want to start with a whole suite of computational software for solving all types of linear and constraint problems, routing ones specifically.

OR-Tools require you to get your hands dirty in programming and they have a separate library for VRPs. The tool has detailed documentation and an active community. Besides that, OR-Tools can optimally schedule a complex set of tasks and pack objects into bins with maximum capacities. This is not a beginner-friendly solution but is the most customizable. We will talk about creating custom routing software later in the article.

Use cases: TSM, capacitated VRP, pickup and delivery VRP, VRP with time windows, resource constraints.

Price. Most OR-Tools are free of charge.

APIs. Distance Matrix API calculates a distance matrix for any set of locations defined by address, latitude, and longitude. Without downloading OR-Tools, you can solve simple TSPs with the Direction API. To use it for development, you'll need your own free Directions API key. Commercial use of Direction API requires an enterprise key. OptimoRoute is a route optimization solution highly-ranked on many respected platforms like Capterra, G2Crows, and GetApp. It supports mobile with its OptimoRoute Driver app. OptimoRoute operates in a broad range of industries: food delivery, retail, maintenance, healthcare, waste collection, field sales, inspection services, post and courier, laundry, and more. Although it serves customers of all sizes, it’s small businesses that love OptimoRoute the most for its flexible per-driver pricing.

OptimoRoute claims that its algorithm will enable clients to reach many more customers and destinations than Google Maps. Maybe that’s why they don’t integrate with popular GPS systems.

OptimoRoute dashboard of planned routes

OptimoRoute dashboard of planned routes

Use cases. OptimoRoute capabilities, such as automated planning, suggest that it’ll best serve VRP with time windows. The solution will also be suitable for solving pickup and delivery VRP. With capacitated VRP, they increase productivity by doing automatic return-to-depot planning. Their CTO Frane Saric explains that feature: “Once a truck is empty, we will plan a restocking return trip to depot and continue doing deliveries after that”.

Price. Subscriptions are either monthly or annually, with the latter giving a 10 percent discount. OptimoRoute offers three pricing plans. The cheapest one - Starter, for $17.10 per driver/month – allows for planning 250 orders at once. If your business needs live tracking, it’s included in the Business plan (accounts for $26.10), along with web service API. Fat cats had better go for Enterprise plan, as it enables instant planning of over 750 orders, topped with analytics tools. Before making a purchase, you can test OptimoRoute with their 30-day trial.

API. OptimoRoute REST API uses JSON for structured data exchange. It requires SSL and is limited to five concurrent requests for one account or IP address. API allows for the following operations:
  • create/remove an order in the system
  • define object location
  • get the routes for a specific date
  • get the scheduling information for the specified order
  • start/stop the planning process for the specified date and return its status

Badger Maps: addressing salespeople’s specific needs

Badger Maps is primarily concerned with building and maintaining customer account base and optimizing sales routes. They offer smooth CRM integration, combine schedule planning, route optimization, and lead generation on the sales rep’s mobile device. Supporting Waze, Google Maps, Apple Maps, Garmin, and Magellan, Badger allows its users to easily navigate with their favorite GPS.

You can create a route simply by circling a set of points.
How To Create Routes with Lasso- Badger Maps [Android App]PlayButton

Badger's Lasso feature for simple route creation

Use case: traveling salesman problem.

Price. You can decide for yourself with a free trial or a demo for starters. After that, here are two pricing plans to consider. The Business plan is a match for field salespeople. It will cost a salesperson $59 a month, or $49 if billed annually. For larger companies, a better fit is the Enterprise plan ($105 monthly payment). Its personalized approach includes field support, custom CRM Integration, and one-on-one training.

API: Badger Maps doesn’t have an API. It has integration with main CRMs, a mobile app, and a web app.

Route4Me: cloud-based platform for route planning

Route4Me runs smoothly on any device. Among its pros, users highlight the ease of creating new maps from imported addresses. Route4Me is also flexible in terms of route modification: Its drag-and-drop feature will insert new addresses easily into existing routes.

Dragging and dropping a destination in Route4Me

Dragging and dropping a destination in Route4Me

Use case. All routing tasks.

The Route4Me solution addresses a large number of constraints: avoidance zones, predictive weather, weight and revenue constraints, and curbside/rooftop delivery, to name a few.

Price. Route4Me offers a free 7-day test drive trial. Its Dynamic Routing plan has three options: basic route management ($149/mo), route optimization of single-person routes ($199/month), and advanced route optimization ($299/month) that allows for optimizing multi-person routes. Prices are calculated for up to 10 members. Adding each additional member costs $50. Other pricing plans are Scheduled & Recurring Routing, Territory Management & Optimization, and Operational Assessment. Contact Route4Me for more details.

API. Route4Me offers the following APIs: Platform API’s, Operational Assessment API, Telematics Gateway API, and Resource API. You can use them to build custom solutions as well.

MapQuest: building blocks for a customized solution

MapQuest is an online web mapping service by Verizon. It can be the platform of choice when it comes to getting turn-by-turn directions from point A to point B, or points C, D and E.

Use case: pickup and delivery routing problem.

Price. MapQuest for Business can be used for free if your use is limited to 15,000 transactions per month. Otherwise, you’ll have to pay starting from $99 per month for 30,000 transactions (Basic plan) up to $899 for 500,000 transactions. For customized plans, you can always make direct inquiries.

MapQuest offers a wide range of APIs:

Data Manager API. Equipped with security settings, it stores custom datasets in a dedicated database on MapQuest servers.

Directions API. It performs routing optimized to certain preferences like the quickest time or the shortest distance. You can choose from several potential routes. Besides that, the API shows mileage and driving time between locations, visualizes the route, and allows for on-the-fly route modifications.

Geocoding API. Using this API, you can associate latitude and longitude with an address, and thus, define your location on the map.

Icons API. You can use the MapQuest icon set: markers, circles, vias, flags, etc., customizing them by size, color, style. You can also reference your own icons.

MapQuest icons

MapQuest icons

Search APIs. MapQuest Search API searches by radius or within a specified area. It’ll search through the MapQuest hosted database, as well as your uploaded data. Mixing data sources is also possible.

Place Search API complements Search Ahead API. The former performs the backend search to fulfill requests, while the latter is a predictive search engine that returns suggestions based on just a few input characters.

Static Map API. It gives you the power to make maps using geocoding, directions, traffic, and shapes. Then you can embed it in your app, site, or print media.

Maps created with MapQuest

Maps created with MapQuest Static Map API

Traffic API. It returns real-time traffic data. In particular, a structured list of traffic incidents and an image of the current traffic situation for a particular area. (If you want to have traffic predictions, visit our related post for information.)

There are also open-source alternatives: APIs for directions, elevation changes along a route, geocoding, location guidance, search API, and Static Map API.

WorkWave Route Manager: adaptable product for business management

WorkWave Route Manager is praised for visibility into vehicles’ whereabouts, effective syncing with drivers via their app, and helpful customer support. Route Manager precisely plans routes, scheduling time for each stop.

Use case: VRP with time windows.

WorkWave Route Manager dashboard with analytics on time windows violations, order fulfillment, and vehicle usage

WorkWave Route Manager dashboard with analytics on time windows violations, order fulfillment, and vehicle usage

Price. The Route Manager package starts at $49 per month/per vehicle. Real-time adjustments and mobile GPS tracking functions are available with the Route Manager 360 package. Individual driver monitoring is enabled with the 360+ package, as it provides GPS in-vehicle via on-board diagnostics. For more pricing insight, reach out to them directly. To be on the safe side before investing in this solution, try it out by booking a demo.

API. Apart from the basic APIs for GPS tracking, returns of available territories, depots, regions, and vehicles, what catches the eye is the Scheduling API, filtering options for orders and routes, routing plan approvals, and the experimental functionality of the Proposals API that suggests the best route to assign the order in a desired time slot.

Routific: helps delivery businesses get the job done

Routific is the best fit for small and mid-sized delivery businesses. Its driver mobile web app has a signature capture feature enabling customers to sign the delivery right on the driver's phone screen.

Proof of delivery with customer signatures in Routific's mobile app

Proof of delivery with customer signatures in Routific's mobile app

Use case: VLP with time windows, capacitated VLP, same-day pickup and delivery routing.

Price. With Routific you have three pricing alternatives: Essentials is $33 per vehicle per month. The Professional plan for $49 will open the doors to live tracking, driver analytics, API integration, and support for 1,000 stops per vehicle. Your vehicles don’t have to be limited to 1,000 stops with the Premium plan. If your team is growing and needs custom support, contact Routific to discuss the details. Also, for additional price of $16, Routific will keep your customers updated on the status of their delivery.

API. Engine API integrates Routific proprietary algorithms into your software. It finds the optimal routes and can reassign orders among drivers if necessary. Engine API can build open-ended routes. It’s useful for on-demand businesses that need to get deliveries done and don’t need drivers to be at a certain location at the end of the shift.

Apart from the ones we describe above, make a note about MapAnything (a good alternative to Badger Maps for field sales), MyRouteOnline, and ElasticRoute.

Closing up, we’d like to remind about the challenge businesses face while connecting every node in their supply chain, route optimization included. Intelligent route optimization requires insights into inventory availability, internal and external delivery resource capacity and availability, driver certifications and skills, customer information for prioritization, eCommerce and support platforms, and more. Yael Almog from Bringg suggests that an optimal solution in this regard is to utilize a centralized delivery orchestration platform that can seamlessly integrate route optimization with the many other business platforms, resources and nodes in the supply chain.

If nothing worked for you: in-house solution

Developing your own solution from scratch is quite a bumpy road. So usually companies choose the easy way of a ready-made software. Rahim Rasool, associate data scientist at Data Science Dojo, designs optimal and dynamic routes for public transport systems in metropolises. He advises out-of-the-box solutions for optimization problems on several grounds:
  • reliability: It has worked on a large number of problems before
  • less bugs and errors: It’s been tried and tested several times
  • support
  • flexibility
Minh Tu Quy, marketing team lead at ABIVIN, warns those who are determined to build route optimization solutions themselves: “Vehicle Routing Problem is an NP-hard problem. In research, they usually solve this problem with 5 - 10 constraints and a small number of vehicles and delivery points. But in the real business world, there are 20 - 30 different constraints to satisfy, while the number of vehicles can be hundreds, and the number of delivery points can be thousands. In other words, not many people can effectively solve this problem and apply it in the real business world”.

Nonetheless, many businesses still opt for an in-house solution, either to work on something heavily customized, or to ensure the safety of their client’s data. In this regard, Rahim notes: “The nature of every problem is different, and, in such cases, the off-the-shelf solutions might not be able to cater to this problem. Every delivery optimization problem has a focus on minimizing a set of parameters specific to the company based on their preference.”

But where should you begin?

Get a better understanding of the field. Learning about the types of routing problems should be your first task. Understand what applies to your specific business type, so you know what attributes and variables to consider when building a custom system.

Analyze pros and cons of different methods. By analyzing the market, you’ll be able to combine the best strategies to create a cheaper and more competitive route optimization solution that will outperform the available solutions on the market.

Modify the existing solutions to match your purposes. You may decide not to spend months coding all the different algorithms but opt for an open-source software suite as a foundation to build your tool around. As an example, GoGoVan on-demand ride-sharing service initially used OR-Tools. However, it didn't scale well as the delivery points were extended. So, based on the DBSCAN clustering algorithm, they built recursive-DBSCAN. The latter outperformed OR-Tools reducing the memory requirements.

Comments2

Sort by