How can we prove that Quintiq's optimization technology is number one?

We've broken some of the toughest optimization puzzles in the world. Here are our latest wins:
Featured content

Vehicle Routing Problem with Time Windows

What's the problem
The VRPTW is one of the most studied problems in the field of combinatorial optimization. It is a variant of the Vehicle Routing Problem (VRP) first defined by Dantzig & Ramser in 1959. A solution to the VRPTW is a set of routes consisting of a sequence of visits to customers, where each route is assigned to a vehicle and all customers are visited within their time windows. The total volume assigned to each route must not exceed the capacity of the vehicle. The challenge is finding a solution that minimizes the total amount of vehicles used and distance traveled.

The VRPTW has been the subject of attention in the scientific community since the 1970s. Hundreds of papers have been published on the methods for arriving at a solution. In order to make a fair comparison of these divergent methods, scientists such as Gehring & Homberger and Solomon have defined sets of benchmarks which enable comparison of the results regardless of the method employed.

There are several recognized variations of the Solomon and Gehring & Homberger benchmarks. Gehring & Homberger has several instances, each with a different number of customers from 200 to 1000. Other values such as order specifications and distances also vary according to the instance of the problem.

It has the following characteristics :
  • You have a central depot and a set of customers
  • Each customer requires a specified volume to be delivered within a specified time window – this varies from customer to customer
  • There are given distances between the customers and the depot. For each of these trips a travel time is given
  • You have a set of vehicles, each of which has a maximum capacity
  • It’s not possible to spread one order across more than one vehicle

Quintiq's world records

Quintiq first took on Gehring & Homberger's 1000-customer benchmark, instance C1_10_4, and has solved many other instances since then. We chose the 1000-customer benchmark, which is the largest and therefore most difficult to solve, because it’s closest in scale to the real-life planning problems of our customers.

Here are some of our latest and most impressive wins:
Former World Record Quintiq's World Record
Date Record Number of routes Total distance Number of routes Total distance
Oct 9, 2014 Vehicle Routing Problem with Time Windows, C1_8_8 74 25293.09 73 26684.02
Sep 15, 2014 Vehicle Routing Problem with Time Windows, C1_8_9 72 24389.50 72 24349.32
Sep 15, 2014 Vehicle Routing Problem with Time Windows, C1_8_6 79 28665.57 79 27202.70
Sep 5, 2014 Vehicle Routing Problem with Time Windows, C1_10_6 99 44108.34 99 43830.21
Aug 25, 2014 Vehicle Routing Problem with Time Windows, C1_10_8 93 42220.24 93 42149.58
Aug 22, 2014 Vehicle Routing Problem with Time Windows, C1_8_8 74 25293.09 74 25250.78
Aug 21, 2014 Vehicle Routing Problem with Time Windows, C1_10_7 97 44806.73 97 43453.92
Jul 28, 2014 Vehicle Routing Problem with Time Windows, C1_8_3 72 24278.18 72 24267.08
Jun 24, 2014 Vehicle Routing Problem with Time Windows, C1_6_8 56 14429.48 56 14422.48
May 16, 2014 Vehicle Routing Problem with Time Windows, C1_6_6 59 16345.44 59 16039.29
Apr 14, 2014 Vehicle Routing Problem with Time Windows, C1_6_7 58 14816.55 57 15927.17
Apr 11, 2014 Vehicle Routing Problem with Time Windows, C1_10_7 97 44806.73 97 43772.66
Sep 13, 2013 Vehicle Routing Problem with Time Windows, C1_6_4 56 13560.21 56 13558.93
July 8, 2013 Vehicle Routing Problem with Time Windows, C1_8_4 72 23840.32 72 23827.02
Apr 1, 2013 Vehicle Routing Problem with Time Windows, C1_10_4 90 39641.46 90 39468.60

Find out how our optimization team solved the VRPTW
SINTEF is an independent research organization that keeps track of the best known solutions to the Solomon and Gehring & Homberger instances. World records are verified and recorded by SINTEF on their Transportation Optimization Portal.

Quintiq continues to invest time and resources into breaking world records in optimization. We expect to have more good news in the near future. Watch this space!