mysql - 使用 Rails 和 mysql 的具有多个下车点、目的地的机票预订算法

Question

我正在运行一项具有简单的一对一出发地和目的地的预订服务。随着我的服务不断增长，我正在考虑实现多个下车点，目的地如下

A----->B----->C----->D

假设从 A(出发地)到 D(目的地)的旅程在旅途中经过 B 和 C。

我的用户可以预订 A->B、A->C、A->D、B->C、B->D 和 C->D 的座位。我的问题是找到一个很好的座位可用性算法，给出一个问题例如 B->D。

我想出了一个简单的解决方案，如下

Routes:
-------------
id orig dest  seats   many_drop_off_points   desc               
1   A    D     40     yes                   multiple drop-offs
2   A    H     20     no                    straight
3   B    H     12     no                    straight
4   A    D     12     no                    straight

我有一个包含出发地、目的地的路线表。为简单起见，我只输入该路线的座位总数。

路由表可以有一个或多个路由，如下所示

Routhings
-----------------
id orig dest route_id  denormalize_seats
1   A    B      1          40
2   B    C      1          40
3   C    D      1          40
4   A    H      2          20

路由属于特定的路由。路线可以在特定日期有多个预订。

RoutingReservation
---------------------------------
id  routing_id  date  customer_id

当设置从 A 到 D 并经过 B 和 C 的路线时。

 create in Routings table three record as shown in the table above(A->B, B->C, C->D).

如果从A->H直行，没有经过任何地方。 在路由表中创建一条记录(A->H)

当客户想要搜索从C->D的路线时，我只需从Route或Routings中搜索(复杂的计算)

预留座位也复杂。

使用 1 号路线从 A -> D 预订 10 个座位(多个下车点)

 Create 10 reservations for Routing 1 (from A->B)
 Create 10 reservations for Routing 2 (from B->C)
 Create 10 reservations for Routing 3 (from C->D)

预留 5 个座位​​，从 A -> C

 Create 5 reservations from Routing 1 (from A->B)
 Create 5 reservations from Routing 2 (from B->C)

从 B -> D 预订 10 个座位

  Create 10 seats from Routing 2 (from B->C)
  Create 10 seats from Routing 3 (from C->D)

通过上述 3 个步骤计算路由的预留总数(复杂计算)

  Routing 1 (from A->B) 10 + 5
  Routing 2 (from B->C) 10 + 5 + 10
  Routing 3 (from C->D) 10 + 10

A->D路线的可用座位

  Total - Max(total number of reservation) from A->B, B->C, C->D

  40 - Max(15, 25, 20) = 15  # Route with id 1
  20 - 0  = 0   # Route with id 4

A->C航线的可用座位

  Total - Max(total number of reservation) from A->B, B->C
  40 - Max(15, 25) = 15 

B->D 的可用座位

  Total - Max(total number of reservation) from B->C, C->D
  40 - Max(25, 20) = 15 # Route with id 1

C->D 的可用座位

   Total - Max(total number of reservation) from C->D
   40 - Max(20) = 20  # Route with id 1

这种多下车点好像是可以实现的，但是需要大量的计算，目前我有超过30个合作伙伴，一千多条路线，但我想介绍一下这几个合作伙伴的多个下车点作为我的起点。

我正在寻找一种可以更有效地解决这个问题的算法。我当前的环境是 rubyonrails 和 mysql。

感谢您提前提供的帮助。

ps:我也对其他类型的数据存储持开放态度，例如elasticsearch或mongodb。

Answer 1

如果您认为所有路线都有许多下车点，并且仅将简单路线(A->B、B->C)视为微不足道的情况，那么这可能是最简单的。然后，您的数据库架构可能如下所示:

== routes table ==
id | seats | name
---|-------|------------------
1  | 10    | simple route
2  | 30    | the scenic route

== stops table ==
id    | route_id | location | next_location
--------------------------------------------
1     | 1        | A        | B
2     | 1        | B        |
3     | 2        | A        | B
4     | 2        | B        | C
5     | 2        | C        | D
6     | 2        | D        |

== reservations table ==
// for one trip from A to B on route 1 for 5ppl
// and one trip from A to C on route 2 for 20ppl
id | route_id | start_stop_id | end_stop_id | seats_needed
------------------------------------------------------------
1  | 1        | 1             | 2           | 5
2  | 2        | 3             | 5           | 20

您会注意到，我通过添加 next_location 稍微对停靠点表进行了非规范化，这一列不一定会添加任何额外信息，但会简化我们以后的计算。

使用此模式，我们可以通过这个相当简单的查询计算(每条路线或每条可能的航段)总容量和已用容量 :

robert=# SELECT routes.id as route_id, stops.id as stop_id, location, next_location,
  SUM(routes.seats) as capacity,
  SUM(reservations.seats_needed) as used
FROM stops
JOIN routes ON routes.id = stops.route_id
LEFT JOIN reservations
  ON reservations.route_id = routes.id
  AND reservations.start_stop_id <= stops.id
  AND reservations.end_stop_id > stops.id
WHERE next_location IS NOT NULL
GROUP BY routes.id, stops.id
ORDER BY routes.id, location;

 route_id | stop_id | location | next_location | capacity | used
----------+---------+----------+---------------+----------+------
        1 |       1 | A        | B             |       10 |    5
        2 |       3 | A        | B             |       30 |   20
        2 |       4 | B        | C             |       30 |   20
        2 |       5 | C        | D             |       30 |

此表简明地表示了您的路线。我们可以用它来回答更复杂的问题。

假设您想知道从 A 到 D 的旅程有多少个座位。此查询将找到所有此类座位，但它不会告诉您可以使用什么路线来执行此操作:

SELECT MIN(available) as available
FROM (
  SELECT location, next_location, SUM(routes.seats) - COALESCE(SUM(reservations.seats_needed),0) as available
  FROM stops
  JOIN routes ON routes.id = stops.route_id
  LEFT JOIN reservations
    ON reservations.route_id = routes.id
    AND reservations.start_stop_id <= stops.id
    AND reservations.end_stop_id > stops.id
  WHERE next_location IS NOT NULL
  GROUP BY location, next_location
) availabilities
JOIN (
  SELECT 'A' as a, 'B' as b
  UNION ALL
  SELECT 'B' as a, 'C' as b
  UNION ALL
  SELECT 'C' as a, 'D' as b
) legs
  ON legs.a = location AND legs.b = next_location;

 available
-----------
        10

现在，这是很多 SQL，它并不能完全回答你的问题。但是，我所做的是创建一个模式来对设置的有向图进行建模，并演示了一些有关如何使用该有向图的查询。所以，是的，可以在 SQL 中进行图形计算 - 但正如您所看到的，特别是对于上面查询中的 legs 表，它有时会很麻烦。但这绝不是不可能的。