使用or-工具来结合取货和送货、多趟行程和容量限制

Question

我搜索了很多类似的问题，但找不到适合我情况的解决方案。如果你们能给我一些建议，我将非常感激。

这就是我的情况

一辆车在仓库装载一些新机器，然后访问多个地点。当车辆将新机器运送到每个节点时，它们还会从每个节点收集损坏的机器。

同时，车辆也有容量限制。

此外，我需要复制仓库以允许多次行程：车辆需要返回仓库卸下损坏的机器并装载新机器并再次行驶，直到完成所有送货和取货。

主要思想类似于这个例子：https://github.com/google/or-tools/blob/master/ortools/constraint_solver/samples/cvrp_reload.py，但是现在我不考虑时间约束。

我做了什么

主要思想是：

• 取消注释时间窗口约束。
• 使用交付维度来跟踪新机器的交付情况
• 使用拾取器维度来跟踪损坏机器的拾取器
• 添加一个约束，在每个节点， CumulVar(pickups) + CumulVar(deliveries) <=capacity

寻求帮助

示例任务是这样的：

问题是：

如果我将车辆容量设置为10，问题就可以解决。但是当我设置 7 时，然后“找不到解决方案”！

但显然，车辆至少可以行驶 4 次才能完成所有工作：

第1轮：在仓库装载5台新机器，前往节点1，卸载它们， 然后捡起4台坏掉的机器回到仓库

第2轮：在仓库装载5台新机器，前往节点2，卸载它们， 并捡起6台坏掉的机器返回仓库

round3：在仓库装载2台新机器，前往节点3，卸载它们， 并捡起 7 台损坏的机器返回仓库

第4轮：在仓库装载3台新机器，前往节点4，卸载它们， 然后捡起3台坏掉的机器回到仓库

我可以理解为什么求解器没有找到这个解。因为每次车辆离开重复的站点节点时，交付维度都会重置为 _capacity。当_capacity为7时，车辆可以满足节点1和节点4的需求。（在节点1卸载5台新机器，装载4台坏机。在节点4卸载3台坏机，装载3台新机器）机器。）

但在节点 2 和节点 3，取货/送货分别为 +6/-5 和 +7/-2。当车辆从重复站点节点出发时，其容量为7，节点2和节点3都会突破容量限制。 (+6-5>0, +7-2>0)

所以这个问题的根本原因是：重复的仓库节点不应该将deliveries维度值设置为固定值（_capacity），而应该设置为[0, _capacity]之间的值。

但是 max_slack 是一个正数，我不知道如何使交付维度的值介于 [0, _capacity] 之间。

有人可以帮助我吗？非常感谢。

下面是我的代码。

from functools import partial
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
from itertools import repeat

###########################
# Problem Data Definition #
###########################
def create_data_model():
    """Stores the data for the problem"""
    data = {}
    _capacity = 10  # 7 doesn't work
    _duplicate_depot_num = 5
    # Locations in block unit
    _locations = [
        (4, 4),  # depot
        (2, 0), (8, 0),  # 1, 2
        (0, 1), (1, 1)]  # 3, 4
    _locations[1:1] = tuple(repeat(_locations[0], _duplicate_depot_num))

    data['locations'] = _locations
    data['num_locations'] = len(data['locations'])
    data['pickups'] = [0,  # depot
                       4, 6,  # 1, 2
                       7, 3]  # 3, 4
    data['pickups'][1:1] = tuple(repeat(-_capacity, _duplicate_depot_num))

    data['deliveries'] = [0,  # depot
                          -5, -5,  # 1, 2
                          -2, -3]  # 3, 4
    data['deliveries'][1:1] = tuple(repeat(_capacity, _duplicate_depot_num))

    data['vehicle_max_distance'] = 1000
    data['vehicle_capacity'] = _capacity
    data['num_vehicles'] = 1
    data['depot'] = 0
    data['dup_depot_num'] = _duplicate_depot_num
    return data


#######################
# Problem Constraints #
#######################
def manhattan_distance(position_1, position_2):
    """Computes the Manhattan distance between two points"""
    return (abs(position_1[0] - position_2[0]) +
            abs(position_1[1] - position_2[1]))


