Closed abhiagra94 closed 5 years ago
does your len(start_locations) == len(end_locations) == num_vehicles
?
Which version of ortools are you using ?
Yes I am giving start_locations=[0,0,0] end location=[68,68,68] and we are using 3 vehicle. we are using version 6.10.6025
Hey found the mistake. Now we are not getting any error but when we are running the script jupyter it's showing The kernel appears to have died. It will restart automatically. and not giving any output kindly help
and how many locations do you have in num_locations ? note: should be >= 69
yes there are 69 location.
This is the code i am using:
import math
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
from numpy import genfromtxt
import pandas as pd
def create_distance_callback(dist_matrix):
def distance_callback(from_node, to_node):
return int(dist_matrix[from_node][to_node])
for to_node in range(num_locations):
if from_node == depot or to_node == depot:
self.matrix[from_node][to_node] = 0
else:
dist_matrix[from_node][to_node] = (
manhattan_distance(locations[from_node], locations[to_node]))
return distance_callback
dist_matrix = genfromtxt('DM100_x.csv', delimiter=',')
class CreateDemandCallback(object):
"""Create callback to get demands at each node."""
def __init__(self, demands):
self.matrix = demands
def Demand(self, from_node, to_node):
return self.matrix[from_node]
class CreateServiceTimeCallback(object):
"""Create callback to get time windows at each node."""
def __init__(self, demands, time_per_demand_unit):
self.matrix = demands
self.time_per_demand_unit = time_per_demand_unit
def ServiceTime(self, from_node, to_node):
return self.matrix[from_node] * self.time_per_demand_unit
class CreateTotalTimeCallback(object):
def __init__(self, service_time_callback, dist_callback, speed):
self.service_time_callback = service_time_callback
self.dist_callback = dist_callback
self.speed = speed
def TotalTime(self, from_node, to_node):
return self.service_time_callback(from_node, to_node) + self.dist_callback(from_node, to_node) / self.speed
def DisplayPlan(routing, assignment):
dropped = ''
for order in range(1, routing.nodes()):
if assignment.Value(routing.NextVar(order)) == order:
if (dropped.empty()):
dropped += " %d", order
else: dropped += ", %d", order
if not dropped.empty():
plan_output += "Dropped orders:" + dropped + "\n"
return plan_output
def main():
data = create_data_array()
dist_matrix = data[0]
demands = data[1]
start_times = data[2]
end_times=data[3]
num_locations = len(dist_matrix)
depot = 0
num_vehicles = 3
if num_locations > 0:
start_locations = [0,0,0]
end_locations = [68, 68, 68]
routing = pywrapcp.RoutingModel(num_locations, num_vehicles, start_locations, end_locations)
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
dist_callback = create_distance_callback(dist_matrix)
routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
demands_at_locations = CreateDemandCallback(demands)
demands_callback = demands_at_locations.Demand
vehicle_capacity = 9000;
null_capacity_slack = 0;
fix_start_cumul_to_zero = False
capacity = "Capacity"
routing.AddDimension(demands_callback, null_capacity_slack, vehicle_capacity,
fix_start_cumul_to_zero, capacity)
capacity_dimension = routing.GetDimensionOrDie(capacity)
for node_index in [1, 2, 3, 4, 5]:
index = routing.NodeToIndex(node_index)
capacity_dimension.SlackVar(index).SetRange(0, vehicle_capacity)
routing.AddDisjunction([node_index], 0)
time_per_demand_unit = 0.01
horizon = 750
time = "Time"
speed = 40
service_times = CreateServiceTimeCallback(demands, time_per_demand_unit)
service_time_callback = service_times.ServiceTime
total_times = CreateTotalTimeCallback(service_time_callback, dist_callback, speed)
total_time_callback = total_times.TotalTime
fix_start_cumul_to_zero = False
routing.AddDimension(total_time_callback,
horizon,
horizon,
fix_start_cumul_to_zero,
time)
time_dimension = routing.GetDimensionOrDie("Time")
for order in range(1, num_locations):
start = start_times[order]
end=end_times[order]
x=start.item()
y=end.item()
time_dimension.CumulVar(routing.NodeToIndex(order)).SetRange(x, y)
vehicle_start_time = [120,300,240]
solver = routing.solver()
intervals = []
for i in range(num_vehicles):
intervals.append(solver.FixedDurationIntervalVar(routing.CumulVar(routing.Start(i), time),
vehicle_start_time[i],
"depot_interval"))
depot_capacity = 1;
depot_usage = [1 for i in range(num_vehicles * 1)]
solver.AddConstraint(
solver.Cumulative(intervals, depot_usage, depot_capacity, "depot"))
for i in range(num_vehicles):
routing.AddVariableMinimizedByFinalizer(routing.CumulVar(routing.End(i), time))
routing.AddVariableMinimizedByFinalizer(routing.CumulVar(routing.Start(i), time))
assignment = routing.SolveWithParameters(search_parameters)
if assignment:
print("Total distance of all routes: " + str(assignment.ObjectiveValue()) + "\n")
total_distance = 0
total_load = 0
total_time = 0
penalty = 100000
for i in range(1, num_locations):
routing.AddDisjunction([routing.NodeToIndex(i)], penalty)
capacity_dimension = routing.GetDimensionOrDie(capacity);
time_dimension = routing.GetDimensionOrDie(time);
for vehicle_nbr in range(num_vehicles):
index = routing.Start(int(vehicle_nbr))
plan_output = 'Route {0}:'.format(vehicle_nbr)
while not routing.IsEnd(index):
node_index = routing.IndexToNode(index)
load_var = capacity_dimension.CumulVar(index)
time_var = time_dimension.CumulVar(index)
plan_output += \
" {node_index} Load({load}) Time({tmin}, {tmax}) -> ".format(
node_index=node_index,
load=assignment.Value(load_var),
tmin=str(assignment.Min(time_var)),
tmax=str(assignment.Max(time_var)))
index = assignment.Value(routing.NextVar(index))
node_index = routing.IndexToNode(index)
load_var = capacity_dimension.CumulVar(index)
time_var = time_dimension.CumulVar(index)
plan_output += \
" {node_index} Load({load}) Time({tmin}, {tmax})".format(
node_index=node_index,
load=assignment.Value(load_var),
tmin=str(assignment.Min(time_var)),
tmax=str(assignment.Max(time_var)))
print("\n")
plan_output += 'Load of the route: {}\n'.format(assignment.Value(load_var))
plan_output += 'Time of the route: {}\n'.format(assignment.Value(time_var))
total_load += assignment.Value(load_var)
total_time += assignment.Value(time_var)
print(plan_output)
print('Total Load of all routes: {}'.format(total_load))
print('Total Time of all routes: {}min'.format(total_time))
else:
print('No solution found.')
else:
print('Specify an instance greater than 0.')
def create_data_array():
tv=pd.read_csv('constraints3_x.csv')
demands = tv.Demand
start_times=tv.lower_limit_time_Summary
end_times=tv.upper_limit_time_Summary
data = [dist_matrix, demands, start_times,end_times]
return data
if __name__ == '__main__':
main()
when I am giving start_locations=[0,0,0] end location=[0,0,0] it's running and giving the output
@Mizux Hey mizux can you please help me with this if possible
code look "good", maybe try to reduce the range of your disjunction loop
for i in range(1, num_locations-1): # don't take into account the end node 68
routing.AddDisjunction([routing.NodeToIndex(i)], penalty)
Showing the same error. The kernel appears to have died. It will restart automatically. Do I need to change something here as well? capacity_dimension = routing.GetDimensionOrDie(capacity) for node_index in [1, 2, 3, 4, 5]: index = routing.NodeToIndex(node_index) capacity_dimension.SlackVar(index).SetRange(0, vehicle_capacity) routing.AddDisjunction([node_index], 0)
try to run it in a real python interpreter locally, to be sure jupyter don't kill it too soon. Do you have a stack trace ? is it possible to reproduce it without a minimal, standalone, example code ?
here a simple working example with last node as end using v6.10
"""Simple Vehicles Routing Problem."""
# [START import]
from __future__ import print_function
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'] = [
[
0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354,
468, 776, 662
],
[
548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674,
1016, 868, 1210
],
[
776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164,
1130, 788, 1552, 754
],
[
696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822,
1164, 560, 1358
],
[
582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708,
1050, 674, 1244
],
[
274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628,
514, 1050, 708
],
[
502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856,
514, 1278, 480
],
[
194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320,
662, 742, 856
],
[
308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662,
320, 1084, 514
],
[
194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388,
274, 810, 468
],
[
536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764,
730, 388, 1152, 354
],
[
502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114,
308, 650, 274, 844
],
[
388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194,
536, 388, 730
],
[
354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0,
342, 422, 536
],
[
468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536,
342, 0, 764, 194
],
[
776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274,
388, 422, 764, 0, 798
],
[
662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730,
536, 194, 798, 0
],
]
data['num_vehicles'] = 4
# [START starts_ends]
data['starts'] = [0, 0, 0, 0]
data['ends'] = [16, 16, 16, 16]
# [END starts_ends]
return data
# [END data_model]
# [START solution_printer]
def print_solution(data, routing, assignment):
"""Prints assignment on console."""
print('Objective: {}'.format(assignment.ObjectiveValue()))
total_distance = 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
while not routing.IsEnd(index):
plan_output += ' {} ->'.format(routing.IndexToNode(index))
previous_index = index
index = assignment.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id)
plan_output += ' {}\n'.format(routing.IndexToNode(index))
plan_output += 'Distance of the route: {}m\n'.format(route_distance)
print(plan_output)
total_distance += route_distance
print('Total distance of all routes: {}m'.format(total_distance))
# [END solution_printer]
def main():
"""Entry point of the program."""
# Instantiate the data problem.
# [START data]
data = create_data_model()
# [END data]
# Create Routing Model.
# [START routing_model]
routing = pywrapcp.RoutingModel(
len(data['distance_matrix']), data['num_vehicles'], data['starts'],
data['ends'])
# [END routing_model]
# Create and register a transit callback.
# [START distance_callback]
def distance_callback(from_node, to_node):
"""Returns the distance between the two nodes."""
return data['distance_matrix'][from_node][to_node]
# [END distance_callback]
# Define cost of each arc.
# [START arc_cost]
routing.SetArcCostEvaluatorOfAllVehicles(distance_callback)
# [END arc_cost]
# Add Distance constraint.
# [START distance_constraint]
dimension_name = 'Distance'
routing.AddDimension(
distance_callback,
0, # no slack
2500, # vehicle maximum travel distance
True, # start cumul to zero
dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)
## [END distance_constraint]
# Setting first solution heuristic.
# [START parameters]
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # pylint: disable=no-member
# [END parameters]
# Solve the problem.
# [START solve]
assignment = routing.SolveWithParameters(search_parameters)
# [END solve]
# Print solution on console.
# [START print_solution]
if assignment:
print_solution(data, routing, assignment)
# [END print_solution]
if __name__ == '__main__':
main()
# [END program]
$ python3 vrp_starts_ends.py
Objective: 212316
Route for vehicle 0:
0 -> 7 -> 4 -> 3 -> 5 -> 9 -> 14 -> 16
Distance of the route: 2054m
Route for vehicle 1:
0 -> 1 -> 13 -> 16
Distance of the route: 1758m
Route for vehicle 2:
0 -> 8 -> 6 -> 2 -> 10 -> 16
Distance of the route: 1530m
Route for vehicle 3:
0 -> 12 -> 11 -> 15 -> 16
Distance of the route: 1574m
Total distance of all routes: 6916m
We found the reason of error this is because
for order in range(1, num_locations):
start = start_times[order]
end=end_times[order]
x=start.item()
y=end.item()
time_dimension.CumulVar(routing.NodeToIndex(order)).SetRange(x, y)
when we are giving num_location-1
we are not facing the issue of kernel crashing. Can you please elaborate on why this is happening?
Is it a crash or a timeout ? Where does it crash ? do you have log ? stack trace ?
I suspect num_location-1
index being your end node.
What is:
time_dimension
(i.e. max value allowed) ?start_time[num_location-1]
?end_times[num_location-1]
?Previously in this code https://github.com/google/or-tools/issues/1078#issuecomment-466001072 we were getting error of The kernel appears to have died. It will restart automatically. but in this part of code:
_for order in range(1, num_locations): start = start_times[order] end=end_times[order] x=start.item() y=end.item() timedimension.CumulVar(routing.NodeToIndex(order)).SetRange(x, y)
when we are using num_location-1, we are not facing any issue. We have taken Horizon=750 start_time[num_location-1]=0 end_times[num_location-1]=750 There are total 69 locations, but when we are giving time constraint on end location or dumping point(0,750), we are facing the issue of Kernal died. Can you please elaborate?
@abhiagra94 I am facing the same issue of kernel getting dead while setting the initial node. I am using google OR tools and trying to work on a capacitated vehicle routing problem. Everything works fine but when I set the initial node to the index number of my dataset (or any random index), it shows 'kernel is dead'. Have you resolved this issue of kernel crashing, if yes then how?? please help!
Most likely an exception and a crash.
Le lun. 22 mars 2021 à 06:51, Darshika Verma @.***> a écrit :
@abhiagra94 https://github.com/abhiagra94 I am facing the same issue of kernel getting dead while setting the initial node. I am using google OR tools and trying to work on a capacitated vehicle routing problem. Everything works fine but when I set the initial node to the index number of my dataset (or any random index), it shows 'kernel is dead'. Have you resolved this issue of kernel crashing, if yes then how?? please help!
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1078#issuecomment-803781119, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3KVL6X36ENKDQLH5YLTE3LFDANCNFSM4GY4S66A .
Below I am sharing my code. Please let me know what the reason of kernel being dead could be
dist = DistanceMetric.get_metric('haversine')
def create_data_model_cap_con(df_user,no_fos):
"""Stores the data for the problem."""
data = {}
data['distance_matrix'] = dist.pairwise(df_user [['lat','lon']].to_numpy())*6373
#a = dist.pairwise(df_user_org[['lat','lon']])
#a[:,0] = 0
#a[0,:] = 0
#data['depot'] = 0
data['starts'] = [2,6,7,8]
data['ends'] = [3,7,8,9]
#A = dist.pairwise(df_user [['lat','lon']].to_numpy())*6373
#x = np.c_[np.zeros(len(A[0])),A ]
#y = np.vstack([np.zeros(len(x[0])),x])
#data['distance_matrix']=y
data['num_vehicles'] = no_fos
#data['starts'] = data['num_vehicles']
#data['ends'] = data['starts']
#len(data['starts']) == len(data['ends'])
#len(data['num_vehicles']) == len(data['starts'])
#data['starts'] = [2]*11212
#data['ends'] = [3]*11212
data['demands'] = df_user["no_cases"].to_list()
data['vehicle_capacities'] = [75]*no_fos
return data
def print_solution_cap_con(data, manager, routing, assignment):
"""Prints assignment on console."""
# Display dropped nodes.
dropped_nodes = 'Dropped nodes:'
for node in range(routing.Size()):
if routing.IsStart(node) or routing.IsEnd(node):
continue
if assignment.Value(routing.NextVar(node)) == node:
dropped_nodes += ' {}'.format(manager.IndexToNode(node))
print(dropped_nodes)
# Display routes
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 = assignment.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))
def distance_cap_con(x,y,data):
dis = data['distance_matrix'][x][y]
return dis
def get_routes_cap_con(solution, routing, manager,df_user,data):
"""Get vehicle routes from a solution and store them in an array."""
# Get vehicle routes and store them in a two dimensional array whose
# i,j entry is the jth location visited by vehicle i along its route.
routes = []
#routes_dist = []
for route_nbr in range(routing.vehicles()):
index = routing.Start(route_nbr)
route = [manager.IndexToNode(index)]
while not routing.IsEnd(index):
index = solution.Value(routing.NextVar(index))
route.append(manager.IndexToNode(index))
routes.append(route)
#routes = get_routes(solution, routing, manager)
routes_t = pd.DataFrame(routes).T
col_to_iter = routes_t.columns
routes_t['route_info'] = routes_t.index
routes_t = pd.melt(routes_t, id_vars=['route_info'], value_vars=col_to_iter)
routes_t = routes_t.drop_duplicates(subset='value', keep="first")
df_user['value'] = df_user.index
df_user_out = pd.merge(df_user, routes_t, on="value")
df_user_out = df_user_out.sort_values(by=['variable','route_info'])
df_user_out['route_lag'] = df_user_out.groupby('variable')['value'].shift(-1).fillna(0)
df_user_out['route_lag'] = df_user_out['route_lag'].astype(np.int64)
df_user_out['route_info'] = df_user_out['route_info'].astype(np.int64)
df_user_out['dist'] = df_user_out.apply(lambda row: distance_cap_con(row['route_lag'], row['value'],data), axis=1)
return df_user_out
def get_sol_cap_con(sub_dist_fil,fos_cnt,state_fil):
df_user_org_sub = df_user_org[(df_user_org.sub_district == sub_dist_fil) & (df_user_org.State == state_fil) ]
df_user_org_sub.reset_index( inplace=True,drop=True)
print(sub_dist_fil," no fos",fos_cnt)
fos_cnt=fos_cnt
data = create_data_model_cap_con(df_user_org_sub,fos_cnt)
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'],data['starts'],data['ends'])
# 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)
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')
# Allow to drop nodes.
penalty = 1000
for node in range(1, len(data['distance_matrix'])):
routing.AddDisjunction([manager.NodeToIndex(node)], penalty)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.time_limit.seconds = 30
search_parameters.solution_limit = 100
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(30)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
out_df = get_routes_cap_con(solution, routing, manager,df_user_org_sub,data)
# Print solution on console.
#if solution:
# print_solution_cap_con(data, manager, routing, solution)
return out_df
By using data['starts'] and data['ends'] , the error of kernel being dead is arising (and I do not want to use data['depot']= 0)
Help
Hello, I want to add a new end point for all location also I am adding time window, demand, and different start time constraint in the code. for doing that I have used the logic given here, they have written that for changing the end point, we just need to add end location in this line of code (
routing = pywrapcp.RoutingModel(num_locations, num_vehicles, start_locations, end_locations)
but when I am doing the same for our actual data I am getting the error of Wrong number or type of arguments for overloaded function 'new_RoutingModel'. Kindly help