-
Notifications
You must be signed in to change notification settings - Fork 0
/
Genetic Algorithms on Wh Scheduling
151 lines (136 loc) · 15.3 KB
/
Genetic Algorithms on Wh Scheduling
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
# -*- encoding: utf-8 -*-
import random
import math
from GA import GA
import pandas as pd
import numpy as np
from random import choice
data_p = pd.read_excel('出库数据.xlsx', sheet_name=2)
dv = pd.DataFrame(data_p)
price_info = dv.loc[:, ['始发地', '目的地', '时效', '起始重量', '单票最低运费', '续重价格']]
price_pool = []
for i in range(16000):
price_pool.append((price_info.loc[i, '始发地'], price_info.loc[i, '目的地'], price_info.loc[i, '时效'], price_info.loc[i, '起始重量'], price_info.loc[i, '单票最低运费'], price_info.loc[i, '续重价格']))
# print(price_pool)
data_w = pd.read_excel('出库数据.xlsx', sheet_name=4)
du = pd.DataFrame(data_w)
weight_info = du.loc[:, ['始发地代码', '目的地代码', '周均重量']]
weight_info = weight_info.sort_values(by=['目的地代码'])
weight_list = weight_info['周均重量'].tolist()
dest_list = weight_info['目的地代码'].tolist()
weight_pool = []
start_list = []
for i in range(173):
weight_pool.append((weight_info.loc[i, '始发地代码'],weight_info.loc[i, '目的地代码'], weight_info.loc[i, '周均重量']))
start_list.append(weight_info.loc[i, '始发地代码'])
# print(weight_pool)
start_list = set(start_list)
print('可选的始发仓为:',start_list)
time_period = 0.00
sum_price = 0.00
current_gene = []
current_combo = []
for i in weight_pool: # 在目的地与需求重量列表内遍历
time_pool = []
for j in price_pool: # 在所有始发地报价表内寻找可发当前目的地的报价集合
if (i[0] == j[1]) and (j[0] in start_list):
time_pool.append(j)
print(time_pool)
rand_item = choice(time_pool)
current_gene.append((rand_item))
current_combo.append((rand_item[0]))
print(rand_item)
time_period += rand_item[2] # 已计提时效加上所选的路段配送时效
sum_price += (rand_item[4] + (i[1]-rand_item[3]) * rand_item[5]) if (i[1]>rand_item[3]) else rand_item[4]
print('现有基因的信息为', current_gene)
print('该基因组合总价格为:', sum_price)
print('该基因组合总时效为:', time_period)
print('现有基因的始发地组合为', current_combo)
# 按概率突变
lives = []
lives.append(current_combo)
# def mutation(current_combo):
rate2 = random.random()
mutationCount = 0
if rate2 < 0.02:
index1 = random.randint(0, len(current_combo) - 1)
index2 = random.randint(0, len(current_combo) - 1)
newGene = current_combo[:] # 产生一个新的基因序列,以免变异的时候影响父种群
newGene[index1], newGene[index2] = newGene[index2], newGene[index1]
mutationCount += 1
print('原来的基因型为:',current_combo,'变异后的基因型为:',newGene)
lives.append(newGene)
print('lives_Count:',len(lives),'mutation_Count:',mutationCount,'lives:',lives)
current_combo = newGene
def getOne():
return choice(lives)
# 按概率交叉
rate1 = random.random()
if rate1 < 0.7:
ano_combo = getOne()
index1 = random.randint(0, len(current_combo) - 1)
index2 = random.randint(index1, len(current_combo) - 1)
print(index1,index2)
tempGene = ano_combo[index1:index2] # 交叉的基因片段
print(tempGene)
newGene = []
p1len = 0
crossCount = 0
for g in current_combo:
if p1len == index1: #g是元素内容,p1len是该内容位置距原点的长度
newGene.extend(tempGene) # 到达插入点时插入基因片段
p1len = index2 #当前位点所在长度
if p1len <index1: #g not in tempGene:
newGene.append(g)
p1len += 1
if p1len == index2:
newGene.append(current_combo[index2:])
p1len = len(current_combo)
crossCount += 1
if newGene != current_combo:
lives.append(newGene)
print('原来的基因型为:',current_combo,'交叉后的基因型为:',newGene)
lives.append(newGene)
print('lives_Count:',len(lives),'cross_Count:',crossCount,'lives:',lives)
current_combo = newGene
time_pack = []
price_pack = []
for k in lives:
current_combo = k
time_sum = 0.00
price_sum = 0.00
best_time = 10000000000000000
best_price = 10000000000000000
for i in range(173):
for j in range(len(price_pool)):
if (price_pool[j][0]==current_combo[i]) and (price_pool[j][1]==dest_list[i]):
time_sum += price_pool[j][2]
price_sum += price_pool[j][4] + price_pool[j][5] * (weight_list[i] - price_pool[j][3]) if weight_list[i] > price_pool[j][3] else price_pool[j][4]
if time_sum <best_time:
best_time = time_sum
best_time_combo = current_combo
if price_sum <best_price:
best_price = price_sum
best_price_combo = current_combo
# time_pack.append((time_sum, current_combo))
# price_pack.append((price_sum, current_combo))
print('最优的总时效为:',best_time,'使总时效最优的组合为',best_time_combo)
print('最优的总价格为:',best_price,'使总价格最优的组合为:',best_price_combo)
# print('time_pack:',time_pack)
# print('price_pack:',price_pack)
Output:
可选的始发仓为: {898, 10, 7311, 20, 21, 532, 23, 24, 25, 411, 27, 28, 29, 431, 571, 451, 595, 991, 871, 755, 371}
[(10, 10, 23.95, 80, 153, 1.0), (20, 10, 71.35, 80, 342, 2.7), (21, 10, 61.83, 80, 299, 2.6), (23, 10, 74.44, 80, 283, 3.2), (24, 10, 51.76, 80, 239, 1.5), (25, 10, 56.84, 80, 290, 2.5), (27, 10, 55.8, 80, 269, 2.2), (28, 10, 74.94, 80, 305, 2.6), (29, 10, 61.05, 80, 317, 3.0), (371, 10, 45.35, 80, 236, 1.7), (411, 10, 50.28, 80, 239, 2.1), (431, 10, 53.1, 80, 279, 2.4), (451, 10, 58.29, 80, 256, 2.2), (532, 10, 44.65, 80, 239, 2.2), (571, 10, 60.76, 80, 298, 2.4), (595, 10, 72.83, 80, 289, 2.5), (755, 10, 71.39, 80, 342, 3.2), (871, 10, 82.02, 80, 383, 3.6), (898, 10, 92.08, 80, 325, 3.0), (991, 10, 82.58, 80, 384, 3.3), (7311, 10, 64.44, 80, 289, 2.4)]
(29, 10, 61.05, 80, 317, 3.0)
[(755, 20, 21.75, 80, 144, 1.0), (20, 20, 22.94, 80, 144, 1.0), (595, 20, 37.79, 80, 203, 1.6), (898, 20, 51.45, 80, 222, 1.8), (7311, 20, 34.56, 80, 226, 1.8), (371, 20, 54.49, 80, 240, 1.8), (27, 20, 51.36, 80, 241, 1.9), (28, 20, 61.77, 80, 278, 2.2), (532, 20, 60.38, 80, 293, 2.2), (23, 20, 56.16, 80, 274, 2.3), (571, 20, 54.72, 80, 279, 2.3), (25, 20, 50.88, 80, 273, 2.4), (21, 20, 53.4, 80, 276, 2.4), (431, 20, 78.53, 80, 290, 2.4), (29, 20, 65.73, 80, 294, 2.4), (411, 20, 79.92, 80, 299, 2.4), (871, 20, 56.09, 80, 287, 2.5), (24, 20, 78.43, 80, 299, 2.6), (451, 20, 83.67, 80, 306, 2.7), (10, 20, 72.55, 80, 320, 2.9), (991, 20, 119.18, 80, 366, 3.1)]
(991, 20, 119.18, 80, 366, 3.1)
[(571, 21, 31.25, 80, 161, 1.0), (21, 21, 23.36, 80, 162, 1.1), (25, 21, 24.81, 80, 169, 1.1), (371, 21, 47.46, 80, 222, 1.6), (595, 21, 51.88, 80, 229, 1.6), (532, 21, 41.37, 80, 235, 1.6), (27, 21, 50.29, 80, 237, 1.7), (7311, 21, 51.16, 80, 252, 2.0), (23, 21, 58.51, 80, 275, 2.2), (10, 21, 56.25, 80, 271, 2.3), (28, 21, 66.84, 80, 283, 2.3), (20, 21, 51.08, 80, 281, 2.4), (451, 21, 76.64, 80, 289, 2.4), (29, 21, 53.37, 80, 291, 2.5), (24, 21, 58.82, 80, 297, 2.5), (898, 21, 75.31, 80, 307, 2.5), (755, 21, 50.02, 80, 281, 2.6), (411, 21, 53.38, 80, 297, 2.6), (431, 21, 60.96, 80, 305, 2.6), (871, 21, 77.51, 80, 327, 2.8), (991, 21, 109.75, 80, 368, 3.0)]
(20, 21, 51.08, 80, 281, 2.4)
...
...
现有基因的信息为 [(29, 10, 61.05, 80, 317, 3.0), (991, 20, 119.18, 80, 366, 3.1), (20, 21, 51.08, 80, 281, 2.4), (755, 10, 71.39, 80, 342, 3.2), (755, 23, 54.66, 80, 314, 3.1), (871, 24, 93.21, 80, 393, 3.5), (7311, 25, 49.73, 80, 256, 2.3), (21, 27, 50.68, 80, 275, 2.4), (431, 28, 76.1, 80, 315, 2.7), (755, 29, 57.55, 80, 322, 2.7), (451, 871, 100.19, 80, 353, 3.5), (10, 10, 23.95, 80, 153, 1.0), (20, 10, 71.35, 80, 342, 2.7), (871, 10, 82.02, 80, 383, 3.6), (532, 10, 44.65, 80, 239, 2.2), (411, 10, 50.28, 80, 239, 2.1), (10, 10, 23.95, 80, 153, 1.0), (571, 10, 60.76, 80, 298, 2.4), (24, 10, 51.76, 80, 239, 1.5), (20, 371, 52.17, 80, 306, 2.4), (25, 371, 39.25, 80, 283, 2.4), (25, 371, 39.25, 80, 283, 2.4), (29, 371, 33.14, 80, 222, 1.8), (10, 371, 48.75, 80, 284, 2.4), (29, 371, 33.14, 80, 222, 1.8), (411, 371, 67.43, 80, 289, 2.6), (991, 371, 87.527, 80, 356, 2.8), (25, 371, 39.25, 80, 283, 2.4), (23, 371, 51.49, 80, 267, 2.3), (10, 371, 48.75, 80, 284, 2.4), (24, 371, 51.01, 80, 288, 2.4), (431, 371, 66.6, 80, 309, 2.7), (595, 371, 62.05, 80, 271, 2.3), (451, 371, 74.75, 80, 294, 2.7), (24, 371, 51.01, 80, 288, 2.4), (21, 371, 49.47, 80, 284, 2.5), (10, 371, 48.75, 80, 284, 2.4), (7311, 371, 48.76, 80, 233, 1.8), (898, 371, 75.8, 80, 299, 2.7), (7311, 371, 48.76, 80, 233, 1.8), (10, 411, 49.02, 80, 254, 2.2), (451, 24, 35.26, 80, 164, 1.2), (20, 24, 73.3, 80, 365, 3.1), (898, 24, 101.4, 80, 337, 3.1), (23, 24, 81.34, 80, 310, 2.8), (21, 24, 58.8, 80, 319, 2.9), (755, 24, 72.12, 80, 365, 3.5), (871, 24, 93.21, 80, 393, 3.5), (451, 24, 35.26, 80, 164, 1.2), (25, 24, 53.76, 80, 324, 3.1), (595, 24, 76.83, 80, 341, 2.9), (28, 431, 81.12, 80, 344, 2.9), (595, 431, 78.64, 80, 378, 3.2), (871, 431, 95.0, 80, 421, 4.1), (431, 431, 23.16, 80, 143, 1.0), (29, 431, 72.41, 80, 345, 3.1), (571, 431, 74.12, 80, 340, 2.8), (991, 431, 100.03, 80, 431, 3.9), (595, 431, 78.64, 80, 378, 3.2), (25, 431, 61.95, 80, 326, 3.1), (27, 451, 72.95, 80, 300, 2.5), (25, 451, 73.22, 80, 352, 2.9), (7311, 451, 76.27, 80, 304, 2.5), (451, 451, 22.96, 80, 135, 0.9), (23, 451, 93.53, 80, 351, 3.0), (28, 451, 87.86, 80, 351, 2.9), (10, 451, 50.53, 80, 264, 2.3), (21, 451, 74.09, 80, 359, 3.2), (23, 451, 93.53, 80, 351, 3.0), (24, 451, 30.75, 80, 192, 1.3), (7311, 451, 76.27, 80, 304, 2.5), (571, 991, 104.69, 80, 525, 4.5), (871, 25, 84.7, 80, 339, 3.2), (371, 25, 33.83, 80, 241, 1.8), (25, 25, 18.59, 80, 144, 1.0), (29, 25, 58.76, 80, 286, 2.5), (451, 25, 85.85, 80, 301, 3.0), (871, 25, 84.7, 80, 339, 3.2), (10, 25, 61.04, 80, 281, 2.6), (871, 25, 84.7, 80, 339, 3.2), (991, 25, 111.47, 80, 377, 3.4), (532, 25, 39.87, 80, 233, 1.7), (871, 25, 84.7, 80, 339, 3.2), (25, 25, 18.59, 80, 144, 1.0), (21, 532, 47.02, 80, 275, 2.3), (29, 532, 57.64, 80, 293, 2.5), (24, 532, 57.15, 80, 251, 2.2), (898, 532, 86.48, 80, 314, 2.9), (7311, 532, 56.4, 80, 279, 2.4), (371, 532, 43.44, 80, 203, 1.4), (10, 532, 43.52, 80, 245, 1.9), (871, 532, 75.48, 80, 363, 3.5), (27, 532, 50.75, 80, 263, 2.4), (7311, 532, 56.4, 80, 279, 2.4), (451, 532, 68.95, 80, 279, 2.5), (28, 25, 68.18, 80, 285, 2.4), (29, 25, 58.76, 80, 286, 2.5), (7311, 25, 49.73, 80, 256, 2.3), (25, 25, 18.59, 80, 144, 1.0), (29, 571, 59.73, 80, 286, 2.5), (371, 571, 48.02, 80, 241, 2.0), (10, 571, 57.46, 80, 281, 2.8), (20, 571, 49.45, 80, 291, 2.5), (595, 571, 53.17, 80, 226, 1.3), (411, 571, 54.6, 80, 294, 2.7), (431, 571, 63.56, 80, 303, 2.7), (27, 571, 54.42, 80, 264, 2.4), (24, 571, 62.77, 80, 294, 2.5), (23, 571, 61.26, 80, 271, 2.5), (991, 571, 112.77, 80, 379, 3.2), (24, 595, 72.897, 80, 309, 2.9), (28, 595, 57.09, 80, 308, 2.8), (21, 595, 46.65, 80, 276, 2.3), (411, 595, 70.43, 80, 309, 3.0), (595, 595, 26.78, 80, 128, 1.0), (755, 595, 26.62, 80, 241, 2.1), (898, 532, 86.48, 80, 314, 2.9), (595, 532, 63.36, 80, 293, 2.4), (21, 532, 47.02, 80, 275, 2.3), (7311, 20, 34.56, 80, 226, 1.8), (371, 27, 33.34, 80, 196, 1.2), (23, 27, 51.13, 80, 248, 1.9), (871, 27, 60.64, 80, 331, 3.1), (23, 27, 51.13, 80, 248, 1.9), (10, 27, 55.27, 80, 309, 2.9), (595, 27, 58.38, 80, 241, 1.9), (991, 27, 85.107, 80, 365, 3.1), (871, 7311, 55.8, 80, 324, 2.9), (431, 7311, 80.08, 80, 300, 2.5), (532, 7311, 59.5, 80, 294, 2.5), (871, 20, 56.09, 80, 287, 2.5), (24, 20, 78.43, 80, 299, 2.6), (411, 755, 75.36, 80, 299, 3.0), (371, 20, 54.49, 80, 240, 1.8), (29, 20, 65.73, 80, 294, 2.4), (7311, 20, 34.56, 80, 226, 1.8), (21, 20, 53.4, 80, 276, 2.4), (27, 20, 51.36, 80, 241, 1.9), (21, 871, 74.13, 80, 332, 3.0), (411, 871, 101.83, 80, 340, 3.4), (20, 871, 53.24, 80, 291, 2.3), (898, 595, 52.41, 80, 253, 2.3), (29, 595, 70.42, 80, 317, 3.1), (371, 28, 52.01, 80, 267, 2.4), (898, 28, 83.41, 80, 312, 3.1), (898, 28, 83.41, 80, 312, 3.1), (871, 28, 50.24, 80, 273, 2.2), (571, 28, 76.64, 80, 340, 2.9), (371, 28, 52.01, 80, 267, 2.4), (10, 28, 72.07, 80, 347, 3.4), (898, 28, 83.41, 80, 312, 3.1), (431, 28, 76.1, 80, 315, 2.7), (755, 871, 50.77, 80, 292, 2.7), (431, 871, 98.2, 80, 352, 3.0), (24, 871, 101.16, 80, 340, 3.0), (755, 871, 50.77, 80, 292, 2.7), (24, 871, 101.16, 80, 340, 3.0), (371, 871, 61.88, 80, 288, 2.5), (991, 871, 112.013, 80, 395, 3.6), (431, 871, 98.2, 80, 352, 3.0), (898, 898, 23.15, 80, 150, 1.1), (871, 29, 67.31, 80, 325, 3.0), (431, 29, 61.06, 80, 294, 2.5), (7311, 29, 55.71, 80, 273, 2.3), (571, 29, 62.43, 80, 295, 2.5), (28, 29, 48.69, 80, 243, 2.0), (571, 29, 62.43, 80, 295, 2.5), (871, 29, 67.31, 80, 325, 3.0), (7311, 29, 55.71, 80, 273, 2.3), (991, 29, 78.84, 80, 274, 2.3), (25, 7311, 54.23, 80, 265, 2.2), (29, 7311, 61.35, 80, 264, 2.1), (20, 898, 52.01, 80, 260, 2.1)]
该基因组合总价格为: 300762.79999999993
该基因组合总时效为: 10842.564
现有基因的始发地组合为 [29, 991, 20, 755, 755, 871, 7311, 21, 431, 755, 451, 10, 20, 871, 532, 411, 10, 571, 24, 20, 25, 25, 29, 10, 29, 411, 991, 25, 23, 10, 24, 431, 595, 451, 24, 21, 10, 7311, 898, 7311, 10, 451, 20, 898, 23, 21, 755, 871, 451, 25, 595, 28, 595, 871, 431, 29, 571, 991, 595, 25, 27, 25, 7311, 451, 23, 28, 10, 21, 23, 24, 7311, 571, 871, 371, 25, 29, 451, 871, 10, 871, 991, 532, 871, 25, 21, 29, 24, 898, 7311, 371, 10, 871, 27, 7311, 451, 28, 29, 7311, 25, 29, 371, 10, 20, 595, 411, 431, 27, 24, 23, 991, 24, 28, 21, 411, 595, 755, 898, 595, 21, 7311, 371, 23, 871, 23, 10, 595, 991, 871, 431, 532, 871, 24, 411, 371, 29, 7311, 21, 27, 21, 411, 20, 898, 29, 371, 898, 898, 871, 571, 371, 10, 898, 431, 755, 431, 24, 755, 24, 371, 991, 431, 898, 871, 431, 7311, 571, 28, 571, 871, 7311, 991, 25, 29, 20]
最优的总时效为: 11070.305000000006 使总时效最优的组合为 [29, 991, 20, 755, 755, 871, 7311, 21, 431, 755, 451, 10, 20, 871, 532, 411, 10, 571, 24, 20, 25, 25, 29, 10, 29, 411, 991, 25, 23, 10, 24, 431, 595, 451, 24, 21, 10, 7311, 898, 7311, 10, 451, 20, 898, 23, 21, 755, 871, 451, 25, 595, 28, 595, 871, 431, 29, 571, 991, 595, 25, 27, 25, 7311, 451, 23, 28, 10, 21, 23, 24, 7311, 571, 871, 371, 25, 29, 451, 871, 10, 871, 991, 532, 871, 25, 21, 29, 24, 898, 7311, 371, 10, 871, 27, 7311, 451, 28, 29, 7311, 25, 29, 371, 10, 20, 595, 411, 431, 27, 24, 23, 991, 24, 28, 21, 411, 595, 755, 898, 595, 21, 7311, 371, 23, 871, 23, 10, 595, 991, 871, 431, 532, 871, 24, 411, 371, 29, 7311, 21, 27, 21, 411, 20, 898, 29, 371, 898, 898, 871, 571, 371, 10, 898, 431, 755, 431, 24, 755, 24, 371, 991, 431, 898, 871, 431, 7311, 571, 28, 571, 871, 7311, 991, 25, 29, 20]
最优的总价格为: 138587.54 使总价格最优的组合为: [29, 991, 20, 755, 755, 871, 7311, 21, 431, 755, 451, 10, 20, 871, 532, 411, 10, 571, 24, 20, 25, 25, 29, 10, 29, 411, 991, 25, 23, 10, 24, 431, 595, 451, 24, 21, 10, 7311, 898, 7311, 10, 451, 20, 898, 23, 21, 755, 871, 451, 25, 595, 28, 595, 871, 431, 29, 571, 991, 595, 25, 27, 25, 7311, 451, 23, 28, 10, 21, 23, 24, 7311, 571, 871, 371, 25, 29, 451, 871, 10, 871, 991, 532, 871, 25, 21, 29, 24, 898, 7311, 371, 10, 871, 27, 7311, 451, 28, 29, 7311, 25, 29, 371, 10, 20, 595, 411, 431, 27, 24, 23, 991, 24, 28, 21, 411, 595, 755, 898, 595, 21, 7311, 371, 23, 871, 23, 10, 595, 991, 871, 431, 532, 871, 24, 411, 371, 29, 7311, 21, 27, 21, 411, 20, 898, 29, 371, 898, 898, 871, 571, 371, 10, 898, 431, 755, 431, 24, 755, 24, 371, 991, 431, 898, 871, 431, 7311, 571, 28, 571, 871, 7311, 991, 25, 29, 20]