SynthCharge: An Electric Vehicle Routing Instance Generator with Feasibility Screening to Enable Learning-Based Optimization and Benchmarking

Each language version is independently generated for its own context, not a direct translation.

¡Claro que sí! Imagina que quieres organizar una flota de camiones eléctricos para repartir paquetes en una ciudad. No es tan sencillo como en las películas de reparto clásico, ¿verdad? Aquí tienes dos problemas nuevos: la batería se agota y hay que parar a cargar.

Este paper presenta una herramienta llamada SynthCharge. Para explicártelo de forma sencilla, vamos a usar una analogía de un videojuego de construcción de ciudades.

1. El Problema: El "Mundo Abierto" que no funciona

Antes de SynthCharge, los investigadores que crean algoritmos inteligentes (IA) para estos camiones tenían un problema: usaban mapas de prueba que eran estáticos y a veces estaban rotos.

La analogía: Imagina que estás entrenando a un piloto de dron para que entregue pizzas. Pero le das un mapa donde la casa del cliente está en medio de un lago sin puente, o donde la batería del dron se acaba antes de llegar a la primera casa. Si entrenas a tu IA con estos mapas "rotos", la IA aprenderá cosas malas o no sabrá qué hacer cuando el mundo real sea diferente.
La solución: Necesitas un generador de mapas que cree situaciones realistas, variadas y, lo más importante, que sepa si el mapa es posible de recorrer antes de dártelo.

2. La Solución: SynthCharge, el "Arquitecto de Mundos"

SynthCharge es como un arquitecto de videojuegos que crea niveles de prueba para tus camiones eléctricos. No solo dibuja calles y casas; piensa en la física de la batería.

Aquí está cómo funciona, paso a paso:

A. Dibuja el mapa (Geometría y Topología)

El arquitecto puede crear tres tipos de ciudades:

Caóticas (Random): Como una ciudad donde las casas están esparcidas al azar por todo el mapa.
Vecindarios (Clustered): Como una ciudad con barrios densos, donde las casas están muy juntas en grupos.
Mixtas (Mixed): Una combinación de ambos.

B. Coloca las estaciones de carga (La magia de la "Alcance")

Aquí es donde SynthCharge es brillante. En lugar de poner las estaciones de carga en lugares fijos y tontos, el arquitecto las coloca inteligentemente.

La analogía: Imagina que el camión tiene un tanque de gasolina que le permite recorrer 100 km. El arquitecto se asegura de que, si el camión va de la casa A a la casa B y está a punto de quedarse sin batería, haya una estación de carga justo en el medio o cerca.
Si el mapa es tan grande que el camión no puede llegar a ningún cliente sin recargar, el arquitecto no te da ese mapa. Lo descarta inmediatamente.

C. El "Filtro de Realidad" (Screening de Factibilidad)

Esta es la parte más importante. SynthCharge tiene dos filtros de seguridad:

El Filtro Rápido (Ojo de Águila): Revisa rápidamente si hay clientes que están simplemente demasiado lejos de cualquier estación de carga o del depósito. Si un cliente está en una isla sin puente, ¡basta! Se tira el mapa y se hace otro.
El Filtro de Experto (Para mapas pequeños): Para mapas con pocos clientes (menos de 10), el sistema hace un cálculo matemático perfecto y lento para asegurarse al 100% de que existe una ruta posible.

3. ¿Por qué es esto importante para la Inteligencia Artificial?

Hoy en día, usamos IA (aprendizaje automático) para que los camiones encuentren las rutas más rápidas. Pero la IA es como un estudiante que estudia solo para un examen específico. Si el examen cambia un poco (más clientes, calles más largas, baterías más pequeñas), la IA falla.

Sin SynthCharge: La IA entrena con los mismos 50 mapas viejos. Aprende de memoria, pero no entiende la lógica.
Con SynthCharge: Podemos generar miles de mapas nuevos con diferentes niveles de dificultad (tiempos más ajustados, baterías más pequeñas, calles más largas). Esto obliga a la IA a aprender reglas generales y no solo a memorizar rutas. Es como si el estudiante practicara con miles de exámenes diferentes en lugar de solo uno.

