Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Different Python version provide different ouput in Vehicle Routing Model #4217

Open
khangthinh-huynh19 opened this issue May 8, 2024 · 3 comments

Comments

@khangthinh-huynh19
Copy link

khangthinh-huynh19 commented May 8, 2024

What version of OR-Tools and what language are you using?
Version: 9.9
Language: Python

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)
Routing Solver

What operating system (Linux, Windows, ...) and version?
Linux

What did you do?

  1. Copying the Capacity Constraint Routing on ORTOOLS
  2. Create a data with 300 points, distance matrix, demand dimension and 300 vehicles with capacity is 10
  3. Run the model in 2 different versions 3.9.5 and 3.11.5
  4. The output of 3.9.5 was feasible
  5. Error happened in version 3.11.5

What did you expect to see
The feasible solution or no solution found in the 2 versions of Python
What did you see instead?
Python 3.11.5 provide an error while Python 3.9.5 found the feasible solution
Output of Python 3.9.5:
image

Output of Python 3.11.5:
image

Anything else we should know about your project / environment
The code of the project:

"""Capacited Vehicles Routing Problem (CVRP)."""

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

import random
import numpy as np
import json

f = open('distance_matrix_300.json')
dist_mat = json.load(f)
print(len(dist_mat['distance matrix'][0]))



def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data["distance_matrix"] = dist_mat['distance matrix']
    data["demands"] = dist_mat['demands']
    data["vehicle_capacities"] = [20 for i in range(300)]
    data["num_vehicles"] = 300
    data["depot"] = 0
    return data


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 = f"Route for vehicle {vehicle_id}:\n"
        route_distance = 0
        route_load = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route_load += data["demands"][node_index]
            plan_output += f" {node_index} Load({route_load}) -> "
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id
            )
        plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n"
        plan_output += f"Distance of the route: {route_distance}m\n"
        plan_output += f"Load of the route: {route_load}\n"
        print(plan_output)
        total_distance += route_distance
        total_load += route_load
    print(f"Total distance of all routes: {total_distance}m")
    print(f"Total load of all routes: {total_load}")


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

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
        len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
    )

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    # Create and register a transit callback.
    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["distance_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add 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",
    )

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    search_parameters.time_limit.FromSeconds(1)

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)


if __name__ == "__main__":
    main()

Distance and Demand parameter json file:
distance_matrix_300.json

**Question
I want to ask that is there any method to solve this problem in ortools with Python 3.11.5 ? If there is any available solution, show me step by step.
Thank you for considering this issue and helping me. Hope a good working week.

@lperron
Copy link
Collaborator

lperron commented May 8, 2024

Can you check with 9.10?

@khangthinh-huynh19
Copy link
Author

Can you check with 9.10?

I am using the ORTOOLS 9.9 by using
pip install ortools

Can you show me how to install the ORTOOLS lib 9.10 ?

Moreover, I heard that the VRP in ORTOOLS now can support the multithread calculation ? Is that true ?

@lperron
Copy link
Collaborator

lperron commented May 8, 2024 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants