运筹优化1:枚举-排列组合(python之itertools库)

这货很强大, 必须掌握。

在工业场景中的很多优化问题，其最优解可认为是多种排列组合的一种，今天在做aps项目时，考虑小规模优化问题时，枚举法时最直接、最干脆的手段，今天分享一下python环境的一个排列组合求解包itertools。

例：假设有四个数字要进行排列组合，0，1，2，3，去获得可能的排列组合形式（不重复）。

定义数字集合：[0, 1, 2, 3]

废话少说，直接上代码：

from itertools import permutations

items = [0, 1, 2, 3]

for i in permutations(items):

print(i)

输出：

(0, 1, 2, 3)

(0, 1, 3, 2)

(0, 2, 1, 3)

...

(3, 2, 1, 0)

例:假设有四个装配订单[0,1,2,3]需要在一台装配机完成，它们作业时间分别为[6,5,4,8],两两订单之间的换型切换时间，见下表：

目标：装配机完成四个订单的时间最短

本例中，订单比较少，可以采用枚举法列举可能的生产顺序，然后计算累积时间。

上代码：

from itertools import permutations

def useTime(p,dataChangeTime,itemsTime):#每种装配顺序所用累积时间

totalSum = 0

for i in range(len(p)):

totalSum = totalSum + itemsTime[p[i]]

if i > 0:

totalSum = totalSum + dataChangeTime[(p[i-1],p[i])]

return totalSum

def minUseTime(items,dataChangeTime):#生产所有订单的排列组合

totalSum = float('inf')

minLst = []

for i in permutations(items):

Sum = useTime(i,dataChangeTime,itemsTime)

if totalSum > Sum:

totalSum = Sum

minLst = list(i)

return totalSum,minLst

if __name__ == '__main__':

items = [0, 1, 2, 3]

itemsTime = {0:6,1:5,2:4,3:8}

dataChangeTime = {(0,1):4,(0,2):2,(0,3):1,(1,0):3,(1,2):4,(1,3):0,(2,0):0,(2,1):3,(2,3):5, (3,0):6,(3,1):0,(3,2):4}

minSum = minUseTime(items,dataChangeTime)

print(minSum)

输出：(24, [2, 0, 3, 1])

后续将围绕规划算法、启发式算法、强化学习在生产排程、供应链优化以及路径规划等场景中实例应用进行分享，跟大家共同学习。