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?