Toggle navigation OptaPlanner logo
  • Home
  • Download
  • Learn
    • Documentation
    • Videos
    • Slides
    • Training
    • Use cases
    • Compatibility
    • Testimonials and case studies
  • Get help
  • Source
  • Team
  • Services
  • Star
  • @OptaPlanner
  • Fb
Fork me on GitHub
  • Cheating on the N Queens benchmark
  • Open benchmarks for the win

Vehicle routing with real road distances

Tue 2 September 2014

Avatar Geoffrey De Smet

Geoffrey De Smet


Twitter LinkedIn GitHub

OptaPlanner lead

In the real world, vehicles in a Vehicle Routing Problem (VRP) have to follow the roads: they can’t travel in a straight line from customer to customer. Most VRP research papers and demos happily ignore this implementation detail. As did I, in the past. Although using road distances (instead of air distances) doesn’t impact the NP-hard nature of a VRP much, it does result in a few extra challenges. Let’s take a look at those challenges.

Datasets with road distances

First off, we need realistic datasets. Unfortunately, public VRP datasets with road distances are scarce in the VRP research community. The VRP Web has few small ones, such as a dataset of Bavaria with 29 locations, but nothing serious. So I had to generate some realistic datasets myself with the following requirements:

  1. Use Google Maps like roads with real distances in km between every pair of locations in the dataset.

    • For example, use highways when reasonable over small roads.

  2. For every dataset, generate an air distance variant and a road distance variant, to compare results.

  3. Generate a similar dataset in multiple orders of magnitude, to compare scalability.

  4. Add reasonable vehicle capacities and customer demands, for the vehicle capacity constraint in VRP.

I ended up generating datasets of Belgium with a location for cities, towns and subtowns. The biggest one has 2750 locations. I might add a road variant of the USA datasets later, those go up to 100 000 locations.

belgium datasets unsolved

By using the excellent Java library GraphHopper, based on OpenStreetMap, querying practical road distances was relatively easy. It’s also fast, as long as the entire road network (only 200MB for Belgium) can be loaded into memory. Loading the entire road network of North-America (6GB) is a bit more challenging. I 'll submit these datasets to the VRP Web, so others researchers can use them too.

All this happens before OptaPlanner's VRP example starts solving it. During solving, the distances are already available in a lookup table. Once we start generating datasets with 1000 locations or more, pre-calculating all distances between every location pair can introduce memory and performance issues. I’ll explain those and the remedies in my next blog.

Air distance vs Road distance

For clarity, I’ll focus on the dataset belgium-n50-k10.vrp which has 50 locations and 10 vehicles with capacity 125 each. OptaPlanner was given 5 minutes to solve both variants (air and road distance).

Using air distances (which calculates the euclidean distance based on latitude and longitude) results in:

belgium n52 airSolution

The total distance, 22.99 doesn’t mean much because it’s not in a common unit of measurement and because our vehicles can’t fly from point to point anyway. We need to apply this air distance solution on the real road network (shown below), to know the real distance:

belgium road n51 airSolution

Now, let’s compare that air distance solution above with the road distance solution below.

belgium road n50 roadSolution

The road distance solution takes 108.45 km less, so it’s almost 5% better! And that’s on one of the most dense road networks in the world (Belgium’s road network): on more sparse road networks the gain might be more.

Conclusion

Using real distances instead of air distances does matter. Solving an VRP with air distances and then apply road distances is suboptimal.

But can we really pre-calculate every locations pair in big datasets? Stay tuned.


Comments Permalink
 tagged as vehicle routing insight

Comments

Visit our forum to comment
  • Cheating on the N Queens benchmark
  • Open benchmarks for the win
Atom News feed
Don't want to miss a single blog post?
Follow us on
  • T
  • Fb
Blog archive
Latest release
  • 8.1.0.Final released
    Fri 15 January 2021
Upcoming events
  • KIE Live
    Worldwide - Tue 19 January 2021
    • OptaPlanner Shadow Variables for the Vehicle Routing Problem and Task Assignment by Geoffrey De Smet, Karina Varela, Alex Porcelli
  • Javaland
    Worldwide - Tue 16 March 2021
    • AI on Quarkus: I love it when an OptaPlan comes together by Geoffrey De Smet
Add event / Archive
Latest blog posts
  • Solve the facility location problem
    Fri 9 October 2020
     Jiří Locker
  • OptaPlanner Week 2020 recordings
    Mon 7 September 2020
     Geoffrey De Smet
  • Let’s OptaPlan your jBPM tasks (part 1) - Integrating the two worlds
    Fri 3 July 2020
     Walter Medvedeo
  • AI versus Covid-19: How Java helps nurses and doctors in this fight
    Fri 8 May 2020
     Christopher Chianelli
  • Workflow processes with AI scheduling
    Tue 5 May 2020
     Christopher Chianelli
  • Constraint Streams - Modern Java constraints without the Drools Rule Language
    Tue 7 April 2020
     Geoffrey De Smet
  • How to plan (and optimize) a Secret Santa
    Wed 18 December 2019
     Christopher Chianelli
Blog archive
Latest videos
  • YT Shadow variables
    Tue 19 January 2021
     Geoffrey De Smet
  • YT Domain modeling and design patterns
    Tue 17 November 2020
     Geoffrey De Smet
  • YT Quarkus insights: AI constraint solving
    Tue 20 October 2020
     Geoffrey De Smet
  • YT AI in kotlin
    Wed 23 September 2020
     Geoffrey De Smet
  • YT Planning agility: continuous planning, real-time planning and more
    Thu 3 September 2020
     Geoffrey De Smet
  • YT Quarkus and OptaPlanner: create a school timetable application
    Thu 3 September 2020
     Radovan Synek
  • YT Business use cases and the impact of OptaPlanner
    Thu 3 September 2020
     Satish Kale
Video archive

KIE projects

  • Drools rule engine
  • OptaPlanner constraint solver
  • jBPM workflow engine

Community

  • Blog
  • Get Help
  • Team
  • Governance
  • Academic research

Code

  • Build from source
  • Submit a bug
  • License (Apache-2.0)
  • Release notes
  • Upgrade recipes
Sponsored by
Red Hat
More coder content at
Red Hat Developers
© Copyright 2006-2021, Red Hat, Inc. or third-party contributors - Privacy statement - Terms of use - Website info