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

Question

过去几周我一直在尝试解决与我正在进行的个人项目相关的问题。我尝试了几种不同的方法，但其中 none 似乎给了我想要的结果，所以我希望这里的人至少可以帮助我指明正确的方向。

情况：我想建造一系列的桥，这些桥将在每座桥之间的中点连接。我得到了地面的地形和将用作桥腿的柱子。（每座桥有 2 条腿支撑其上方的道路）。腿站立的地面不一定是平坦的，因此每座桥的腿之间的角度会有所不同。如果我在每座桥的腿上都放一条路，由于桥的角度和腿的相对高度不同，当桥上放路时，路不一定与路相连它将建在两座桥之间中点的下一座桥上。因此，我可以在一组边界内升高 any/all 桥腿，以使桥腿顶部的每条道路在中点与相邻道路相连桥梁之间。（这条路延伸到桥腿之外，终止于任何相邻桥梁之间的中点）

示例： 我有一个沿 x 轴放置桥腿的点列表：x = [0, 200, 300, 500, 600, 800]（每条桥腿之间的距离一座桥是 200，从桥的第二条腿到相邻桥的第一条腿的距离是 100。桥 1 将停靠在位于 0 和 200 单位的腿上，桥 2 将停靠在位于 0 和 200 单位的腿上300 和 500 单位，等等...道路应连接桥梁 1 和 2 的中点位于 250 单位）。

我也知道桥腿的底部高度位于这些高度：y = [6, 1, 6, 9, 9, 12] 海拔高度（高于 0）。

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

我正在尝试创建一种算法，其中 returns 需要对每条支路进行调整的列表，以确保每座桥在其共享中点连接到其相邻桥。

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

这也有可能不是优化问题，可以通过其他方式解决，在这种情况下，我很乐意听取任何可以帮助我指明正确方向的人的其他方法。

如果有人能帮我解决这个问题，或者至少帮我指明正确的方向，我将不胜感激。

非常感谢任何反馈，我一定会快速回复您的任何问题或意见。非常感谢！

编辑： 例如：这是我们的桥梁在任何调整之前的样子（红色是桥的腿，绿色是桥之间的中点，蓝色箭头是桥梁道路终止的地方，蓝色水平条代表基础高度桥的）

这就是我们的桥梁经过一系列成功调整后的样子：（黑色箭头是新道路在支腿顶部的位置）

如您所见，为了让我们的桥梁连接起来，一种可能的解决方案是抬高第 2 条腿和第 5 条腿（分别升高大约 4 个单位和 1 个单位）

Answer 1

根据要求，以下是如何将其表示为线性程序并使用 OR-Tools 求解的方法。

为每条腿创建一个变量。此变量的下限是腿的当前高度。这个变量的上限是腿的最大高度（例如，current + 10）。

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

对于 objective，我将满足于最小化坡度的最大差异。我们使用斜率而不是角度，因为它是线性的，并且斜率的差异很好地近似于角度的差异。（绝对可以直接优化角度差异，但我们必须切换到 cvxpy 或支持非线性 objectives 的东西。）

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]

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

Connect series of bridges at midpoint by raising legs

python

algorithm

optimization

trigonometry

scipy