jmarca · October 12, 2022 07:43 · bb-vh-suraj · Oct 12, 2022 · jmarca · Oct 12, 2022
diff --git a/vrp_tweak.py b/vrp_tweak.py
 #!/usr/bin/env python3
 # Copyright 2010-2022 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.

 # based on the sample vrp program in the OR Tools library, but hacked
 # by James Marca to mimic the Java program reported on the forum post

 # [START program]
 """Capacited Vehicles Routing Problem (CVRP)."""

 # [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["distance_matrix"] = []
    # [START demands_capacities]
    data["penalties"] = [1, 1, 100, 5, 5]
    data["demands"] = [0, 0, 50, 30, 30]
    data["vehicle_capacities"] = [75]
    # [END demands_capacities]
    data["num_vehicles"] = 1
    data["startdepot"] = [0]
    data["enddepot"] = [1]
    return data
    # [END data_model]


 # [START solution_printer]
 def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    total_distance = 0
    total_load = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = "Route for vehicle {}:\n".format(vehicle_id)
        route_distance = 0
        route_load = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route_load += data["demands"][node_index]
            plan_output += " {0} Load({1}) -> ".format(node_index, route_load)
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id
            )
        plan_output += " {0} Load({1})\n".format(manager.IndexToNode(index), route_load)
        plan_output += "Distance of the route: {}m\n".format(route_distance)
        plan_output += "Load of the route: {}\n".format(route_load)
        print(plan_output)
        total_distance += route_distance
        total_load += route_load
    print("Total distance of all routes: {}m".format(total_distance))
    print("Total load of all routes: {}".format(total_load))
    # [END solution_printer]


 def main():
    """Solve the CVRP problem."""
    # Instantiate the data problem.
    # [START data]
    data = create_data_model()
    # [END data]

    # Create the routing index manager.
    # [START index_manager]
    manager = pywrapcp.RoutingIndexManager(
        5, data["num_vehicles"], data["startdepot"], data["enddepot"]
    )
    # [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 distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        return 0

    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]

    # Add Capacity constraint.
    # [START capacity_constraint]
    def demand_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data["demands"][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        data["vehicle_capacities"],  # vehicle maximum capacities
        True,  # start cumul to zero
        "Capacity",
    )
    # [END capacity_constraint]

    for node in range(2, len(data["demands"])):
        routing.AddDisjunction([manager.NodeToIndex(node)], data["penalties"][node])

    # Setting first solution heuristic.
    # [START parameters]
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.log_search = True
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
        # routing_enums_pb2.FirstSolutionStrategy.PATH_MOST_CONSTRAINED_ARC
        # routing_enums_pb2.FirstSolutionStrategy.EVALUATOR_STRATEGY
        # routing_enums_pb2.FirstSolutionStrategy.SAVINGS
        # routing_enums_pb2.FirstSolutionStrategy.SWEEP
        # routing_enums_pb2.FirstSolutionStrategy.CHRISTOFIDES
        # routing_enums_pb2.FirstSolutionStrategy.ALL_UNPERFORMED
        # routing_enums_pb2.FirstSolutionStrategy.BEST_INSERTION
        # routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION
        # routing_enums_pb2.FirstSolutionStrategy.SEQUENTIAL_CHEAPEST_INSERTION
        # routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_INSERTION
        # routing_enums_pb2.FirstSolutionStrategy.GLOBAL_CHEAPEST_ARC
        # routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_ARC
        # routing_enums_pb2.FirstSolutionStrategy.FIRST_UNBOUND_MIN_VALUE
    )
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    search_parameters.time_limit.FromSeconds(10)
    # [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)
    else:
        print("no solution")
    # [END print_solution]


 if __name__ == "__main__":
    main()
 # [END program]
	#!/usr/bin/env python3
	# Copyright 2010-2022 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.

	# based on the sample vrp program in the OR Tools library, but hacked
	# by James Marca to mimic the Java program reported on the forum post

	# [START program]
	"""Capacited Vehicles Routing Problem (CVRP)."""

	# [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["distance_matrix"] = []
	# [START demands_capacities]
	data["penalties"] = [1, 1, 100, 5, 5]
	data["demands"] = [0, 0, 50, 30, 30]
	data["vehicle_capacities"] = [75]
	# [END demands_capacities]
	data["num_vehicles"] = 1
	data["startdepot"] = [0]
	data["enddepot"] = [1]
	return data
	# [END data_model]


	# [START solution_printer]
	def print_solution(data, manager, routing, solution):
	"""Prints solution on console."""
	print(f"Objective: {solution.ObjectiveValue()}")
	total_distance = 0
	total_load = 0
	for vehicle_id in range(data["num_vehicles"]):
	index = routing.Start(vehicle_id)
	plan_output = "Route for vehicle {}:\n".format(vehicle_id)
	route_distance = 0
	route_load = 0
	while not routing.IsEnd(index):
	node_index = manager.IndexToNode(index)
	route_load += data["demands"][node_index]
	plan_output += " {0} Load({1}) -> ".format(node_index, route_load)
	previous_index = index
	index = solution.Value(routing.NextVar(index))
	route_distance += routing.GetArcCostForVehicle(
	previous_index, index, vehicle_id
	)
	plan_output += " {0} Load({1})\n".format(manager.IndexToNode(index), route_load)
	plan_output += "Distance of the route: {}m\n".format(route_distance)
	plan_output += "Load of the route: {}\n".format(route_load)
	print(plan_output)
	total_distance += route_distance
	total_load += route_load
	print("Total distance of all routes: {}m".format(total_distance))
	print("Total load of all routes: {}".format(total_load))
	# [END solution_printer]


	def main():
	"""Solve the CVRP problem."""
	# Instantiate the data problem.
	# [START data]
	data = create_data_model()
	# [END data]

	# Create the routing index manager.
	# [START index_manager]
	manager = pywrapcp.RoutingIndexManager(
	5, data["num_vehicles"], data["startdepot"], data["enddepot"]
	)
	# [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 distance_callback(from_index, to_index):
	"""Returns the distance between the two nodes."""
	return 0

	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]

	# Add Capacity constraint.
	# [START capacity_constraint]
	def demand_callback(from_index):
	"""Returns the demand of the node."""
	# Convert from routing variable Index to demands NodeIndex.
	from_node = manager.IndexToNode(from_index)
	return data["demands"][from_node]

	demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
	routing.AddDimensionWithVehicleCapacity(
	demand_callback_index,
	0, # null capacity slack
	data["vehicle_capacities"], # vehicle maximum capacities
	True, # start cumul to zero
	"Capacity",
	)
	# [END capacity_constraint]

	for node in range(2, len(data["demands"])):
	routing.AddDisjunction([manager.NodeToIndex(node)], data["penalties"][node])

	# Setting first solution heuristic.
	# [START parameters]
	search_parameters = pywrapcp.DefaultRoutingSearchParameters()
	search_parameters.log_search = True
	search_parameters.first_solution_strategy = (
	routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
	# routing_enums_pb2.FirstSolutionStrategy.PATH_MOST_CONSTRAINED_ARC
	# routing_enums_pb2.FirstSolutionStrategy.EVALUATOR_STRATEGY
	# routing_enums_pb2.FirstSolutionStrategy.SAVINGS
	# routing_enums_pb2.FirstSolutionStrategy.SWEEP
	# routing_enums_pb2.FirstSolutionStrategy.CHRISTOFIDES
	# routing_enums_pb2.FirstSolutionStrategy.ALL_UNPERFORMED
	# routing_enums_pb2.FirstSolutionStrategy.BEST_INSERTION
	# routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION
	# routing_enums_pb2.FirstSolutionStrategy.SEQUENTIAL_CHEAPEST_INSERTION
	# routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_INSERTION
	# routing_enums_pb2.FirstSolutionStrategy.GLOBAL_CHEAPEST_ARC
	# routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_ARC
	# routing_enums_pb2.FirstSolutionStrategy.FIRST_UNBOUND_MIN_VALUE
	)
	search_parameters.local_search_metaheuristic = (
	routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
	)
	search_parameters.time_limit.FromSeconds(10)
	# [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)
	else:
	print("no solution")
	# [END print_solution]


	if __name__ == "__main__":
	main()
	# [END program]