Optimizing Vehicle Routing Problem with Time Windows using Constraint Programming & Metaheuristics. Uses Google OR tools. -- Finds very good solution for large problem in seconds. Check https://developers.google.com/optimization/reference/constraint_solver/routing/RoutingModel/, https://developers.google.com/optimization/reference/constraint_sol…

0CP_VRPTW.py

"""Capacitated Vehicle Routing Problem with Time Windows (CVRPTW).
"""
import csv
import math
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2


"""Check https://developers.google.com/optimization/reference/constraint_solver/routing/RoutingModel/, 
https://developers.google.com/optimization/reference/constraint_solver/routing/RoutingDimension/, 
and https://developers.google.com/optimization/reference/constraint_solver/constraint_solver/Solver/ 
for more features. Check their examples in c++ (more number of examples) and python at 
https://github.com/google/or-tools/tree/master/examples.""" 



###^#####################  PARAMETERS, COSTS, AND SWITCHES  ###############################################
####^####################                           ###############################################



SOLVERTIMER = 30  # in seconds

NumberOfLocations = 100      # excluding depot 0. Need to change this /!\

NumberOfVehicles = 70


# --CAPACITY OF VEHICLE PARAMETERS

CapacityOfVehicles = 75                         # ignore if SameCapacityORDifferentCapacities = 1

CapacitiesOfVehicles = [75, 50, 60, 30, 50]     # ignore if SameCapacityORDifferentCapacities = 0


# --DEPOT PARAMETERS

depot = 0                                       # ignore if SingleDepotORMultipleStartEndLocations = 1

startLocations = [1, 2, 1, 2, 1]                # ignore if SingleDepotORMultipleStartEndLocations = 0

endLocations = [1, 2, 1, 2, 1]                  # ignore if SingleDepotORMultipleStartEndLocations = 0


# --RESOURCE AT DEPOT PARAMETERS

VehicleLoadTime = 1                                          # ignore if ResourceConstraintAtDepot = 0

VehicleUnloadTime = 1                                        # ignore if ResourceConstraintAtDepot = 0

DepotCapacity = 2                                            # space available in depot, ignore if ResourceConstraintAtDepot = 0

DepotUsage = [1, 1, 1, 1, 1]                  # space each vehicle takes when loading & unloading, ignore if ResourceConstraintAtDepot = 0


MinimizeMaxOfDistanceTraveledCOST = 50                       # ignore if MinimizeMaxOfDistanceTraveled = 0

MaxDistanceVehicleTravel = 12                                # ignore if MinimizeMaxOfDistanceTraveled = 0


MinimizeNumberOfVehiclesCOST = 10                            # ignore if MinimizeNumberOfVehicles = 0, and SameVehicleCostORDifferentCosts = 1

MinimizeNumberOfVehiclesDiffCOSTS = [10, 10, 15, 20, 10]     # ignore if MinimizeNumberOfVehicles = 0, and SameVehicleCostORDifferentCosts = 0


CustomersCanBeSkippedWithPenaltyCOST = 100                   # ignore if CustomersCanBeSkippedWithPenalty = 0

VehicleReturnToDepotTime = 44                                # ignore if TimeWindowConstraint = 0

LimitEachVehicleDistance = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]    # ignore if LimitEachVehicleTravel = 0

RestBreakTime = [24, 28, 2]                                  # ignore if AllowVehicleToTakeBreak = 0 [startTimeMin, startTimeMax, duration]


InitialRoutes = [[1, 2, 5], [8, 3], [9, 6], [10, 4, 7], []]  # ignore if ResumeOptFromSolutionEntered is 0, length of it == NumberOfVehicles



#------------------------------------------------------------------------------------------------------
# APPLICATION SWITCHES (0 or 1)
#------------------------------------------------------------------------------------------------------


SingleDepotORMultipleStartEndLocations = 0          # 0 -> use single depot, 1 -> use multiple start-end locations

