Algoritmo de asignación de reservas

Question

Estoy buscando algoritmos para asignar reservas a los recursos. Esto podría ser reservas de hotel que coincidan con las habitaciones disponibles: reservas de reuniones que coincidan con las salas de reuniones disponibles: reservas de restaurante que coincidan con las tablas.

Lo que tienen en común:

• Cada reserva tiene una hora de inicio y fin inmutable específica.
• Cada reserva no está vinculada a un recurso específico antes de la hora de inicio.
• Puede haber una cantidad variable de recursos.
• Cada vez que llega una nueva reserva, el algoritmo debería al menos poder verificar si es posible hacer coincidir un recurso o no.

Hasta ahora he mirado en su mayoría algoritmo genético enfoques para resolver el problema, pero estoy teniendo problemas para codificar el problema de cromosomas.

Cualquier idea sobre los algoritmos para esto es bienvenida, también los algoritmos que solo encuentran una solución "buena" en lugar de una óptima.

Answer 1

Tome un vistazo a Búsqueda Tabú y recocido simulado como un reemplazo para los algoritmos genéticos.

Esto es muy similar al ejemplo de PAS en Drools Planner (java, código abierto), que trata sobre la programación de pacientes en camas de hospital con todo tipo de restricciones. Ver the slide y la siguiente diapositiva.

Answer 2

Este article incluye varias operaciones de tiempo para verificar períodos de tiempo libres, superpuestos e intersectados. Puede combinar fácilmente estas clases con sus objetos comerciales:

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