import random as rd
import matplotlib.pyplot as plt
import functools
import math
import copy
import time
def points_generate(x_min, y_min, x_max, y_max, nums):
points = []
for i in range(nums):
points.append([i, int((x_max-x_min) * rd.random() + x_min),
int((y_max-y_min) * rd.random() + y_min)])
return points
def OD_generate(num_min, num_max, nums_w, nums_d, nums_s):
ODs = [[0 for j in range(nums_w+nums_d+nums_s)] for i in range(nums_w+nums_d+nums_s)]
for i in range(nums_w):
for j in range(nums_w+nums_d, nums_w+nums_d+nums_s):
ODs[i][j] = int((num_max-num_min) * rd.random() + num_min)
return ODs
def OD_plot(points, ODs, x_min, y_min, x_max, y_max):
scala = min(x_max - x_min, y_max - y_min)
plt.xlim(x_min - 0.1*scala, x_max + 0.1*scala)
plt.ylim(y_min - 0.1*scala, y_max + 0.1*scala)
#显示框大小
plt.gcf().set_size_inches(8, 8)
#画点
for i in range(len(points)):
plt.text(points[i][1], points[i][2], str(points[i][0]), color='r', size=scala/10)
#画流量箭头
arrow_params = {'length_includes_head': True, 'shape': 'right',
'head_starts_at_zero': True}
#箭头端点空出比例
scala_edge = 0.1
#字符在边的比例
scala_text = 0.3
for i in range(len(points)):
for j in range(len(points)):
x, y, dx, dy = points[i][1], points[i][2], points[j][1] - points[i][1], points[j][2] - points[i][2]
if (dx == 0 and dy == 0) or ODs[i][j] == 0:
continue
ddx,ddy = -0.01*scala*dy/(math.sqrt(dx*dx+dy*dy)), 0.01*scala*dx/(math.sqrt(dx*dx+dy*dy))
plt.arrow(x + scala_edge * dx + ddx, y + scala_edge * dy + 0.01 * scala + ddy, (1 - 2 * scala_edge) * dx,
(1 - 2 * scala_edge) * dy, width=0.01*scala, head_width=0.015*scala, **arrow_params)
plt.text(x + scala_text*dx + 4*ddx, y + scala_text*dy + 4*ddy, str(ODs[i][j]))
plt.show()
def calculate_euclidean_distance(x1, y1, x2, y2):
return math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))
def A_generate(points, nums_w, nums_d, nums_s):
A = [[0 for j in range(nums_w+nums_d+nums_s)] for i in range(nums_w+nums_d+nums_s)]
# 欧式距离和球面距离
Dis = [[calculate_euclidean_distance(points[i][1], points[i][2], points[j][1], points[j][2]) for j in range(nums_w+nums_d+nums_s)]
for i in range(nums_w+nums_d+nums_s)]
for i in range(nums_w):
idex_w = nums_w
for j in range(nums_w+1, nums_w+nums_d):
if Dis[i][idex_w] > Dis[i][j]:
idex_w = j
A[i][idex_w] = 1
for i in range(nums_w+nums_d, nums_w+nums_d+nums_s):
idex_s = nums_w
for j in range(nums_w+1, nums_w+nums_d):
if Dis[idex_s][i] > Dis[j][i]:
idex_s = j
A[idex_s][i] = 1
for i in range(nums_w, nums_w+nums_d):
for j in range(nums_w, nums_w + nums_d):
if i != j:
A[i][j] = 1
return A
#流量分配在网络上
def ODs_adjust(ODs, A):
nums = len(A)
T = [[1 if ODs[i][j] > 0 else 0 for j in range(nums)] for i in range(nums)]
T_sum = A
L = [A]
An = A
while sum([sum([T[i][j] - T_sum[i][j] if T[i][j] - T_sum[i][j] > 0 else 0 for j in range(nums)]) for i in range(nums)]) > 0:
An = [[sum([An[i][k]*A[k][j] for k in range(nums)]) for j in range(nums)] for i in range(nums)]
L.append([[1 if i != j and T_sum[i][j] == 0 and An[i][j] > 0 else 0 for j in range(nums)] for i in range(nums)])
T_sum = [[1 if i != j and (T_sum[i][j] == 1 or An[i][j] > 0) else 0 for j in range(nums)] for i in range(nums)]
m = len(L)-1
ODs1 = copy.deepcopy(ODs)
while m > 0:
Am = L[m]
Al = L[m-1]
for i in range(nums):
for j in range(nums):
if Am[i][j] == 1:
for k in range(nums):
if Al[i][k] == 1 and A[k][j] == 1:
ODs1[i][k] += ODs1[i][j]
ODs1[k][j] += ODs1[i][j]
ODs1[i][j] = 0
ODs1[j][k] += ODs1[j][i]
ODs1[k][i] += ODs1[j][i]
ODs1[j][i] = 0
break
m -= 1
return ODs1
if __name__ == "__main__":
# 点的范围及个数
x_min, y_min, x_max, y_max, nums_w, nums_d, nums_s = 0, 0, 100, 100, 5, 1, 5
# 点集生成
points = points_generate(x_min, y_min, x_max, y_max, nums_w+nums_d+nums_s)
#流量范围
num_min, num_max = 1,10
#流量生成
ODs = OD_generate(num_min, num_max, nums_w, nums_d, nums_s)
print(points)
print(ODs)
OD_plot(points, ODs, x_min, y_min, x_max, y_max)
#生成仓、分拣、站点连接关系邻接矩阵
A = A_generate(points, nums_w, nums_d, nums_s)
OD_plot(points, A, x_min, y_min, x_max, y_max)
#流量分配在网络A上
ODs1 = ODs_adjust(ODs, A)
OD_plot(points, ODs1, x_min, y_min, x_max, y_max)
