我正在尝试将社团分配给送货卡车。卡车可以承受有限的负载并且有有限的时间。一个社会有一个交付时间。我也有仓库之间的旅行时间（卡车只从这里出发）和一个数据框，其中包含从每个社会到其他社会的旅行时间。
代码运行良好，但是当数据很大时会花费很多时间。有一个简单的方法吗？
1 辆卡车最大装载量：350 个订单。
1 辆卡车最长交货时间：135 分钟
下面是数据表。
Order_Count : 社会订单数
仓库时间：从仓库到社会的旅行时间
DeliveryTime : 在社会上交付订单的时间。
Society_ID Order_Count warehouse_time DeliveryTime
1 305 1722 4122
2 168 1409 4557
3 231 1331 7026
7 216 1466 4684
8 212 1202 3929
9 65 1050 2341
10 59 1355 2580
11 199 1417 4957
12 54 1380 1352
14 117 1498 3388
另一个数据框有来自每个社会的旅行时间。
s1 s2 Time
1 1 0
2 1 914
3 1 898
7 1 1000
8 1 1024
9 1 1044
10 1 1140
11 1 1173
12 1 822
14 1 1013
1 2 907
2 2 0
3 2 1076
7 2 1054
8 2 1013
9 2 1033
10 2 623
11 2 656
12 2 804
14 2 1173
1 3 675
2 3 824
3 3 0
7 3 514
8 3 633
9 3 653
10 3 1049
11 3 1083
12 3 296
14 3 633
1 7 767
2 7 958
3 7 507
7 7 0
8 7 768
9 7 787
10 7 1184
11 7 1217
12 7 431
14 7 604
1 8 1009
2 8 1159
3 8 896
7 8 875
8 8 0
9 8 303
10 8 1384
11 8 1417
12 8 631
14 8 994
1 9 903
2 9 1052
3 9 790
7 9 769
8 9 131
9 9 0
10 9 1278
11 9 1311
12 9 525
14 9 888
1 10 900
2 10 661
3 10 1069
7 10 1048
8 10 1006
9 10 1026
10 10 0
11 10 242
12 10 798
14 10 1167
1 11 963
2 11 723
3 11 1131
7 11 1110
8 11 1069
9 11 1089
10 11 261
11 11 0
12 11 860
14 11 1229
1 12 562
2 12 711
3 12 744
7 12 723
8 12 681
9 12 701
10 12 937
11 12 970
12 12 0
14 12 842
1 14 805
2 14 990
3 14 539
7 14 654
8 14 799
9 14 819
10 14 1221
11 14 1254
12 14 463
14 14 0
目前我已经编写了一个逻辑，但是当数据大小增加时需要时间。下面是相同的代码。
# stored the order count, if exceeding 350 then find remainder
orderCount = defaultdict( lambda: 0 )
# will store how many fully loaded trucks shall be sent to society with 350 orders
fullyLoadedTrucks = defaultdict( lambda: 0 )
for index, row in wdf.iterrows():
orderCount[row['Society_ID']] = (int(row['Order_Count']))
# implementation of above mentioned comments.
for i in orderCount:
if orderCount[i] > maxOrderCount:
fullyLoadedTrucks[i] = orderCount[i]// maxOrderCount
orderCount[i] %= maxOrderCount
# quotient = no. of fully loaded truck for eg. OrderCount for some society id = 1225, then we need to send 3
#fullyloaded trucks and one partially filled with 175 orders 1225//350 = 3, 1225 % 350 = 175
# time spent from going from wh to society
timeFromWH = OrderedDict()
# time spent during delivery within the society
deliveryTime = dict()
for _, row in wdf.iterrows():
sid = int(row['Society_ID'])
timeFromWH[sid] = int(row['total_time'])
deliveryTime[sid] = int(row['Delivery_Time'])
for _, row in sdf.iterrows():
sid = int(row['society_1'])
sdf.at[_, 'Time'] = deliveryTime[sid] + int(row['Time'])
# set 'time' of i'th society equal to time spent in delivering goods in that society + time spent on traveling
sdf.head()
time = defaultdict(OrderedDict)
for _, row in sdf.iterrows():
_from = int(row['society_2'])
_to = int(row['society_1'])
if _from == _to: continue
time[_from][_to] = int(row['Time'])
# MOST IMPORTANT: if we decide to go from society x to y then how much time will we require on travel and delivering goods in society y,
# NOTE: we don't consider the time spent in societey x in time[x][y], we assume we have already somehow reached x
# this loop is the reason why overall time complexity of this code reaches O(n**2)
visited = defaultdict(lambda : False) # No society is visited
CountOfVisited = 0 # initially 0 societies are visited
path = defaultdict(lambda : [])
truck = 1 # This variable will give the total number of trucks required
truckNumber = defaultdict(lambda: []) # This dict will store the trucknumber of i'th society
truckOrder = defaultdict(lambda: [])
considered = defaultdict(lambda: True)
while CountOfVisited != len(wdf):
# until all societies are visited
if not len(timeFromWH): break
society, timereq = timeFromWH.popitem(last=False)
''' ^^^^^^
pops out closest society and timereq for both: going from warehouse to the society and delivering goods in the society
'''
while visited[society]:
society, timereq = timeFromWH.popitem(last=False) # closest society has already been visited then find next closest
if timereq > maxTime or orderCount[society]>maxOrderCount:
# if total time required is more than MaxTime, then we don't consider going to this society
considered[society] = False
visited[society] = True
truckNumber[society] = -1 # not considering
truckOrder[society ] = -1 # not considering
CountOfVisited += 1
continue
ordersf = orderCount[society]
timesf = timereq # we went to closest society and time_so_far = delivery time + travel time
queue = 1 # this society is where the truck shall go first (truck Order)
while timesf < maxTime and ordersf < maxOrderCount:
# if we have more time left then continue finding the closest society and deliver goods.
visited[society] = True # mark as current society visited
CountOfVisited += 1
truckNumber[society] = truck
truckOrder[society] = queue
queue += 1
society, timreq = time[society].popitem(last=False)
while visited[society]:
society, timereq = time[society].popitem(last=False) #find next closest and repeat.
timesf += timereq
ordersf += orderCount[society]
# if we are here, then truck went back from societies due to time limit, and we need to send other trucks there to
# deliver goods and hence increment the truck number by one and repeat this whole process
truck += 1
下面是所需的输出。这个社会被分配了这辆卡车。
Society_ID Order_Count warehouse_time DeliveryTime Truck
1 305 1722 4122 1
2 168 1409 4557 2
3 231 1331 7026 3
7 216 1466 4684 4
8 212 1202 3929 5
9 65 1050 2341 2
10 59 1355 2580 2
11 199 1417 4957 6
12 54 1380 1352 3
14 117 1498 3388 4