💻 computer science

A Graph-based Decomposition Framework for Flow-based Charging Station Location Problems

Este artículo propone un marco de descomposición basado en grafos que mejora la eficiencia computacional y la escalabilidad al resolver problemas de localización de estaciones de carga basados en flujo en redes de transporte a gran escala mediante la partición de la red en subproblemas más pequeños, su resolución individual y el refinamiento de los resultados agregados.

Autores originales: Jingyu Xiang, Paula Carroll, Annunziata Esposito Amideo

Publicado 2026-08-25

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Jingyu Xiang, Paula Carroll, Annunziata Esposito Amideo

Artículo original bajo licencia CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

La transición hacia los vehículos eléctricos es uno de los cambios más significativos en el transporte moderno, prometiendo limpiar el aire y reducir la huella de carbono de los viajes diarios. Sin embargo, para que esta transición tenga éxito, los conductores necesitan una red fiable de estaciones de carga. A diferencia de llenar un tanque de gasolina, que toma minutos y está disponible en casi cada esquina, recargar un vehículo eléctrico requiere tiempo y una ubicación específica. Si un conductor no puede encontrar un cargador cuando la batería se agota, el vehículo se vuelve inútil, creando un fenómeno conocido como ansiedad por la autonomía. Esta ansiedad es particularmente aguda para los viajes de larga distancia, donde el vehículo debe atravesar vastas extensiones de carretera sin la red de seguridad de un punto de abastecimiento cercano. En consecuencia, los planificadores urbanos e ingenieros se enfrentan a un rompecabezas complejo: ¿dónde exactamente deben construirse estas estaciones para servir a la mayor cantidad de personas de manera eficiente, sin desperdiciar dinero en infraestructura redundante?

Esta pregunta no se trata simplemente de elegir puntos en un mapa; es un desafío matemático masivo. La red de transporte es una trama de carreteras que conecta miles de pueblos e intersecciones, con millones de posibles viajes ocurriendo cada día. Para encontrar la solución perfecta, las computadoras deben analizar cada ruta posible, cada tecnología de carga posible y cada combinación posible de ubicaciones de estaciones. A medida que el tamaño de la red de carreteras crece, el número de cálculos requeridos se dispara, abrumando a menudo incluso a las supercomputadoras más potosas. Los métodos tradicionales que intentan resolver todo el problema a la vez suelen quedarse estancados, incapaces de encontrar una buena respuesta en un tiempo razonable. Investigadores del University College Dublin han desarrollado una nueva forma de abordar este problema dividiendo la enorme red en piezas más pequeñas y manejables, lo que les permite encontrar soluciones de alta calidad para sistemas de autopistas a gran escala que anteriormente eran demasiado difíciles de resolver.

Los investigadores se centraron en la red de autopistas irlandesa, un sistema de 90 nodos clave que representan ciudades principales e intersecciones. Su objetivo era determinar las ubicaciones óptimas para las nuevas estaciones de carga, equilibrando dos metas contrapuestas: mantener lo más bajo posible el costo de construcción y operación de las estaciones, y minimizar el tiempo adicional que los conductores pasan cargando o realizando desvíos para llegar a un cargador. Utilizaron un modelo sofisticado que tiene en cuenta diferentes tipos de carga, como cargadores lentos de conexión fija, cargadores rápidos y estaciones de intercambio de baterías, así como el hecho de que los conductores podrían tomar rutas ligeramente más largas para llegar a una estación si eso les ahorra tiempo en general. Cuando intentaron resolver este problema utilizando métodos directos estándar en una computadora potente, el sistema tuvo dificultades. Incluso después de ejecutarse durante cinco horas, la computadora no pudo encontrar una solución que fuera tanto económica como eficiente, dejando a menudo el costo de la red propuesta significativamente más alto de lo necesario.

