in

Google OR-Tools: Pickup/deliveries with optional nodes for refueling


I’m trying to solve a pickup and delivery vehicle routing problem where some nodes represent charging stations. To accomplish this, I add a disjunction with zero cost for the charging stations, and have a callback where you can recharge by a fixed amount only at the charging stations.

However, when I run the code, the solver prefers to drop pickup/delivery pairs rather than go to a charging station, even though it leads to a much higher objective value. (If you change the energy_capacity_kWh of each vehicle to 100, it will not drop pickup/delivery pairs.)

What is going on here? Is it possible to have a PDP where some nodes are not specified as part of pickup and delivery pairs? If you look at the debug print it seems that the solver only tests going from the charging nodes to themselves (doesn’t test going from any other node to a charging node).

Here’s the data:

vehicles:

locations:

locations

load schedule:

load_schedule

And here’s the code:

import pandas as pd
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

SEC_PER_MIN = 60
MIN_PER_HR = 60
W_PER_KW = 1000
METERS_PER_MI = 1609
MILES_PER_KWH = 0.5

def print_solution(data, manager, routing, solution):
    print("Objective: {}".format(solution.ObjectiveValue()))
    # Display dropped nodes
    dropped_nodes = "Dropped nodes:"
    for node in range(routing.Size()):
        if routing.IsStart(node) or routing.IsEnd(node):
            continue
        if solution.Value(routing.NextVar(node)) == node:
            dropped_nodes += " {}".format(manager.IndexToNode(node))
    dropped_nodes += "n"
    print(dropped_nodes)
    # Display routes
    max_route_distance = 0
    total_distance = 0
    energy_dimension = routing.GetDimensionOrDie('Energy')
    max_route_energy = 0
    total_energy = 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
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            energy_var = energy_dimension.CumulVar(index)
            plan_output += "t{0}: Energy Consumed = {1:.0f}kWh ->n".format(
                data['node_name'][node_index],
                solution.Min(energy_var) / W_PER_KW)
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
        energy_var = energy_dimension.CumulVar(index)
        route_energy = solution.Min(energy_var)
        plan_output += "t{0}: Energy Consumed = {1:.0f}kWhn".format(
            data['node_name'][manager.IndexToNode(index)],
            route_energy / W_PER_KW)
        plan_output += "Distance of the route: {:.2f}n".format(route_distance)
        plan_output += "Energy of the route: {:.0f}kWhn".format(route_energy / W_PER_KW)
        print(plan_output)
        max_route_distance = max(route_distance, max_route_distance)
        total_distance += route_distance
        total_energy += route_energy
        max_route_energy = max(route_energy, max_route_energy)
    print("Maximum of the route distances: {:.2f}".format(max_route_distance))
    print("Total distance of all routes: {:.2f}".format(total_distance))
    print("Maximum of the route energies: {:.0f}kWh".format(max_route_energy / W_PER_KW))
    print("Total energy of all routes: {:.0f}kWh".format(total_energy / W_PER_KW))

