Я пытаюсь присвоить общества грузовику доставки.Грузовик может принять ограниченную нагрузку и имеет ограниченное время.У общества есть время доставки.У меня также есть время в пути между складом (грузовик отправляется отсюда только) и фреймом данных, в котором есть время в пути от каждого общества к другому.
Код работает нормально, но занимает много времени, когда данные большие.Для этого может быть простой способ?
1 максимальная загрузка грузовика: 350 заказов.
1 максимальное время доставки грузовика: 135 минут
Ниже приведены таблицы данных.
Order_Count: количество заказов в обществе
warehouse_time: время в пути от склада до общества
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