Algoritmos para la programación de vehículos eléctricos en los esquemas de movilidad-on-Demand a gran escala

Se estudia un escenario donde se pueden alquilar vehículos eléctricos (EVs) para conducir desde la recogida en puntos de entrega en un esquema de movilidad-on-Demand (MoD). El objetivo del sistema es, o bien para maximizar el número de clientes que son atendidos, o de la utilización total de EV. Para ello, nos caracterizan el problema de optimización como un problema de flujo máximo para determinar el conjunto de viajes factibles dado el EVs disponible en cada lugar. Continuación modelo y resolver el problema de programación de EV a viaje offline y óptima usando técnicas de programación entera mixta (MIP) y muestran que las escalas de solución hasta medio tamaño de problemas. Ante esto, desarrollamos dos algoritmos no óptima, es decir, un algoritmo incremental-MIP para medianas y grandes problemas y un algoritmo heurístico voraz para problemas muy grandes. Además, desarrollamos una técnica de búsqueda local basado en la búsqueda de tabu para mejorar y comparar con la solución de los algoritmos no óptima. Estudiamos el funcionamiento de estos algoritmos en entornos donde se utiliza el intercambio de batería o carga de la batería en cada estación para hacer frente a la autonomía limitada del SVE. Además, en ajustes donde EVs necesitan ser programadas en línea, proponemos un algoritmo novedoso que representa la incertidumbre en el futuro viaje de solicitudes. Todos los algoritmos se evalúan empíricamente utilizando datos reales de ubicación de las estaciones de recogida y entrega de vehículo compartido. En nuestros experimentos, observamos que cuando EVs todos llevan la misma batería que es lo suficientemente grande para los viajes más largos, el algoritmo codicioso con swap de la batería con la solución de flujo máximo como al paso, proporciona la solución óptima. Al mismo tiempo, el algoritmo voraz con la carga de la batería está cerca de la óptima (97% en promedio) y se mejora aún más cuando se utiliza la búsqueda local. Cuando algunos EVs no dispone de una batería lo suficientemente grande como para ejecutar algunos de los viajes más largos, incremental-MIP genera soluciones un poco mejores que los avaros, mientras que el algoritmo óptimo es el mejor pero escala hasta problemas de tamaño medio sólo. Por otra parte, el algoritmo en línea se muestra que en promedio al menos el 90% de la óptima. Por último, el algoritmo voraz escala a 10 – veces más tareas que el incremental de MIP y 1000 – veces más que el MIP estática en tiempo razonable.

Haga clic aquí para más información