Planificación de Rutas Unificadas para Movilidad Compartida: Un Marco Basado en Inserciones

Ha habido un crecimiento dramático de aplicaciones de movilidad compartida como el uso compartido de vehículos, la entrega de alimentos y la entrega de paquetes colaborativa. La movilidad compartida se refiere a servicios de transporte que son compartidos entre usuarios, donde un tema central es la planificación de rutas. Dado un conjunto de trabajadores y solicitudes, la planificación de rutas encuentra para cada trabajador una ruta, es decir, una secuencia de ubicaciones para recoger y dejar pasajeros/paquetes que llegan de vez en cuando, con diferentes objetivos de optimización. Los estudios anteriores carecen de aplicabilidad debido a sus objetivos conflictivos y la ineficiencia en insertar una nueva solicitud en una ruta, una operación básica llamada inserción. Además, las soluciones de planificación de rutas anteriores no aprovechan los patrones de aparición de futuras solicitudes ocultas en datos históricos para la optimización. En este documento, presentamos una formulación unificada de la planificación de rutas llamada URPSM. Tiene una función objetivo parametrizada bien definida que elimina los objetivos contradictorios en estudios anteriores y permite una planificación de rutas multiobjetivo flexible para la movilidad compartida. Proponemos dos marcos basados en inserciones para resolver el problema URPSM. El primero se basa en la inserción simple ampliamente utilizada en estudios previos, que procesa solo solicitudes en línea, mientras que el segundo se basa en un nuevo operador de inserción llamado inserción profeta que maneja tanto solicitudes en línea como previstas. Se diseñan nuevos algoritmos de programación dinámica para acelerar ambas inserciones a tiempo lineal. El análisis teórico muestra que ningún algoritmo en línea puede tener una relación competitiva constante para el problema URPSM bajo el modelo de análisis competitivo, sin embargo, nuestro marco basado en inserción profeta puede lograr una relación de optimalidad constante bajo el modelo de optimalidad por instancia. Resultados experimentales extensivos en conjuntos de datos reales muestran que nuestras soluciones basadas en inserciones superan a los algoritmos de última generación en efectividad y eficiencia por un amplio margen (por ejemplo, hasta un 30\ (%) más efectivas en el objetivo y hasta un 20\ (%) más rápidas).