python - Google ortools - mVRP 加油

Question

我正在尝试用python在几个加油站(仅用于补给)通过加油来解决mVRP。我发现了这个:https://github.com/google/or-tools/blob/master/examples/cpp/cvrptw_with_refueling.cc 。

我引用了github上的代码，但是我的代码存在一些问题。

1)我按照Python中的方式(来自上面的github代码)

(github代码)

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));

}

(我的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))

问题

1) 如果我在 for 循环中使用 idx = manager.NodeToIndex(i) 到 fuel_dimension 的 SetValue，它给了我一个错误如下:

Process finished with exit code -1073741819 (0xC0000005)

如果我使用 i 而不是 idx (来自 NodeToIndex)，则不会发生错误。谁能解释一下吗？

2)当我打印结果时，结果(尤其是燃料尺寸)似乎很奇怪。例如，

结果

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

简而言之，节点 0 是虚拟仓库，节点 8 是指定代理的起始节点。并且，任务节点:[1,2,3,4,5,6,7]，站点节点:[8,9,10,11]。特别是，节点 8 和 9 是同一站，但我复制了它以允许重新访问加油，并且 10 和 11 也是如此。节点之间的距离与 1 相同，我假设曼哈顿距离。

问题是加油站的燃油不是最大燃油(此处为 4)。此外，第二个转换 (9 (fuel: 0) -> 7 (fuel: 3)) 消耗的燃料应该为 1，但事实并非如此。

更糟糕的是，转换 (11 (fuel: 2) -> 6 (fuel: 4) -> 4 (fuel: 3)) 是完全错误的。

上述问题的索引图如下:

完整代码如下:

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()

谢谢，

另外，下面是数据代码

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))

谢谢!

Answer 1

作为盲目修复(因为您不提供数据来测试)，我会重写:

   # 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))

对于曼哈顿，如果您有浮点值，请注意 int() 转换 !:

def manhattan_distance(position_1, position_2):
    return int(abs(position_1[0] - position_2[0]) +
        abs(position_1[1] - position_2[1]))