<jupyter_start><jupyter_text>Time Depentend Vehicle Routing Problem<jupyter_code>import osmnx as ox
import requests
import json
import networkx as nx
import numpy as np
import pandas as pd
G = ox.load_graphml('istanbulfull.graphml')
print('GraphML was read from file and Grahp was created.')<jupyter_output>GraphML was read from file and Grahp was created.<jupyter_text>Map information was taken with the overpass query.<jupyter_code># overpass_url = "http://overpass-api.de/api/interpreter"
# overpass_query = """
# [out:json];
# area["name"="Üsküdar"]->.a;
# (
#   node["tourism"~"viewpoint|theme_park|museum"]["name"](area.a);
#   node["historic"~"."]["name"](area.a);
#   node["natural"~"."]["name"](area.a);
# );

# out center;                                                                                                                       
# """

# response = requests.get(overpass_url,params={'data': overpass_query})
# data = response.json()

# with open('uskudar.json', 'w') as outfile:
#     json.dump(data, outfile)
#     print("POI list was written.")<jupyter_output><empty_output><jupyter_text>The downloaded information was read from the file.<jupyter_code>with open('uskudar.json', 'r') as f:
    data = json.load(f)
    print("POI list was read.")
#Information about all places read from the file.
all_places = [element for element in data['elements']]
print("Number of places: " + str(len(all_places)))<jupyter_output>Number of places: 15<jupyter_text>Distance matrix was created with Networkx and OSMNX.<jupyter_code>places = []
nearest_nodes = []
for place in all_places:
    point = (place["lat"],place["lon"])
    places.append(place["tags"]["name"])
    nearest = ox.get_nearest_node(G, point, method='haversine', return_dist=False)
    nearest_node = G.nodes[nearest]
    nearest_node["name"] = place["tags"]["name"]
    nearest_nodes.append(nearest_node)
    
    
distance_matrix = []
for source_node in nearest_nodes:
    distance_row = []
    for target_node in nearest_nodes:        
        distance = 0;
        if source_node['osmid'] != target_node['osmid']:
            distance = nx.shortest_path_length(G, source_node['osmid'],target_node['osmid'],weight='length', method='dijkstra')
        distance_row.append(distance)
    distance_matrix.append(distance_row)
    
distance_matrix = np.array(distance_matrix)<jupyter_output><empty_output><jupyter_text>Distance -> TimeEstimated Speed: 40km/h1km/h -> 16.67meter/minutes = 60km/h -> 1000meter/minutes & 40km/h -> 667meter/minutes<jupyter_code>kmh_to_meterpermin = 667

time_matrix = distance_matrix/kmh_to_meterpermin
places = np.array(places)
def create_environment(time_matrix, cities, eps = 0.0001):
    N =len(cities)

    def pheremon_matrix(cities, eps = eps):
        N =len(cities)
        data = (np.ones((N,N))- np.eye(N)) /(N-1)
        return pd.DataFrame(data=data, columns = cities, index = cities)

    return pd.DataFrame(time_matrix, columns = cities, index = cities), pheremon_matrix(cities)

