预留分配算法

Question

我正在寻找关于资源分配预订的算法。这可能包括酒店预订匹配可用房间、会议预订匹配可用会议室、餐厅预订匹配桌子。

它们的共同点：

• 每个预订都有一个具体且不可更改的开始和结束时间。
• 在开始时间之前，每个预订并未绑定到特定的资源。
• 可以有可变数量的资源。
• 每当出现新的预订时，该算法至少应能检查是否可能将其与某个资源匹配。

到目前为止，我主要研究了基因算法来解决这个问题，但是我在将问题编码到染色体中时遇到了麻烦。

欢迎任何关于此问题的算法思路，也包括只能找到“良好”解决方案而非最优解的算法。

- Lemmedaskeren

---

这是一个在线问题（您一次只收到一个请求），还是您提前获得所有预订的问题？ - EmeryBerger

这将是一次请求。但是，在开始时间之前，预订不必绑定到资源。因此，当添加新的预订时，将会有绑定的预订和未绑定的预订。 - Lemmedaskeren

这里的问题是什么？既然您说起始/结束是不可改变的，那么这只是一个问题：“我能接受预订X吗？” - Lasse V. Karlsen

基本上，这个问题不就是问：在预定的整个时间段内，所需数量的资源是否当前可用？如果不是这个问题，那它是什么？为什么需要遗传算法来解决这个问题？ - Lasse V. Karlsen

没错。如果在您的情况下，必须接受一段时间 [开始时间，结束时间] 的预订，只要该时间段对于所有“资源”都没有先前的预订，就可以接受该预订；如果出现了重叠，则应该拒绝该预订，那么您只需要为每个资源检查这些时间段即可。 - EmeryBerger

Answer 1

本文章介绍了各种时间操作，用于检查空闲、重叠和相交的时间段。您可以轻松地将这些类与您的业务对象结合使用：

// ----------------------------------------------------------------------
public void TimeRangeSample()
{
  // --- time range 1 ---
  TimeRange timeRange1 = new TimeRange(
    new DateTime( 2011, 2, 22, 14, 0, 0 ),
    new DateTime( 2011, 2, 22, 18, 0, 0 ) );
  Console.WriteLine( "TimeRange1: " + timeRange1 );
  // > TimeRange1: 22.02.2011 14:00:00 - 18:00:00 | 04:00:00

  // --- time range 2 ---
  TimeRange timeRange2 = new TimeRange(
    new DateTime( 2011, 2, 22, 15, 0, 0 ),
    new TimeSpan( 2, 0, 0 ) );
  Console.WriteLine( "TimeRange2: " + timeRange2 );
  // > TimeRange2: 22.02.2011 15:00:00 - 17:00:00 | 02:00:00

  // --- time range 3 ---
  TimeRange timeRange3 = new TimeRange(
    new DateTime( 2011, 2, 22, 16, 0, 0 ),
    new DateTime( 2011, 2, 22, 21, 0, 0 ) );
  Console.WriteLine( "TimeRange3: " + timeRange3 );
  // > TimeRange3: 22.02.2011 16:00:00 - 21:00:00 | 05:00:00

  // --- relation ---
  Console.WriteLine( "TimeRange1.GetRelation( TimeRange2 ): " +
                     timeRange1.GetRelation( timeRange2 ) );
  // > TimeRange1.GetRelation( TimeRange2 ): Enclosing
  Console.WriteLine( "TimeRange1.GetRelation( TimeRange3 ): " +
                     timeRange1.GetRelation( timeRange3 ) );
  // > TimeRange1.GetRelation( TimeRange3 ): EndInside
  Console.WriteLine( "TimeRange3.GetRelation( TimeRange2 ): " +
                     timeRange3.GetRelation( timeRange2 ) );
  // > TimeRange3.GetRelation( TimeRange2 ): StartInside

  // --- intersection ---
  Console.WriteLine( "TimeRange1.GetIntersection( TimeRange2 ): " +
                     timeRange1.GetIntersection( timeRange2 ) );
  // > TimeRange1.GetIntersection( TimeRange2 ):
  //             22.02.2011 15:00:00 - 17:00:00 | 02:00:00
  Console.WriteLine( "TimeRange1.GetIntersection( TimeRange3 ): " +
                     timeRange1.GetIntersection( timeRange3 ) );
  // > TimeRange1.GetIntersection( TimeRange3 ):
  //             22.02.2011 16:00:00 - 18:00:00 | 02:00:00
  Console.WriteLine( "TimeRange3.GetIntersection( TimeRange2 ): " +
                     timeRange3.GetIntersection( timeRange2 ) );
  // > TimeRange3.GetIntersection( TimeRange2 ):
  //             22.02.2011 16:00:00 - 17:00:00 | 01:00:00
} // TimeRangeSample

- user687474

Answer 2

看看禁忌搜索和模拟退火算法，作为遗传算法的替代方案。

这与Drools Planner（Java，开源）中PAS示例非常相似，该示例涉及将患者安排到具有各种约束条件的医院床位中。请参见幻灯片和下一张幻灯片。

- Geoffrey De Smet

Answer 3

使用稀疏矩阵。

在酒店客房预订的情况下：

1. 横轴代表客房
2. 纵轴代表日期
3. 第三个轴代表时间间隔，指向预订数据对象。

它们（1、2、3）都可以表示为列表或哈希表（对于3）。

例如：

x = room 10
y = date 2021/4/3
z = time from 10am till 9pm

然后，您添加所有用于插入、删除、冲突等预订逻辑的方法。

可以证明，使用此结构，您可以通过遍历矩阵轻松管理任何预订。

- hjoab