Para superar este obstáculo, el equipo introdujo un marco de descomposición basado en grafos. En lugar de intentar resolver toda la red de autopistas como un solo bloque gigante, utilizaron técnicas matemáticas para rebanar la red en subredes más pequeñas y distintas. Imagine el sistema de autopistas como una gran bola de estambre enredada; el método de los investigadores la desenreda cuidadosamente en varios paquetes más pequeños y ordenados. Probaron tres formas diferentes de cortar estos paquetes: un método que agrupaba los pueblos según límites administrativos, otro que utilizaba un algoritmo de alta calidad para equilibrar el flujo de tráfico entre los grupos, y un tercero que agrupaba los pueblos basándose en qué tan cerca estaban unos de otros. Una vez dividida la red, los investigadores resolvieron el problema de las estaciones de carga para cada pequeño paquete de forma independiente. Luego, cosieron estas soluciones locales nuevamente, añadiendo algunas estaciones extra para gestionar el tráfico que se movía entre los diferentes paquetes. Finalmente, realizaron un proceso de refinamiento para eliminar cualquier estación innecesaria y asegurar que todo el sistema funcionara fluidamente en su conjunto.

Los resultados de este enfoque fueron sorprendentes. Al desglosar el problema, los investigadores pudieron encontrar soluciones que no solo fueron más rápidas de computar, sino también significativamente mejores que las encontradas por el método directo. En sus pruebas, el marco de descomposición produjo redes de estaciones de carga que costaban sustancialmente menos de construir y operar, manteniendo al mismo tiempo las restricciones de tiempo para los conductores. Por ejemplo, en un escenario donde el método directo no logró encontrar una buena solución tras cinco horas, el método de descomposición encontró una solución superior en menos de una hora. El estudio demostró que la forma en que se cortaba la red importaba enormemente. El método que equilibraba el flujo de tráfico entre los grupos más pequeños fue el que mejor funcionó, sugiriendo que una buena solución depende de comprender cómo se mueven realmente las personas a través del paisaje, no solo de cómo están conectadas físicamente las carreteras.

Los investigadores también descubrieron que simplemente hacer las piezas más pequeñas no siempre era mejor. Si cortaban la red en demasiados fragmentos diminutos, las conexiones entre las piezas se volvían demasiado débiles y la solución final sufría. El enfoque más efectivo fue una división moderada que preservaba el flujo natural del tráfico mientras mantenía los problemas individuales lo suficientemente pequeños como para resolverse rápidamente. Este hallazgo ofrece un camino claro hacia adelante para los planificadores: la clave para resolver estos masivos rompecabezas de infraestructura reside en respetar la estructura subyacente de la red y los patrones de viaje humano. Al utilizar este marco de descomposición, los planificadores pueden ahora abordar problemas de estaciones de carga a gran escala que antes estaban fuera de su alcance, asegurando que la revolución de los vehículos eléctricos esté respaldada por una red de infraestructura de carga robusta, eficiente y bien planificada.

Resumen Técnico: Un Marco de Descomposición Basado en Grafos para Problemas de Localización de Estaciones de Carga Basados en Flujos

Planteamiento del Problema

El Problema de Localización de Estaciones de Carga (CSLP, por sus siglas en inglés) es fundamental para apoyar la adopさせて de los Vehículos Eléctricos (EV) y alcanzar los objetivos de neutralidad de carbono. Si bien se han desarrollado modelos avanzados de CSLP basados en flujos para considerar restricciones realistas —como tecnologías de carga heterogéneas, límites de capacidad, desviaciones de ruta y compensaciones multiobjetivo entre el costo de infraestructura y el tiempo de viaje del usuario—, resolver estos modelos en redes de transporte a gran escala sigue siendo computacionalmente prohibitivo.

Las técnicas de descomposición existentes para CSLP típicamente particionan el modelo de optimización separando variables, restricciones o escenarios. Sin embargo, estos métodos a menudo no logran aprovechar la estructura topológica subyacente de la red de transporte. En consecuencia, existe una brecha en la literatura con respecto a los enfoques de descomposición basados en grafos que preserven la conectividad de la red y las distribuciones de flujo espacial, particularmente para modelos de flujo bi-objetivo donde los compromisos globales son difíciles de mantener cuando los subproblemas se resuelven de forma independiente.

Metodología

El artículo propone un marco de descomposición basado en grafos diseñado para resolver modelos de CSLP basados en flujos bi-objetivo a gran escala. El marco se ilustra mediante el Modelo de Localización de Reabastecimiento de Multicamino Capacitado con Múltiples Tipos de Estaciones de Carga (CMPRLM-MTCS), un Programa Lineal Entero Mixto (MILP) bi-objetivo que minimiza:

$z_1$ : Costos totales de inversión y operación de nuevas estaciones y expansiones.
$z_2$ : Tiempo de viaje adicional total (tiempo de carga + tiempo de desviación) experimentado por los usuarios de EV.

El marco opera a través de un proceso de cuatro etapas:

1. Descomposición de la Red

La red de transporte original $G=(N, A)$ se descompone en $P$ subredes disjuntas utilizando técnicas de partición de grafos o agrupamiento (clustering). El estudio evalúa tres métodos específicos:

KaHIP: Una herramienta de partición de grafos de alta calidad que minimiza los cortes de aristas mientras equilibra los pesos de los nodos (flujo de tráfico).
Partición Geográfica: Descomposición basada en regiones administrativas (por ejemplo, provincias irlandesas), refinada posteriormente mediante KaHIP.
Agrupamiento Jerárquico: Agrupamiento aglomerativo basado en distancias inter-clúster, con variantes para pares O-D (Origen-Destino) no ponderados y ponderados por flujo.

2. Descomposición del Flujo de Tráfico y Resolución de Subproblemas

La demanda de tráfico se categoriza en tres componentes:

Flujos intra-subred: Pares O-D dentro de la misma subred. Estos se resuelven como subproblemas de CSLP independientes.
Flujos inter-subred agregados: Pares O-D que cruzan los límites de las subredes. Para evitar reintroducir la carga computacional completa, estos flujos se agregan en pares O-D representativos que conectan las subredes. La selección de representantes se basa en métricas de distancia (media, mediana, media/mediana ponderada por flujo) relativas al rango de conducción del EV.
Flujos no atendidos: Pares O-D residuales que permanecen sin cobertura tras resolver las dos primeras etapas.

El marco resuelve primero los subproblemas intra-subred, fijando las ubicaciones de las estaciones resultantes como instalaciones existentes. Luego, resuelve un subproblema para los flujos inter-subred agregados.

3. Recuperación e Integración

Dado que resolver subproblemas descompuestos de forma independiente no garantiza una solución factible para el problema global original (específicamente con respecto a la restricción de tiempo global $z_2$ ), se introduce un paso de recuperación. Se resuelve una versión relajada del modelo original ( $M''$ ) para identificar cualquier par O-D no atendido. Se añade un término de penalización a la función objetivo para forzar la selección de estaciones adicionales que cubran estos flujos residuales.

4. Refinamiento Final

Se aplica un algoritmo de refinamiento de post-procesamiento (Algoritmo 1) a la solución integrada. Esta etapa:

Asigna el tipo de carga más eficiente a las ubicaciones seleccionadas.
Elimina iterativamente las estaciones redundantes si la factibilidad se preserva.
Realiza intercambios de tipos de carga (por ejemplo, intercambiar tipos de estación entre ubicaciones) para reducir el costo total manteniendo la factibilidad.

Contribuciones Clave

