#!/usr/bin/env python3 # Copyright 2010-2025 Google LLC # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # http://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. # [START program] """Vehicles Routing Problem (VRP) with Resource Constraints.""" # [START import] from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp # [END import] # [START data_model] def create_data_model(): """Stores the data for the problem.""" data = {} data["time_matrix"] = [ [0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7], [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14], [9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9], [8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16], [7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14], [3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8], [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5], [2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10], [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6], [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5], [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4], [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10], [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8], [4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6], [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2], [9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9], [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0], ] data["time_windows"] = [ (0, 5), # depot (7, 12), # 1 (10, 15), # 2 (5, 14), # 3 (5, 13), # 4 (0, 5), # 5 (5, 10), # 6 (0, 10), # 7 (5, 10), # 8 (0, 5), # 9 (10, 16), # 10 (10, 15), # 11 (0, 5), # 12 (5, 10), # 13 (7, 12), # 14 (10, 15), # 15 (5, 15), # 16 ] data["num_vehicles"] = 4 # [START resources_data] data["vehicle_load_time"] = 5 data["vehicle_unload_time"] = 5 data["depot_capacity"] = 2 # [END resources_data] data["depot"] = 0 return data # [END data_model] # [START solution_printer] def print_solution(data, manager, routing, solution): """Prints solution on console.""" print(f"Objective: {solution.ObjectiveValue()}") time_dimension = routing.GetDimensionOrDie("Time") total_time = 0 for vehicle_id in range(data["num_vehicles"]): if not routing.IsVehicleUsed(solution, vehicle_id): continue index = routing.Start(vehicle_id) plan_output = f"Route for vehicle {vehicle_id}:\n" while not routing.IsEnd(index): time_var = time_dimension.CumulVar(index) plan_output += ( f"{manager.IndexToNode(index)}" f" Time({solution.Min(time_var)}, {solution.Max(time_var)})" " -> " ) index = solution.Value(routing.NextVar(index)) time_var = time_dimension.CumulVar(index) plan_output += ( f"{manager.IndexToNode(index)}" f" Time({solution.Min(time_var)},{solution.Max(time_var)})\n" ) plan_output += f"Time of the route: {solution.Min(time_var)}min\n" print(plan_output) total_time += solution.Min(time_var) print(f"Total time of all routes: {total_time}min") # [END solution_printer] def main(): """Solve the VRP with time windows.""" # Instantiate the data problem. # [START data] data = create_data_model() # [END data] # Create the routing index manager. # [START index_manager] manager = pywrapcp.RoutingIndexManager( len(data["time_matrix"]), data["num_vehicles"], data["depot"] ) # [END index_manager] # Create Routing Model. # [START routing_model] routing = pywrapcp.RoutingModel(manager) # [END routing_model] # Create and register a transit callback. # [START transit_callback] def time_callback(from_index, to_index): """Returns the travel time between the two nodes.""" # Convert from routing variable Index to time matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data["time_matrix"][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(time_callback) # [END transit_callback] # Define cost of each arc. # [START arc_cost] routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # [END arc_cost] # Add Time Windows constraint. # [START time_windows_constraint] time = "Time" routing.AddDimension( transit_callback_index, 60, # allow waiting time 60, # maximum time per vehicle False, # Don't force start cumul to zero. time, ) time_dimension = routing.GetDimensionOrDie(time) # Add time window constraints for each location except depot. for location_idx, time_window in enumerate(data["time_windows"]): if location_idx == 0: continue index = manager.NodeToIndex(location_idx) time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1]) # Add time window constraints for each vehicle start node. for vehicle_id in range(data["num_vehicles"]): index = routing.Start(vehicle_id) time_dimension.CumulVar(index).SetRange( data["time_windows"][0][0], data["time_windows"][0][1] ) # [END time_windows_constraint] # Add resource constraints at the depot. # [START depot_load_time] solver = routing.solver() intervals = [] for i in range(data["num_vehicles"]): # Add time windows at start of routes intervals.append( solver.FixedDurationIntervalVar( time_dimension.CumulVar(routing.Start(i)), data["vehicle_load_time"], "depot_interval", ) ) # Add time windows at end of routes. intervals.append( solver.FixedDurationIntervalVar( time_dimension.CumulVar(routing.End(i)), data["vehicle_unload_time"], "depot_interval", ) ) # [END depot_load_time] # [START depot_capacity] depot_usage = [1 for _ in range(len(intervals))] solver.Add( solver.Cumulative(intervals, depot_usage, data["depot_capacity"], "depot") ) # [END depot_capacity] # Instantiate route start and end times to produce feasible times. # [START depot_start_end_times] for i in range(data["num_vehicles"]): routing.AddVariableMinimizedByFinalizer( time_dimension.CumulVar(routing.Start(i)) ) routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i))) # [END depot_start_end_times] # Setting first solution heuristic. # [START parameters] search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC ) # [END parameters] # Solve the problem. # [START solve] solution = routing.SolveWithParameters(search_parameters) # [END solve] # Print solution on console. # [START print_solution] if solution: print_solution(data, manager, routing, solution) # [END print_solution] else: print("No solution found !") if __name__ == "__main__": main() # [END program]