通过抬高腿连接中点的一系列桥梁

Question

在过去的几个星期里，我一直在努力解决一个与我正在做的个人项目有关的问题。我尝试过几种不同的方法，但似乎没有一种方法能给我带来我想要的结果，所以我希望这里的人至少能帮我找到正确的方向。

情景：，我想要构建一系列桥梁，它们将在每个桥之间的中点连接起来。我被赋予土地的地形和支柱，将作为桥梁的腿。(每座桥有两条腿支撑上面的道路)。腿所站的地面不一定是平的，因此每座桥的腿之间的角度都会有所不同。如果我把一条路放在每座桥腿的顶部，由于桥的角度和支腿的相对高度是不同的，当道路放在桥上时，这条路可能不一定与在两座桥之间中点将建在下面一座桥上的道路相连。因此，我被允许在一组界限内抬高桥梁的任何/所有支腿，以便使每条位于桥梁腿顶部的道路与桥梁之间中点的相邻道路相连。(这条路延伸到桥腿以外，并在任何相邻桥梁之间的中点处终止)

示例：i有一个沿x轴放置桥梁支腿的点的列表：x = [0, 200, 300, 500, 600, 800] (桥的每一支腿之间的距离为200，从桥的第二段到相邻桥梁的第一段的距离为100 )。第一桥将在坐0和200个单元的腿上休息，第2号桥将停留在300和500个单元的腿上，等等。道路连接桥梁1和2之间的中点位于250个单元)。

我还知道，桥腿的基础高度位于这些高度：y = [6, 1, 6, 9, 9, 12]高于海平面(高于0)。

每条腿只能在bounds = (0, 10)的范围内向上移动(每条腿可以从基础高度上升0到10个单位)，以便使放置在腿顶部的道路连接到桥梁之间的中点附近的道路。

我正在尝试创建一个算法，返回需要对每个腿进行调整的列表，以确保每个桥都在共享的中点连接到其相邻的桥接器。

到目前为止，我认为这是一个优化问题，在这个问题中，我试图将桥梁中点的道路两端之间的垂直距离降到最小。然而，我已经尝试了多次不同的迭代，到目前为止还没有成功。我对优化算法非常陌生，所以这可能是我失败的原因。(使用scipy.optimize.minimize)

还有一个机会，这不是一个优化问题，它可以通过其他方法解决，在这种情况下，我愿意听取其他方法，谁可以帮助我指出正确的方向。

如果有人能帮我解决这个问题，或者至少帮我指出正确的方向，我会非常感激的。

任何反馈都是非常感谢的，我一定会迅速回应您的任何问题或评论。非常感谢!

编辑：，例如:这就是我们的桥梁在任何调整之前的样子(红色是桥梁的腿，绿色是桥梁之间的中点，蓝色的箭头是桥梁道路的尽头，蓝色的水平条代表桥梁的基本高度)

​

这就是我们的桥梁经过一系列成功的调整后的样子：(黑色箭头是新道路停在腿上的地方)

​

正如你所看到的，要使我们的桥梁连接起来，一个可行的解决方案是将腿2和腿5(分别提高约4个单元和1个单元)。

Answer 1

根据要求，这里是如何将其表述为一个线性规划，并使用OR-工具进行求解.

对每条腿，做一个变量。这个变量的下界是腿的当前高度。这个变量的上限是腿的最大高度(例如，电流+ 10)。

对于每对相邻的桥梁，我们将相邻两桥腿之间的中点限制在相同的高度上。

为了一个目标，我会满足于最小化最大的坡度差异。我们用斜率代替角度，因为它是线性的，斜率上的差异很好地近似于角度的差异。(可以直接优化角度的差异，但我们必须切换到cvxpy或支持非线性目标的东西。)

from ortools.linear_solver import pywraplp

x = [0, 200, 300, 500, 600, 800]
y = [6, 1, 6, 9, 9, 120]
initial_bounds = [(0, 10), (0, 9), (0, 9.5), (0, 8), (0, 7), (0, 9)]

# Returns the y value at x2 of the line between (x0,y0) and (x1,y1).
def extrapolate(x0, y0, x1, y1, x2):
    return y0 + (x2 - x0) / (x1 - x0) * (y1 - y0)


def solve(is_phase_one, bounds):
    solver = pywraplp.Solver.CreateSolver("GLOP")
    if is_phase_one:
        objective = solver.NumVar(0, solver.infinity(), "objective")
        new_y = [
            solver.NumVar(-solver.infinity(), solver.infinity(), "y%d" % i)
            for i in range(len(y))
        ]
        for i in range(len(y)):
            solver.Add(new_y[i] >= y[i] + bounds[i][0] - objective)
            solver.Add(new_y[i] <= y[i] + bounds[i][1] + objective)
    else:
        objective = 0
        new_y = [
            solver.NumVar(y[i] + bounds[i][0], y[i] + bounds[i][1], "y%d" % i)
            for i in range(len(y))
        ]
    for i in range(3, len(y), 2):
        midpoint = (x[i - 2] + x[i - 1]) / 2
        solver.Add(
            extrapolate(x[i - 3], new_y[i - 3], x[i - 2], new_y[i - 2], midpoint)
            == extrapolate(x[i - 1], new_y[i - 1], x[i], new_y[i], midpoint)
        )
    if not is_phase_one:
        for i in range(1, len(y), 2):
            z = solver.NumVar(0, solver.infinity(), "")
            slope = (new_y[i] - new_y[i - 1]) / (x[i] - x[i - 1])
            solver.Add(z >= slope)
            solver.Add(z >= -slope)
            objective += z
    solver.Minimize(objective)
    status = solver.Solve()
    assert status == pywraplp.Solver.OPTIMAL
    if is_phase_one:
        return [
            (
                bounds[i][0] - objective.solution_value(),
                bounds[i][1] + objective.solution_value(),
            )
            for i in range(len(y))
        ]
    else:
        return [variable.solution_value() for variable in new_y]


relaxed_bounds = solve(True, initial_bounds)
print(relaxed_bounds)
heights = solve(False, relaxed_bounds)
print(heights)

样本输出：

[(-6.1999999999999975, 16.199999999999996), (-6.1999999999999975, 15.199999999999998), (-6.1999999999999975, 15.699999999999998), (-6.1999999999999975, 14.199999999999998), (-6.1999999999999975, 13.199999999999998), (-6.1999999999999975, 15.199999999999998)]
[-0.1999999999999975, 16.199999999999996, 16.800000000000033, 2.8000000000000025, 22.199999999999996, 113.8]