Blog post

Unravelling Real-Time Route Optimization: New Ways to Solve Vehicle Routing Problems

Learn how route optimization algorithms tell you which path to take at any given time

December 20, 2022 12 mins read

Global transportation has existed for centuries, from on-foot migrations to caravan shipments.

In the last decade, however, globalization has magnified the volume of transported people and assets. Last year, over 4,000 parcels were shipped every second across 13 of the world’s major markets. China Railway moved a record 147,520 persons per minute in September 2022.

The above numbers are far from a plateau. Urban populations are growing. Meanwhile, rising fuel costs and concerns over emissions are prompting people to ditch personal vehicle ownership in favor of mobility as a service (MaaS) offerings. Logistics companies are facing a pressing need to reduce emissions and improve delivery times simultaneously.

All of the above factors strengthen the need for real-time route optimization solutions powered by big data and machine learning (ML) algorithms.

But as with every new technology, the natural question is this: Which tangible results can route optimization software deliver for transportation businesses? Let’s unpack the answer together.

What is route optimization software?

Unravelling Real-Time Route Optimization: New Ways to Solve Vehicle Routing Problems

Route optimization is the process of establishing the optimal route for traveling based on input factors such as best cost or earliest estimated time of arrival (ETA). A route optimization algorithm analyzes different travel paths and automatically generates navigation instructions, updating them in real time.

The goal of routing optimization isn’t to find the shortest or fastest route but to suggest the most efficient based on pre-programmed conditions (such as number of stops, planned delivery windows, or traffic congestion levels).

Popular route optimization use cases include:

  • Delivery route optimization
  • Public transport route optimization
  • Freight shipment route optimization
  • Multi-modal transport route optimization

In every case, the ultimate goal is to achieve better transport efficiency and harness cost savings — a pressing priority for most companies. Over 70% of UK logistics companies reported transportation cost bumps of 25% or more in Q1 2022. In the US, freight rates increased 28%between 2010 and 2022.

Escalated shipping costs can further trigger disruptions across global markets, where consumers’ purchasing power continues to decrease:

Shipping costs are an important driver of inflation around the world: when freight rates double, inflation picks up by about 0.7 percentage points. Most importantly, the effects are quite persistent, peaking after a year and lasting up to 18 months. This implies that the increase in shipping costs observed in 2021 could increase inflation by about 1.5 percentage points in 2022.

International Monetary Fund (IMF)

On the passenger side, transportation companies are experiencing an influx of new riders post-pandemic. At the same time, many are pressed to modernize their fleets to meet transport sector decarbonization goals set by governments.

Faster travel times and convenience are the key factors prompting consumers to choose public transit over private. Yet in the US, the allocative efficiency of public transport sits at 68% and cost efficiency is 50%.

The transportation sector needs routing optimization software with dynamic planning capabilities to resolve the ongoing mayhem. Thankfully, the technology is already available.

How does real-time route planning optimization work?

Unravelling Real-Time Route Optimization: New Ways to Solve Vehicle Routing Problems

Real-time dynamic routing software uses available big data such as vehicle telemetry data, historic travel times for routes, and traffic data to determine the optimal path between several geographic points.

The route-building part is done automatically by algorithms — statistical or machine learning models trained to evaluate different route, schedule, and stop combinations to find the best travel route.

ML-based route optimization algorithms can identify patterns in large data sets without prior knowledge of the system. Also, the best-in-class systems can evaluate millions of data points per second to find more optimal combinations.

To better understand how vehicle route optimization systems work, let’s put the magnifying glass over their two components — big data and optimization algorithms.

Big data

Big data in transportation has ample use cases, ranging from traffic predictions to smarter parking management.

Fleet management and transportation companies, in turn, rely on vehicle telematics, location-based services, and geospatial intelligence to optimize asset use, shave operating costs, and improve network efficiency.

Vehicle routing planning and optimization can also benefit tremendously from the growing number of available big data sources (proprietary and external).

