OR-Tools带容量约束的取送问题代码修改求助

Hey there! I see you're trying to add capacity constraints to a Pickup and Delivery Problem (PDP) using OR-Tools but running into issues. Let's break down what's going wrong and fix your code step by step.

The Core Issue: Incorrect Demand Values #

The biggest problem in your current code is that all demand values are positive, which doesn't align with how PDP works. When you pick up an item, the vehicle's load increases (positive demand), but when you deliver it, the load should decrease (negative demand). Your current setup just keeps adding load at every node, which will almost certainly violate capacity constraints and lead to no valid solution.

For each pickup-delivery pair [pickup_node, delivery_node], we need to set:

• data['demands'][pickup_node] = positive value (amount being picked up)
• data['demands'][delivery_node] = negative value (amount being delivered, so it subtracts from the load)

Fixed Code with Explanations #

Here's the revised version of your code with proper capacity handling, plus comments explaining key changes:

from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

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['pickups_deliveries'] = [
        [1, 6],
        [2, 10],
        [4, 3],
        [5, 9],
        [7, 8],
        [15, 11],
        [13, 12],
        [16, 14],
    ]
    data['num_vehicles'] = 4
    data['depot'] = 0
    data['vehicle_capacities'] = [15,15,15,15]
    
    # FIXED: Demands - pickups are positive, deliveries are negative
    data['demands'] = [
        0,   # Depot (0)
        1,   # Pickup 1
        1,   # Pickup 2
        -3,  # Delivery 3 (matches pickup 4)
        3,   # Pickup 4
        3,   # Pickup 5
        -1,  # Delivery 6 (matches pickup 1)
        8,   # Pickup 7
        -8,  # Delivery 8 (matches pickup 7)
        -3,  # Delivery 9 (matches pickup 5)
        -1,  # Delivery 10 (matches pickup 2)
        -8,  # Delivery 11 (matches pickup 15)
        -6,  # Delivery 12 (matches pickup 13)
        6,   # Pickup 13
        -8,  # Delivery 14 (matches pickup 16)
        8,   # Pickup 15
        8    # Pickup 16
    ]
    return data

def print_solution(data, manager, routing, assignment):
    """Prints assignment on console."""
    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)
            # Update load correctly: add demand (which can be negative for deliveries)
            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 main():
    """Entry point of the program."""
    # Instantiate the data problem.
    data = create_data_model()

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

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

    # Define cost of each arc.
    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        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)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Capacity constraint (this part was correct, but demands were wrong)
    def demand_callback(from_index):
        """Returns the demand of the node."""
        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 (no extra space allowed)
        data['vehicle_capacities'],  # vehicle maximum capacities
        True,  # start cumul to zero (load starts at 0 at depot)
        'Capacity')

    # Add Distance constraint (unchanged, but useful for limiting travel distance)
    dimension_name = 'Distance'
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        3000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

    # Define Transportation Requests (unchanged, but critical for PDP logic)
    for request in data['pickups_deliveries']:
        pickup_index = manager.NodeToIndex(request[0])
        delivery_index = manager.NodeToIndex(request[1])
        routing.AddPickupAndDelivery(pickup_index, delivery_index)
        routing.solver().Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))
        routing.solver().Add(distance_dimension.CumulVar(pickup_index) <= distance_dimension.CumulVar(delivery_index))
        
        # Optional: Ensure that load after pickup is sufficient to cover the delivery
        capacity_dimension = routing.GetDimensionOrDie('Capacity')
        routing.solver().Add(capacity_dimension.CumulVar(pickup_index) >= capacity_dimension.CumulVar(delivery_index) + data['demands'][delivery_index])

    # Setting first solution heuristic (PARALLEL_CHEAPEST_INSERTION works well for PDP)
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)
    # Optional: Enable local search to improve the solution
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_parameters.time_limit.seconds = 10

    # Solve the problem.
    assignment = routing.SolveWithParameters(search_parameters)
    
    # Print solution on console.
    if assignment:
        print_solution(data, manager, routing, assignment)
    else:
        print("No valid solution found! Check constraints (e.g., vehicle capacities, demand sums)")

if __name__ == '__main__':
    main()

Key Changes Explained #

1. Demand Values: We flipped the sign for all delivery nodes so that when the vehicle visits a delivery node, the load decreases by the amount delivered. This ensures the vehicle's load never exceeds its capacity (as long as the sum of pickups on a route doesn't exceed capacity).
2. Optional Capacity Safeguard: We added an extra constraint to explicitly ensure that the load after pickup is sufficient to cover the delivery (though the demand signs should handle this, it's a good safeguard).
3. Local Search: Enabled guided local search with a time limit to find better, more efficient solutions.

Testing the Code #

When you run this revised code, you should see valid routes where:

• Each vehicle's load never exceeds 15 (your capacity limit)
• Every pickup is followed by its corresponding delivery on the same route
• The total load across all routes sums to 0 (since all pickups are matched with deliveries)

If you still get no solution, check:

• Are your vehicle capacities too low for the total pickup demand?
• Are there any impossible pickup-delivery pairs (e.g., a delivery that requires more load than any vehicle can carry)?

内容的提问来源于stack exchange，提问作者nik