Use OR-Tools in Python to Solve VRP Problems

Posted on Views: Word count in article: 1.6k Reading time ≈ 6 mins.

The official manual gives sample code for using OR-Tools to solve problems:

https://developers.google.com/optimization/routing/vrp

The python code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
"""Simple Vehicles Routing Problem (VRP).

   This is a sample using the routing library python wrapper to solve a VRP
   problem.
   A description of the problem can be found here:
   http://en.wikipedia.org/wiki/Vehicle_routing_problem.

   Distances are in meters.
"""

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp


def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data["distance_matrix"] = [
        # fmt: off
        [0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
        [548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
        [776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
        [696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
        [582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
        [274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
        [502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
        [194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
        [308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
        [194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
        [536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
        [502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
        [388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
        [354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
        [468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
        [776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
        [662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0],
        # fmt: on
    ]
    data["num_vehicles"] = 4
    data["depot"] = 0
    return data


def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    max_route_distance = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"Route for vehicle {vehicle_id}:\n"
        route_distance = 0
        while not routing.IsEnd(index):
            plan_output += f" {manager.IndexToNode(index)} -> "
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id
            )
        plan_output += f"{manager.IndexToNode(index)}\n"
        plan_output += f"Distance of the route: {route_distance}m\n"
        print(plan_output)
        max_route_distance = max(route_distance, max_route_distance)
    print(f"Maximum of the route distances: {max_route_distance}m")


def main():
    """Entry point of the program."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
        len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
    )

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    # Create and register a transit callback.
    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["distance_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Distance constraint.
    dimension_name = "Distance"
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        3000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name,
    )
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )

    # Output log
    search_parameters.log_search = True

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print("No solution found !")


if __name__ == "__main__":
    main()

The output of this code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
I0000 00:00:1749123891.150723   11012 search.cc:308] Start search (memory used = 28.79 MB)
I0000 00:00:1749123891.150834   11012 search.cc:308] Root node processed (time = 0 ms, constraints = 136, memory used = 28.93 MB)
I0000 00:00:1749123891.151456   11012 search.cc:308] Solution #0 (302188, time = 0 ms, branches = 35, failures = 1, depth = 33, memory used = 29.54 MB)
I0000 00:00:1749123891.151899   11012 search.cc:308] Solution #1 (301960, improvement rate = -2.28e+07%/s, maximum = 302188, time = 1 ms, branches = 39, failures = 3, depth = 33, Relocate<1>, neighbors = 31, filtered neighbors = 1, accepted neighbors = 1, memory used = 29.61 MB)
I0000 00:00:1749123891.152326   11012 search.cc:308] Solution #2 (286188, improvement rate = -1.5772e+09%/s, maximum = 302188, time = 1 ms, branches = 44, failures = 5, depth = 33, Relocate<1>, neighbors = 104, filtered neighbors = 2, accepted neighbors = 2, memory used = 29.65 MB)
I0000 00:00:1749123891.152596   11012 search.cc:308] Solution #3 (270348, improvement rate = -1.584e+09%/s, maximum = 302188, time = 1 ms, branches = 48, failures = 7, depth = 33, Relocate<1>, neighbors = 105, filtered neighbors = 3, accepted neighbors = 3, memory used = 29.68 MB)
I0000 00:00:1749123891.152876   11012 search.cc:308] Solution #4 (239032, improvement rate = -3.1316e+09%/s, maximum = 302188, time = 2 ms, branches = 54, failures = 9, depth = 33, Relocate<1>, neighbors = 112, filtered neighbors = 4, accepted neighbors = 4, memory used = 29.69 MB)
I0000 00:00:1749123891.153112   11012 search.cc:308] Solution #5 (225364, improvement rate = -1.3668e+09%/s, maximum = 302188, time = 2 ms, branches = 58, failures = 11, depth = 33, Relocate<1>, neighbors = 113, filtered neighbors = 5, accepted neighbors = 5, memory used = 29.69 MB)
I0000 00:00:1749123891.153635   11012 search.cc:308] Solution #6 (225136, improvement rate = -2.28e+07%/s, maximum = 302188, time = 2 ms, branches = 63, failures = 13, depth = 33, Relocate<1>, neighbors = 181, filtered neighbors = 6, accepted neighbors = 6, memory used = 29.69 MB)
I0000 00:00:1749123891.154082   11012 search.cc:308] Solution #7 (224976, improvement rate = -1.6e+07%/s, maximum = 302188, time = 3 ms, branches = 67, failures = 15, depth = 33, Relocate<1>, neighbors = 211, filtered neighbors = 7, accepted neighbors = 7, memory used = 29.69 MB)
I0000 00:00:1749123891.154816   11012 search.cc:308] Solution #8 (209912, improvement rate = -1.5064e+09%/s, maximum = 302188, time = 4 ms, branches = 74, failures = 17, depth = 33, Relocate<1>, neighbors = 308, filtered neighbors = 8, accepted neighbors = 8, memory used = 29.69 MB)
I0000 00:00:1749123891.155472   11012 search.cc:308] Solution #9 (209752, improvement rate = -1.6e+07%/s, maximum = 302188, time = 4 ms, branches = 78, failures = 19, depth = 33, Relocate<1>, neighbors = 393, filtered neighbors = 9, accepted neighbors = 9, memory used = 29.69 MB)
I0000 00:00:1749123891.160007   11012 search.cc:308] Solution #10 (209660, improvement rate = -10.9653%/s, maximum = 302188, time = 9 ms, branches = 83, failures = 21, depth = 33, Cross, neighbors = 947, filtered neighbors = 10, accepted neighbors = 10, memory used = 29.70 MB)
I0000 00:00:1749123891.160286   11012 search.cc:308] Solution #11 (209636, improvement rate = -2.4e+06%/s, maximum = 302188, time = 9 ms, branches = 87, failures = 23, depth = 33, Cross, neighbors = 948, filtered neighbors = 11, accepted neighbors = 11, memory used = 29.70 MB)
I0000 00:00:1749123891.160576   11012 search.cc:308] Solution #12 (207988, improvement rate = -1.648e+08%/s, maximum = 302188, time = 9 ms, branches = 93, failures = 25, depth = 33, Cross, neighbors = 957, filtered neighbors = 12, accepted neighbors = 12, memory used = 29.70 MB)
I0000 00:00:1749123891.160969   11012 search.cc:308] Solution #13 (207944, improvement rate = -4.4e+06%/s, maximum = 302188, time = 10 ms, branches = 97, failures = 27, depth = 33, Cross, neighbors = 991, filtered neighbors = 13, accepted neighbors = 13, memory used = 29.70 MB)
I0000 00:00:1749123891.161680   11012 search.cc:308] Solution #14 (207784, improvement rate = -1.6e+07%/s, maximum = 302188, time = 10 ms, branches = 102, failures = 29, depth = 33, Cross, neighbors = 1113, filtered neighbors = 14, accepted neighbors = 14, memory used = 29.70 MB)
I0000 00:00:1749123891.161896   11012 search.cc:308] Solution #15 (194116, improvement rate = -1.3668e+09%/s, maximum = 302188, time = 11 ms, branches = 106, failures = 31, depth = 33, Cross, neighbors = 1114, filtered neighbors = 15, accepted neighbors = 15, memory used = 29.70 MB)
I0000 00:00:1749123891.162349   11012 search.cc:308] Solution #16 (193888, improvement rate = -2.28e+07%/s, maximum = 302188, time = 11 ms, branches = 114, failures = 33, depth = 33, Cross, neighbors = 1164, filtered neighbors = 16, accepted neighbors = 16, memory used = 29.70 MB)
I0000 00:00:1749123891.162767   11012 search.cc:308] Solution #17 (193820, improvement rate = -6.8e+06%/s, maximum = 302188, time = 11 ms, branches = 118, failures = 35, depth = 33, Cross, neighbors = 1202, filtered neighbors = 17, accepted neighbors = 17, memory used = 29.70 MB)
I0000 00:00:1749123891.164996   11012 search.cc:308] Solution #18 (184528, improvement rate = -2397.07%/s, maximum = 302188, time = 14 ms, branches = 123, failures = 37, depth = 33, RelocateExpensiveChain, neighbors = 1676, filtered neighbors = 18, accepted neighbors = 18, memory used = 29.73 MB)
I0000 00:00:1749123891.165661   11012 search.cc:308] Solution #19 (177660, improvement rate = -6.868e+08%/s, maximum = 302188, time = 14 ms, branches = 127, failures = 39, depth = 33, RelocateExpensiveChain, neighbors = 1794, filtered neighbors = 19, accepted neighbors = 19, memory used = 29.75 MB)
I0000 00:00:1749123891.165991   11012 search.cc:308] Solution #20 (177500, improvement rate = -1.6e+07%/s, maximum = 302188, time = 15 ms, branches = 133, failures = 41, depth = 33, RelocateExpensiveChain, neighbors = 1828, filtered neighbors = 20, accepted neighbors = 20, memory used = 29.75 MB)
I0000 00:00:1749123891.177741   11012 search.cc:308] Finished search tree (time = 26 ms, branches = 166, failures = 75, neighbors = 2966, filtered neighbors = 20, accepted neigbors = 20, memory used = 29.87 MB)
I0000 00:00:1749123891.177778   11012 search.cc:308] End search (time = 26 ms, branches = 166, failures = 75, memory used = 29.87 MB, speed = 6384 branches/s)
Objective: 177500
Route for vehicle 0:
 0 ->  9 ->  10 ->  2 ->  6 ->  5 -> 0
Distance of the route: 1712m

Route for vehicle 1:
 0 ->  16 ->  14 ->  8 -> 0
Distance of the route: 1484m

Route for vehicle 2:
 0 ->  7 ->  1 ->  4 ->  3 -> 0
Distance of the route: 1552m

Route for vehicle 3:
 0 ->  13 ->  15 ->  11 ->  12 -> 0
Distance of the route: 1552m

Maximum of the route distances: 1712m

Note: We can use search_parameters.log_search = True to output logs of OR-Tools.