Skip to content

Instantly share code, notes, and snippets.

@jmarca
Created October 12, 2022 07:43
Show Gist options
  • Save jmarca/d5f0cd81f3cac30b8cdae03f969ae1d2 to your computer and use it in GitHub Desktop.
Save jmarca/d5f0cd81f3cac30b8cdae03f969ae1d2 to your computer and use it in GitHub Desktop.
Bad optimum value with path cheapest arc strategy
#!/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]
@bb-vh-suraj
Copy link

Hi @jmarca , thanks for the lookout and confirming the problem. So,what should i do now, sir?
Will or tools mods log it as an issue? or Should i just change my first strategy and move on?

@jmarca
Copy link
Author

jmarca commented Oct 12, 2022 via email

@bb-vh-suraj
Copy link

Got it. Thanks for the advice.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment