Example

We will show you how define the VRPSolverEasy model for the capacitated vehicle routing problem with time windows (VRPTW).

Data

In the VRPTW, the objective is to minimize the total route length (traveled distance) such that each customer is served within his time window and the total demand delivered by each truck does not exceed its capacity. The distance between points are calculated using the Euclidean norm and the traveling time between points is equal to the distance.

# data
cost_per_distance = 10
begin_time = 0
end_time = 5000
nb_point = 7

# map with names and coordinates
coordinates = {"Wisconsin, USA": (44.50, -89.50),  # depot
               "West Virginia, USA": (39.000000, -80.500000),
               "Vermont, USA": (44.000000, -72.699997),
               "Texas, the USA": (31.000000, -100.000000),
               "South Dakota, the US": (44.500000, -100.000000),
               "Rhode Island, the US": (41.742325, -71.742332),
               "Oregon, the US": (44.000000, -120.500000)
               }

# demands of points
demands = [0, 500, 300, 600, 658, 741, 436]

In this example, we solve a very small VRPTW instance in which time windows of customers are equal. This special case is called distance constrained vehicle routing problem (DCVRP).

Model VRPSolverEasy

# Initialisation
model = solver.Model()

# Add vehicle type
model.add_vehicle_type(
    id=1,
    start_point_id=0,
    end_point_id=0,
    name="VEH1",
    capacity=1100,
    max_number=6,
    var_cost_dist=cost_per_distance,
    tw_end=5000)

# Add depot
model.add_depot(id=0, name="D1", tw_begin=0, tw_end=5000)

coordinates_keys = list(coordinates.keys())
# Add Customers
for i in range(1, nb_point):
    model.add_customer(
        id=i,
        name=coordinates_keys[i],
        demand=demands[i],
        tw_begin=begin_time,
        tw_end=end_time)

# Add links
coordinates_values = list(coordinates.values())
for i in range(0, 7):
    for j in range(i + 1, 7):
        dist = compute_euclidean_distance(coordinates_values[i][0],
                                          coordinates_values[j][0],
                                          coordinates_values[i][1],
                                          coordinates_values[j][1])
        model.add_link(
            start_point_id=i,
            end_point_id=j,
            distance=dist,
            time=dist)

Solving model

model.solve()

Results

After solving, we can print the solution if it found:

if model.solution.is_defined():
    print(model.solution)

You obtain the following output:

Route for vehicle 1:
    ID : 0 --> 2 --> 5 --> 0
    Name : DEPOT --> Vermont, USA --> Rhode Island, the US --> DEPOT
    End time : 0.0 --> 16.807 --> 19.259 --> 37.230000000000004
    Load : 0.0 --> 300.0 --> 1041.0 --> 1041.0
    Total cost : 372.29999999999995

Route for vehicle 1:
    ID : 0 --> 1 --> 3 --> 0
    Name : DEPOT --> West Virginia, USA --> Texas, the USA --> DEPOT
    End time : 0.0 --> 10.548 --> 31.625 --> 48.728
    Load : 0.0 --> 500.0 --> 1100.0 --> 1100.0
    Total cost : 487.2800000000001

Route for vehicle 1:
    ID : 0 --> 4 --> 6 --> 0
    Name : DEPOT --> South Dakota, the US --> Oregon, the US --> DEPOT
    End time : 0.0 --> 10.5 --> 31.006 --> 62.010000000000005
    Load : 0.0 --> 658.0 --> 1094.0 --> 1094.0
    Total cost : 620.1

Note

You can also enumerate all feasible solutions by changing parameters before solving

model.parameters.action = "enumAllFeasibleRoutes"

Enumeration works only for very small instances, and should be used only for debugging and demonstration/teaching purposes.

Full documentation of the VRPSolver API is given in src: solver API.