Using or tools to solve the path planning problem with capacity constraints (CVRP)

We introduced TSP、VRP problem , So that we have a preliminary understanding of vehicle path planning , Today we are right VRP The problem extends further , Let's discuss the vehicle routing problem with capacity constraints ：CVRP( capacitated vehicle routing problem).CVRP yes VRP Another application of , The specific application scenario is as follows : The vehicle has carrying capacity , Each vehicle needs to pick up or deliver goods at different places under the condition of limited carrying capacity . Quantity of goods , Weight or volume , And vehicles have the maximum capacity they can carry . What we need to do is to pick up or deliver the goods at the lowest cost , At the same time, the maximum capacity of the vehicle cannot be exceeded . Let's take a specific example , Before we talk about this example, let's assume , All locations have goods that need to be picked up , Here, in order to simplify the problem , We only consider taking delivery of goods, not delivery ( In the future, we will consider the situation of both delivery and delivery ), That is, let each car pick up the goods at different places , But you can't exceed the capacity limit of the vehicle every time .

CVRP Example

Next, we will take a case with capacity limitation CVRP Example . This example is in the previous VRP Based on the example :

There is a cargo to be picked up at each location , And the goods at each location have their own capacity ( Volume or weight, etc ). Besides , The maximum capacity of each vehicle is 15.（ Here, in order to simplify the calculation , We do not specify the unit of capacity .）

The blue circle in the grid below indicates the place to visit , The black circle in the middle shows the location of the logistics company . The volume of goods to be picked up at each location is shown at the bottom right of the circle . 

Our requirement is to allocate access routes to these locations for each vehicle , And make the total journey of all vehicles the shortest , And the goods extracted by each vehicle cannot exceed its own capacity limit , All goods must be picked up .

Use OR-Tools solve CVRP problem

Creating a data model

First , Create a data model based on the above data example , The data model includes ：

• Distance matrix （distance_matrix）
• Number of vehicles (num_vehicles)
• Starting point index (depot)
• Cargo capacity demand at each location (demands)
• The maximum capacity of each vehicle (vehicle_capacities)

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['num_vehicles'] = 4 # Number of vehicles 
    data['depot'] = 0 # Starting point index 
    data['demands'] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8] # Demand per location 
    data['vehicle_capacities'] = [15, 15, 15, 15]# Capacity of each vehicle 
    return data

data = create_data_model()

Here we assume that 4 Vehicles , The capacity of each car is 15, in total 17 Sites need to be visited ( Including the starting point ), Each location has different volumes of goods to be picked up .

Create a routing model

The following code creates the index manager in the main part of the program (manager) And the routing model (routing). manager Mainly based on distance_matrix To manage the index of each location , and routing Used to calculate and store access paths .

manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),data['num_vehicles'], data['depot'])

routing = pywrapcp.RoutingModel(manager)

Create a distance callback function

Here we define a distance callback function to return from distance_matrix Returns the distance between a given two places , Next, we need to set the travel cost (routing.SetArcCostEvaluatorOfAllVehicles) It will tell the solver how to calculate the access cost of any two locations , Here our cost refers to the distance between any two places .

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)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

Add capacity demand callback and capacity constraint

Except for distance callback , The solver also needs a capacity demand callback , It returns the requirements of each location , And the dimension of capacity constraints .

def demand_callback(from_index):
    from_node = manager.IndexToNode(from_index)
    return data['demands'][from_node]
    

demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
    demand_callback_index, # callback_index
    0,  # slack_max
    data['vehicle_capacities'],  # capacity
    True,  # fix_start_cumulative_to_zero
    'Capacity' # Dimension name )

AddDimension Parameter description of the method ：

• callback_index： The index of the callback that returns the distance between two locations . The index is the internal reference of the solver to the callback , from RegisterTransitCallback or RegisterUnitaryTransitCallback And so on .
• slack_max：slack The maximum of , A variable , Used to indicate the waiting time of the position . If the problem does not involve waiting time , Usually you can put slack_max Set to 0.
• capacity： Capacity , The maximum value of the total quantity accumulated along each route . Use capacity to create something like CVRP Constraints in . If our problem does not have such constraints , Can be capacity Set to a value large enough , So that there are no restrictions on routing — for example , The sum of all entries of the matrix or array used to define the callback .
• fix_start_cumulative_to_zero： Boolean value . If true, Then the cumulative value of the quantity starts from 0 Start . in the majority of cases , It should be set to True. however , about VRPTW Or resource constraints , Due to time window limitations , Some vehicles may have to be in time 0 After the start , Therefore, you should address these issues by fix_start_cumulative_to_zero Set to False.
• Dimension name ： String of dimension name , for example “ distance ”, You can use it to access variables elsewhere in the program . 

Set the search policy

Similar to before TSP Settings in the application , Here we also need to set  first_solution_strategy：PATH_CHEAPEST_ARC, Here, the first solution strategy is set to PATH_CHEAPEST_ARC, It will not lead to previously visited nodes by repeatedly adding （ Except the starting point ） The edge with the least weight of creates the initial path for the solver , This strategy can quickly get a feasible solution .

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

#search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
#search_parameters.time_limit.FromSeconds(30)

Later, we try to use more advanced search strategies ( The temporarily commented out part of the code )：LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH, The change strategy is called : Guide local search , It enables the solver to continue searching after avoiding the local minimum , But the final result is not necessarily the global optimal solution .

Be careful : Use GUIDED_LOCAL_SEARCH Or other meta heuristic algorithms , You need to set the search time limit for the solver —— Otherwise the solver will not terminate . You can set the time limit to 30 second .

Add print access path function

This function can print the route of each vehicle , And its cumulative load ： The total capacity of the vehicle when it stops on its route .

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    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)
            route_load += data['demands'][node_index]
            plan_output += ' {0} Load({1}) -> '.format(node_index, route_load)
            previous_index = index
            index = solution.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))

problem solving

solution = routing.SolveWithParameters(search_parameters)

if solution:
    print_solution(data, manager, routing, solution)

  This plan doesn't look ideal , because  vehicle 0 and  vehicle 1 They all go around in two big circles , And their driving routes exceed 2000.

Here is how we switch our search strategy to GUIDED_LOCAL_SEARCH The output after ：

  By switching search strategies , The shortest path is from the original 6872 Reduced to 6208, And the access route of each vehicle is more reasonable , There is no big circle , And the length of the driving path of each vehicle is 2000 before , A fellow 1552.

Summary  

1. stay CVRP In the application scenario of , The data model needs to increase the demand for cargo capacity at each location :demands and The maximum capacity of each vehicle :vehicle_capacities.

2. You need to add capacity demand callback function and capacity constraint .

3. By switching search strategies , A satisfactory solution can be obtained .