4. En resumen

SynthCharge es una fábrica de problemas de reparto eléctrico que:

Crea escenarios variados (ciudades caóticas, barrios densos).
Asegura que la batería y las estaciones de carga tengan sentido (no crea escenarios imposibles).
Filtra los escenarios "rotos" antes de que lleguen al investigador.
Permite probar si las nuevas IAs son realmente inteligentes o solo están memorizando.

Es la herramienta que necesita la ciencia para decir: "Oye, mi algoritmo de camiones eléctricos no solo funciona en el mapa que le di, sino que es lo suficientemente listo para manejar cualquier ciudad que le lances".

Each language version is independently generated for its own context, not a direct translation.

Resumen Técnico: SynthCharge

1. El Problema: Limitaciones en la Evaluación de EVRPTW

El Problema de Enrutamiento de Vehículos Eléctricos con Ventanas de Tiempo (EVRPTW) es una extensión compleja del VRPTW clásico que incorpora restricciones de capacidad de batería y decisiones sobre la ubicación y el momento de recarga.

El artículo identifica dos limitaciones críticas en el estado actual de la investigación:

Falta de datos dinámicos y verificables: Los conjuntos de datos de referencia (benchmarks) existentes suelen ser estáticos, finitos y carecen de información verificable sobre la factibilidad de las instancias. Esto dificulta la evaluación reproducible de modelos de optimización basados en aprendizaje (redes neuronales, aprendizaje por refuerzo).
Bottleneck de generalización: Los modelos de aprendizaje profundo entrenados en distribuciones fijas de instancias tienden a degradarse cuando enfrentan cambios en la estructura espacial, el tamaño del problema o los parámetros de restricción (desplazamiento de distribución). Las suites de benchmarks actuales no permiten una variación paramétrica sistemática para probar la robustez de estos modelos.

2. Metodología: El Generador SynthCharge

Para abordar estas carencias, los autores presentan SynthCharge, un generador de instancias EVRPTW totalmente paramétrico diseñado para crear datos sintéticos diversos, geoespaciales y con factibilidad garantizada.

Componentes Clave del Generador:

Generación de Topología Espacial:
- Los nodos (depósito, clientes, estaciones de carga) se generan dentro de un cuadrado unitario $[0, 1]^2$ .
- Soporta tres familias espaciales inspiradas en los benchmarks de Solomon: Aleatoria (R), Agrupada (C) y Mixta (RC).
- El depósito puede ubicarse en el centro, aleatoriamente o en una posición específica.
Infraestructura de Carga Inteligente (Range-Aware):
- A diferencia de los benchmarks estáticos, la ubicación de las estaciones de carga no es fija. Se determina mediante reglas geométricas basadas en el rango de viaje máximo ( $R$ ) del vehículo.
- Se insertan estaciones candidatas entre pares de clientes o entre clientes y el depósito si la distancia supera ciertos umbrales relativos a $R$ (ej. $0.8R$ o $0.7R$ ), asegurando la conectividad básica.
Escalado Adaptativo de Energía:
- La capacidad de la batería ( $B$ ) no es un valor fijo arbitrario. Se escala dinámicamente en función de la dispersión espacial de la instancia (distancia máxima entre clientes).
- Esto evita instancias triviales (demasiado fáciles o imposibles) a medida que cambia el tamaño o la distribución espacial.
Asignación de Ventanas de Tiempo:
- Se define un horizonte de planificación $[0, H]$ y una fracción de ancho $\phi$ .
- Permite tres regímenes: amplio ( $\phi=0.8$ ), medio ( $\phi=0.4$ ) y ajustado ( $\phi=0.2$ ).
Procedimiento de Filtrado de Factibilidad (Dos Etapas):
Para garantizar la validez estructural, SynthCharge aplica un filtro riguroso:
1. Fase 1 (Detección Estructural Lineal): Verifica condiciones necesarias en tiempo lineal $O(N)$ $O (N)$ :
  - Alcance energético: Cada cliente debe estar dentro del rango $R$ de al menos un nodo de recarga (depósito o estación).
  - Consistencia de retorno: Debe ser posible volver al depósito dentro del horizonte de tiempo.
  - Accesibilidad a estaciones: Existencia de una ruta de recarga viable.
  - Las instancias que fallan se descartan y regeneran.
