Vehicle Routing with Time Windows

Overview

The Vehicle Routing Problem with Time Windows (VRPTW) problem is an established extension of the classic Vehicle Routing Problem (VRP), distinguished by the introduction of time window constraints for each customer, adding a temporal dimension to the already intricate tasks of fleet sizing, route planning, and capacity management.

These additional constraints make the VRPTW a better reflection of real-world logistical challenges and opens up a broader landscape for algorithmic innovation. The presence of time windows makes the problem computationally more challenging and encourages the exploration of novel algorithmic frameworks.

Challenge Formulation

VRPTW involves determining a set of cost-effective routes for a fleet of identical vehicles operating from a single depot to serve a geographically dispersed set of customers. Each vehicle has a fixed capacity and each customer has a known demand for goods and a defined time window during which service must begin. If a vehicle arrives before this time window, it must wait; if it arrives after, service is considered infeasible. The primary objective is to minimise the total distance the fleet must travel to deliver goods to all customers and return to the depot, such that:

Notes: Each unit of distance takes the equivalent amount of time to travel. i.e. a vehicle will take 100 time units to reach a customer that is 100 distance units away.

Example

The following is an example of the Vehicle Routing Problem with Time Windows with configurable difficulty. Two parameters can be adjusted in order to vary the difficulty of the challenge instance:

Demand of each customer is selected independently and uniformly at random from the range [1, 35]. Each customer is assigned a time window between which they must be serviced. Service duration is set to a fixed value of 10 time units per customer. The maximum capacity of each vehicle is set to 200.

Consider an example instance with $num\_nodes=8$ and $better\_than\_baseline=0.8$ with the $baseline=3875$:

# A sample generated example
CUSTOMER
CUST NO.  XCOORD.   YCOORD.   DEMAND    READY TIME  DUE TIME   SERVICE TIME
       0       500       500         0            0      2318             0
       1        75       250        10            0       868            10
       2       940       582        11          825       884            10
       3       398       419        22            0       682            10
       4       424       690         6          256       273            10
       5       143       482        19          674       717            10
       6       187       292        27            0      1785            10
       7       382       204         3            0       832            10
       8       465       274        25         1386      1437            10
       
max_capacity = 200 # total demand for each route must not exceed this number
fleet_size = 4 # the total number of routes must not exceed this number
max_total_distance = baseline*better_than_baseline = 3100 # (better_than_baseline * baseline) routes must have total distance under this number to be a solution

The depot is the first node (node 0) with demand 0. The vehicle capacity is set to 200 and the fleet capacity to 4. In this example, routes must have a total distance of 3100 or less to be a solution.

Now consider the following routes:

Route 1: [0, 6, 1, 7, 8, 0]
Route 2: [0, 4, 2, 0]
Route 3: [0, 3, 5, 0]

When evaluating these routes, each route has demand less than 200, the number of vehicles used, 3, is less than the fleet capacity, the time windows are not violated, and the total distance is shorter than 3100, thereby these routes are a solution:

Our Challenge

In TIG, the baseline route is determined by using Solomon's I1 insertion heuristic that iteratively inserts customers into routes based on a cost function that balances distance and time constraints. The routes are built one by one until all customers are served. The goal is to produce a solution better than the baseline's total distance by at least the specified factor ($better\_than\_baseline$), while ensuring all VRPTW constraints are satisfied. Please see the challenge code for a precise specification.

Applications

Efficient transportation logistics is increasingly important in modern society, and the Vehicle Routing Problem with Time Windows (VRPTW) plays a key role in this area. By optimizing routes within specific time limits, VRPTW solutions support effective route design and fleet management, leading to significant economic and environmental benefits. Research in this field has helped develop a specialized tool industry that enhances operational efficiency across various sectors.

Originally developed for transportation logistics, VRPTW methodologies have expanded to include applications such as: