Nearest neighbor, two opt, iterated local search on two opt, simulated annealing on two opt

heuristicsMetaheuristicsForVRP.py

import math, random, networkx
from matplotlib import pyplot


def getData():
    data = {}
    data["locationList"] = ["Depot", "loc1", "loc2", "loc3", "loc4", "loc5", "loc6", "loc7", "loc8", "loc9", "loc10"]
    data["travelMatrix"] = {'Depot': {'Depot': 0, 'loc1': 35, 'loc2': 10, 'loc3': 15, 'loc4': 23, 'loc5': 20, 'loc6': 34, 'loc7': 3, 'loc8': 37, 'loc9': 12, "loc10": 20},
                            'loc1': {'Depot': 35, 'loc1': 0, 'loc2': 25, 'loc3': 22, 'loc4': 12, 'loc5': 18, 'loc6': 14, 'loc7': 37, 'loc8': 6, 'loc9': 23, "loc10": 20},
                            'loc2': {'Depot': 10, 'loc1': 25, 'loc2': 0, 'loc3': 5, 'loc4': 13, 'loc5': 11, 'loc6': 25, 'loc7': 12, 'loc8': 27, 'loc9': 4, "loc10": 13},
                            'loc3': {'Depot': 15, 'loc1': 22, 'loc2': 5, 'loc3': 0, 'loc4': 10, 'loc5': 12, 'loc6': 20, 'loc7': 16, 'loc8': 23, 'loc9': 7, "loc10": 15},
                            'loc4': {'Depot': 23, 'loc1': 12, 'loc2': 13, 'loc3': 10, 'loc4': 0, 'loc5': 9, 'loc6': 15, 'loc7': 25, 'loc8': 14, 'loc9': 11, "loc10": 13},
                            'loc5': {'Depot': 20, 'loc1': 18, 'loc2': 11, 'loc3': 12, 'loc4': 9, 'loc5': 0, 'loc6': 24, 'loc7': 22, 'loc8': 25, 'loc9': 8, "loc10": 3},
                            'loc6': {'Depot': 34, 'loc1': 14, 'loc2': 25, 'loc3': 20, 'loc4': 15, 'loc5': 24, 'loc6': 0, 'loc7': 36, 'loc8': 10, 'loc9': 25, "loc10": 27},
                            'loc7': {'Depot': 3, 'loc1': 37, 'loc2': 12, 'loc3': 16, 'loc4': 25, 'loc5': 22, 'loc6': 36, 'loc7': 0, 'loc8': 39, 'loc9': 15, "loc10": 23},
                            'loc8': {'Depot': 37, 'loc1': 6, 'loc2': 27, 'loc3': 23, 'loc4': 14, 'loc5': 25, 'loc6': 10, 'loc7': 39, 'loc8': 0, 'loc9': 25, "loc10": 24},
                            'loc9': {'Depot': 12, 'loc1': 23, 'loc2': 4, 'loc3': 7, 'loc4': 11, 'loc5': 8, 'loc6': 25, 'loc7': 15, 'loc8': 25, 'loc9': 0, "loc10": 10},
                            "loc10": {'Depot': 20, 'loc1': 20, 'loc2': 13, 'loc3': 15, 'loc4': 13, 'loc5': 3, 'loc6': 27, 'loc7': 23, 'loc8': 24, 'loc9': 10, "loc10": 0}}
    data['numberOfVehicles'] = 2
    data["numberOfLocations"] = len(data["locationList"])
    data["maxTravelTimePerVehicle"] = 100
    data['depotLocation'] = "Depot"
    return data



def getNearestLoc(unvisited, currentLoc, data):

    nearestLoc, nearestTravelTime = None, 1e7
    for nextLoc in unvisited:
        if data["travelMatrix"][currentLoc][nextLoc] < nearestTravelTime:
            nearestTravelTime = data["travelMatrix"][currentLoc][nextLoc]
            nearestLoc = nextLoc

    return nearestLoc



def findTspRouteUsingNearestNeighbor(data):

    unvisited = {loc for loc in data["locationList"] if loc!= data["depotLocation"]}
    currentLoc = data["depotLocation"]
    route = [currentLoc]

    while unvisited:
        nearestLoc = getNearestLoc(unvisited, currentLoc, data)
        unvisited.remove(nearestLoc)
        route.append(nearestLoc)
        currentLoc = nearestLoc

    route.append(data["depotLocation"])
    print("Tsp route:", route)
    return route



