psing

psing.py

#!/usr/bin/env python3
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

time_mat = [
    [
        0, 998, 940, 336, 4003, 2039, 1786, 791, 651, 1027, 470, 1143, 761,
        1390, 118, 3525
    ],
    [
        961, 0, 2160, 810, 3066, 1102, 2932, 1761, 1605, 2342, 774, 2154, 1948,
        2562, 865, 2588
    ],
    [
        926, 2322, 0, 1487, 5083, 3118, 995, 1164, 322, 145, 1590, 525, 195,
        599, 1035, 4605
    ],
    [
        359, 989, 1414, 0, 3751, 1786, 2186, 1015, 1002, 1597, 227, 1408, 1202,
        1817, 262, 3273
    ],
    [
        4044, 3030, 4963, 3750, 0, 3043, 5735, 4564, 4635, 5145, 3577, 4957,
        4751, 5365, 3947, 511
    ],
    [
        2071, 1057, 2990, 1777, 3029, 0, 3762, 2591, 2662, 3173, 1604, 2984,
        2778, 3393, 1974, 2551
    ],
    [
        1907, 2942, 931, 2107, 5703, 3738, 0, 1784, 1167, 745, 2210, 1145,
        1040, 326, 2053, 5225
    ],
    [
        798, 1830, 1174, 996, 4592, 2627, 1799, 0, 885, 1209, 1099, 645, 995,
        1295, 907, 4114
    ],
    [
        639, 1837, 364, 1003, 4598, 2634, 1210, 874, 0, 450, 1106, 740, 185,
        813, 748, 4120
    ],
    [
        1047, 2277, 189, 1442, 5038, 3073, 781, 1119, 443, 0, 1545, 480, 316,
        549, 1388, 4560
    ],
    [
        468, 790, 1507, 252, 3551, 1586, 2279, 1108, 1179, 1689, 0, 1501, 1295,
        1910, 371, 3073
    ],
    [
        1160, 2195, 632, 1360, 4956, 2991, 1163, 604, 615, 573, 1463, 0, 541,
        793, 1306, 4478
    ],
    [
        763, 1961, 210, 1127, 4722, 2758, 1052, 998, 159, 293, 1230, 582, 0,
        656, 871, 4244
    ],
    [
        1410, 2617, 635, 1783, 5379, 3414, 309, 1311, 806, 558, 1886, 821, 679,
        0, 1729, 4901
    ],
    [
        97, 939, 1030, 277, 3945, 1980, 1876, 881, 741, 1117, 411, 1233, 851,
        1480, 0, 3467
    ],
    [
        3560, 2546, 4479, 3267, 507, 2559, 5251, 4080, 4152, 4662, 3093, 4473,
        4267, 4882, 3463, 0
    ],
]

demand_new = [
    00000,
    100000,
    200000,
    900000,
    100000,
    200000,
    600000,
    1000000,
    400000,
    500000,
    600000,
    1900000,
    100000,
    500000,
    500000,
    800000,
]

vehicle_cap = [
    50000000,
    50000000,
    50000000,
    50000000,
    50000000,
]


def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data['time_matrix'] = time_mat
    data['demands'] = demand_new
    data['vehicle_capacities'] = vehicle_cap
    data['num_vehicles'] = 5
    data['depot'] = 0
    assert len(data['time_matrix']) == len(data["demands"])
    assert len(data['vehicle_capacities']) == data["num_vehicles"]
    return data


def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    time_dimension = routing.GetDimensionOrDie('Time')
    load_dimension = routing.GetDimensionOrDie('Capacity')
    total_time = 0
    for vehicle_id in range(manager.GetNumberOfVehicles()):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        while not routing.IsEnd(index):
            node = manager.IndexToNode(index)
            time_var = time_dimension.CumulVar(index)
            plan_output += f'{node} [{solution.Min(time_var)}, {solution.Max(time_var)}] -> '
            index = solution.Value(routing.NextVar(index))
        node = manager.IndexToNode(index)
        time_var = time_dimension.CumulVar(index)
        plan_output += f'{node} {solution.Min(time_var)}\n'
        plan_output += 'Time of the route: {}min\n'.format(solution.Min(time_var))
        print(plan_output)
        total_time += solution.Min(time_var)
    print('Total time of all routes: {}min'.format(total_time))


def main():
    """Solve the VRP with time windows."""
    # Instantiate the data problem.
    data = create_data_model()

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

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

    # Add Capacity constraint.
    def demand_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        value = data['demands'][from_node]
        #print(f'Load({from_node}): {value}')
        return value

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)

    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        data['vehicle_capacities'],  # vehicle maximum capacities
        True,  # start cumul to zero
        'Capacity')

    # Create and register a transit callback.
    def time_callback(from_index, to_index):
        """Returns the travel time between the two nodes."""
        # Convert from routing variable Index to time matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        value =  data['time_matrix'][from_node][to_node]
        #print(f'Time({from_node},{to_node}): {value}')
        return 1800 + value

    transit_callback_index = routing.RegisterTransitCallback(time_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Time Windows constraint.
    time = 'Time'
    routing.AddDimension(
        transit_callback_index,
        0,  # allow waiting time
        28800,  # maximum time per vehicle
        False,  # Don't force start cumul to zero.
        time)
    time_dimension = routing.GetDimensionOrDie(time)
    # Add time window constraints for each location except depot.
    """for location_idx, time_window in enumerate(data['time_windows']):
        if location_idx == data['depot']:
            continue
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
    # Add time window constraints for each vehicle start node.
    depot_idx = data['depot']
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        time_dimension.CumulVar(index).SetRange(
            data['time_windows'][depot_idx][0],
            data['time_windows'][depot_idx][1])"""

    # Instantiate route start and end times to produce feasible times.
    for i in range(data['num_vehicles']):
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.Start(i)))
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.End(i)))

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
#    search_parameters.time_limit.seconds = 30
    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.log_search = True
    search_parameters.time_limit.FromSeconds(10)

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(manager, routing, solution)
    else:
        print('No solution found!')


if __name__ == '__main__':
    main()

zz.md

Output:

$ python3 psing.py
Objective: 44262
Route for vehicle 0:
0 [0, 0] -> 0 1800
Time of the route: 1800min

Route for vehicle 1:
0 [0, 0] -> 0 1800
Time of the route: 1800min

Route for vehicle 2:
0 [0, 0] -> 0 1800
Time of the route: 1800min

Route for vehicle 3:
0 [0, 0] -> 7 [2591, 2591] -> 11 [5036, 5036] -> 13 [7629, 7629] -> 6 [9738, 9738] -> 9 [12283, 12283] -> 2 [14272, 14272] -> 12 [16267, 16267] -> 8 [18226, 18226] -> 0 20665
Time of the route: 20665min

Route for vehicle 4:
0 [0, 0] -> 3 [2136, 2136] -> 10 [4163, 4163] -> 5 [7549, 7549] -> 4 [12378, 12378] -> 15 [14689, 14689] -> 1 [19035, 19035] -> 14 [21700, 21700] -> 0 23597
Time of the route: 23597min

Total time of all routes: 49662min