使用 Pulp 在工作日平均分配数量（需求）

Question

我必须在工作日安排商店，但当然，一条路线有容量，而且商店有不同的天数下降。

更明确地说，有一辆卡车每天都会移动，但对于商店来说，有些卡车应该在所有 6 天都放下，有些只需要两天，依此类推。

Key代表店名value代表天数

Days = {
    "S1":6, "S2":6, "S3":6, "S4":3, "S5":3,
    "S6":3, "S7":2, "S8":2, "S9":2, "S10":1,
    "S11":1, "S12":1, "S13":1 ,"S13":1,
    "S14":1, "S15":1 
}

需求（体积）是每家商店所有六天的纸箱总数。

我试着用需求量除以天数，求出大概每天的纸箱数量。我不确定这是否是一个好方法。

Demand = {
    "S1":400/6, "S2":300/6, "S3":250/6, "S4":200/3, "S5":300/3,
    "S6":200/3, "S7":300/2, "S8":200/2, "S9":300/2, "S10":50/1,
    "S11":40/1, "S12":45/1, "S13":30/1, "S13":44/1, "S14":47/1,
    "S15":60/1,
}

容量是所有商店纸箱的总和，我将需求除以可用的六天，就像我对商店需求所做的那样

Capacity = 2736/6

我想根据他们的数量在工作日平均分配商店，所以我使用这个约束来实现它：

for d in no_days_list:
    prob += pulp.lpSum([Demand[s] * storeVars[d][s] for s in Store]) <= Capacity

不幸的是，这个约束有两个问题：

如果商店需求除以天数后大于容量，我将得到一个非最佳解决方案 (-1) -（我正在寻找一个灵活的约束条件，如果它大约等于容量)
如果店铺需求远小于容量，我会得到一个最优解(1) 但它不会均匀分布，有些日子的商店数量和数量大于其他日子 - （我想我必须再添加一个约束来解决这种情况以尽可能均匀地分布它们）

如果我找到第二点的解决方案，我可以删除此约束。

拜托，我需要你的建议来增强代码。

StoreSched = pd.DataFrame(columns = ["Store_Code","Route","Demand"])
Capacity = 2736/6

route="R1"
days_list=["SAT","SUN","MON", "TUE","WED","THU"]
no_days_list = range(1,7)
Store = ["S1","S2","S3","S4","S5","S6","S7","S8","S9","S10","S11","S12","S13","S14","S15"]
Demand = {
    "S1":400/6, "S2":300/6, "S3":250/6 ,   "S4":200/3 , "S5":300/3,     
    "S6":200/3 ,  "S7":300/2, "S8":200/2, "S9":300/2,  "S10":50/1, 
    "S11":40/1,  "S12":45/1, "S13":30/1, "S13":44/1,    "S14":47/1,
    "S15":60/1,
}

Days = {
    "S1":6, "S2":6, "S3":6 , "S4":3, "S5":3,
    "S6":3, "S7":2, "S8":2, "S9":2, "S10":1,
    "S11":1, "S12":1, "S13":1, "S13":1,
    "S14":1, "S15":1,
}
    
prob = LpProblem("store_schedule",LpMaximize)
storeVars = LpVariable.dicts("Days",(no_days_list,Store),0,1,LpInteger)
    
for d in no_days_list:
    prob += pulp.lpSum([Demand[s] * storeVars[d][s] for s in Store]) <= Capacity
for s in Store:
    # Every store should be assigned based on its DayNo.
    prob += pulp.lpSum(storeVars[d][s] for d in no_days_list) == Days[s]

prob.solve()
print(prob.solve())
for vi in prob.variables():
    if vi.varValue == 1:
        code= vi.name.split("_")[2];
        day = days_list[int(vi.name.split("_")[1])-1];
        if ((StoreSched['Store_Code'] == code).any() == False):
            StoreSched = StoreSched.append({'Store_Code': code,"Route":route,"Days":Days[code],"Demand":Demand[code]}, ignore_index=True)
        for index in StoreSched.index:    
            if StoreSched.loc[index,'Store_Code']== code:                    
                StoreSched.loc[index,day] = 1                    
StoreSched.fillna(0,inplace=True)
StoreSched

Answer 1

您可以尽量减少一天最大负载和一天最小负载之间的差异。更改为 LpMinimize-问题：

prob = LpProblem("store_schedule",LpMinimize)

引入两个变量minLoad和maxLoad:

minLoad = LpVariable("minLoad", 0, Capacity, cat=LpContinuous)
maxLoad = LpVariable("maxLoad", 0, Capacity, cat=LpContinuous)

添加为objective:

prob += maxLoad - minLoad

添加约束以设置新变量：

for d in no_days_list:
    prob += minLoad <= pulp.lpSum([Demand[s] * storeVars[d][s] for s in Store])
    prob += maxLoad >= pulp.lpSum([Demand[s] * storeVars[d][s] for s in Store])

为了使问题可行，您需要增加 Capacity，即：

Capacity = 2836/6

CBC MILP 求解器的运行时间非常糟糕。您可以通过 storeVars:

的额外约束来改进

for s in Store:
    if Days[s] == 2:
        for d in range(1,5):
            prob += pulp.lpSum(storeVars[d][s] + storeVars[d+1][s] + storeVars[d+2][s]) <= 1
    if Days[s] == 3:
        for d in range(1,6):
            prob += pulp.lpSum(storeVars[d][s] + storeVars[d+1][s]) <= 1

运行每天给一个负荷：

d = 1, load = 465.0
d = 2, load = 464.0
d = 3, load = 455.33333333333337
d = 4, load = 458.33333333333337
d = 5, load = 441.6666666666667
d = 6, load = 451.6666666666667

使用 Pulp 在工作日平均分配数量（需求）

Distribute volume (demands) equally cross the weekdays with Pulp

python

optimization

pulp