Formulaciones basadas en flujos en redes para un problema de ruteo en last mile

Abstract

En el presente trabajo se busca analizar y proponer formulaciones matemáticas algebraicas para un problema específico de ruteo de última milla que apoya procesos de transporte y distribución del e-commerce, el problema específico se basa en el problema del vendedor viajero (TSP) con reemplazo de drones. Este problema es analizado debido al alza del e-commerce abordado por las grandes compañías con la nueva tecnología que reduce los costos de transporte reemplazando la energía de combustibles que usan los vehículos por la energía eléctrica usada por los drones. Los distintos modelos se diferencian en la forma de eliminación de sub-tours que puede producir el TSP. Los modelos que se analizan son: MTZ, F1 y F2. Se resuelven 15 instancias distintas variando la cantidad de drones que estarán a disposición en distintas bases de datos. Los modelos son resueltos con AMPL utilizando el solver CPLEX. Como conclusión se obtiene que los modelos no tienen diferencia en su valor óptimo escogido, pero si existe diferencia en el tamaño del problema y en los tiempos de ejecución de los solver. Obteniendo como los modelos más recomendables los modelos F1 y luego en F2 (en ese orden). El modelo MTZ no es un buen modelo para este problema por los tiempos de ejecución alto.