algorithm - 拼车预订的数据库/算法

Question

我在一个小型拼车网站上工作，人们可以在其中使用谷歌地图 API(纬度和经度)创建带有中途停留的路线。

我可以像这个答案一样在给定路线(包括中途停留)上创建所有可能的组合:

(Java) Find all possible pairs in an array

示例:如果从 A 到 D 的旅程有 2 个中途停留点(B 和 C)，则将有 6 种可能的“旅程”:

1. 城市 A - 城市 D(最长行程)
2. 城市 A - 城市 C(全 1 站行程)
3. B 市 - D 市(全 1 站行程)
4. A 市 - B 市(在这个城市没有中途停留)
5. B 市 - C 市(没有中途停留)
6. C 市 - D 市(这一个没有中途停留)

当乘客在给定旅程中预订座位时，其他一些旅程也会根据他们在“金字塔”中的位置预订座位。

我还没有找到一种方法来以编程方式确定在任何给定行程中预订座位时哪些行程会受到影响(或不受影响)。

我发现的最接近的想法是来自 phpjabbers 的巴士预订脚本和这个 SO 答案: Database design for bus reservation ，但是这两个解决方案已经将城市/停靠点存储在数据库中，而在“我的”解决方案中，停靠点始终是动态的(使用谷歌地图 API)。

到目前为止我已经尝试过:

• 在旅程和“主”旅程之间建立一种 EAV 关系。
• 根据中途停留的数量创建类似的“级别”(第 1 级是最长的旅行，第 2 级是有 n-1 个中途停留的旅程，依此类推。
• 尝试根据起点/终点玩矩阵。

我没有以正确的方式解决问题(当然)，但我不确定这个问题是否与数学、算法或其他任何问题有关。请原谅。

我想了解如何解决这个问题:公式、算法、一些基本代码或其他任何内容。

编辑:

为了更好地解释问题，这将是一个典型的场景:

1. 司机安排了从 A 到 D 的行程，并提供三个座位。司机在 B 和 C 中添加了两个中途停留点。它生成了 6 个旅程(见上文)。

四个点或城市(A、B、C、D)是从 google maps api 中选择的，因此它们不会存储在本地。每个点的纬度和经度都“附加”到游乐设施。

1. 乘客 Z 在最长的行程 (#1) 上预订了一个座位。现在所有游乐设施都只有两个座位。很简单。

2. 乘客 Y 在行程 #6(从 C 到 D)上预订了一个座位。现在，#1、#3 和 #6 游乐设施少了一个座位(2 个已占用，1 个可用)。

3. 乘客 X 在行程 #2(从 A 到 C)上预订了一个座位。 这就是它变得复杂的地方。现在，#2、#4 和#5 的游乐设施少了一个座位(1 个已占用，2 个可用)，这同样适用于 #3(2 个已占用，1 个可用) ).

此时即使有 3 名乘客预订了“子游乐设施”的座位，1 号游乐设施仍有 1 个可用座位(见上文第 3 点)。这是我的问题，我不知道如何确定乘客 X 的预订不能修改 ride #1(第 4 点)。

Answer 1

我认为答案在于从一开始就将从 A 到 D 并在 B 和 C 中途停留的旅程存储为 3 个独立的行程，并单独存储完整的行程，并在行程和行程之间来回链接。 (忽略 AC 或 BD 等组合边。)

RIDES TABLE:
ride: {id=1, from: "New York", to: "Newport", legIDs=[1,2,3], user=John, ...}

LEGS TABLE:
leg: {id=1, from "New York", to "New Haven", seats = 3, rideID=1, ...}
leg: {id=2, from "New Haven", to "New London", seats = 3, rideID=1, ...}
leg: {id=3, from "New London", to "Newport", seats = 3, rideID=1, ...}

然后，当乘客寻找行程时，您将他的旅程分成几段，并为这些不同的行程寻找行程，优先选择属于同一行程的行程。

然后，在预订行程时，您可以从旅程的每段行程中扣除一个座位，无论这些行程属于哪个行程。