1#!/usr/bin/env python3
2# Copyright 2010-2021 Google LLC
3# Licensed under the Apache License, Version 2.0 (the "License");
4# you may not use this file except in compliance with the License.
5# You may obtain a copy of the License at
6#
7#     http://www.apache.org/licenses/LICENSE-2.0
8#
9# Unless required by applicable law or agreed to in writing, software
10# distributed under the License is distributed on an "AS IS" BASIS,
11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12# See the License for the specific language governing permissions and
13# limitations under the License.
14# [START program]
15"""Capacitated Vehicle Routing Problem with Time Windows (CVRPTW).
16
17   This is a sample using the routing library python wrapper to solve a CVRPTW
18   problem.
19   A description of the problem can be found here:
20   http://en.wikipedia.org/wiki/Vehicle_routing_problem.
21
22   Distances are in meters and time in minutes.
23"""
24
25# [START import]
26import functools
27from ortools.constraint_solver import routing_enums_pb2
28from ortools.constraint_solver import pywrapcp
29# [END import]
30
31
32# [START data_model]
33def create_data_model():
34    """Stores the data for the problem."""
35    data = {}
36    # Locations in block unit
37    locations_ = \
38            [(4, 4),  # depot
39             (2, 0), (8, 0),  # locations to visit
40             (0, 1), (1, 1),
41             (5, 2), (7, 2),
42             (3, 3), (6, 3),
43             (5, 5), (8, 5),
44             (1, 6), (2, 6),
45             (3, 7), (6, 7),
46             (0, 8), (7, 8)]
47    # Compute locations in meters using the block dimension defined as follow
48    # Manhattan average block: 750ft x 264ft -> 228m x 80m
49    # here we use: 114m x 80m city block
50    # src: https://nyti.ms/2GDoRIe "NY Times: Know Your distance"
51    data['locations'] = [(l[0] * 114, l[1] * 80) for l in locations_]
52    data['numlocations_'] = len(data['locations'])
53    data['time_windows'] = \
54          [(0, 0),
55           (75, 85), (75, 85),  # 1, 2
56           (60, 70), (45, 55),  # 3, 4
57           (0, 8), (50, 60),  # 5, 6
58           (0, 10), (10, 20),  # 7, 8
59           (0, 10), (75, 85),  # 9, 10
60           (85, 95), (5, 15),  # 11, 12
61           (15, 25), (10, 20),  # 13, 14
62           (45, 55), (30, 40)]  # 15, 16
63    data['demands'] = \
64          [0,  # depot
65           1, 1,  # 1, 2
66           2, 4,  # 3, 4
67           2, 4,  # 5, 6
68           8, 8,  # 7, 8
69           1, 2,  # 9,10
70           1, 2,  # 11,12
71           4, 4,  # 13, 14
72           8, 8]  # 15, 16
73    data['time_per_demand_unit'] = 5  # 5 minutes/unit
74    data['num_vehicles'] = 4
75    data['breaks'] = [(2, False), (2, False), (2, False), (2, False)]
76    data['vehicle_capacity'] = 15
77    data['vehicle_speed'] = 83  # Travel speed: 5km/h converted in m/min
78    data['depot'] = 0
79    return data
80    # [END data_model]
81
82
83def manhattan_distance(position_1, position_2):
84    """Computes the Manhattan distance between two points."""
85    return (abs(position_1[0] - position_2[0]) +
86            abs(position_1[1] - position_2[1]))
87
88
89def create_distance_evaluator(data):
90    """Creates callback to return distance between points."""
91    distances_ = {}
92    # precompute distance between location to have distance callback in O(1)
93    for from_node in range(data['numlocations_']):
94        distances_[from_node] = {}
95        for to_node in range(data['numlocations_']):
96            if from_node == to_node:
97                distances_[from_node][to_node] = 0
98            else:
99                distances_[from_node][to_node] = (manhattan_distance(
100                    data['locations'][from_node], data['locations'][to_node]))
101
102    def distance_evaluator(manager, from_node, to_node):
103        """Returns the manhattan distance between the two nodes."""
104        return distances_[manager.IndexToNode(from_node)][manager.IndexToNode(
105            to_node)]
106
107    return distance_evaluator
108
109
110def create_demand_evaluator(data):
111    """Creates callback to get demands at each location."""
112    demands_ = data['demands']
113
114    def demand_evaluator(manager, node):
115        """Returns the demand of the current node."""
116        return demands_[manager.IndexToNode(node)]
117
118    return demand_evaluator
119
120
121def add_capacity_constraints(routing, data, demand_evaluator_index):
122    """Adds capacity constraint."""
123    capacity = 'Capacity'
124    routing.AddDimension(
125        demand_evaluator_index,
126        0,  # null capacity slack
127        data['vehicle_capacity'],
128        True,  # start cumul to zero
129        capacity)
130
131
132def create_time_evaluator(data):
133    """Creates callback to get total times between locations."""
134
135    def service_time(data, node):
136        """Gets the service time for the specified location."""
137        return data['demands'][node] * data['time_per_demand_unit']
138
139    def travel_time(data, from_node, to_node):
140        """Gets the travel times between two locations."""
141        if from_node == to_node:
142            travel_time = 0
143        else:
144            travel_time = manhattan_distance(
145                data['locations'][from_node],
146                data['locations'][to_node]) / data['vehicle_speed']
147        return travel_time
148
149    total_time_ = {}
150    # precompute total time to have time callback in O(1)
151    for from_node in range(data['numlocations_']):
152        total_time_[from_node] = {}
153        for to_node in range(data['numlocations_']):
154            if from_node == to_node:
155                total_time_[from_node][to_node] = 0
156            else:
157                total_time_[from_node][to_node] = int(
158                    service_time(data, from_node) +
159                    travel_time(data, from_node, to_node))
160
161    def time_evaluator(manager, from_node, to_node):
162        """Returns the total time between the two nodes."""
163        return total_time_[manager.IndexToNode(from_node)][manager.IndexToNode(
164            to_node)]
165
166    return time_evaluator
167
168
169def add_time_window_constraints(routing, manager, data, time_evaluator_index):
170    """Add Global Span constraint."""
171    time = 'Time'
172    horizon = 120
173    routing.AddDimension(
174        time_evaluator_index,
175        horizon,  # allow waiting time
176        horizon,  # maximum time per vehicle
177        False,  # don't force start cumul to zero
178        time)
179    time_dimension = routing.GetDimensionOrDie(time)
180    # Add time window constraints for each location except depot
181    # and 'copy' the slack var in the solution object (aka Assignment) to print it
182    for location_idx, time_window in enumerate(data['time_windows']):
183        if location_idx == data['depot']:
184            continue
185        index = manager.NodeToIndex(location_idx)
186        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
187        routing.AddToAssignment(time_dimension.SlackVar(index))
188    # Add time window constraints for each vehicle start node
189    # and 'copy' the slack var in the solution object (aka Assignment) to print it
190    for vehicle_id in range(data['num_vehicles']):
191        index = routing.Start(vehicle_id)
192        time_dimension.CumulVar(index).SetRange(data['time_windows'][0][0],
193                                                data['time_windows'][0][1])
194        routing.AddToAssignment(time_dimension.SlackVar(index))
195        # The time window at the end node was impliclty set in the time dimension
196        # definition to be [0, horizon].
197        # Warning: Slack var is not defined for vehicle end nodes and should not
198        # be added to the assignment.
199
200
201# [START solution_printer]
202def print_solution(data, manager, routing, assignment):  # pylint:disable=too-many-locals
203    """Prints assignment on console."""
204    print('Objective: {}'.format(assignment.ObjectiveValue()))
205
206    print('Breaks:')
207    intervals = assignment.IntervalVarContainer()
208    for i in range(intervals.Size()):
209        brk = intervals.Element(i)
210        if brk.PerformedValue() == 1:
211            print('{}: Start({}) Duration({})'.format(brk.Var().Name(),
212                                                      brk.StartValue(),
213                                                      brk.DurationValue()))
214        else:
215            print('{}: Unperformed'.format(brk.Var().Name()))
216
217    total_distance = 0
218    total_load = 0
219    total_time = 0
220    capacity_dimension = routing.GetDimensionOrDie('Capacity')
221    time_dimension = routing.GetDimensionOrDie('Time')
222    for vehicle_id in range(data['num_vehicles']):
223        index = routing.Start(vehicle_id)
224        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
225        distance = 0
226        while not routing.IsEnd(index):
227            load_var = capacity_dimension.CumulVar(index)
228            time_var = time_dimension.CumulVar(index)
229            slack_var = time_dimension.SlackVar(index)
230            plan_output += ' {0} Load({1}) Time({2},{3}) Slack({4},{5}) ->'.format(
231                manager.IndexToNode(index), assignment.Value(load_var),
232                assignment.Min(time_var), assignment.Max(time_var),
233                assignment.Min(slack_var), assignment.Max(slack_var))
234            previous_index = index
235            index = assignment.Value(routing.NextVar(index))
236            distance += routing.GetArcCostForVehicle(previous_index, index,
237                                                     vehicle_id)
238        load_var = capacity_dimension.CumulVar(index)
239        time_var = time_dimension.CumulVar(index)
240        plan_output += ' {0} Load({1}) Time({2},{3})\n'.format(
241            manager.IndexToNode(index), assignment.Value(load_var),
242            assignment.Min(time_var), assignment.Max(time_var))
243        plan_output += 'Distance of the route: {0}m\n'.format(distance)
244        plan_output += 'Load of the route: {}\n'.format(
245            assignment.Value(load_var))
246        plan_output += 'Time of the route: {}\n'.format(
247            assignment.Value(time_var))
248        print(plan_output)
249        total_distance += distance
250        total_load += assignment.Value(load_var)
251        total_time += assignment.Value(time_var)
252    print('Total Distance of all routes: {0}m'.format(total_distance))
253    print('Total Load of all routes: {}'.format(total_load))
254    print('Total Time of all routes: {0}min'.format(total_time))
255    # [END solution_printer]
256
257
258def main():
259    """Entry point of the program."""
260    # Instantiate the data problem.
261    # [START data]
262    data = create_data_model()
263    # [END data]
264
265    # Create the routing index manager
266    manager = pywrapcp.RoutingIndexManager(data['numlocations_'],
267                                           data['num_vehicles'], data['depot'])
268
269    # Create Routing Model
270    routing = pywrapcp.RoutingModel(manager)
271
272    # Define weight of each edge
273    distance_evaluator_index = routing.RegisterTransitCallback(
274        functools.partial(create_distance_evaluator(data), manager))
275    routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator_index)
276
277    # Add Capacity constraint
278    demand_evaluator_index = routing.RegisterUnaryTransitCallback(
279        functools.partial(create_demand_evaluator(data), manager))
280    add_capacity_constraints(routing, data, demand_evaluator_index)
281
282    # Add Time Window constraint
283    time_evaluator_index = routing.RegisterTransitCallback(
284        functools.partial(create_time_evaluator(data), manager))
285    add_time_window_constraints(routing, manager, data, time_evaluator_index)
286
287    # Add breaks
288    time_dimension = routing.GetDimensionOrDie('Time')
289    node_visit_transit = {}
290    for index in range(routing.Size()):
291        node = manager.IndexToNode(index)
292        node_visit_transit[index] = int(data['demands'][node] *
293                                        data['time_per_demand_unit'])
294
295    break_intervals = {}
296    for v in range(data['num_vehicles']):
297        vehicle_break = data['breaks'][v]
298        break_intervals[v] = [
299            routing.solver().FixedDurationIntervalVar(15, 100, vehicle_break[0],
300                                                      vehicle_break[1],
301                                                      f'Break for vehicle {v}')
302        ]
303        time_dimension.SetBreakIntervalsOfVehicle(break_intervals[v], v,
304                                                  node_visit_transit.values())
305
306    # Setting first solution heuristic (cheapest addition).
307    # [START parameters]
308    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
309    search_parameters.first_solution_strategy = (
310        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)  # pylint: disable=no-member
311    # [END parameters]
312
313    # Solve the problem.
314    # [START solve]
315    assignment = routing.SolveWithParameters(search_parameters)
316    # [END solve]
317
318    # Print solution on console.
319    # [START print_solution]
320    if assignment:
321        print_solution(data, manager, routing, assignment)
322    else:
323        print('No solution found!')
324    # [END print_solution]
325
326
327if __name__ == '__main__':
328    main()
329# [END program]
330