我目前正在为一家出租车公司的模型进行轮类调度模拟。该公司经营350辆出租车，并且在任何一天都在使用中。司机每个工作5类，每个工作12个小时，每天有四个重叠的类次。从3:00-15:00、15:00-3:00、16:00-4:00和4:00-16:00轮类。我最初是用Python开发的，因为需要快速开发它，并且我认为性能是可以接受的。原始参数一天只需要轮类两次(3:00-15:00和15:00-3:00)，虽然性能不是很好，但对于我的使用来说已经足够了。它可以使用简单的蛮力算法为驾驶员制定每周约8分钟的时间表(评估所有潜在的调换情况，看看情况是否可以得到改善)。
在四个重叠的转变中，性能绝对是糟糕透顶的。每周计划需要一个多小时。我已经使用cProfile进行了一些分析，看来罪魁祸首是两种方法。一种是确定在将驾驶员换档时是否存在冲突的方法。确保他们不在同一天的轮类中服务，也不在之前或之后的轮类中服务。每天只需两类，这很容易。只需确定驾驶员是否已被安排在之前或之后直接在轮类中工作。随着四个重叠的转变，这变得更加复杂。第二个罪魁祸首是确定轮类是白类还是夜类的方法。同样，对于原始的两个类次，这很容易确定类次号是偶数还是奇数，类次号从0开始。第一个类次(类次0)被指定为夜类，第二个类次被指定为白天，等等等等。现在，前两个是夜晚，接下来的两个是，依此类推。这些方法相互调用，因此我将其 body 放在下面。
def conflict_exists(shift, driver, shift_data):
next_type = get_stype((shift+1) % 28)
my_type = get_stype(shift)
nudge = abs(next_type - my_type)
if driver in shift_data[shift-2-nudge] or driver in shift_data[shift-1-nudge] or driver in shift_data[(shift+1-(nudge*2)) % 28] or driver in shift_data[(shift+2-nudge) % 28] or driver in shift_data[(shift+3-nudge) % 28]:
return True
else:
return False
请注意，get_stype返回类次的类型，其中0表示夜类，而1表示日类。
为了确定类次类型，我使用了以下方法:
def get_stype(k):
if (k / 4.0) % 1.0 < 0.5:
return 0
else:
return 1
这是cProfile的相关输出:
ncalls tottime percall cumtime percall
57662556 19.717 0.000 19.717 0.000 sim8.py:241(get_stype)
28065503 55.650 0.000 77.591 0.000 sim8.py:247(in_conflict)
是否有人对我如何改善此脚本的性能有任何明智的建议或技巧？任何帮助将不胜感激!
干杯，
提姆
编辑:对不起，我应该澄清每个类次的数据都存储为一个集合，即shift_data [k]是集合数据类型的。
编辑2:
根据下面的请求添加主循环，以及其他调用的方法。有点困惑，对此我深表歉意。
def optimize_schedule(shift_data, driver_shifts, recheck):
skip = set()
if len(recheck) == 0:
first_run = True
recheck = []
for i in xrange(28):
recheck.append(set())
else:
first_run = False
for i in xrange(28):
if (first_run):
targets = shift_data[i]
else:
targets = recheck[i]
for j in targets:
o_score = eval_score = opt_eval_at_coord(shift_data, driver_shifts, i, j)
my_type = get_stype(i)
s_type_fwd = get_stype((i+1) % 28)
if (my_type == s_type_fwd):
search_direction = (i + 2) % 28
end_direction = i
else:
search_direction = (i + 1) % 28
end_direction = (i - 1) % 28
while True:
if (end_direction == search_direction):
break
for k in shift_data[search_direction]:
coord = search_direction * 10000 + k
if coord in skip:
continue
if k in shift_data[i] or j in shift_data[search_direction]:
continue
if in_conflict(search_direction, j, shift_data) or in_conflict(i, k, shift_data):
continue
node_a_prev_score = o_score
node_b_prev_score = opt_eval_at_coord(shift_data, driver_shifts, search_direction, k)
if (node_a_prev_score == 1) and (node_b_prev_score == 1):
continue
a_type = my_type
b_type = get_stype(search_direction)
if (node_a_prev_score == 1):
if (driver_shifts[j]['type'] == 'any') and (a_type != b_type):
test_eval = 2
else:
continue
elif (node_b_prev_score == 1):
if (driver_shifts[k]['type'] == 'any') and (a_type != b_type):
test_eval = 2
else:
test_eval = 0
else:
if (a_type == b_type):
test_eval = 0
else:
test_eval = 2
print 'eval_score: %f' % test_eval
if (test_eval > eval_score):
cand_coords = [search_direction, k]
eval_score = test_eval
if (test_eval == 2.0):
break
else:
search_direction = (search_direction + 1) % 28
continue
break
if (eval_score > o_score):
print 'doing a swap: ',
print cand_coords,
shift_data[i].remove(j)
shift_data[i].add(cand_coords[1])
shift_data[cand_coords[0]].add(j)
shift_data[cand_coords[0]].remove(cand_coords[1])
if j in recheck[i]:
recheck[i].remove(j)
if cand_coords[1] in recheck[cand_coords[0]]:
recheck[cand_coords[0]].remove(cand_coords[1])
recheck[cand_coords[0]].add(j)
recheck[i].add(cand_coords[1])
else:
coord = i * 10000 + j
skip.add(coord)
if first_run:
shift_data = optimize_schedule(shift_data, driver_shifts, recheck)
return shift_data
def opt_eval_at_coord(shift_data, driver_shifts, i, j):
node = j
if in_conflict(i, node, shift_data):
return float('-inf')
else:
s_type = get_stype(i)
d_pref = driver_shifts[node]['type']
if (s_type == 0 and d_pref == 'night') or (s_type == 1 and d_pref == 'day') or (d_pref == 'any'):
return 1
else:
return 0
最佳答案
没有任何东西会明显降低这些功能的速度，并且实际上它们并不慢。他们只是被叫了很多。您说您正在使用蛮力算法-您可以编写一种不会尝试所有可能组合的算法吗？还是有一种更有效的方法，例如通过驱动程序而不是通过移位存储数据？
当然，如果您需要即时加速，则可以通过在诸如PyPy的解释器中运行或使用Cython将关键部分转换为C来受益。
关于python - Python中高效的类次调度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6431261/