153 lines
4.8 KiB
Python
Executable File
153 lines
4.8 KiB
Python
Executable File
#!/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]
|
|
"""Simple Travelling Salesman Problem.
|
|
|
|
A description of the problem can be found here:
|
|
http://en.wikipedia.org/wiki/Travelling_salesperson_problem.
|
|
"""
|
|
|
|
# [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 = {}
|
|
# Locations in block units
|
|
locations = [
|
|
# fmt:off
|
|
(4, 4), # depot
|
|
(2, 0), (8, 0), # locations to visit
|
|
(0, 1), (1, 1),
|
|
(5, 2), (7, 2),
|
|
(3, 3), (6, 3),
|
|
(5, 5), (8, 5),
|
|
(1, 6), (2, 6),
|
|
(3, 7), (6, 7),
|
|
(0, 8), (7, 8)
|
|
# fmt:on
|
|
]
|
|
# Convert locations in meters using a city block dimension of 114m x 80m.
|
|
data["locations"] = [(l[0] * 114, l[1] * 80) for l in locations]
|
|
data["num_vehicles"] = 1
|
|
data["depot"] = 0
|
|
return data
|
|
# [END data_model]
|
|
|
|
|
|
# [START distance_callback]
|
|
def create_distance_callback(data, manager):
|
|
"""Creates callback to return distance between points."""
|
|
distances_ = {}
|
|
index_manager_ = manager
|
|
# precompute distance between location to have distance callback in O(1)
|
|
for from_counter, from_node in enumerate(data["locations"]):
|
|
distances_[from_counter] = {}
|
|
for to_counter, to_node in enumerate(data["locations"]):
|
|
if from_counter == to_counter:
|
|
distances_[from_counter][to_counter] = 0
|
|
else:
|
|
distances_[from_counter][to_counter] = abs(
|
|
from_node[0] - to_node[0]
|
|
) + abs(from_node[1] - to_node[1])
|
|
|
|
def distance_callback(from_index, to_index):
|
|
"""Returns the manhattan distance between the two nodes."""
|
|
# Convert from routing variable Index to distance matrix NodeIndex.
|
|
from_node = index_manager_.IndexToNode(from_index)
|
|
to_node = index_manager_.IndexToNode(to_index)
|
|
return distances_[from_node][to_node]
|
|
|
|
return distance_callback
|
|
# [END distance_callback]
|
|
|
|
|
|
# [START solution_printer]
|
|
def print_solution(manager, routing, assignment):
|
|
"""Prints assignment on console."""
|
|
print(f"Objective: {assignment.ObjectiveValue()}")
|
|
index = routing.Start(0)
|
|
plan_output = "Route for vehicle 0:\n"
|
|
route_distance = 0
|
|
while not routing.IsEnd(index):
|
|
plan_output += f" {manager.IndexToNode(index)} ->"
|
|
previous_index = index
|
|
index = assignment.Value(routing.NextVar(index))
|
|
route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
|
|
plan_output += f" {manager.IndexToNode(index)}\n"
|
|
plan_output += f"Distance of the route: {route_distance}m\n"
|
|
print(plan_output)
|
|
# [END solution_printer]
|
|
|
|
|
|
def main():
|
|
"""Entry point of the program."""
|
|
# 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["locations"]), 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]
|
|
distance_callback = create_distance_callback(data, manager)
|
|
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
|
|
# [END transit_callback]
|
|
|
|
# Define cost of each arc.
|
|
# [START arc_cost]
|
|
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
|
|
# [END arc_cost]
|
|
|
|
# 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]
|
|
assignment = routing.SolveWithParameters(search_parameters)
|
|
# [END solve]
|
|
|
|
# Print solution on console.
|
|
# [START print_solution]
|
|
if assignment:
|
|
print_solution(manager, routing, assignment)
|
|
# [END print_solution]
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|
|
# [END program]
|