Problema de reprogramación de vehículos

El problema de reprogramación de vehículos ( VRSP , por sus siglas en inglés) es un problema de optimización combinatoria y programación entera que busca atender a los clientes en un viaje después de un cambio de horario, como una avería del vehículo o un retraso importante. Propuesto por Li, Mirchandani y Borenstein en 2007, ^{[ 1 ]} el VRSP es un problema importante en los campos del transporte y la logística.

Determinar la solución óptima es un problema NP-completo en optimización combinatoria , por lo que en la práctica se utilizan métodos heurísticos y deterministas para encontrar soluciones aceptablemente buenas para el VRSP.

Existen varias variantes y especializaciones del problema de reprogramación de vehículos:

• Problema de reprogramación de vehículos en un solo depósito (SDVRSP): Varios viajes deben reprogramarse debido a retrasos, averías de vehículos o cualquier otro motivo. El objetivo es encontrar la reprogramación óptima de la flota existente, utilizando posiblemente vehículos adicionales del depósito, para minimizar los retrasos y los costos operativos. En la variante de depósito único, solo hay un depósito que contiene todos los vehículos adicionales, y en el que cada vehículo inicia y finaliza su horario.
• Problema de reprogramación de vehículos en múltiples depósitos (MDVRSP): Similar al SDVRSP, pero con la adición de depósitos. Cada depósito tiene restricciones de capacidad y un número variable de vehículos adicionales. Generalmente, los horarios de los vehículos incluyen una restricción adicional que exige que cada vehículo regrese al depósito donde inició su recorrido.
• Problema abierto de reprogramación de vehículos (OVRSP): Los vehículos no tienen que regresar al depósito.

Aunque VRSP está relacionado con el Problema de Programación de Vehículos en un Solo Depósito y el Problema de Programación de Vehículos en Múltiples Depósitos , existe una diferencia significativa en los requisitos de tiempo de ejecución, ya que VRSP debe resolverse casi en tiempo real para permitir la reprogramación durante las operaciones, mientras que SDVSP y MDVSP generalmente se resuelven utilizando métodos de programación lineal de larga duración. ^{[ 2 ]}

Otro campo donde se utiliza VRSP es en el transporte de mercancías para reprogramar las rutas cuando la demanda cambia sustancialmente ^{[ 3 ].}

• Optimización combinatoria
• Problema de enrutamiento de vehículos

• Optibus archivado el 9 de marzo de 2019 en Wayback Machine : plataforma SaaS comercial para resolver VRSP en tiempo real.
• Ecolane archivado el 27/07/2014 en Wayback Machine : software comercial para el transporte a demanda.