To perform vehicle routing optimization, at a minimum you need access to the following data sources:

    Task order data (destination, package weight/dimensions, transportation conditions, delivery time slots, etc.)

  • Available resources (drivers, idle vehicles, vehicle type and capacity, etc.)
  • Operational data (delivery facility addresses, access constraints, special compliance requirements or customer instructions, etc.)
  • Road intelligence (mapping data, traffic information, historical delivery times, road conditions, etc.)

These data points are most likely available in your fleet management software and vehicle telematics systems. Mapping, traffic, and GIS data can be obtained via public or private APIs (which are plentiful) for real-time routing optimization.

Route optimization algorithms

The quest to figure out the optimal vehicle routing paths dates back to 1959. Back then, George Dantzig and John Ramser proposed the first algorithmic solution to the vehicle routing problem (VRP).

The vehicle routing problem is a combinatorial optimization that involves finding an optimal design of routes traveled by a fleet of vehicles to serve a set of customers.

International Journal of Production Economics

Since then, other scientists have come up with multiple algorithmic solutions to the vehicle routing problem for trucks and public transportation fleets.

Classification of dynamic route planning algorithms

Unravelling Real-Time Route Optimization: New Ways to Solve Vehicle Routing Problems

Source: Core — A Comparative Study of Vehicles’ Routing Algorithms for Route Planning in Smart Cities

Each of the proposed dynamic route optimization algorithms has different performance rates, evaluated by three quality parameters:

  • Computational complexity. Algorithms that find the fastest routes but have longer computation times aren’t the best contenders, especially for dynamic route planning.
  • Scalability. If the size of the road network increases, an algorithm’s degree of scalability decreases. An algorithm that performs well with a smaller sample may not always be applicable to larger networks.
  • Quality of the best route. To determine which algorithm is calculating the optimal route, this metric compares the best routes calculated by different algorithms based on the same metrics (travel distance, travel time, fuel consumption, etc.).

Additionally, the performance of routing optimization algorithms can be further improved with extra data such as:

  • Real-time road information: current traffic conditions, incident rates, weather conditions, etc.
  • Destination information: purpose of travel, on-site delivery constraints, etc.
  • Vehicle information: remaining fuel (or battery charge for EVs), real-time vehicle performance conditions, maintenance status, etc.

Over the years, however, the original vehicle routing problem has seen new iterations that transport companies face on a daily basis:

  • Capacitated Vehicle Routing Problem (CVRP) — Figuring out the best routing optimization approach for fleet units with varying load capacity
  • Vehicle Routing Problem with Time Windows (VRPTW) — Optimizing delivery routes based on specific timeframes selected by end customers (or around predefined transport schedules)
  • Pickup and Delivery Vehicle Routing Problem (PDVRP) — Performing dynamic route planning for vehicles that pick up parcels or passengers at one location and drop them off at another

The above routing problems are best solved by machine learning algorithms such as neural networks (NNs), support vector machine (SVM) algorithms, and Naive Bayes classifiers.

Such algorithms can capture and dynamically process more data points collected from connected vehicles, onboard telematics units, and/or external data sources to deliver route planning optimization in real time. Though there are certain limitations.

Comparison of machine learning algorithms

 

Techniques Overview Limitation Aplication
SVM The SVM performs the coordination of individual observation. The result of this model creates an optimal hyperplane that separates classes. The training and testing function of SVM is slow. Context-aware security of IoV
Neural network It is an ANN biological NN and is organized in layers that are made up of several interconnected “nodes”. It takes a large time to process and requires a large dataset. Speed forecasting in IoV
Naive Bayesian It is a bioinspired neural system organized in Layers that are connected with cache other node. The function of Bayesian is dependent on hardware and is repeatedly faced with inexplicable behavior. Fast vehicular communication
K-nearest neighbor (KNN) This algorithm is use to utilize a database to categorize into several classes for forecasting the simple point. Its learning process is low. Communication of IoV is fast
HMM The function of HMM is processed only on the partially observable. It needs a large amount of computational time. Best routing process