def create_distance_evaluator(data):
    """Creates callback to return distance between points."""
    _distances = {}
    # precompute distance between location to have distance callback in O(1)
    for from_node in range(data['num_locations']):
        _distances[from_node] = {}
        for to_node in range(data['num_locations']):
            if from_node == to_node:
                _distances[from_node][to_node] = 0
            # Forbid start/end/reload node to be consecutive.
            elif from_node in range(data['dup_depot_num']+1) and to_node in range(data['dup_depot_num']+1):
                _distances[from_node][to_node] = data['vehicle_max_distance']
            else:
                _distances[from_node][to_node] = (manhattan_distance(
                    data['locations'][from_node], data['locations'][to_node]))

    def distance_evaluator(manager, from_node, to_node):
        """Returns the manhattan distance between the two nodes"""
        return _distances[manager.IndexToNode(from_node)][manager.IndexToNode(
            to_node)]

    return distance_evaluator


def add_distance_dimension(routing, manager, data, distance_evaluator_index):
    """Add Global Span constraint"""
    distance = 'Distance'
    routing.AddDimension(
        distance_evaluator_index,
        0,  # null slack
        data['vehicle_max_distance'],  # maximum distance per vehicle
        True,  # start cumul to zero
        distance)
    # distance_dimension = routing.GetDimensionOrDie(distance)
    # Try to minimize the max distance among vehicles.
    # /!\ It doesn't mean the standard deviation is minimized
    # distance_dimension.SetGlobalSpanCostCoefficient(100)


def create_demand_evaluator(data):
    """Creates callback to get demands at each location."""
    _demands = data['pickups']

    def demand_evaluator(manager, from_node):
        """Returns the demand of the current node"""
        return _demands[manager.IndexToNode(from_node)]

    return demand_evaluator


def add_pickups_constraints(routing, manager, data, pickups_evaluator_index):
    """Adds capacity constraint"""
    vehicle_capacity = data['vehicle_capacity']
    capacity = 'pickups'
    routing.AddDimension(
        pickups_evaluator_index,
        vehicle_capacity,
        vehicle_capacity,
        True,  # since this is pickups, so start cumul should be zero
        capacity)


def create_deliveries_evaluator(data):
    """Creates callback to get demands at each location."""
    _deliveries = data['deliveries']

    def deliveries_evaluator(manager, from_node):
        """Returns the demand of the current node"""
        return _deliveries[manager.IndexToNode(from_node)]

    return deliveries_evaluator


def add_deliveries_constraints(routing, manager, data, deliveries_evaluator_index):
    """Adds capacity constraint"""
    vehicle_capacity = data['vehicle_capacity']
    capacity = 'deliveries'
    routing.AddDimension(
        deliveries_evaluator_index,
        vehicle_capacity,
        vehicle_capacity,
        False,  # there is a initial capacity to be delivered
        capacity)

