Reservation allocation algorithm

I am looking for algorithms for allocating reservations to resources. This could be Hotel reservations matched to available rooms - Meeting reservations matched to available meeting rooms - Restaura开发者_StackOverflow社区nt reservations matched to tables.

What they have in common:

• Each reservation has a specific unchangeable start and end time.
• Each reservation is not bound to a specific resource before the start time.
• There can be a variable number of resources.
• Every time a new reservation comes, the algorithm should at least be able to check if it is possible to match to a resource or not.

So far I have mostly looked at genetic algorithm approaches to solve the problem, but I'm having trouble encoding the problem to chromosomes.

Any thoughts on algorithms for this is welcome, also algorithms that only finds a "good" solution as opposed to an optimal one.

This article includes various time operation to check for free, overlapping and intersecting time periods. You can easily combine this classes with your business objects:

// ----------------------------------------------------------------------
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

Take a look at Tabu search and Simulated Annealing as a replacement for genetic algorithms.

This is very similar to the PAS example in Drools Planner (java, open source), which is about scheduling patients into hospital beds with all kinds of constraints. See the slide and the next slide.

Use a sparse matrix.

In the case of a hotel rooms reservations

1. axe x you have the rooms
2. axe y you have the dates
3. axe z you have the time intervals, pointing to the reservation data object.

All them (1,2,3) could be represented as a list or for 3 a hash table.

Example:

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

Then you add all the methods for inserting, deleting, collisions etc. reservations logic.

It can be proved that with this structure you can easily manage any reservation by traveling the matrix.