env, phe = create_environment(time_matrix = time_matrix, cities = places)<jupyter_output><empty_output><jupyter_text>Data preparation section has finished.<jupyter_code>def cost(route):
    result = 0
    for i in range(len(route)-1):
        result += env.loc[route[i], route[i+1]]
    result+= env.loc[route[len(route)-1],route[0]]
    return result<jupyter_output><empty_output><jupyter_text>Ant Class<jupyter_code>class Ant():
    def __init__(self, env, phe, 
                 start = nearest_nodes[0]['name'],
                alpha = 1, beta = 1, time_constraint = 3500):
        
        self.outliers = []
        self.time_constraint = time_constraint
        
        self.phe  = phe
        self.env = self.outlier(env)
        
        self.alpha, self.beta = alpha, beta
        self.cities = list(self.env.columns)
        self.current_city = start
        self.depot = start
        
        self.route = [self.current_city]
  
        self.possible_cities = self.cities.copy()
        self.possible_cities.remove(self.current_city)
        
    def move(self):
        """
        Move one step
        """

        if len(self.possible_cities) == 0:
            return

        distances = self.env.loc[self.current_city][self.possible_cities]
        pheremons = self.phe.loc[self.current_city][self.possible_cities]
        
        distances[distances == 0] = 1

        preferences = pheremons**self.alpha/distances**self.beta
        probabilities = preferences/preferences.sum()

        probabilities.dropna(inplace=True)
        
        self.current_city = np.random.choice(a = probabilities.index, 
                                             size=1, 
                                             p = probabilities.values)[0]

        self.route.append(self.current_city)
        self.possible_cities.remove(self.current_city)
        
        temp_route = np.array(self.route)
        current_depot = np.where(temp_route == self.depot)[0][-1]
        

        if (cost(self.route[current_depot:]) > (self.time_constraint)):

            self.route.pop()

            self.possible_cities.append(self.current_city)

            self.current_city = self.depot
            if self.route[-1] != self.depot:
                self.route.append(self.depot)
                
        
    def go(self):
        """
        Build route/path
        """

        while len(self.possible_cities) != 0:
            self.move()


    def deposit(self):
        return self.route
        
    def cost(self):
        result = 0
        for i in range(len(self.route)-1):
            result += self.env.loc[self.route[i], self.route[i+1]]
        result+= self.env.loc[self.route[len(self.route)-1],self.route[0]]
        return result


    def outlier(self, en):
        control = []       
        for i,_ in enumerate(en.index.values):
            control.append(cost([en.index.values[0],en.index.values[i]]))
            
        control_np = np.array(control)
        
        out = en.index.values[control_np>self.time_constraint]
        
        self.outliers.append(out)
               
        en = en.drop(out, axis=1)    
        en = en.drop(out, axis=0)
        
        return en<jupyter_output><empty_output><jupyter_text>Ant Colony Class<jupyter_code>class AntColony():
    def __init__(self, time_matrix,
                 cities, start = nearest_nodes[0]['name'], time_constraint = 3500):
        
        self.cities = cities
        self.start = start  
        self.env, self.phe = create_environment(time_matrix, cities = cities)
        self.time_constraint = time_constraint

    def evaporation(self, decay = 0.05):
        # Evaporation of Pheromon
        self.phe = self.phe * (1 - decay)
        
    def deposit(self, route, delta = 1):
        env[env == 0] = 10**-8
        for i,j in zip(route[:-1], route[1:]):
            self.phe.loc[i, j] +=  delta/self.env.loc[i, j]
        
    def run(self, K = 40, time = 10):
        # in each time step
        for t in range(time):
            # K ants exist in the colony
            self.colony = [Ant(env = self.env, phe = self.phe, 
                          start= self.start, time_constraint = self.time_constraint) 
                      for k in range(K)]

            # distributed and paralel moves of K ants
            for k in range(K):
                self.colony[k].go()   

            # after independent moves, ants deposit pheremon
            for k in range(K):
                path = self.colony[k].deposit()
                self.deposit(route = path)
                
            self.evaporation()<jupyter_output><empty_output><jupyter_text>TDVRP Class<jupyter_code>class TimeDepentendVRP():
    def __init__(self, Swarm, K, Time):
        self.swarm = Swarm
        
        self.swarm.run(K,Time)
        
    def getSwarm(self):
        return self.swarm
        
        
    def printDetails(self, routes, routes_cost, outliers):
        count = 1
        for a,i in zip(routes,routes_cost):
            print("Vehicle " + str(count) + ": " + str(a) + " = " + str(round(i,3)) + " Minutes", end='\n\n')
            count+=1
        print("Total Time: " + str(round(np.sum(routes_cost),3)) + " Minutes", end='\n\n')
        print("Outliers: " + str(outliers))
        
        
    def getResult(self, getAsDataFrame = True):
        results = [(a.route, a.cost()) for a in self.swarm.colony]

        results_dist = [results[i][1] for i in range(len(results))]

        min_result_index = np.argmin(results_dist)
       
        best_routes = np.array(self.swarm.colony[min_result_index].route)

        outliers = np.array(self.swarm.colony[min_result_index].outliers[0])
        start = self.swarm.colony[min_result_index].depot


        depot_points = np.where(best_routes == self.swarm.start)[0] 

        
        route_ranges = [range(depot_points[i],depot_points[i+1]) for i in range(len(depot_points)-1)]
       
        
        route_ranges.append(range(depot_points[-1],len(best_routes)))
        
        routes = [best_routes[route_ranges[i]].tolist() for i in range(len(route_ranges))]

        [routes[i].append(start) for i in range(len(routes))]

        
        routes_cost = [cost(routes[i]) for i in range(len(routes))]
        
        self.printDetails(routes, routes_cost, outliers)
        
        if getAsDataFrame == True:
            return pd.DataFrame([routes, routes_cost]).T
daily_limit_of_work = 600 #60min x 10hour
swarm = AntColony(time_matrix, cities = places, start = nearest_nodes[0]['name'], time_constraint = daily_limit_of_work)

VRP = TimeDepentendVRP(swarm, 5, 10)
df = VRP.getResult()
df<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12700051626226122, 'fraction_numerical': 0.010325245224574084, 'mean_word_length': 2.429886685552408, 'pattern_counts': {'":': 1, '<': 35, '<?xml version=': 0, '>': 42, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '20854', 'license': 'MIT', 'n_tokens_mistral': 3222, 'n_tokens_neox': 3089, 'n_words': 589, 'path': 'notebooks/TDVRP.ipynb', 'repo_name': 'kaveai/inspired-by-nature', 'size': '9685'}