SameCapacityORDifferentCapacities = 0               # 0 -> use same capacity for all vehicles, 1 -> use different capacities

SameVehicleCostORDifferentCosts = 0                 # 0 -> use same cost for all vehicles, 1 -> use different costs

MinimizeTransitTimes = 1                            # 0 -> solver will not minimize travel times/transit, 1 -> solver will minimize transit

MinimizeMaxOfDistanceTraveled = 0                   # 0 -> solver will not try to minimize the max/highest distance traveled among vehicles

LimitEachVehicleTravel = 0                          # 0 -> there is no limit on how much dist. vehicle can travel, 1 -> limit dist. for each vehicle

MinimizeNumberOfVehicles = 1                        # 0 -> solver will not try to minimize the number of vehicles used, 1 -> minimize vehicles

CapacityConstraint = 1                              # 0 -> constraint is off, 1 -> constraint in on

TimeWindowConstraint = 1                            # 0 -> constraint is off, 1 -> constraint in on

ResourceConstraintAtDepot = 0                       # 0 -> constraint is off, 1 -> constraint in on

CustomersCanBeSkippedWithPenalty = 0                # 0 -> All customers must be served, 1 -> customer(s) can be skipped with penalty cost

AllowVehicleToTakeBreak = 0                         # 0 -> vehicles will not take lunch/rest break, 1 -> vehicles will take break

StoreSolutionToResumeOptLater = 0                   # 0 -> Does not store/print solution, 1 -> stores/print solution which can be used to resume optimization later

ResumeOptFromSolutionEntered = 0                    # 0 -> Starts optimization normally, 1 -> Starts optimization from the solution you have entered



##################################################################################################
##################################################################################################






#------------------------------------------------------------------------------------------------------
# GETTING & PREPARING DATA
#------------------------------------------------------------------------------------------------------



locations = list(range(NumberOfLocations + 1))

num_locations = len(locations)


if SingleDepotORMultipleStartEndLocations == 1:
    assert NumberOfVehicles == len(startLocations) == len(endLocations)  # Checks whether start and end locations are equal to number of vehicles


if SameCapacityORDifferentCapacities == 1:
    assert NumberOfVehicles == len(CapacitiesOfVehicles)        # check if capacity of vehicle information is available to every vehicle


if SameVehicleCostORDifferentCosts == 1:
    assert NumberOfVehicles == len(MinimizeNumberOfVehiclesDiffCOSTS)


if ResourceConstraintAtDepot == 1:
    assert NumberOfVehicles*2 == len(DepotUsage)


if ResumeOptFromSolutionEntered == 1:
    assert NumberOfVehicles == len(InitialRoutes)


if LimitEachVehicleTravel == 1:
    assert NumberOfVehicles == len(LimitEachVehicleDistance)



# -----------------------READING FROM TRAVEL TIMES DATA FILE AND STORING---------------------------


with open('travel_times.csv') as csvfile:
    data = list(csv.reader(csvfile))

travelTimes = {}
for i in range(1, NumberOfLocations + 1):
    for j in range(1, NumberOfLocations + 1):
        if data[j][i].isdigit() and i != j:
            travelTimes[(i, j)] = float(int(data[j][i]) / 10)
        elif data[j][i].isdigit() and i == j:
            travelTimes[(i, j)] = 0

# Addition of 0 as it is depot in this model.
for i in range(1, NumberOfLocations + 1):
    travelTimes[(0, i)] = 0
    travelTimes[(i, 0)] = 0

travelTimes[(0, 0)] = 0
# Addition of symmetrical travel times
for i in range(2, NumberOfLocations + 1):
    for j in range(1, i):
        travelTimes[(i, j)] = travelTimes[(j, i)]



# -----------------------READING FROM LOCATION DATA FILE AND STORING---------------------------


with open('location_data_CP.csv') as csvfile1:
    data1 = list(csv.reader(csvfile1))

