OptaPlanner logo
  • Download
  • Learn
    • Documentation
    • Videos

    • Use cases
    • Compatibility
    • Testimonials and case studies
  • Get help
  • Blog
  • Source
  • Team
  • Services
  • Star
  • T
  • L
  • F
  • YT
Fork me on GitHub

False assumptions for the Vehicle Routing Problem

Tue 6 August 2013
Avatar Geoffrey De Smet
Geoffrey De Smet

Twitter LinkedIn GitHub

OptaPlanner creator

Many companies are faced with the vehicle routing problem, when they need to:

  • Deliver/pick up items at multiple locations

  • Or execute repairs/maintenance at multiple locations

These companies want to minimize their fuel and time usage, to reduce their costs and ecological footprint. Sounds easy, right? Just take the shortest route. Unfortunately it’s not that simple…​ Let’s take a closer look.

Minimize the distance

In Vehicle Routing Problem (VRP), we need to transport items from the warehouse to the customers:

vrpPresumptions01

In this case, we have 7 customers across the region and 2 available vehicles stationed at the warehouse.

The shortest route to visit all these customers is this:

vrpPresumptions02

This optimal solution requires 210 fuel (which includes each vehicle driving back to the warehouse).

Notice that we only use 1 vehicle. Let’s continue from that assumption.
Assumption: An optimal VRP route uses only 1 vehicle. (false)

Vehicle capacity

In a real-world delivery/pick up scenario, each customer needs a number of items, but a vehicle’s capacity to transport items is limited.

vrpPresumptions03

In this case, all 7 customers need 20 items and a vehicle can transport 100 items. So a single vehicle cannot transport the 140 items of all customers.

We need to use 2 vehicles now:

vrpPresumptions04

This optimal solution requires 224 fuel, which is - of course - more than the 210 fuel of the previous solution. The yellow truck transports 60 items and the green one 80 items.

Notice that none of the lines cross. Let’s assume that’s always the case.
Assumption: An optimal VRP route has no crossing lines. (false)

Let’s see what happens when some of the customers require more items than other customers.

vrpPresumptions05

In this case, 2 customers need 50 items and the other 5 still need 20 items. So the previous solution is infeasible because the yellow truck would need to transport 120 items.

Now the lines do need to cross:

vrpPresumptions06

The optimal solution now requires even more fuel: 284. We found a feasible solution with 2 vehicles.

So we don’t seem to need any more vehicles.
Assumption: An optimal, feasible VRP route with n vehicles is still optimal for n+1 vehicles. (false)

Let’s add a 3rd vehicle to disprove that:

vrpPresumptions07

By adding an extra vehicle, the optimal solution now uses less fuel: only 274. This is a paradox: buying more vehicles can reduce expenses.

Notice that in both solutions above, no vehicle crosses its own line.
Assumption: An optimal VRP route has no crossing lines of the same color. (false)

Time Windows

In any real-world scenario, time is of the essence. Items need to be delivered on time, within the time window of each customer.

vrpPresumptions08

In the case above, a vehicle needs to arrive at the top left customer between 3 and 4 o’clock. Different customers have different time windows. For example, all 4 customers on the right are flexible: they are available between 1 and 6 o’clock. Additionally, each delivery/pick up/repair at a customer takes 1 hour to complete.

In the optimal solution, the yellow truck does cross its own line now:

vrpPresumptions09

In the optimal solution, the yellow truck arrives at the most left customer at 1 o’clock. An hour later it leaves for the bottom left customer at which it arrives at 2:20 (because driving takes some 20 minutes). Again an hour later it departs and arrives at its 3rd customer at 3:40.

Notice how the time windows pretty much dictate the route, especially on the left side.
Assumption: We can focus on time windows before focusing on capacity (or vice versa). (false)

Let’s see what happens if the time windowed customers also need a number of items:

vrpPresumptions10

Given these requirements, we need to focus on the capacity and the time windows in parallel:

vrpPresumptions11

The optimal solution now puts the bottom right customer in the yellow truck, because there was no more room in the green truck.

Conclusion

In a real-world vehicle routing problem, many assumptions fail. Finding a good solution is hard: there are no short-cuts. We need to be able to optimize without making assumptions. Yet, we cannot iterate through all possible states in a brute force manner either - even on relatively small problems - because of hardware limitations. So we need good, flexible algorithms - such as the heuristics and metaheuristics implemented in OptaPlanner (Open Source, Java) - to solve bigger cases:

vrpPresumptions12

All screenshots are taken from the OptaPlanner vehicle routing example.


Permalink
 tagged as vehicle routing insight

Comments

Visit our forum to comment
AtomNews feed
Don’t want to miss a single blog post?
Follow us on
  • T
  • L
  • F
Blog archive
Latest release
  • 8.35.0.Final released
    Fri 3 March 2023
Upcoming events
    Add event / Archive
Latest blog posts
  • OptaPlanner 9 is coming
    Tue 21 February 2023
    Lukáš Petrovický
  • Farewell - a new lead
    Tue 15 November 2022
    Geoffrey De Smet
  • Run OptaPlanner workloads on OpenShift, part II
    Wed 9 November 2022
    Radovan Synek
  • Bavet - A faster score engine for OptaPlanner
    Tue 6 September 2022
    Geoffrey De Smet
  • Run OptaPlanner workloads on OpenShift, part I.
    Thu 9 June 2022
    Radovan Synek
  • OptaPlanner deprecates score DRL
    Thu 26 May 2022
    Lukáš Petrovický
  • Real-time planning meets SolverManager
    Mon 7 March 2022
    Radovan Synek
  • Blog archive
Latest videos
  • The Vehicle Routing Problem
    Fri 23 September 2022
    Geoffrey De Smet
  • Introduction to OptaPlanner AI constraint solver
    Thu 25 August 2022
    Anna Dupliak
  • On schedule: Artificial Intelligence plans that meet expectations
    Sat 23 July 2022
    Geoffrey De Smet
  • Host your OptaPlanner app on OpenShift (Kubernetes)
    Mon 7 February 2022
    Geoffrey De Smet
  • OptaPlanner - A fast, easy-to-use, open source AI constraint solver for software developers
    Mon 31 January 2022
  • Order picking planning with OptaPlanner
    Fri 31 December 2021
    Anna Dupliak
  • AI lesson scheduling on Quarkus with OptaPlanner
    Thu 18 November 2021
    Geoffrey De Smet
  • Video archive

OptaPlanner is open. All dependencies of this project are available under the Apache Software License 2.0 or a compatible license. OptaPlanner is trademarked.

This website was built with JBake and is open source.

Community

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

Code

  • Build from source
  • Issue tracker
  • Release notes
  • Upgrade recipes
  • Logo and branding
CC by 3.0 | Privacy Policy
Sponsored by Red Hat