Marco Novedoso: El artículo introduce una estrategia de descomposición que particiona la topología de la red en lugar de solo las variables de optimización, preservando las características espaciales y topológicas esenciales de la instancia original a gran escala.
Adaptación Bi-Objetivo: El marco aborda específicamente los desafíos de la optimización bi-objetivo en la descomposición. Emplea un mecanismo de recuperación y una estrategia de preservación de restricciones globales (usando el método $\epsilon$ -restricción) para asegurar que las soluciones de los subproblemas locales se integren en una solución global de alta calidad sin perder el compromiso previsto entre costo y tiempo.
Estrategia de Agregación: Propone un método para agregar flujos inter-subred utilizando pares O-D representativos, equilibrando la eficiencia computacional con la necesidad de capturar mejor las características de distribución espacial en comparación con los enfoques de un solo nodo medián.
Evaluación Empírica: El estudio proporciona una evaluación sistemática de diferentes configuraciones de descomposición (variando métodos, número de subredes $P$ y esquemas de ponderación) utilizando tanto indicadores basados en grafos (por ejemplo, cortes de aristas, diámetro de la subred) como indicadores basados en flujos (por ejemplo, desequilibrio de carga de flujo, ratio de flujo inter-subred).

Resultados Experimentales

El marco fue probado en una instancia de una red de carreteras irlandesa de 90 nodos. Los experimentos computacionales compararon el marco de descomposición contra la resolución directa del modelo original utilizando el optimizador Gurobi (con un límite de tiempo de 18,000 segundos).

Eficiencia Computacional: El marco de descomposición consistentemente logró soluciones con valores de la función objetivo relacionados con el costo ( $z_1$ ) menores en tiempos de computación sustancialmente más cortos (típicamente por debajo de 4,000 segundos) en comparación con el benchmark de Gurobi.
Calidad de la Solución: Para instancias desafiantes (por ejemplo, restricciones de tiempo más estrictas con $\alpha=0.9$ o mayores márgenes de desviación), Gurobi a menudo falló en encontrar soluciones factibles de alta calidad dentro del límite de tiempo, devolviendo costos altos o grandes brechas de integralidad. El marco de descomposición encontró con éxito soluciones factibles y de menor costo.
Comparación de Métodos: Las descomposiciones basadas en KaHIP generalmente produjeron los mejores resultados de CSLP, superando tanto a la partición geográfica como al agrupamiento jerárquico. Esto sugiere que mantener cargas de tráfico equilibradas y minimizar los cortes de aristas es más crítico para el desempeño del CSLP que la mera compacidad espacial.
Impacto de $P$ : Aumentar el número de subredes ( $P$ ) no mejoró el rendimiento de forma lineal. Las descomposiciones excesivamente finas (por ejemplo, $P=13$ o $18$) fragmentaron la red, aumentaron la proporción de flujos inter-subred y degradaron la calidad de la solución. Los niveles de descomposición moderados (por ejemplo, $P=6$ o $9$) resultaron óptimos.
Esquemas de Ponderación: La incorporación de pesos de arista y pesos de flujo O-D en el proceso de descomposición generalmente mejoró los resultados del CSLP, resaltando la importancia de reflejar tanto la estructura de la red como la intensidad de la demanda de tráfico en el proceso de partición.

Significado y Reivindicaciones

El artículo afirma que el marco propuesto ofrece una estrategza de solución efectiva y escalable para modelos de CSLP basados en flujos bi-objetivo en redes de transporte a gran escala. Su importancia radica en:

Cerrar la Brecha: Conecta el análisis de descomposición de red con la optimización de CSLP, demostrando que preservar las características topológicas y los patrones de flujo es crucial para la calidad de la solución.
Aplicabilidad Práctica: El marco apoya una lógica de planificación progresiva (despliegue local $\to$ soporte inter-regional $\to$ refinamiento de todo el sistema) que refleja las estrategias de despliegue de infraestructura del mundo real.
Desempeño: Demuestra que la descomposición basada en la topología de la red puede superar a la optimización directa y a los métodos de descomposición basados en variables en términos de tiempo de computación y costo de la solución para problemas complejos de planificación de infraestructura de EV a gran escala.

Los autores concluyen que, si bien el marco es prometedor, la investigación futura debería explorar reglas adaptativas para seleccionar el número de subredes, estrategias avanzadas para el manejo de flujos inter-subred y la integración de metaheurísticas en las etapas del marco.