@ecotner VRPTW problem

ampmroutes.py

import time, re

from colorama import Fore, Back, Style
import numpy as np
from scipy.spatial.distance import pdist, squareform
from ortools.constraint_solver import pywrapcp, routing_enums_pb2

RNG_SEED = 42
PRECISION = 1_000

NUM_STOPS = 200
MEAN_DIST = 50 # "Kilometers"
NUM_VEHICLES = 10
NUM_MUST_RETURN = 2
VEHICLE_SPEED = 50 # "KPH"

MAX_TIME = 11 # "Hours" that we serve customers in.
EXTRA_TIME = 1 # Time at EOD that we wont schedule customers in.
DROP_PENALTY = 10000 * PRECISION

def color_substr(string, substr, color):
    start = getattr(Fore, color)
    end = Fore.RESET
    return re.sub(substr, start + substr + end, string)


def main():
    np.random.seed(RNG_SEED)
    locations = np.random.randn(NUM_STOPS + 1, 2)
    locations *= (MEAN_DIST / np.sqrt(2))
    locations[0] = (0, 0)

    # Set up routing manager/problem
    manager = pywrapcp.RoutingIndexManager(len(locations), NUM_VEHICLES, 0)
    routing = pywrapcp.RoutingModel(manager)

    D = squareform(pdist(locations))

    # Convert to integers
    D = (PRECISION * D).round().astype(int)

    def dist_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return int(D[from_node, to_node])


    def time_callback(from_index, to_index):
        return dist_callback(from_index, to_index) // VEHICLE_SPEED

    DIST_CALLBACK_IDX = routing.RegisterTransitCallback(dist_callback)
    TIME_CALLBACK_IDX = routing.RegisterTransitCallback(time_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(DIST_CALLBACK_IDX)

    MAX_TW = PRECISION * MAX_TIME
    EXTRA_TW = PRECISION * EXTRA_TIME

    FREE_VEH_IDX = slice(NUM_MUST_RETURN, NUM_VEHICLES)
    VEH_CAP = np.full(NUM_VEHICLES, MAX_TW // 2)
    VEH_CAP[FREE_VEH_IDX] = MAX_TW
    VEH_CAP += EXTRA_TW

    routing.AddDimensionWithVehicleCapacity(
        TIME_CALLBACK_IDX,
        int(MAX_TW),  # time slack
        VEH_CAP,  # Max travel distance per vehicle
        False,  # don't force start cumul to zero
        "Time",  # Name of the dimension
    )

    # Create customer time windows
    TW = np.random.uniform(size=(NUM_STOPS + 1, 2))
    TW = (MAX_TW * TW).round().astype(int)
    TW.sort(axis=1)
    

    # Apply windows
    time_dimension = routing.GetDimensionOrDie("Time")
    for loc_idx, tw in enumerate(TW):
        if loc_idx == 0:
            continue
        idx = manager.NodeToIndex(loc_idx) # Offset cuz depot
        routing.AddDisjunction([idx], DROP_PENALTY)
        time_dimension.CumulVar(idx).SetRange(int(tw[0]), int(tw[1]))

    # Minimize Global Time
    time_dimension.SetGlobalSpanCostCoefficient(1)
    
    #Solve
    search_params = pywrapcp.DefaultRoutingSearchParameters()
    search_params.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_params.time_limit.seconds = 90
    search_params.log_search = True
    tic = time.time()
    solution = routing.SolveWithParameters(search_params)
    toc = time.time()

    # Print Results
    print(
        [
            "ROUTING NOT SOLVED",
            "ROUTING SUCCESS",
            "ROUTING FAIL",
            "ROUTING FAIL TIMEOUT",
            "ROUTING INVALID",
        ][routing.status()]
    )
    print(f"{toc-tic:.1f} sec elapsed")
    stops = []
    for route_nr in range(NUM_VEHICLES):
        index = routing.Start(route_nr)
        node_idx = manager.IndexToNode(index)
        stops.append([node_idx])
        while not routing.IsEnd(index):
            prev_idx = index
            index = solution.Value(routing.NextVar(index))
            node_idx = manager.IndexToNode(index)
            stops[-1].append(node_idx)
    dept_idx = [0]
    cust_idx = list(range(1, NUM_STOPS + 1))
    drop_idx = []

    for node in range(routing.Size()):
        if routing.IsStart(node) or routing.IsEnd(node):
            continue
        if solution.Value(routing.NextVar(node)) == node:
            drop_idx += [manager.IndexToNode(node)]

    print("Depot:", dept_idx)
    print("Customers:", cust_idx)
    print("Dropped Nodes:", Fore.RED, drop_idx, Fore.RESET)
    print("Routes:")
    for i, route in enumerate(stops):
        print(f"\t{i}: {route}")    

if __name__ == "__main__":
    main()

SOLUTION

ROUTING SUCCESS
90.0 sec elapsed
Depot: [0]
Customers: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200]
Dropped Nodes:  [] 
Routes:
        0: [0, 37, 198, 67, 199, 92, 40, 172, 109, 12, 0]
        1: [0, 165, 177, 17, 61, 69, 111, 39, 96, 179, 77, 147, 90, 81, 128, 153, 182, 34, 144, 184, 166, 21, 178, 49, 0]
        2: [0, 145, 173, 31, 162, 47, 58, 99, 113, 16, 132, 11, 18, 6, 24, 60, 138, 139, 0]
        3: [0, 53, 186, 163, 106, 149, 82, 74, 48, 97, 140, 160, 52, 143, 107, 95, 112, 155, 33, 45, 181, 0]
        4: [0, 152, 57, 44, 4, 86, 183, 54, 159, 154, 158, 176, 167, 136, 157, 41, 187, 189, 110, 142, 133, 135, 141, 194, 0]
        5: [0, 185, 72, 29, 175, 35, 180, 32, 105, 121, 129, 103, 164, 151, 156, 27, 59, 126, 117, 78, 124, 10, 197, 93, 0]
        6: [0, 38, 169, 25, 171, 64, 116, 84, 123, 5, 190, 63, 19, 13, 79, 80, 114, 195, 137, 8, 98, 192, 120, 174, 108, 130, 66, 91, 119, 146, 26, 76, 170, 115, 134, 0]
        7: [0, 14, 46, 168, 28, 42, 150, 85, 102, 73, 9, 94, 51, 2, 0]
        8: [0, 100, 87, 70, 36, 56, 89, 104, 193, 83, 62, 101, 3, 43, 148, 188, 20, 75, 0]
        9: [0, 30, 68, 122, 50, 127, 55, 118, 131, 191, 7, 200, 22, 65, 71, 125, 15, 161, 196, 23, 88, 1, 0]