预留分配算法

Question

我正在寻找为资源分配预留的算法。这可以是与可用房间匹配的酒店预订-与可用会议室匹配的会议预订-与餐桌匹配的餐厅预订。

它们的共同点是：

• 每个预订都有特定的、不可更改的开始和结束时间。
• 每个预留在开始时间之前不绑定到特定资源。
• 资源的数量可以是可变的。
• 每次新的预留到来时，算法至少应该能够检查是否可以匹配资源。

到目前为止，我主要研究了解决该问题的遗传算法方法，但我在将问题编码到染色体上时遇到了麻烦。

关于算法的任何想法都是受欢迎的，也欢迎只找到“好的”解决方案而不是最佳解决方案的算法。

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

Answer 2

看一下禁忌搜索和模拟退火作为遗传算法的替代品。

这与 Drools Planner（java，开源）中的 PAS 示例非常相似，其中是关于在各种限制下将患者安排到医院病床上。
请参阅 幻灯片 和下一张幻灯片。

Answer 3

使用稀疏矩阵。

在酒店客房预订 ax x 的情况下，

1. 您有房间
2. ax y 您有日期
3. ax z 您有时间间隔，指向预订数据对象。

所有它们（1,2,3）都可以表示为列表，或者 3 可以表示为哈希表。

示例：

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

然后添加所有插入、删除、冲突等保留逻辑的方法。

可以证明，通过这种结构，您可以通过移动矩阵轻松管理任何预订。