DISTANCE_MATRIX = [
    [0, 2211, 5696, 7887, 5505, 106559, 104238, 97920, 2615, 2358, 7476, 6629, 5532, 96103, 100287, 96079, 123016, 3148, 7412, 7412, 7412, 7412],
    [2210, 0, 3359, 6567, 5472, 106695, 104373, 98056, 3932, 777, 6157, 3581, 7295, 96239, 100423, 96215, 123152, 4470, 8734, 8734, 8734, 8734],
    [5594, 3310, 0, 3743, 10457, 109343, 107022, 100704, 7425, 2901, 3332, 5221, 11735, 98887, 103071, 98863, 125801, 7963, 12205, 12205, 12205, 12205],
    [7759, 6070, 3743, 0, 12622, 111508, 109187, 102869, 9590, 5662, 532, 7253, 13900, 101052, 105236, 101029, 127966, 10128, 9833, 9833, 9833,
  9833],
    [6133, 5472, 10420, 12611, 0, 104467, 102146, 95828, 8247, 5987, 12200, 8152, 2005, 94011, 98195, 93988, 120925, 8784, 13026, 13026, 13026, 13026],
    [106112, 106911, 110400, 112591, 103918, 0, 9230, 15909, 108226, 108448, 112180, 107093, 104592, 9537, 12146, 13792, 18967, 108764, 113006, 113006, 113006, 113006],
    [104536, 105335, 108824, 111014, 102341, 9533, 0, 7314, 106650, 106871, 110604, 105517, 103015, 6077, 5242, 11190, 9645, 107188, 111430, 111430, 111430, 111430],
    [97717, 98516, 102005, 104196, 95523, 17004, 7438, 0, 99832, 100053, 103785, 98699, 96197, 6181, 3203, 3450, 25860, 100369, 104611, 104611, 104611, 104611],
    [2615, 3955, 6977, 9168, 8718, 108951, 106630, 100312, 0, 3639, 8757, 7910, 6573, 98495, 102679, 98472, 125409, 546, 4385, 4385, 4385, 4385],
    [2355, 772, 2949, 6157, 5982, 107378, 105056, 98738, 3632, 0, 5746, 4593, 7264, 96921, 101105, 96898, 123835, 4170, 8434, 8434, 8434, 8434],
    [7348, 5660, 3332, 532, 12212, 111098, 108777, 102459, 9180, 5251, 0, 6652, 13490, 100642, 104826, 100618, 127555, 9717, 9422, 9422, 9422, 9422],
    [6841, 3581, 5255, 7253, 8066, 106567, 104245, 97928, 8672, 4593, 6843, 0, 9889, 96111, 100294, 96087, 123024, 9210, 13452, 13452, 13452, 13452],
    [5664, 6944, 12243, 14434, 2005, 104977, 102655, 96338, 6584, 7211, 14023, 10028, 0, 94521, 98705, 94497, 121434, 7122, 10011, 10011, 10011, 10011],
    [96340, 97139, 100627, 102818, 94145, 9142, 5581, 5038, 98454, 98675, 102408, 97321, 94819, 0, 3860, 5506, 22491, 98992, 103233, 103233, 103233, 103233],
    [95552, 96351, 99840, 102031, 93357, 12145, 5274, 2876, 97666, 97888, 101620, 96533, 94032, 4525, 0, 4746, 21799, 98204, 102446, 102446, 102446, 102446],
    [95962, 96761, 100250, 102440, 93767, 13822, 11167, 3357, 98076, 98297, 102030, 96943, 94441, 6202, 4757, 0, 27098, 98614, 102856, 102856, 102856, 102856],
    [123365, 124164, 127652, 129843, 121170, 19176, 9879, 25804, 125479, 125700, 129432, 124346, 121844, 22697, 22130, 27665, 0, 126016, 130258, 130258, 130258, 130258],
    [3148, 4489, 7511, 9701, 9255, 109489, 107167, 100850, 546, 4173, 9291, 8444, 7110, 99033, 103217, 99009, 125946, 0, 3656, 3656, 3656, 3656],
    [6699, 8039, 11493, 9829, 12529, 112763, 110441, 104124, 4392, 7723, 9418, 13279, 10000, 102307, 106490, 102283, 129220, 3656, 0, 0, 0, 0],
    [6699, 8039, 11493, 9829, 12529, 112763, 110441, 104124, 4392, 7723, 9418, 13279, 10000, 102307, 106490, 102283, 129220, 3656, 0, 0, 0, 0],
    [6699, 8039, 11493, 9829, 12529, 112763, 110441, 104124, 4392, 7723, 9418, 13279, 10000, 102307, 106490, 102283, 129220, 3656, 0, 0, 0, 0],
    [6699, 8039, 11493, 9829, 12529, 112763, 110441, 104124, 4392, 7723, 9418, 13279, 10000, 102307, 106490, 102283, 129220, 3656, 0, 0, 0, 0]]

locations = pd.read_csv('locations.csv', index_col="id")
vehicles = pd.read_csv('vehicles.csv', index_col="id", thousands=",")
load_schedule = pd.read_csv('load_schedule.csv', index_col="id", thousands=",")

def create_data_model(locations, vehicles, load_schedule):
    # Aggregate deliveries that can be grouped
    load_schedule['load_description'] = load_schedule.groupby(
        by=['origin_id', 'destination_id'])['load_description'].transform(lambda x: 'n'.join(x))
    grouped_loads = load_schedule.groupby(
        by=['origin_id', 'destination_id', 'load_description']).sum().reset_index()

    # The VRP solver doesn't allow visiting a node more than once, so each delivery
    # originating from the same place requires another set of nodes.
    # For pickups and deliveries, document when demands are added and removed.
    loads_added = grouped_loads[['origin_id', 'load_description']].rename(
        columns={'origin_id': 'location_id'})
    loads_removed = grouped_loads[['destination_id', 'load_description']].rename(
        columns={'destination_id': 'location_id'})
    loads = pd.concat([loads_added, loads_removed])
    locations['location_id'] = locations.index
    locations_loads = loads.merge(
        locations, on='location_id', how='left')

    # Concatenate vehicle depots and charging locations
    depot_locations = locations[(locations['depot'] == True)]
    charging_locations = locations[(locations['depot'] == False) & (locations['charging'] == True)]
    # The VRP solver doesn't allow visiting a node more than once,
    # so duplicate charging locations to enable each vehicle to charge once.
    charging_locations = charging_locations.loc[charging_locations.index.repeat(len(vehicles.index))]
    locations_loads = pd.concat([locations_loads, depot_locations, charging_locations], ignore_index=True)

    distance_matrix = DISTANCE_MATRIX

    # Build pickups and deliveries
    # We use the index in the final data model rather than the original location ids
    num_pairs = grouped_loads.shape[0]
    pickups_deliveries = [(x, x + num_pairs) for x in range(num_pairs)]

    # Create data model
    data = {}
    data['node_name'] = locations_loads['name'].tolist()
    data['distance_matrix'] = distance_matrix
    data['num_nodes'] = len(data['distance_matrix'])
    data['charging_power'] = locations_loads['charging_power_kw'].tolist()
    data['num_vehicles'] = len(vehicles.index)
    data['vehicle_capacities_energy'] = [e * W_PER_KW for e in vehicles['energy_capacity_kwh']]
    data['vehicle_load_time'] = 30
    data['vehicle_unload_time'] = 30
    data['vehicle_charge_time'] = 30
    data['pickups_deliveries'] = pickups_deliveries
    starts = []
    for i in vehicles['depot_id']:
        starts.append(int(locations_loads[locations_loads['location_id'] == i].index.values[0]))
    data['starts'] = starts
    data['ends'] = data['starts']
    data['charging_stops'] = locations_loads[(locations_loads['charging'] == True) & (locations_loads['depot'] == False)].index.tolist()
    return data

