乘客预约数据库/算法

Question

我正在开发一个小型的拼车网站，在那里人们可以使用google (纬度和经度)创建中途停留的路线。

我可以在给定的路线上创建所有可能的组合(包括中途停留)，如下所示：

(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市(这一次不得中途停留)

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

--我还没有找到一种方法来从程序上确定在任何一次旅行中预定座位时哪些行程会受到影响(或不会)。

我发现的最接近的想法是phpjabber的一个总线预订脚本，这个答案是：Database design for bus reservation，但是这两个解决方案已经在DB上存储了城市/站点，而在“我的”解决方案中，停止总是动态的(使用google )。

到目前为止，我已经尝试过：

• 在旅程和“主人”之旅之间建立一种EAV关系。
• 根据中途停留的数量创建类似的“等级”(1级是最长的行程，2级是n-1中途停留的旅程，等等)。
• 试着按照起点/终点来处理矩阵。

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

我想知道和想法如何解决这个问题:公式，算法，一些基本代码或其他什么。

编辑：

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

1. 司机创造了一个从A到D的搭便车，有三个座位。司机增加两个中途停留，在B和C，它产生6次旅程(见上文)。

这四个点或城市(A，B，C，D)是从google地图api中选择的，所以它们不是本地存储的。每个点的纬度和经度都“附加”在游乐上。

1. 乘客Z预定的座位是最长的(第一)。现在所有的乘车都只有两个座位。很简单。
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个座位可用的(见上文第3点)。这是我的问题，我不知道如何确定第一次乘坐不能被乘客X号的预订所改变(第4点)。

Answer 1

我认为答案在于从A到D的旅程，从B和C到B和C，从一开始就有3条分开的腿，并分别存储完整的行程，在骑车和腿之间来回链接。(忽略AC或BD等组合腿)

乘车桌： 骑行：{id=1，从：“纽约”到："Newport"，legIDs=1,2,3，user=John，.} 腿桌： 腿：{id=1，从“纽约”到“纽黑文”，座位= 3，rideID=1，.} 腿：{id=2，从“纽黑文”到“新伦敦”，座位= 3，rideID=1，.} 腿：{id=3，从“新伦敦”到“新港”，座位= 3，rideID=1，.}

然后，当乘客想要搭便车的时候，你会把他的旅程分成两条腿，然后寻找这些不同的腿的乘车方式，而选择属于同一条腿的腿。

然后，在预订一辆车时，你会从旅程的每一条腿上扣除一个座位，无论这些腿属于哪一条腿。