Different Python version provide different ouput in Vehicle Routing Model

[khangthinh-huynh19]

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:

Output of Python 3.11.5:

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]

Can you check with 9.10?

[khangthinh-huynh19]

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]

    pip install --upgrade ortools

And no for parallelism.

--Laurent