什么是优化保龄球道保留的最佳算法

Question

我正在寻找有关客人预订优化算法的建议。背景：我在一家娱乐公司（想想保龄球馆）工作，该公司在每个场地都有 n 条车道。客人可以预订两个小时的预订，并且只能停留在一个球道上（与保龄球示例相同）。给定一天的 x 个预订，我需要重新安排预订，以便最小化停滞时间（预订之间的时间 <2 小时）并最大化每个隔间的利用率（总预订时间/总开放时间）。所以我需要先垂直堆叠预订，如果不可能 - 然后水平。

我开发了一个幼稚的贪婪解决方案，它一次获取一个预订并找到下一个最佳空位，它已经运行良好，但我在考虑如何改进它。我认为基于梯度下降的真正优化会更好。我将这些数据编码为列是车道，行是 15 分钟的时间块（10:00，10:15，等等），预订被编码为 1，阻塞时间（你不能插入任何东西）为 9，清洁时间（预约结束后员工需要清洁15分钟）为2，开放时间编码为0。（屏幕截图中的示例）

我的数据很小，他们每天最多只有200个预订，所以计算不是什么大问题。即使是 O(N^2) 的东西也会快几毫秒。请推荐一些文章，或者如果有人在过去开发过类似的东西，将不胜感激。 PuLP 可以帮助解决这个问题吗？我只是不确定如何在我的数据集上使用它。

Answer 1

正如@DanielJunglas 所说，使用 PuLP 将为您提供最佳解决方案，并且您应该能够合理地将此问题简单地建模为混合整数或可能是纯二进制整数程序。请注意，这些求解器的工作方式与传统算法截然不同，因此对性能有多种影响。例如，这个问题有很多对称性（具有相同 objective 值的不同解决方案），这可能会影响解决时间。

线性规划被表述为一组变量、一组对这些变量值的约束，以及一个基于我们试图 max/min 的变量的 objective 函数。求解器将找到满足 largest/smallest objective 值约束的解（变量的值）。 PuLP 让您以相当用户友好的方式编写公式，然后让您调用开源求解器来求解它。

这是一个 BIP 公式示例：

from pulp import *
import random

prob = LpProblem("Prob1", LpMinimize)

# Define the input parameters (randomly generated)
hours = 10
resLenInts = 8 # 2 hours in 15 min intervals
numres = 50
resStartTimes = {x:random.randint(0,hours*4 - 2*4 - 1) for x in range(numres)} #id:starttime dict
resLengths = {x:8 for x in range(numres)} # Res length in intervals
cleanTime = 1
T = range(hours*4)
lanes = range(0,40)

# Create our variables
X = LpVariable.dicts("resInLane", (resStartTimes.keys(), lanes), cat=LpBinary) # 1 if reservation r uses lane l, 0 otherwise

Y = LpVariable.dicts("laneEmpty", (lanes), cat=LpBinary) # 1 if a lane l has no reservations, 0 otherwise

# Perturbing the objective function to try and break some symmetry
coeffs = {r:{l:random.random()*0.00001 for l in lanes} for r in resStartTimes}

# Objective function, the function we are trying to minimize the value of
# This should be a pure statement, not an equation (not an equality/inequality)
prob += - lpSum(Y[l] for l in lanes) - lpSum(Y[l]*((len(lanes)-l)/len(lanes)) for l in lanes) - lpSum(X[r][l]*coeffs[r][l] for r in resStartTimes for l in lanes), "Maximize empty lanes"

## Constraints
# These are the restrictions on which solutions are valid

# Reservation can only use one lane
for r in resStartTimes.keys():
    prob += lpSum(X[r][l] for l in lanes) == 1

# Reservations cannot overlap
for r1 in resStartTimes.keys():
    for r2 in resStartTimes.keys():
        if r1 != r2:
            if resStartTimes[r1] < resStartTimes[r2]:
                if resStartTimes[r1] + resLengths[r1] + cleanTime > resStartTimes[r2]:
                    for l in lanes:
                        prob += X[r1][l] + X[r2][l] <= 1
            elif resStartTimes[r2] < resStartTimes[r1]:
                if resStartTimes[r2] + resLengths[r2] + cleanTime > resStartTimes[r1]:
                    for l in lanes:
                        prob += lpSum(X[r1][l] + X[r2][l]) <= 1    
            else:
                for l in lanes:
                    prob += lpSum(X[r1][l] + X[r2][l]) <= 1                  

# Restricts Y so that it represents what we want
# Ie. 1 if a lane has no reservations, 0 otherwise
for l in lanes:
    prob += lpSum(X[r][l] for r in resStartTimes.keys()) - 0.1 <= 9999*(1 - Y[l])
    prob += 0.1 - lpSum(X[r][l] for r in resStartTimes.keys()) <= 9999*Y[l]

prob.X = X
prob.Y = Y

# Solve the problem using CBC, stopping early when we get within 50% of the theoretical best
prob.solve(PULP_CBC_CMD(msg=True, fracGap=0.5))

# Print the solution
laneslist = [f'{lane} '.zfill(3) for lane in lanes]
print(f"\t {''.join(laneslist)}")
for t in range(hours*4):
    temp = [[f'{r} '.zfill(3) if (prob.X[r][l].varValue == 1 and t in range(resStartTimes[r], resStartTimes[r] + resLengths[r])) else '' for r in resStartTimes.keys()] for l in lanes]
    for i in range(len(temp)):
        tempstr = ""
        for j in range(len(temp[i])):
            tempstr += temp[i][j]
        temp[i] = tempstr
    temp = [x if x != '' else '   ' for x in temp]
    print(f"{t} \t {''.join(temp)}")

不过，这可能很难在 50 条车道左右进行超过 50 次预订，而且它只能通过最大化已用车道的利用率来间接最小化停滞时间。在某种程度上，该问题几乎不受约束，线性规划无法发挥作用。一些简单的事情，比如将问题分解成子问题（预留和车道集），然后将它们重新组合在一起，可能是轻松提高性能的好方法，而且由于车道和预留是独立的，它应该工作得很好。

在 PuLP 之外，您可以尝试启发式算法，例如遗传算法的无数变体之一（例如模拟退火、粒子群算法）。这些不能保证最优性，但由于特定的问题结构，与 LP 相比，性能与时间相比可能更胜一筹。专用的调度求解器可能会为您提供最佳结果，因为它们会利用所有可能的技术，但我不确定 free/open-source 选项是什么样的。

一些其他注意事项：

问题的表述对于 LP 的解决至关重要，因此好的表述是获得良好性能的最有效途径。如果您使用 PuLP，请花一些时间思考表示问题的最佳方式：变量、约束、objective.
利用求解器日志查看求解器在何处遇到问题。 This paper 很好地描述了一些常见问题和可能的解决方案。

希望这可以帮助您确定 PuLP 是否适合您，如果是，也许它可以帮助您入门。祝你好运！

什么是优化保龄球道保留的最佳算法

What is the optimal algorithm to optimize reservations for bowling lanes

python

optimization

pulp