Random (seeded) CVRP solver

vrp_solver.py

import random
import sys

from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

verbose = True
time_limit_ms = 60000
seed = 19
random.seed(seed)


# # Basic functions
def r(l, h, t):
    return [random.randint(l, h) for _ in range(t)]


def create_data():
    min_coord = 0
    max_coord = 5000

    locations_num = 1000

    location_min_capacity = -10
    location_max_capacity = 10

    vehicles_num = 25

    vehicle_min_capacity = 100
    vehicle_max_capacity = 120

    vehicle_min_after_cost = 1
    vehicle_max_after_cost = 5

    vehicle_min_time_limit = 18000
    vehicle_max_time_limit = 27000

    depot = 0

    depot_location = [max_coord // 2, max_coord // 2]
    locations = [depot_location] + [r(min_coord, max_coord, 2) for _ in range(locations_num)]
    locations_capacity = [0] + r(location_min_capacity, location_max_capacity, locations_num)

    vehicles_capacity = r(vehicle_min_capacity, vehicle_max_capacity, vehicles_num)
    vehicles_after_cost = r(vehicle_min_after_cost, vehicle_max_after_cost, vehicles_num)
    vehicles_time_limit = r(vehicle_min_time_limit, vehicle_max_time_limit, vehicles_num)

    return (depot, locations, locations_capacity, vehicles_capacity,
            vehicles_after_cost, vehicles_time_limit)


def manhattan_distance(x1, y1, x2, y2):
    dist = abs(x1 - x2) + abs(y1 - y2)
    return dist


# # Callbacks
# Create callback to calculate cost between points (we'll use the manhattan distance on this example, but the cost will be time)
class CreateCostCallback(object):

    def __init__(self, locations):
        size = len(locations)
        self.matrix = {}

        for from_node in range(size):
            self.matrix[from_node] = {}
            for to_node in range(size):
                x1 = locations[from_node][0]
                y1 = locations[from_node][1]
                x2 = locations[to_node][0]
                y2 = locations[to_node][1]
                self.matrix[from_node][to_node] = manhattan_distance(x1, y1,
                                                                     x2, y2)

    def calculate(self, from_node, to_node):
        return int(self.matrix[from_node][to_node])


# Create callback to calculate cost of deliver and/or pickup in a stop
class CreateAfterCostCallback(object):

    def __init__(self, vehicles_after_cost):
        self.vehicles_after_cost = vehicles_after_cost
        self.matrix = {}

    def calculate(self, to_node, vehicle):
        if to_node == 0:
            return 0
        else:
            return self.vehicles_after_cost[vehicle]


# Capacity callback
class CreateCapacityCallback(object):

    def __init__(self, capacity):
        self.matrix = capacity

    def calculate(self, from_node, to_node):
        return self.matrix[from_node]


# # Configuring model
# Create the data
(depot, locations, locations_capacity, vehicles_capacity,
 vehicles_after_cost, vehicles_time_limit) = create_data()
locations_num = len(locations)
vehicles_num = len(vehicles_capacity)

# Create routing model
if locations_num <= 0 or vehicles_num <= 0:
    print('Specify instances greater than 0')
    sys.exit(1)

routing = pywrapcp.RoutingModel(locations_num, vehicles_num, depot)

# Callback to the cost and time function
cost_between_locations = CreateCostCallback(locations)
cost_callback = cost_between_locations.calculate

cost_after_lcoations = CreateAfterCostCallback(vehicles_after_cost)
cost_after_callback = cost_after_lcoations.calculate

vehicle_cost_callbacks = [lambda i, j: cost_callback(i, j) + cost_after_callback(j, vehicle) for vehicle in range(vehicles_num)]
for vehicle in range(vehicles_num):
    routing.SetArcCostEvaluatorOfVehicle(vehicle_cost_callbacks[vehicle], vehicle)

# Adding time dimension
slack_max_time = min(vehicles_time_limit)
fix_start_cumul_to_zero_time = True

time = 'Time'
routing.AddDimensionWithVehicleTransitAndCapacity(
    vehicle_cost_callbacks, slack_max_time, vehicles_time_limit,
    fix_start_cumul_to_zero_time, time)

# Adding capacity dimension per vehicle
slack_max_capacity = max(vehicles_capacity)
fix_start_cumul_to_zero_capacity = False

capacity_at_locations = CreateCapacityCallback(locations_capacity)
capacity_callback = capacity_at_locations.calculate

capacity = 'Capacity'
routing.AddDimensionWithVehicleCapacity(
    capacity_callback, slack_max_capacity, vehicles_capacity,
    fix_start_cumul_to_zero_capacity, capacity)


# # Basic configuration
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.local_search_operators.use_relocate_neighbors = True
# search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_INSERTION
search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.OBJECTIVE_TABU_SEARCH
search_parameters.time_limit_ms = time_limit_ms

# # Solving
assignment = routing.SolveWithParameters(search_parameters)

if not assignment:
    print('No solution found')
    sys.exit(1)

# # Printing
vehicles_used = 0
total_used_cost = 0
total_used_vehicles_time_limit = 0

vehicles_with_over_cost = {}
vehicles_with_over_capacity = {}

for vehicle_i in range(vehicles_num):
    if not routing.IsVehicleUsed(assignment, vehicle_i):
        continue

    vehicles_used += 1
    total_used_vehicles_time_limit += vehicles_time_limit[vehicle_i]

    index = routing.Start(vehicle_i)
    index_next = assignment.Value(routing.NextVar(index))
    route = ''
    route_cost = 0
    route_capacity = 0
    route_list = []

    while not routing.IsEnd(index_next):
        node_index = routing.IndexToNode(index)
        node_index_next = routing.IndexToNode(index_next)
        route += '{0}, '.format(node_index)  # '{0} -> '.format(node_index)
        route_list.append(node_index)
        # Add the cost to the next node
        # route_cost += cost_callback(node_index, node_index_next)
        route_cost += vehicle_cost_callbacks[vehicle_i](node_index, node_index_next)
        # Add capacity
        route_capacity += capacity_callback(node_index, node_index_next)
        index = index_next
        index_next = assignment.Value(routing.NextVar(index))

    node_index = routing.IndexToNode(index)
    node_index_next = routing.IndexToNode(index_next)
    route += '{0}, {1}'.format(node_index, node_index_next)  # '{0} -> {1}'.format(node_index, node_index_next)
    route_list.append(node_index)
    route_list.append(node_index_next)
    route_cost += cost_callback(node_index, node_index_next)
    route_capacity += capacity_callback(node_index, node_index_next)
    total_used_cost += route_cost

    if verbose:
        print('Vehicle {0}'.format(vehicle_i))
        print('###############################')
        print(route)
        print('Maxs: cost = {0}, capacity = {1}'.format(vehicles_time_limit[vehicle_i], vehicles_capacity[vehicle_i]))
        print()  # Jump

        print('Cost')
        print(route_cost)
        print('{0} >= {1} {2}'.format(vehicles_time_limit[vehicle_i], route_cost, vehicles_time_limit[vehicle_i] >= route_cost))
        print()

        print('Capacity')
        _d = {-1: 0}
        cumul_capacity_list = [_d.setdefault(idx, _d[idx - 1] + item) for idx, item in enumerate([locations_capacity[j] for j in route_list])]
        real_used_capacity = max(cumul_capacity_list) - min(cumul_capacity_list)

        print([locations_capacity[j] for j in route_list])
        print(cumul_capacity_list)
        print(real_used_capacity)
        print('{0} >= {1} {2}'.format(vehicles_capacity[vehicle_i], real_used_capacity, vehicles_capacity[vehicle_i] >= real_used_capacity))
        print()

        print()  # Jump

        if not vehicles_time_limit[vehicle_i] >= route_cost:
            vehicles_with_over_cost[vehicle_i] = '{0} >= {1}'.format(vehicles_time_limit[vehicle_i], route_cost)

        if not vehicles_capacity[vehicle_i] >= real_used_capacity:
            vehicles_with_over_capacity[vehicle_i] = '{0} >= {1}'.format(vehicles_capacity[vehicle_i], real_used_capacity)

print('Vehicles used {0}/{1} - Total cost: {2}/{3}/{4}'.format(vehicles_used, vehicles_num, total_used_cost, total_used_vehicles_time_limit, sum(vehicles_time_limit)))
print('##############################################################')
print()  # Jump

print('Over cost:')
for k, v in vehicles_with_over_cost.items():
    print('Vehicle {0}: {1}'.format(k, v))

print()  # Jump

print('Over capacity:')
for k, v in vehicles_with_over_capacity.items():
    print('Vehicle {0}: {1}'.format(k, v))