Optimization World Records
Vehicle Routing Problem with Time Windows
On October 1st 2012 at 3pm CET, Quintiq set a new world record for the Vehicle Routing Problem with Time Windows (commonly referred to as the VRPTW).
Are you ready for optimization? WEBINAR
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. 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.
Solving the VRPTW
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 number 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.
Quintiq took on Gehring & Homberger's 1000-customer benchmark, instance C1_10_4. 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.
Beating the world record
The solution that until recently held the official world record used 90 vehicles - which is the optimal value - and a total distance of 39641.46.
We set the new world record by finding a set of routes that respects all time windows and the maximum capacities of the vehicles and employs 90 vehicles at a distance of only 39468.68*. That’s an improvement of over 170 points or about 0.43%, significant for a benchmark that has been around for so many years.
Learn more about our approach to solving this problem and see the full route plan.
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!
*After some fine tuning, we've improved upon this number by 0.08 points. Our score now stands at 39468.60.