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

Pickup and Delivery Problem with Time Windows

What's the problem

The Pickup and Delivery Problem with Time Windows (PDPTW) is a problem in the field of combinatorial optimization. It is an extension of the Vehicle Routing Problem with Time Windows (VRPTW). The difference is that the customers’ transportation requests do not only have a defined delivery location, but also a specific pickup location, which typically differs from the depot.

A solution to a PDPTW problem is a set of routes for a fleet of vehicles. It consists of a sequence of pickups and deliveries, where all locations are visited within their time windows. For each transportation request, both the pickup and delivery locations must be visited by the same vehicle where obviously the pickup occurs before the delivery.

Compared to the VRPTW, this adds coupling and precedence constraints. Additionally, the total load of a vehicle cannot exceed the capacity at any time. The goal is to minimize the total number of vehicles used; and as a secondary objective, the total traveled distance.

The academic community has been studying the PDPTW since the 1980s, resulting in hundreds of published papers on this topic. Just like with the VRPTW, a set of benchmarks is required, to fairly compare different solution approaches. For this purpose, in 2001 Haibing Li and Andrew Lim took the well-known Solomon and Gehring & Homberger benchmarks and adapted them to the PDPTW. These Li & Lim instances vary in the number of customers, ranging from 100 to 1000, as well as the other dimensions; time windows, demands, vehicle capacity and geographical distribution of the locations.

The PDPTW has the following characteristics:
  • A central depot and a set of customers
  • Each customer specifies a pickup and a delivery location
  • Each customer requires a specified volume to be picked up and delivered within specified time windows – these vary between customers
  • There are given distances and travel times between the locations
  • A set of vehicles, each of which has a maximum capacity

Quintiq's world records

In addition to taking on the Gehring & Homberger's benchmark for VRPTW, Quintiq has decided to take on the Li & Lim benchmark for PDPTW. Many real-life planning problems at our customers come in the form of a pickup and delivery problem.

Here are some of our latest wins:


Former World Record Quintiq's World Record
Date Record Number of routes Total distance Number of routes Total distance
28-Jan-2016Pickup and Delivery Problem with Time Windows, LRC2_4_2116303.36107424.72
21-Jan-2016Pickup and Delivery Problem with Time Windows, LRC2_4_696479.5696337.08
18-Jan-2016Pickup and Delivery Problem with Time Windows, LC2_6_21810277.23189914.1
15-Jan-2016Pickup and Delivery Problem with Time Windows, LC2_6_7197998.18197997.96
14-Jan-2016Pickup and Delivery Problem with Time Windows, LC2_6_10178019.94177965.41
12-Jan-2016Pickup and Delivery Problem with Time Windows, LC2_6_9189501188864.29
11-Jan-2016Pickup and Delivery Problem with Time Windows, LR2_4_5610185.14610084.11
04-Jan-2016Pickup and Delivery Problem with Time Windows, LC2_6_3178728.3178718.22
04-Jan-2016Pickup and Delivery Problem with Time Windows, LC2_6_4178041.97177902.66
04-Jan-2016Pickup and Delivery Problem with Time Windows, LR2_4_967995.7367930.55
20-Oct-2015Pickup and Delivery Problem with Time Windows, LRC2_4_1127471.01127454.14
09-Oct-2015Pickup and Delivery Problem with Time Windows, LC1_4_9367452.21367451.2
08-Oct-2015Pickup and Delivery Problem with Time Windows, LC1_4_2388012.43388007.79
SINTEF is an independent research organization that keeps track of the best known solutions to the Li & Lim 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!