2. Fase 2 (Verificación Exacta MILP): Para instancias pequeñas ( $N \le 10$ ), se ejecuta un solucionador exacto de Programación Lineal Entera Mixta (MILP) para confirmar la existencia de una ruta factible que satisfaga todas las restricciones (flujo, tiempo, energía).
Salida y Reproducibilidad:
- Genera archivos de instancias estandarizados y metadatos JSON detallados.
- Utiliza semillas aleatorias fijas por instancia para garantizar la reproducibilidad exacta.

3. Contribuciones Clave

Infraestructura de Benchmarking Dinámico: SynthCharge no es un solucionador, sino una herramienta para generar datos que permiten evaluar modelos de aprendizaje bajo variaciones sistemáticas de estructura espacial, escala de clientes y restricciones de energía.
Filtrado de Factibilidad Explícito: Introduce un mecanismo de validación que elimina instancias estructuralmente inviables antes de su uso, proporcionando una métrica de "tasa de aceptación" ( $\gamma$ ) como indicador de fiabilidad de los datos.
Escalado Geométrico de Energía: Vincula la capacidad de la batería a la geometría de la instancia, creando un entorno de prueba más realista y desafiante que los benchmarks estáticos tradicionales.
Código Abierto y GUI: Se ofrece una interfaz gráfica interactiva y un paquete de código abierto para facilitar la adopción por la comunidad.

4. Resultados Experimentales

Los autores evaluaron el generador en un rango de tamaños de 5 a 100 clientes, combinando diferentes topologías espaciales y regímenes temporales.

Tasas de Aceptación ( $\gamma$ ):
- La factibilidad no es trivial y depende del régimen. Las ventanas de tiempo más ajustadas reducen la tasa de aceptación, especialmente en configuraciones agrupadas (Clustered).
- Las tasas medias oscilaron entre ~37% y ~47%, lo que demuestra que el filtrado elimina una porción significativa de instancias inviables.
Eficiencia de Generación:
- El tiempo de generación es muy rápido. Para $N > 10$ (donde solo se usa el filtrado estructural), el tiempo es inferior a 0.01 segundos por instancia aceptada.
- Para $N \le 10$ , el tiempo es mayor (~0.1s) debido a la verificación MILP exacta, pero sigue siendo eficiente para fines de entrenamiento.
Validación de Solvabilidad Práctica:
- Se probó un metaheurístico (búsqueda de vecindad variable / búsqueda tabú) en todas las instancias generadas.
- Resultado: El 100% de las instancias que pasaron el filtrado estructural fueron resolubles por el metaheurístico, confirmando que el filtro de Fase 1 es un predictor altamente fiable de la factibilidad real de enrutamiento.
Impacto de las Restricciones:
- Se observó que el ajuste de las ventanas de tiempo y la dispersión espacial aumentan monótonamente la distancia total recorrida y el tamaño de la flota necesaria.

5. Significado e Impacto

El trabajo de SynthCharge es fundamental para el avance de la optimización combinatoria basada en aprendizaje en sistemas de transporte inteligentes (ITS):

Superación del "Overfitting" de Benchmarks: Permite entrenar y evaluar modelos de IA en distribuciones de datos controladas y variables, evitando que los modelos solo aprendan patrones de un conjunto de datos fijo.
Transparencia y Reproducibilidad: Al proporcionar metadatos completos y un proceso de validación explícito, establece un nuevo estándar para la creación de conjuntos de datos en logística sostenible.
Puente entre Teoría y Práctica: Facilita la investigación de algoritmos que deben operar en tiempo real bajo restricciones energéticas y temporales dinámicas, un requisito crítico para la electrificación de la logística de última milla.

En conclusión, SynthCharge proporciona la infraestructura necesaria para evaluar rigurosamente la robustez de los nuevos enfoques de enrutamiento neuronal, asegurando que las mejoras reportadas sean generalizables y no artefactos de conjuntos de datos estáticos y potencialmente inviables.