I'm trying to solve mVRP with refueling at several stations (only for replenishment) with python. I found this: https://github.com/google/or-tools/blob/master/examples/cpp/cvrptw_with_refueling.cc.
I refer the code from github, but there are some problems in my code.
1) I followed the way (from the above github code) in python
(github code)
const int64 kFuelCapacity = kXMax + kYMax;
routing.AddDimension(
routing.RegisterTransitCallback([&locations, &manager](int64 i, int64 j) {
return locations.NegManhattanDistance(manager.IndexToNode(i),
manager.IndexToNode(j));
}),
kFuelCapacity, kFuelCapacity, /*fix_start_cumul_to_zero=*/false, kFuel);
const RoutingDimension& fuel_dimension = routing.GetDimensionOrDie(kFuel);
for (int order = 0; order < routing.Size(); ++order) {
// Only let slack free for refueling nodes.
if (!IsRefuelNode(order) || routing.IsStart(order)) {
fuel_dimension.SlackVar(order)->SetValue(0);
}
// Needed to instantiate fuel quantity at each node.
routing.AddVariableMinimizedByFinalizer(fuel_dimension.CumulVar(order));
}
(my code into python)
fuel_callback_index = routing.RegisterTransitCallback(fuel_callback)
routing.AddDimension(
fuel_callback_index,
data['MFuel'],
data['MFuel'],
False,
'Fuel'
)
fuel_dimension = routing.GetDimensionOrDie('Fuel')
for i in range(routing.Size()):
if (i not in data['vStation']) or routing.IsStart(i):
idx = manager.NodeToIndex(i)
fuel_dimension.SlackVar(idx).SetValue(0)
routing.AddVariableMinimizedByFinalizer(fuel_dimension.CumulVar(i))
Questions
1) if I use idx = manager.NodeToIndex(i)
in the for loop to SetValue
of fuel_dimension
, it gave me an error like below:
Process finished with exit code -1073741819 (0xC0000005)
If I use i
instead of idx
(from NodeToIndex
), the error doesn't occur. Can anyone explain this?
2) When I print results, the results (especially, fuel dimension) seem to be weird. For example,
result
8 (fuel: 0) -> 9 (fuel: 0) -> 7 (fuel: 3) -> 11 (fuel: 2) -> 6 (fuel: 4) -> 4 (fuel: 3) -> 5 (fuel: 1) -> 10 (fuel: 0) -> 3 (fuel: 2) -> 2 (fuel: 1) -> 1 (fuel: 0) -> 0
In brief, node 0 is dummy depot and node 8 is designated starting node for the agent. And, task node: [1, 2, 3, 4, 5, 6, 7], stations node: [8, 9, 10, 11]. Especially, node 8 and 9 are same station but I duplicated it to allow revisit to refuel, and, so do 10 and 11. Distance between nodes are same as 1 and I assume Manhattan dist.
Problem is that fuels at stations are not the maximum fuel (here, 4). Moreover, the 2nd transition (9 (fuel: 0) -> 7 (fuel: 3)) should consume fuel as 1 but it doesn't.
What is worse is that transitions (11 (fuel: 2) -> 6 (fuel: 4) -> 4 (fuel: 3)) are totally wrong.
Above problem's index map is like below:
Below is the entire code:
from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def print_solution(data, manager, routing, solution):
max_route_distance = 0
fuel_dimension = routing.GetDimensionOrDie('Fuel')
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):
fuel_var = fuel_dimension.CumulVar(index)
plan_output += ' {} (fuel: {}) -> '.format(manager.IndexToNode(index), solution.Value(fuel_var))
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
plan_output += '{}\n'.format(manager.IndexToNode(index))
plan_output += 'Distance of the route: {}m\n'.format(route_distance)
max_route_distance = max(route_distance, max_route_distance)
def manhattan_distance(position_1, position_2):
return (abs(position_1[0] - position_2[0]) +
abs(position_1[1] - position_2[1]))
def main():
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'],
data['vStart'],
data['vEnd'])
# 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 fuel_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 -manhattan_distance(data['locations'][from_node], data['locations'][to_node])
# Add Distance constraint.
dimension_name = 'Distance'
routing.AddDimension(
transit_callback_index,
0, # no slack
100, # vehicle maximum travel distance
True, # start cumul to zero
dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)
fuel_callback_index = routing.RegisterTransitCallback(fuel_callback)
routing.AddDimension(
fuel_callback_index,
data['MFuel'],
data['MFuel'],
False,
'Fuel'
)
fuel_dimension = routing.GetDimensionOrDie('Fuel')
for i in range(routing.Size()):
if (i not in data['vStation']) or routing.IsStart(i):
idx = manager.NodeToIndex(i)
fuel_dimension.SlackVar(i).SetValue(0)
routing.AddVariableMinimizedByFinalizer(fuel_dimension.CumulVar(i))
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
if __name__ == '__main__':
main()
Thank you,
Additionally, below is the data code
import numpy as np
from scipy.spatial import distance
np.random.seed(0)
# problem settings
gridX, gridY = 10, 10
N_vehicles = 5
MFuel = 10
coord_stations = [(1,1), (1,4), (1,7), (4,2), (4,5), (4,8), (7,1), (8,4), (4,2), (7,7)]
coord_starts = [(1,1),(1,7),(4,2),(4,8),(8,4)]
coord_srfs = [(x,y) for x in range(gridX) for y in range(gridY) if (x,y) not in coord_stations]
# dummies
dummy_depot = [(0,0)]
N_dummy = 5
N_dummySta = N_dummy * len(coord_stations)
# prerequisite
MFuels = [MFuel] * N_vehicles
N_v = 1 + len(coord_srfs) + N_dummySta
# make map w/ all vertices
map = {}
idx = {}
coord2vertex = {}
for (x,y) in [(x,y) for x in range(gridX) for y in range(gridY)]:
coord2vertex[(x,y)] = []
map[0] = dummy_depot[0]
idx['depot'] = 0
srfs_idx = []
for i in range(len(coord_srfs)):
map[i+1] = coord_srfs[i]
srfs_idx.append(i+1)
coord2vertex[coord_srfs[i]].append(i+1)
idx['surfaces'] = srfs_idx
stas_idx = []
for i in range(N_dummySta):
sta_idx = i//N_dummy
map[i+idx['surfaces'][-1]+1] = coord_stations[sta_idx]
stas_idx.append(i+idx['surfaces'][-1]+1)
coord2vertex[coord_stations[sta_idx]].append(i+idx['surfaces'][-1]+1)
idx['stations'] = stas_idx
# make distance matrix w/ all vertices
dist_mat = np.zeros((N_v, N_v), dtype=int)
for i in range(N_v):
for j in range(N_v):
if i == 0 or j == 0:
dist_mat[i,j] = 0
else:
if i == j:
dist_mat[i,j] = 0
else:
dist_mat[i,j] = sum(abs(np.array(map[j])-np.array(map[i])))
distance_matrix = dist_mat.tolist()
v_starts = [coord2vertex[coord][0] for coord in coord_starts]
data = dict()
data['distance_matrix'] = distance_matrix
data['num_vehicles'] = N_vehicles
data['vStart'] = v_starts
data['vEnd'] = [0] * N_vehicles
data['MFuel'] = MFuel
data['vStation'] = idx['stations']
data['vSrf'] = idx['surfaces']
data['locations'] = list(map.values())
data['num_locations'] = len(data['locations'])
print('Problem is generated.\n# of vehicles: {} (w/ capacities: {})\n# of tasks: {} (w/ locations: {} & demands: {})\n'.format(N_vehicles, v_capas, N_tasks, coord_tasks, t_demands))
Thank you!
As blind fix (ed since you don't provide data
to test), I would rewrite:
# Add Fuel Constraint.
dimension_name = 'Fuel'
def fuel_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 -manhattan_distance(data['locations'][from_node], data['locations'][to_node])
fuel_callback_index = routing.RegisterTransitCallback(fuel_callback)
routing.AddDimension(
fuel_callback_index,
data['MFuel'],
data['MFuel'],
False,
dimension_name)
fuel_dimension = routing.GetDimensionOrDie(dimension_name)
for i in range(len(data['distance_matrix'])):
if (i not in data['vStation']) and
(i not in data['vStart']) and
(i not in data['vEnd']):
idx = manager.NodeToIndex(i)
fuel_dimension.SlackVar(idx).SetValue(0)
routing.AddVariableMinimizedByFinalizer(fuel_dimension.CumulVar(idx))
and for manhattan, if you have float values, notice the int()
cast !:
def manhattan_distance(position_1, position_2):
return int(abs(position_1[0] - position_2[0]) +
abs(position_1[1] - position_2[1]))
User contributions licensed under CC BY-SA 3.0