8

我正在开发一个航班调度应用程序（免责声明：这是一个大学项目，所以请没有代码答案）。请在回答之前仔细阅读这个问题，因为它有很多特点:(

首先，一些术语问题：
你有飞机和航班，你必须将它们配对。为简单起见，我们假设一架飞机在使用它之前降落的航班是免费的。

航班被视为任务：

  • 他们有一个持续时间
  • 他们有依赖关系
  • 他们有一个预期的开始日期/时间

飞机可以被视为任务（或航班，在我们的术语中）使用的资源。

航班需要特定类型的飞机。例如，航班 200 需要一架 B 型飞机。飞机显然是一种且只有一种特定类型，例如，飞机空军一号是 C 型。

“项目”是航空公司在给定时间段内所有航班的集合。

所需的功能是：

  • 为上述项目寻找最短的持续时间

  • 任务（飞行）的最早和最晚可能开始

  • 关键任务以提供的数据为基础，并带有先前任务的标识符。

  • 自动配对航班和飞机，使所有航班与飞机配对。（注：飞行时间是固定的）

  • 获取带有项目调度的甘特图，其中所有航班尽早开始，以图形方式显示所有先前引用的数据（依赖关系、时间信息等）

所以问题是：我到底是如何做到这一点的？特别：

  • 我们需要使用图表。
    • 图的边和节点分别代表什么？
  • 我们是否需要丢弃任务来完成关键任务集？

如果您还可以推荐一些算法供我们查找，那就太好了。

4

2 回答 2

5

这里有一些建议。

原则上，您可以有一个图，其中每个节点都是一个航班，如果 B 依赖于 A，则从航班 A 到航班 B 有一条边，即 B 在 A 降落之前无法起飞。您可以使用此依赖关系图来计算项目的最短持续时间 --- 当您将路径上所有航班的持续时间相加时，通过图表找到具有最长持续时间的路径。这是您项目的“关键路径”。

但是，您需要与飞机配对这一事实使其变得更加困难，尤其是。正如我猜想的那样，飞机不允许在没有乘客的情况下飞行，即飞机必须从它最后降落的同一个城市起飞。

如果您有过多的飞机，则使用模拟退火等组合优化算法很可能很容易将它们分配给航班。如果计划非常紧凑，即您没有多余的飞机，这可能是个难题。

要为您的航班设置实际起飞时间，例如，您可以将允许的时间表制定为线性规划问题，或半定/二次规划问题。

这里有一些参考：

于 2011-04-21T22:07:18.343 回答
1

从绘制领域模型（类图）开始，并在您的脑海中明确区分：

  • 计划不变的事实: PlaneType, Plane, Flight, FlightBeforeFlightConstraint, ...
  • 规划变量：PlaneToFlightAssignment

将所有这些实例包装在Project该类中（= 解决方案）。然后在这样的解决方案上定义一个评分函数（AKA 适应度函数）。例如，如果有 2 个PlaneToFlightAssignments不符合FlightBeforeFlightConstraint（= 航班依赖），则降低分数。

PlaneToFlightAssignment然后只需通过更改实例来找到得分最高的解决方案即可。您可以使用多种算法来找到最佳解决方案。如果您的数据集真的很小（比如 10 个飞机），您也许可以使用brute force。

于 2011-04-22T06:38:56.217 回答