El problema general de ruteamiento de vehículos (VRP) es un nombre genérico que hace referencia a una gran variedad de problemas aplicados en varias áreas del conocimiento como, transporte (Dantzing & Ramser, 1959), cadena de suministros, planeamiento de producción, telecomunicaciones, entre otros. Lo que hace de este problema uno de los temas más estudiados del área de investigación de operaciones. Es un problema que se combina fácilmente con otros problemas pertenecientes a diversas áreas del conocimiento. En este caso específico el interés es reducir la distancia recorrida por una flota de vehículos que deben salir de un depósito, atender unos clientes y regresar al depósito. Se busca reducir el impacto generado por la contaminación que producen los vehículos que operan con combustibles fósiles. Para esto se propone utilizar vehículos eléctricos que atiendan la ruta siguiendo la menor distancia. Varios trabajos muestran el uso de variantes interesantes como la inclusión de la disminución del uso de combustible en ruteamiento (Bekta? & Laporte, 2011; Koç, Bekta?, Jabali, & Laporte, 2014), el uso de análisis de variables físicas reales que afectan el consumo de combustible de los vehículos (Min, Jayaraman, & Srivastava, 1998), la inclusión de vehículos eléctricos (Schneider, Stenger, & Goeke, 2014), entre otros. En este trabajo, se analiza el uso de vehículos eléctricos (VEs) en el problema de ruteamiento de vehículos capacitado. En este problema surge una dificultad y es la autonomía de estos vehículos lo que exige la localización de estaciones de intercambio de baterías (BSS-EV-LRP, por sus siglas en ingles Batery Swap Station - Electric Vehicle - Location Routing Problem) propuesto por (Yang & Sun, 2015) o la localización de puntos de recarga de baterías. En este trabajo se analiza únicamente la localización de estaciones de intercambio de baterías por ser la que menos tiempo requiere. En consecuencia, este problema requiere determinar las rutas que deben seguir los vehículos y la localización de las estaciones de intercambio de baterías (EIB), las cuales están asociadas a dos características: el costo de apertura y su ubicación geográfica.
Como estrategia de solución se propone el uso de técnicas matheurísticas (Kramer & Subramanian, 2015) que combinen la exploración del espacio de solución por medio de búsquedas en vecindarios, y técnicas de clusterización que nos permitan reducir el espacio de la búsqueda local y así dar solución a las instancias modificadas propuestas en (Yang & Sun, 2015).
La técnica propuesta se basa en la búsqueda de la solución global partiendo de la infactibilidad al iniciar desde una solución parcial del problema de ruteamiento capacitado obtenido por una metaheurística: un algoritmo genético modificado de Chu-Beasley y sin considerar todavía la existencia de estaciones de intercambio de baterías. Al no considerar la carga eléctrica del vehículo ni la apertura de las EIBs, se encuentra una solución infactible para el problema que se resuelve, siendo necesario usar algoritmos de factibilización. En nuestro caso usamos una estrategia basada en soluciones obtenidas con el solver comercial CPLEX. Por otro lado, se plantea una estrategia diferente basada en el concepto de partición del problema en sub-problemas menores, seguido por la solución de los sub-problemas con técnicas exactas y de un proceso de unión de las soluciones parciales. Los sub-problemas resultantes son del tipo BSS-EV-LRP y son más fáciles de resolver por su tamaño. De esta manera es posible llevar a cabo un algoritmo que se encarge de identificar las variables más y menos atractivas para el problema con el fin de permitir al método exato trabajar todo el tiempo dentro de la factibilidad del problema, permitiendo llegar a soluciones de buena calidad para instancias donde una metodología exacta no alcanza una buena solución en el problema sin dividir.
