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
|
"""
Run project like this: $ python example1
TODO: Read "raw" or preprocessed ventas data
"""
from vrptw_base import VrptwGraph
from multiple_ant_colony_system import MultipleAntColonySystem
import math
import numpy as np
import networkx as nx
from readerOPP import read_nodes, read_tramos
def _deg2rad(degrees):
return degrees * math.pi / 180
def distance_between_coordinates(lat1, lon1, lat2, lon2):
"""Returns the distance in km"""
earth_radius_km = 6371 # Avg. radius
lat1 = _deg2rad(lat1)
lat2 = _deg2rad(lat2)
d_lat = lat2 - lat1
d_lon = lon2 - lon1
a = math.sin(d_lat/2) * math.sin(d_lat/2) \
+ math.sin(d_lon/2) * math.sin(d_lon/2) * math.cos(lat1) * math.cos(lat2)
c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
return earth_radius_km * c
def make_complete_customer_node_graph(nodes, tramos):
"""
Nodes + Tramos make a network. An undirected graph. But we only care
about the nodes that are either have demand (aka. customers), or are depots.
This function creates a sub-graph of only depot-or-customer nodes, and
finds the nearest path + path_lenght between them (on the original network).
Parameters
----------
nodes : list
List of Node objects
tramos : list
List of tuples of "ubigeo"
Returns
-------
list
List of depot-or-customer nodes,
Shortest distance matrix (np.narray),
Dict with shortest distance and path object for all pairs of nodes
"""
elist = []
# Load sparse graph
nodes_d = {n.ubigeo: n for n in nodes}
for ubigeo1, ubigeo2 in tramos:
n1 = nodes_d[ubigeo1]
n2 = nodes_d[ubigeo2]
dist = round(distance_between_coordinates(n1.lat, n1.lon,
n2.lat, n2.lon), 0)
elist.append((ubigeo1, ubigeo2, dist))
G = nx.Graph()
G.add_weighted_edges_from(elist)
# Calculate missing edges using the shortest path
# (Thus making the graph complete)
len_path = dict(nx.all_pairs_dijkstra(G, weight='weight'))
# for node, (dist, path) in len_path:
# print(f"{node}: {dist} [{path}]")
# Prune all nodes that have no demand and "reset index" of nodes
depot_customer_nodes = []
i = 0
for n in nodes:
if n.demand > 0 or n.is_depot:
n.index = i
depot_customer_nodes.append(n)
i += 1
node_num = i
# Create distance matrix
node_dist_mat = np.zeros((node_num, node_num))
for n1 in depot_customer_nodes:
for n2 in depot_customer_nodes:
node_dist_mat[n1.index, n2.index] = \
len_path[n1.ubigeo][0][n2.ubigeo]
return depot_customer_nodes, node_dist_mat, len_path
def lab():
depot_num = 3
nodes = read_nodes(depot_num)
tramos = read_tramos()
nodes, node_dist_mat, len_path = \
make_complete_customer_node_graph(nodes, tramos)
# nodes with demand
for n in nodes[:8]:
print(n.__dict__)
# shortest distance between nodes in network
print(node_dist_mat[:8, :8])
# shortest path
for n1 in nodes[:1]:
for n2 in nodes[:8]:
shortest_path = len_path[n1.ubigeo][1][n2.ubigeo]
print(f"{n1.ubigeo} => {n2.ubigeo}: [{shortest_path}]")
def main():
#file_path = './solomon-100/c101.txt'
file_path = './odiparpack/pedidosperu195.txt'
ants_num = 10
beta = 2 # 5
q0 = 0.1 # 0.5 ?
show_figure = True
graph = VrptwGraph(file_path)
macs = MultipleAntColonySystem(graph, ants_num=ants_num, beta=beta, q0=q0,
whether_or_not_to_show_figure=show_figure)
macs.run_multiple_ant_colony_system()
if __name__ == '__main__':
lab()
|