def createRoutesForVehicles(tspRoute, data):

    depot = data["depotLocation"]
    currentTravelTime = 0
    previousLoc = depot
    routes = []
    route = [previousLoc]

    for currentLoc in tspRoute[1:-1]:
        currentTravelTime += data["travelMatrix"][previousLoc][currentLoc]
        if currentTravelTime + data["travelMatrix"][currentLoc][depot] <= data["maxTravelTimePerVehicle"]:
            route.append(currentLoc)
            previousLoc = currentLoc
        else:
            route.append(depot)
            routes.append(route)
            route = [depot, currentLoc]
            currentTravelTime = data["travelMatrix"][depot][currentLoc]

    route.append(depot)
    routes.append(route)
    print("Algorithm1 - Routes for vehicles:", routes, "\n")
    return routes




def findRoutesForVehiclesUsingNearestNeighborAlgorithm1(data):
    tspRoute = findTspRouteUsingNearestNeighbor(data)
    routes = createRoutesForVehicles(tspRoute, data)
    return routes




def findRoutesForVehiclesUsingNearestNeighborAlgorithm2(data):

    routes = []
    depot = data["depotLocation"]
    unvisited = {loc for loc in data["locationList"] if loc!= depot}
    currentLoc = depot
    route = [currentLoc]
    currentTravelTime = 0

    while unvisited:
        nearestLoc = getNearestLoc(unvisited, currentLoc, data)
        nearestTravelTime = data["travelMatrix"][currentLoc][nearestLoc]

        if currentTravelTime + nearestTravelTime + data["travelMatrix"][nearestLoc][depot] <= data["maxTravelTimePerVehicle"]:
            currentTravelTime += nearestTravelTime
            unvisited.remove(nearestLoc)
            route.append(nearestLoc)
            currentLoc = nearestLoc
        else:
            route.append(depot)
            routes.append(route)
            route = [depot]
            currentLoc = depot
            currentTravelTime = 0

    route.append(depot)
    routes.append(route)
    print("Algorithm2 - Routes for vehicles:", routes, "\n")
    return routes




def printTotalCost(routes, data, algorithmName):

    totalCost = 0
    for route in routes:
        for i in range(len(route)-1):
            fromLoc, toLoc = route[i], route[i+1]
            totalCost += data["travelMatrix"][fromLoc][toLoc]

    print(f"Total cost using {algorithmName}: {totalCost}")




################################################################
                  # TWO OPT #
################################################################




def twoOptSwap(route, index1, index2):
    newRoute = route[:index1] + route[index2:index1-1:-1] + route[index2+1:]
    return newRoute



def isMaxTravelTimeConstraintSatisfied(newRoute, lengthOfRoute, data):
    totalTravelTime = 0
    for i in range(lengthOfRoute-1):
        fromLoc, toLoc = newRoute[i], newRoute[i+1]
        totalTravelTime += data["travelMatrix"][fromLoc][toLoc]

    if totalTravelTime > data["maxTravelTimePerVehicle"]:
        return False
    return True



def getTotalCost(route, lengthOfRoute, data):
    totalTravelTime = 0
    for i in range(lengthOfRoute - 1):
        fromLoc, toLoc = route[i], route[i + 1]
        totalTravelTime += data["travelMatrix"][fromLoc][toLoc]
    return totalTravelTime




def performTwoOpt(route, data, nodePositionForGraphVisualization=None):

    lengthOfRoute = len(route)
    bestCost = getTotalCost(route, lengthOfRoute, data)
    hasImproved = True

    while hasImproved:
        hasImproved = False

        for i in range(1, lengthOfRoute-2):
            for j in range(i+1, lengthOfRoute-1):
                newRoute = twoOptSwap(route, i, j)
                visualizeRoute(route, newRoute, lengthOfRoute, nodePositionForGraphVisualization)

                if isMaxTravelTimeConstraintSatisfied(newRoute, lengthOfRoute, data):
                    costOfNewRoute = getTotalCost(newRoute, lengthOfRoute, data)
                    if costOfNewRoute < bestCost:
                        bestCost = costOfNewRoute
                        route = newRoute
                        hasImproved = True

    print("Best cost found:", bestCost)
    print("Best route found:", route)
    return route, bestCost




def visualizeRoute(route, newRoute, lengthOfRoute, nodePositionForGraphVisualization):
    print(newRoute)

    if nodePositionForGraphVisualization != None:
        pyplot.close()
        graph1 = networkx.DiGraph()
        graph2 = networkx.DiGraph()
        for i in range(lengthOfRoute-1):
            graph1.add_edge(route[i], route[i+1])
            graph2.add_edge(newRoute[i], newRoute[i+1])
        labels = {k:k for k,v in nodePositionForGraphVisualization.items()}

        pyplot.figure(1)
        pyplot.subplot(211)
        pyplot.xlabel("Route")
        networkx.draw_networkx_nodes(graph1, pos=nodePositionForGraphVisualization, node_color="red")
        networkx.draw_networkx_edges(graph1, pos=nodePositionForGraphVisualization, connectionstyle="arc3,rad=0.2")
        networkx.draw_networkx_labels(graph1, pos=nodePositionForGraphVisualization, labels=labels, font_size=7)

        pyplot.subplot(212)
        pyplot.xlabel("Route after 2-edges swapped")
        networkx.draw_networkx_nodes(graph2, pos=nodePositionForGraphVisualization, node_color="red")
        networkx.draw_networkx_edges(graph2, pos=nodePositionForGraphVisualization, connectionstyle="arc3,rad=0.2")
        networkx.draw_networkx_labels(graph2, pos=nodePositionForGraphVisualization, labels=labels, font_size=7)

        pyplot.savefig(str(newRoute)+".png")