time_windows = []
for i in range(1, NumberOfLocations + 2):
    time_windows.append((int(data1[i][6]), int(data1[i][7])))

serviceTimes = []
for i in range(1, NumberOfLocations + 2):
    serviceTimes.append(int(data1[i][9]))

demands = []
for i in range(1, NumberOfLocations + 2):
    demands.append(int(data1[i][1]))





#------------------------------------------------------------------------------------------------------
# FOR PRINTING THE RESULTS
#------------------------------------------------------------------------------------------------------



class ConsolePrinter():

    """Print solution to console"""
    def __init__(self, routing, assignment):
        """Initializes the printer"""
        self.routing = routing
        self.assignment = assignment

    def print(self):
        """Prints assignment on console"""
        # Inspect solution.
        capacity_dimension = self.routing.GetDimensionOrDie('Capacity')
        time_dimension = self.routing.GetDimensionOrDie('Time')
        total_dist = 0
        total_time = 0
        for vehicle_id in range(NumberOfVehicles):
            if self.routing.IsVehicleUsed(self.assignment, vehicle_id):
                index = self.routing.Start(vehicle_id)
                plan_output = 'Route for vehicle {0}:\n'.format(vehicle_id)
                route_dist = 0
                while not self.routing.IsEnd(index):
                    node_index = self.routing.IndexToNode(index)
                    next_node_index = self.routing.IndexToNode(
                        self.assignment.Value(self.routing.NextVar(index)))
                    route_dist += travelTimes[node_index, next_node_index]
                    load_var = capacity_dimension.CumulVar(index)
                    route_load = self.assignment.Value(load_var)
                    time_var = time_dimension.CumulVar(index)
                    time_min = self.assignment.Min(time_var)
                    time_max = self.assignment.Max(time_var)
                    slack_var = time_dimension.SlackVar(index)
                    slack_min = self.assignment.Min(slack_var)
                    slack_max = self.assignment.Max(slack_var)
                    plan_output += ' {0} Load({1}) Time({2},{3}) Slack({4},{5}) ->'.format(
                        node_index,
                        route_load,
                        time_min, time_max,
                        slack_min, slack_max)
                    index = self.assignment.Value(self.routing.NextVar(index))

                node_index = self.routing.IndexToNode(index)
                load_var = capacity_dimension.CumulVar(index)
                route_load = self.assignment.Value(load_var)
                time_var = time_dimension.CumulVar(index)
                route_time = self.assignment.Value(time_var)
                time_min = self.assignment.Min(time_var)
                time_max = self.assignment.Max(time_var)
                total_dist += route_dist
                total_time += route_time
                plan_output += ' {0} Load({1}) Time({2},{3})\n'.format(node_index, route_load, time_min, time_max)
                plan_output += 'Distance of the route: {0}m\n'.format(route_dist)
                plan_output += 'Load of the route: {0}\n'.format(route_load)
                plan_output += 'Time of the route: {0}min\n'.format(route_time)
                print(plan_output)
        print('Total Distance of all routes: {0}m'.format(total_dist))
        print('Total Time of all routes: {0}min'.format(total_time))


    def get_routes_array(self):
        # Get the routes for an assignment and return as a list of lists.
        routes = []
        for vehicle_id in range(NumberOfVehicles):
            if self.routing.IsVehicleUsed(self.assignment, vehicle_id):
                node = self.routing.Start(vehicle_id)
                route=[]

                while not self.routing.IsEnd(node):
                    index = self.routing.NodeToIndex(node)
                    if not (node == self.routing.Start(vehicle_id)):
                        route.append(index)
                        node = self.assignment.Value(self.routing.NextVar(node))
                    else:
                        node = self.assignment.Value(self.routing.NextVar(node))
                routes.append(route)
            else:
                continue
        return routes






# ------------------------------------------------------------------------------------------------------
# FUNCTIONS USED IN THE CONSTRAINTS/OBJECTIVE FUNCTIONS
# ------------------------------------------------------------------------------------------------------



def distance_evaluator(from_node, to_node):             # Need to change this for different data
    return travelTimes[from_node, to_node] * 10


def demand_evaluator(from_node, to_node):
    del to_node
    return demands[from_node]


def time_evaluator(from_node, to_node):
    return int(math.ceil(serviceTimes[from_node] + travelTimes[from_node, to_node]))




#------------------------------------------------------------------------------------------------------
# MAIN - THE PROGRAM STARTS FROM HERE
#------------------------------------------------------------------------------------------------------




def main():


    # Creating Routing Model
    if SingleDepotORMultipleStartEndLocations == 0:
        routing = pywrapcp.RoutingModel(num_locations, NumberOfVehicles, depot)

    elif SingleDepotORMultipleStartEndLocations == 1:
        routing = pywrapcp.RoutingModel(num_locations, NumberOfVehicles, startLocations, endLocations)




    # Set cost of each edge/arc in the objective function (for minimizing transit/travel times)
    if MinimizeTransitTimes == 1:
        routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)



    # Set cost for minimizing the max distance among vehicles in the objective function
    # /!\ It doesn't mean the standard deviation is minimized
    if MinimizeMaxOfDistanceTraveled == 1 or LimitEachVehicleTravel == 1:
        distance = "Distance"
        routing.AddDimension(distance_evaluator, 0, MaxDistanceVehicleTravel, True, distance)
        distance_dimension = routing.GetDimensionOrDie(distance)
        if MinimizeMaxOfDistanceTraveled == 1:
            distance_dimension.SetGlobalSpanCostCoefficient(MinimizeMaxOfDistanceTraveledCOST)
        if LimitEachVehicleTravel == 1:
            for vehicle in range(NumberOfVehicles):
                distance_dimension.SetSpanUpperBoundForVehicle(LimitEachVehicleDistance[vehicle], vehicle)



    # Set cost of each vehicle used in the objective function. This is used for minimizing the number of vehicle used.
    if MinimizeNumberOfVehicles == 1:
        if SameVehicleCostORDifferentCosts == 0:
            routing.SetFixedCostOfAllVehicles(MinimizeNumberOfVehiclesCOST)
        elif SameVehicleCostORDifferentCosts == 1:
            for vehicle in range(NumberOfVehicles):
                routing.SetVehicleFixedCost(vehicle, MinimizeNumberOfVehiclesDiffCOSTS[vehicle])



    # Constraint to ensure that vehicle capacity is satisfied
    if CapacityConstraint == 1:
        capacity = "Capacity"
        if SameCapacityORDifferentCapacities == 0:
            routing.AddDimension(demand_evaluator, 0, CapacityOfVehicles, True, capacity)
        elif SameCapacityORDifferentCapacities == 1:
            routing.AddDimensionWithVehicleCapacity(demand_evaluator, 0, CapacitiesOfVehicles, True, capacity)



    # Constraint to ensure that time windows are satisfied
    if TimeWindowConstraint == 1:
        time = "Time"
        routing.AddDimension(time_evaluator, VehicleReturnToDepotTime, VehicleReturnToDepotTime, False, time)

        time_dimension = routing.GetDimensionOrDie(time)
        for location_idx, time_window in enumerate(time_windows):
            if location_idx == 0:
                continue
            index = routing.NodeToIndex(location_idx)
            time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
            routing.AddToAssignment(time_dimension.SlackVar(index))

        for vehicle_id in range(NumberOfVehicles):
            index = routing.Start(vehicle_id)
            time_dimension.CumulVar(index).SetRange(time_windows[0][0], time_windows[0][1])
            routing.AddToAssignment(time_dimension.SlackVar(index))




    # Adding resource constraints at the depot (start and end location of routes).
    # Adding constraints that allow vehicle to take lunch/rest breaks.
    if ResourceConstraintAtDepot == 1 or AllowVehicleToTakeBreak == 1:

        solver = routing.solver()

        if ResourceConstraintAtDepot == 1:
            intervals = []
            for i in range(NumberOfVehicles):
                # Add time windows at start of routes
                intervals.append(solver.FixedDurationIntervalVar(routing.CumulVar(routing.Start(i), time), VehicleLoadTime, "depot_interval"))
                # Add time windows at end of routes.
                intervals.append(solver.FixedDurationIntervalVar(routing.CumulVar(routing.End(i), time), VehicleUnloadTime, "depot_interval"))

            # Constrain the number of maximum simultaneous intervals at depot.
            solver.AddConstraint(solver.Cumulative(intervals, DepotUsage, DepotCapacity, "depot"))

            # Instantiate route start and end times to produce feasible times.
            for i in range(NumberOfVehicles):
                routing.AddVariableMinimizedByFinalizer(routing.CumulVar(routing.End(i), time))
                routing.AddVariableMinimizedByFinalizer(routing.CumulVar(routing.Start(i), time))

        if AllowVehicleToTakeBreak == 1:
            for j in range(NumberOfVehicles):
                breakVar = [solver.FixedDurationIntervalVar(RestBreakTime[0], RestBreakTime[1], RestBreakTime[2], False, "break_interval")]

                time_dimension.SetBreakIntervalsOfVehicle(breakVar, j)




    # Can be used to skip locations. If a location is skipped, a penalty cost(100) is added to the objective function.
    if CustomersCanBeSkippedWithPenalty == 1:
        skipOrder = []
        skipOrder.append(0)
        for i in range(1,routing.nodes()):
            skipOrder[0] = i
            routing.AddDisjunction(skipOrder, CustomersCanBeSkippedWithPenaltyCOST)




# ------------------------------------------------------------------------------------------------------
# SOLVER PARAMETERS
# ------------------------------------------------------------------------------------------------------


    search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()

    search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH

    search_parameters.time_limit_ms = SOLVERTIMER * 1000


    # search_parameters.optimization_step(1)


    if ResumeOptFromSolutionEntered == 1:
        initialAssignment = routing.ReadAssignmentFromRoutes(InitialRoutes, True)

        print("******************Initial Assignment*****************: \n")

        initialPrinter = ConsolePrinter(routing, initialAssignment)
        initialPrinter.print()

        print("#################################################################################")
        print("\n**********************Final Assignment*****************: ")

        assignment = routing.SolveFromAssignmentWithParameters(initialAssignment, search_parameters)

    elif ResumeOptFromSolutionEntered == 0:
        # Setting first solution heuristic (cheapest addition).
        search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC

        # Solving the problem
        assignment = routing.SolveWithParameters(search_parameters)







# ------------------------------------------------------------------------------------------------------
# OTHERS
# ------------------------------------------------------------------------------------------------------


    print("Status of Optimization "
          "(0-Not Solved, 1-Solution Found,2-No Solution Found,"
          "3-No Solution found within time limit,"
          "4-Model Invalid): ", routing.status())

    print()

    printer = ConsolePrinter(routing, assignment)
    printer.print()


    print()
    count = 0
    for i in range(NumberOfVehicles):
        if routing.IsVehicleUsed(assignment,i):
            print("Vehicle:",i," is used")
            count += 1


    print()
    print("Total number of vehicles used: ", count)


    print()
    print("Objective Value :", assignment.ObjectiveValue())
    print()

    print("Number of locations unvisited: ", routing.GetNumberOfDisjunctions())
    print()

    # To print routes array which can be read later to find solutions. Need to store this to excel, etc /!\
    if StoreSolutionToResumeOptLater == 1:
        print("Routes which can be used to resume Optimization later:")
        print(printer.get_routes_array())



if __name__ == '__main__':
    main()

1location_data_CP.csv

2travel_times.csv