For coordinates in (0,1) range, why OR-Tools returns zero as the total tour length?

Viewed 55

I am trying to solve multiple VRP problem by OR-Tools. The 100 coordinates are generated randomly in (0,1) range and for each VRP instance I randomly sample 20 coordinates from 100. I have set number of vehicles to 3. The problem here is that the optimal tour length for all of the instances are zero and the optimal tour is 0 -> 20 -> 19 -> 18 -> 17 -> ... -> 3 -> 2 -> 1 -> 0 for the third vehicle.

My code is:

from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
from scipy.spatial import distance_matrix

import numpy as np
import random
import pandas as pd

nodes = 100

coords = np.round(np.c_[np.random.uniform(0,1,nodes), np.random.uniform(0,1,nodes)],decimals=3)

list_node = list(range(nodes))

nodes_to_shuffle = list(range(nodes))


num_instance = 10

dataset = pd.DataFrame()

for i in range(num_instance):
    
    data = {}
    
    random.shuffle(nodes_to_shuffle)
    customers_id = random.sample(nodes_to_shuffle, 20)
    
    data_vector = np.matrix(np.in1d(list_node,customers_id).astype('int'))
    
    customers_coord = np.array([coords[k] for k in customers_id])
    
    X = np.matrix(customers_coord[:,0])
    Y = np.matrix(customers_coord[:,1])
    
    data['X_coordinate'] = customers_coord[:,0]
    data['Y_coordinate'] = customers_coord[:,1]
    
    
    depot = np.matrix([0.5,0.5])
    customers_coord = np.r_[depot,customers_coord]
    
    
    data['distance_matrix'] = distance_matrix(customers_coord, customers_coord, p=2)
    data['num_vehicles'] = 3
    data['depot'] = 0
    
    
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                           data['num_vehicles'], data['depot'])
    
    routing = pywrapcp.RoutingModel(manager)
    
    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)
    
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    
    dimension_name = 'Distance'
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        1,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)
    
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    
    solution = routing.SolveWithParameters(search_parameters)
    
    if solution:
        data['objective_value'] = solution.ObjectiveValue()
        max_route_distance = 0
        total_distance = 0
        route = {}
        for vehicle_id in range(data['num_vehicles']):
            index = routing.Start(vehicle_id)
            plan_output = []
            route_distance = 0
            while not routing.IsEnd(index):
                plan_output.append(manager.IndexToNode(index))
                previous_index = index
                index = solution.Value(routing.NextVar(index))
                route_distance += routing.GetArcCostForVehicle(
                    previous_index, index, vehicle_id)
            plan_output.append(manager.IndexToNode(index))
            data[f"vehicle_{vehicle_id}_tour"] = plan_output
            data[f"vehicle_{vehicle_id}_tour_length"] = route_distance
            max_route_distance = max(route_distance, max_route_distance)
            total_distance += route_distance
        data["Max_tour_length"] = max_route_distance
        data["Total_tour_length"] = total_distance

Could you explain why I am getting this results?

1 Answers

The solver uses integers. All floating point values are silently rounded by python.

You should scale all distances by some number (100?) and cast to integer.

Related