def createPositionForGraphVisualization(route):
    nodePositionForGraph = {}
    nodePositionForGraph[route[0]] = (0,0)
    for i in range(len(route)):
        nodePositionForGraph[route[i]] = (i,i)
    return nodePositionForGraph




################################################################
                  # ITERATED LOCAL SEARCH #
################################################################




def generateNewRoute(route, lengthOfRoute, data):
    MAX_SHUFFLES = 10000
    print("Generating new route by shuffling. Checking if satisfies constraint. If not shuffling again...")

    for i in range(MAX_SHUFFLES):
        shuffledRouteWithoutDepot = route[1:-1]
        random.shuffle(shuffledRouteWithoutDepot)
        route = [data["depotLocation"]] + shuffledRouteWithoutDepot + [data["depotLocation"]]
        if isMaxTravelTimeConstraintSatisfied(route, lengthOfRoute, data):
            print("Shuffled route satisfies constraint")
            return True
    print(f"Shuffled {MAX_SHUFFLES} times but couldn't find solution. Terminating...")
    return False




def iteratedLocalSearchOnTwoOpt(route, data):

    MAX_SEARCHES = 4
    bestRoute = route
    lengthOfRoute = len(route)
    bestCost = getTotalCost(route, lengthOfRoute, data)

    for i in range(MAX_SEARCHES):
        print(f"Iteration: {i}")
        newRoute, newCost = performTwoOpt(route, data)
        if newCost < bestCost:
            bestCost = newCost
            bestRoute = newRoute

        isSuccessful = generateNewRoute(route, lengthOfRoute, data)
        if not isSuccessful:
            break

    print(f"Best route found after {MAX_SEARCHES} restarts: \n{bestRoute}, cost: {bestCost}")




################################################################
                  # SIMULATED ANNEALING #
################################################################




def twoOptMetropolis(route, cost, lengthOfRoute, temperature):

    MAX_TRIALS = 1000

    for trial in range(MAX_TRIALS):
        i = random.randint(1, lengthOfRoute-3)
        j = random.randint(i+1, lengthOfRoute-2)

        newRoute = twoOptSwap(route, i, j)
        if isMaxTravelTimeConstraintSatisfied(newRoute, lengthOfRoute, data):
            costOfNewRoute = getTotalCost(newRoute, lengthOfRoute, data)
            if (costOfNewRoute < cost) or (math.exp(-(costOfNewRoute - cost) / temperature) > random.random()):
                cost = costOfNewRoute
                route = newRoute

    return route, cost




def simulatedAnnealingOnTwoOpt(route, data):

    temperature = 1000
    MAX_SEARCHES = 1000
    COOLING_RATE = 0.1

    lengthOfRoute = len(route)
    bestRoute = route
    bestCost = getTotalCost(route, lengthOfRoute, data)
    cost = bestCost

    for i in range(MAX_SEARCHES):
        route, cost = twoOptMetropolis(route, cost, lengthOfRoute, temperature)
        if cost < bestCost:
            bestRoute = route
            bestCost = cost

        temperature *= COOLING_RATE
        if temperature == 0:
            break

    print("Best cost found after simulated annealing:", bestCost)
    print("Best route found after simulated annealing:", bestRoute)




if __name__ == '__main__':

    random.seed(0)
    data = getData()
    routesAlgorithm1 = findRoutesForVehiclesUsingNearestNeighborAlgorithm1(data)
    routesAlgorithm2 = findRoutesForVehiclesUsingNearestNeighborAlgorithm2(data)

    printTotalCost(routesAlgorithm1, data, "algorithm1")
    printTotalCost(routesAlgorithm2, data, "algorithm2")

    if len(routesAlgorithm2) > data["numberOfVehicles"]:
        print(f'Not enough vehicles. Need {len(routesAlgorithm2) - data["numberOfVehicles"]} more vehicle')

    route = ['Depot', 'loc6', 'loc8', 'loc1', 'Depot']
    nodePositionForGraphVisualization = createPositionForGraphVisualization(route)
    performTwoOpt(route, data, nodePositionForGraphVisualization)
    iteratedLocalSearchOnTwoOpt(route, data)
    simulatedAnnealingOnTwoOpt(route, data)