Bad optimum value with path cheapest arc strategy

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]

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?

On Wed, Oct 12, 2022 at 01:04:40AM -0700, bb-vh-suraj wrote: 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?

Change your strategy and move on is my advice.

…

-- Reply to this email directly or view it on GitHub: https://gist.github.com/d5f0cd81f3cac30b8cdae03f969ae1d2#gistcomment-4332533 You are receiving this because you were mentioned. Message ID: ***@***.***>

-- James E. Marca Activimetrics LLC

Got it. Thanks for the advice.