Source: Hindawi — A Study to Enhance the Route Optimization Algorithm for the Internet of Vehicle

In practice, most proprietary software for route planning relies on the above approaches. For instance, FedEx Ground dynamic route optimization (DRO) software was designed to dynamically balance routes to avoid unequal package distribution across the network.

FedEx COO Raj Subramaniam said that the system provides near real-time routing data to the company’s massive fleet of contractors, which they can use for effective route planning optimization on their end. Bloomberg later reported that the system also drove the profitability up for certain routes and led to significant improvements in workforce productivity and a bump in on-time deliveries.

James Lohr, head of planning and delivery systems at Ocado, also shared how their dynamic routing software works. Using available task order data, the system first randomly assigns deliveries to a van with a certain geo-region. Then it calculates how long each route will take and proposes more granular improvements to maximally optimize delivery routes.

[Our system] makes a combination of small and large changes, from switching the order of two drop-offs to switching entire chunks of deliveries between vehicles — each time evaluating whether it’s an improvement. Making four million moves a second and keeping track of the best solutions, it slowly approaches the most optimal route it can find.

James Lohr of Ocado

Amazon’s Rabbit and UPS’s Orion VRP software have a similar degree of sophistication. On the back end, Rabbit processes multiple data points such as GPS data, real-time traffic conditions, historical routing data, and current weather, among other factors, to deliver optimized route planning instructions to drivers.

In general, a custom route optimization algorithm can solve multiple problems for transportation companies:

  • High number of required stops
  • Multi-day route planning
  • Multimodal shipping combination
  • Optimized workload allocation
  • Special trip intervals (e.g. to refuel)
  • Custom start/finish locations

Moreover, a dynamic route optimization module can be (and should be!) integrated with other business systems you’re using such as your fleet management software, freight marketplace, or enterprise resource planning (ERP) system. This way, you can improve your visibility across the entire supply chain and mitigate possible disruptions at the onset.

Must-have features for route planner software

The route planner software market stood at $4.32 billion in 2020 and is set to reach $16.25 billion by 2030 (which isn’t surprising given the surging shipment volumes).

In practical terms, the above means that transportation companies have no shortage of commercial routing software. And yet many choose to develop proprietary vehicle route optimization algorithms.

Both options have merit. Smaller fleets can often benefit from using off-the-shelf vehicle routing platforms and then extend them with extra functionality and integrations with other systems.

Custom route planning software development makes sense for companies with a larger logistics arm. In this case, you can create more robust processing algorithms tailored to your operating workflows. Then you can integrate the planning engine into other software — your transportation management system, MaaS platform, or fleet management solution.

Whichever route you choose, we recommend having the following routing software features.

Fleet management software development

Make dynamic route optimization and efficient fleet dispatch your competitive strength

Learn more

Multi-stop route planning

Multiple stops are a given for last-mile logistics and increasingly for mid- and long-haul journeys too. A common optimized route planning approach is to direct drivers with available truck capacity towards extra depots to pick up extra freight. Doing multiple stops is often more cost-effective than dispatching another driver for an end-to-end journey.

The transition to eMobility will further strengthen the need for multi-stop and special interval trip planning since EVs require regular recharging. A dynamic route planning engine also makes a good future-proof investment.

Learn more about the business advantages of dynamic route planning from our case study

Read more

Dynamic dispatch management

Vehicle route planning extends beyond devising optimal navigational paths. You also have to match the routes to the available workforce — and ensure that employees are working proper hours (to avoid staff attrition and compliance issues).

To achieve that, your routing software must work in conjunction with your dispatch management solution (or be part of it). Such tools help fleet managers streamline the creation of driver schedules, automate truck dispatches, and collect a wealth of insights about driver and asset performance.

Learn more about must-have features of a dispatch management platform

Read more

ETA predictions

Estimated time of arrival is a crucial number for fleet managers. Most customers today expect precise deliveries within selected time slots. Yet far fewer logistics companies manage to meet the publicized promises of “blazingly fast” delivery. In Australia, a staggering 88% of local businesses have experienced domestic and international delivery delays this year.

Dynamic route optimization algorithms help you calculate precise ETAs using live information on traffic conditions, vehicle GPS data, and average travel speeds. All of these details can be shared with your end customers or business partners so they can make necessary preparations on their end (e.g. engage ground staff at the depot location for offloading or reprogram a delivery if they’re not available during the assigned time slot).

Learn more about improving the accuracy of ETA estimates

Read more

Multimodal transportation support

Logistics and public transport networks have grown bigger, with more modalities actively used by shippers and passengers alike. Global governments, in turn, are also trying to reduce the volume of road traffic to solve rampant congestion problems and reduce environmental harm. The EU, for instance, plans to shift 30% of long-haul cargo shipments from the road to more sustainable modalities (e.g. rail) by 2030 and shift another 20% by 2050. Passengers, in turn, are looking into on-demand transportation and other MaaS offerings as an alternative to private vehicle ownership.

These changes encourage transportation companies to launch multimodal transportation routes, which often end up being more cost-effective. To delight customers with competitive multimodal transportation freight contracts, you’ll need a fit-for-purpose routing optimization engine that can model different transportation scenarios based on the cargo type, destination, customer specifications (e.g. special transport conditions), and other factors. Machine learning models are well-equipped for this task.

On the passenger side, you’ll need secure integrations with urban transport management systems as well as other mobility players to deliver a seamless passenger transit experience. API programming, big data analytics, and mapping expertise are required to build such solutions.

Learn more about the technical components of multimodal transportation management systems

Read more

Geofencing

Geofencing is a handy feature for last-mile logistics, as it allows you to assign specific delivery zones to drivers and ensure they only cover the given area (rather than roam around town on their own accord).

Your dynamic route optimization solution can supply you with live tracking data on vehicle positions (using GPS technology) and alert you to any deviations from the planned route. This way, you can quickly investigate possible issues (such as a sudden breakdown or problematic driver behaviors). Geofencing functionality can also be helpful to prevent asset theft or unauthorized use. For example, you can program automatic engine shutdown for assets that have left the assigned area for longer than an hour.

Learn more about how fleet truck tracking systems work from our case study

Read more

EV routing

Electric vehicle (EV) fleet management comes with unique constraints. Battery ranges differ a lot by vehicle type, load, and driving conditions (namely the weather or even geographic layout). Many EVs see an up to 20% drop in range in subzero temperatures, rendering such fleets less effective for some destinations. Likewise, aggressive driving behaviors such as heavy acceleration also impact the charging state.

Separately, e-fleets require a different approach to route planning because of their charging needs. At present, EV charging infrastructure is still insufficient to support a full transition, though progress is being made. Fast charging stations are few and solutions for long-haul truck charging such as electric highways are still at the proof-of-concept stage. Because of these constraints, e-fleet operators must engage in meticulous routing optimization to prevent no-return scenarios and ensure optimal charging cadence.

Learn how we’ve developed a convenient multi-stop EV trip planner

Read more

The road forward to smarter vehicle route optimization

Since the 1960s, the industry has made tremendous progress in solving vehicle routing problems. In the 2020s, technological advancements in machine learning and data engineering allow us to set a further bar in route planning efficiency.

Ample new data has become available through OEM-based and external telematics units. GIS tools further enable transportation companies to compile more comprehensive geospatial intelligence for HD maps, while improvements in road infrastructure connectivity now let you collect real-time traffic data.

A challenge that remains is putting this data to optimal use, but that’s an area where technology consulting firms like Intellias can support you.


Intellias helps global transportation companies place technology into the core of their operations. Contact us to discuss various approaches to dynamic route optimization for your business.

Rate this article
5.0/5.0 Thank you for your vote. 53556 8338e4cf7e

How can we help you?

Get in touch with us. We'd love to hear from you.

Contact us

We use cookies to bring best personalized experience for you.
By clicking “Accept” below, you agree to our use of cookies as described in the Cookie Policy

Thank you for your message.
We will get back to you shortly.