data = create_data_model(locations, vehicles, load_schedule)

manager = pywrapcp.RoutingIndexManager(
    len(data['distance_matrix']),
    data['num_vehicles'],
    data['starts'],
    data['ends']
)
routing = pywrapcp.RoutingModel(manager)
solver = routing.solver()

# Register transit distance 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_distance_callback_index = routing.RegisterTransitCallback(distance_callback)

# Add Distance dimension.
dimension_name_distance="Distance"
routing.AddDimension(
    transit_distance_callback_index,
    slack_max=0,
    capacity=sum([sum(x) for x in data['distance_matrix']]),  # vehicle maximum travel distance
    fix_start_cumul_to_zero=True,
    name=dimension_name_distance)
distance_dimension = routing.GetDimensionOrDie(dimension_name_distance)

# Add a cost coefficient for the longest distance any vehicle must travel
# The higher this coefficient, the more the model will want to "balance out" the routes
# to make each vehicle incur a similar distance.
distance_dimension.SetGlobalSpanCostCoefficient(1)

# Define arc costs for all vehicles
routing.SetArcCostEvaluatorOfAllVehicles(transit_distance_callback_index)

# Set vehicle energy capacity (range) constraint
def energy_callback(from_index, to_index):
    """Returns the energy required to travel 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)
    energy_transit = data['distance_matrix'][from_node][to_node] / (METERS_PER_MI * MILES_PER_KWH / W_PER_KW)
    if to_node in data['charging_stops']:
        energy_charged = data['charging_power'][to_node] * W_PER_KW * data['vehicle_charge_time'] / MIN_PER_HR
        if energy_transit < energy_charged:
            print("from_node {} -> to_node {}ntenergy_transit {:.2f} < energy_charged {:.2f} -> could go to this node to charge".format(from_node, to_node, energy_transit, energy_charged))
            return energy_transit - energy_charged
        print("from_node {} -> to_node {}ntenergy_transit {:.2f} >= energy_charged {:.2f} -> should not go to this node to charge".format(from_node, to_node, energy_transit, energy_charged))
    return energy_transit
transit_energy_callback_index = routing.RegisterTransitCallback(energy_callback)

routing.AddDimensionWithVehicleCapacity(
    transit_energy_callback_index,
    slack_max=0,  # null capacity slack
    vehicle_capacities=data['vehicle_capacities_energy'],  # vehicle maximum capacities
    fix_start_cumul_to_zero=True,
    name="Energy")

# Define pickup and delivery constraints
for request in data['pickups_deliveries']:
    pickup_index = manager.NodeToIndex(request[0])
    delivery_index = manager.NodeToIndex(request[1])
    routing.AddPickupAndDelivery(pickup_index, delivery_index)
    solver.Add(
        routing.VehicleVar(pickup_index) ==
        routing.VehicleVar(delivery_index))
    solver.Add(
        distance_dimension.CumulVar(pickup_index) <=
        distance_dimension.CumulVar(delivery_index))

# Allow dropping of nodes.
for node in range(data['num_nodes']):
    if (node not in data['starts']) and (node not in data['ends']):
        # Nodes that exist only for optional charging may be dropped without penalty.
        if node in data['charging_stops']:
            routing.AddDisjunction([manager.NodeToIndex(node), 0])
        else:
            routing.AddDisjunction([manager.NodeToIndex(node)], 10000000)

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.local_search_metaheuristic = (
    routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 30
search_parameters.solution_limit = 3
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC)

solution = routing.SolveWithParameters(search_parameters)

if solution:
    print_solution(data, manager, routing, solution)
else:
    print('No solution found !')



Source: https://stackoverflow.com/questions/70602988/google-or-tools-pickup-deliveries-with-optional-nodes-for-refueling

A helper package for Go Telegram Client, i.e. gotd/td

SPFX with ChartJS v3 Property ‘datasets’ is missing in type ‘{}’ but required in type ‘ChartData<"bar", number[], unknown>