Google ortools - mVRP with refueling

1

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:

enter image description here

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!

python
or-tools
asked on Stack Overflow May 15, 2020 by WKIm • edited May 18, 2020 by WKIm

1 Answer

2

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]))
answered on Stack Overflow May 16, 2020 by Mizux

User contributions licensed under CC BY-SA 3.0