$D_{ij} = \sqrt{(X_{i} - X{j})^2 + (Y_{i} - Y{j})^2}$
$g_{ij} = D_{di} + D_{dj} - D_{ij}$
| X | Y | |
|---|---|---|
| Dep | 00.00 | 00.00 |
| 1 | 13.92 | 35.98 |
| 2 | 17.20 | 26.39 |
| 3 | 51.69 | 12.46 |
| 4 | 99.92 | 70.68 |
| 5 | 43.78 | 66.82 |
| 6 | 50.92 | 40.80 |
| 7 | 09.04 | 75.68 |
| 8 | 80.22 | 04.02 |
| 9 | 64.82 | 55.67 |
| 10 | 38.51 | 03.19 |
Mais informações: http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.12.html
In [1]:
from IPython.display import display
from matplotlib import pyplot as plt
import io
import numpy as np
import pandas as pd
import matplotlib.path as mplPath
%matplotlib inline
In [2]:
def plot_base(df: pd.DataFrame):
plt.figure(figsize=(6, 2))
plt.plot(df.x, df.y, 'o')
plt.title('Routes')
plt.xlabel('X')
plt.ylabel('Y')
plt.grid()
plt.xticks(np.arange(min(df.x), max(df.x)+1, 5))
plt.yticks(np.arange(min(df.y), max(df.y)+1, 10))
In [3]:
def get_next_pair(df: pd.DataFrame, drop=False) -> tuple:
k = df.index[0]
if drop:
df.drop(k, axis=0, inplace=True)
return map(int, k.split('_'))
In [4]:
def connect_points(df: pd.DataFrame, path: list):
plt.plot(
df.iloc[path].x, df.iloc[path].y
)
In [5]:
def check_all_points_satisfied(
routes: list, n_points: int
) -> bool:
return sum([len(r)-2 for r in routes]) >= n_points
In [6]:
def check_route_constraint_violated(route: list, k1: int, k2: int):
# initial validate
if not route:
return False
"""
a. Either, neither i nor j have already been assigned
to a route, in which case a new route is initiated including
both i and j.
"""
if k1 in route and k2 in route:
return True
"""
b. Or, exactly one of the two points (i or j)
has already been included in an existing route and
that point is not interior to that route
(a point is interior to a 'route if it is not adjacent
to the depot D in the order of traversal of points),
in which case the link (i, j) is added to that same route.
"""
if not (
route[1] == k1 or route[-2] == k1 or
route[1] == k2 or route[-2] == k2
):
return True
return False
In [7]:
def merge_posible_routes(routes: list):
"""
c. Or, both i and j have already been included in two
different existing routes and neither point is
interior to its route, in which case the two routes
are merged.
"""
n_routes = len(routes)
for i1, r1 in enumerate(routes):
for i2, r2 in enumerate(routes):
if i2 <= i1:
continue
if r1[1] == r2[1]:
routes[i1] = r2[-1:0:-1] + r1[2:]
elif r1[1] == r2[-2]:
routes[i1] = r2[:-1] + r1[2:]
elif r1[-2] == r2[1]:
routes[i1] = r1[:-1] + r2[2:]
elif r1[-2] == r2[-2]:
routes[i1] = r1[:-2] + r2[-2::-1]
else:
continue
del routes[i2]
return routes
In [8]:
def add_node(routes: list, k1, k2) -> list:
"""
add node into a valid route
"""
n = len(routes)
for i, route in enumerate(routes):
# step 2.a
if check_route_constraint_violated(route, k1, k2):
if k1 in route or k2 in route:
print('## ROUTE CONSTRAINT VIOLATED ##')
break
if i == n-1:
routes.append([0, k1, k2, 0])
return routes
else:
continue
# else
if not route:
route += [0, k1, k2, 0]
elif k1 == route[1]:
route.insert(1, k2)
elif k1 == route[-2]:
route.insert(-1, k2)
elif k2 == route[1]:
route.insert(1, k1)
elif k2 == route[-2]:
route.insert(-1, k1)
routes[i] = route
break
return merge_posible_routes(routes)
In [9]:
# initial data
df = pd.read_csv(io.StringIO("""x;y
0;00.00;00.00
1;13.92;35.98
2;17.20;26.39
3;51.69;12.46
4;99.92;70.68
5;43.78;66.82
6;50.92;40.80
7;09.04;75.68
8;80.22;04.02
9;64.82;55.67
10;38.51;03.19"""
), sep=';')
df
Out[9]:
In [10]:
plot_base(df)
# plot_lines([0, 10, 50, 0], [0, 50, 10, 0])
plt.show()
In [11]:
'''
# distance
$D_{ij} = \sqrt{(X_{i} - X{j})^2 + (Y_{i} - Y{j})^2}$
'''
df_distance = pd.DataFrame({
i: [np.sqrt((df.x[i] - df.x[j])**2 + (df.y[i] - df.y[j])**2)
for j in df.index
] for i in df.index
}, index=df.index, columns=df.index)
df_distance
Out[11]:
In [12]:
'''
# gain
$g_{ij} = D_{di} + D_{dj} - D_{ij}$
'''
n = df.shape[0]
df_gain = pd.DataFrame({
'%s_%s' % ((i, j) if i < j else (j, i)):
[df_distance.iloc[0, i] +
df_distance.iloc[0, j] -
df_distance.iloc[i, j]]
for i in df.index[1:] for j in range(i,n)
if not i == j
}).T
In [13]:
df_gain.sort_values(by=[0], ascending=[False], inplace=True)
assert df_gain.shape[0] == (df.shape[0]-1)*(df.shape[0]-2)/2
df_gain.head()
Out[13]:
In [14]:
routes = [[]]
n_routes = 1
n_points = df.shape[0] - 1
_gain = df_gain.copy()
i = 0
while True:
i += 1
print('=' * 80)
print('ITERATION #%s' % i)
print('=' * 80, end='\n\n')
k1, k2 = get_next_pair(_gain, drop=True)
print('pair:', k1, k2)
routes = add_node(routes, k1, k2)
plot_base(df)
for j, route in enumerate(routes):
print('route #%s' % j)
print(route)
connect_points(df, route)
plt.grid(True)
plt.show()
if check_all_points_satisfied(routes, n_points):
break