###########
# Printer #
###########
def print_solution(data, manager, routing, assignment):  # pylint:disable=too-many-locals
    """Prints assignment on console"""
    print(f'Objective: {assignment.ObjectiveValue()}')
    total_distance = 0
    total_pickups = 0
    # total_time = 0
    total_deliveries = 0
    pickups_dimension = routing.GetDimensionOrDie('pickups')
    # time_dimension = routing.GetDimensionOrDie('Time')
    deliveries_dimension = routing.GetDimensionOrDie('deliveries')
    dropped = []
    for order in range(6, routing.nodes()):
        index = manager.NodeToIndex(order)
        if assignment.Value(routing.NextVar(index)) == index:
            dropped.append(order)
    print(f'dropped orders: {dropped}')
    for reload in range(1, 6):
        index = manager.NodeToIndex(reload)
        if assignment.Value(routing.NextVar(index)) == index:
            dropped.append(reload)
    print(f'dropped reload stations: {dropped}')

    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = f'Route for vehicle {vehicle_id}:\n'
        distance = 0
        while not routing.IsEnd(index):
            pickups_var = pickups_dimension.CumulVar(index)
            deliveries_var = deliveries_dimension.CumulVar(index)
            # time_var = time_dimension.CumulVar(index)
            plan_output += ' {0} Pickups({1}) Deliveries({2})->'.format(
                manager.IndexToNode(index),
                assignment.Value(pickups_var),
                assignment.Value(deliveries_var)
                # assignment.Min(time_var), assignment.Max(time_var)
            )
            previous_index = index
            index = assignment.Value(routing.NextVar(index))
            distance += routing.GetArcCostForVehicle(previous_index, index,
                                                     vehicle_id)
        pickups_var = pickups_dimension.CumulVar(index)
        deliveries_var = deliveries_dimension.CumulVar(index)
        # time_var = time_dimension.CumulVar(index)
        plan_output += ' {0} Pickups({1}) Deliveries({2})\n'.format(
            manager.IndexToNode(index),
            assignment.Value(pickups_var),
            assignment.Value(deliveries_var)
            # assignment.Min(time_var), assignment.Max(time_var)
        )
        plan_output += f'Distance of the route: {distance}m\n'
        plan_output += f'Pickups of the route: {assignment.Value(pickups_var)}\n'
        plan_output += f'Deliveries of the route: {assignment.Value(deliveries_var)}\n'
        # plan_output += f'Time of the route: {assignment.Value(time_var)}min\n'
        print(plan_output)
        total_distance += distance
        total_pickups += assignment.Value(pickups_var)
        total_deliveries += assignment.Value(deliveries_var)
        # total_time += assignment.Value(time_var)
    print('Total Distance of all routes: {}m'.format(total_distance))
    print('Total Pickups of all routes: {}'.format(total_pickups))
    print('Total Deliveries of all routes: {}'.format(total_deliveries))
    # print('Total Time of all routes: {}min'.format(total_time))


########
# Main #
########
def main():
    """Entry point of the program"""
    # Instantiate the data problem.
    data = create_data_model()

    print(data['locations'])

    # Create the routing index manager
    manager = pywrapcp.RoutingIndexManager(data['num_locations'],
                                           data['num_vehicles'], data['depot'])

    # Create Routing Model
    routing = pywrapcp.RoutingModel(manager)

    # Define weight of each edge
    distance_evaluator_index = routing.RegisterTransitCallback(
        partial(create_distance_evaluator(data), manager))
    routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator_index)

    # Add Distance constraint to minimize the longuest route
    add_distance_dimension(routing, manager, data, distance_evaluator_index)

    # Add Demand constraint
    demand_evaluator_index = routing.RegisterUnaryTransitCallback(partial(create_demand_evaluator(data), manager))
    add_pickups_constraints(routing, manager, data, demand_evaluator_index)

    # Add deliveries constraint
    deliveries_evaluator_index = routing.RegisterUnaryTransitCallback(
        partial(create_deliveries_evaluator(data), manager))
    add_deliveries_constraints(routing, manager, data, deliveries_evaluator_index)

    # # Add Slack for reseting to zero unload depot nodes.
    # e.g. vehicle with load 10/15 arrives at node 1 (depot unload)
    # so we have CumulVar = 10(current load) + -15(unload) + 5(slack) = 0.
    pickups_dimension = routing.GetDimensionOrDie("pickups")
    deliveries_dimension = routing.GetDimensionOrDie('deliveries')

    # Allow to drop reloading nodes with zero cost.
    for node in range(1, data['dup_depot_num']+1):
        node_index = manager.NodeToIndex(node)
        routing.AddDisjunction([node_index], 0)

    for node in range(data['dup_depot_num']+1, len(data['pickups'])):
        node_index = manager.NodeToIndex(node)
        pickups_dimension.SlackVar(node_index).SetValue(0)
        deliveries_dimension.SlackVar(node_index).SetValue(0)  # ordinary node don't allow slack
        # routing.AddDisjunction([node_index], 100_000)  # Allow to drop regular node with a cost.

    # Add Constraint: Pick + Deliveries <= max_capacity
    for node in range(len(data['pickups'])):
        index = manager.NodeToIndex(node)
        routing.solver().Add(
            pickups_dimension.CumulVar(index) + deliveries_dimension.CumulVar(index) <= data["vehicle_capacity"])


    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )  # pylint: disable=no-member

    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_parameters.time_limit.FromSeconds(3)

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print("No solution found !")


if __name__ == '__main__':
    main()

Answer 1

如何在每个节点纳入约束、取货+送货< =capacity in the code for multiple vehicle scenario ?