Introducción de penalizaciones de giro en el Problema General de Rutas con Capacidades sobre Grafos Mixtos

Abstract

En los últimos años varios problemas de rutas de vehículos han sido estudiados teniendo en cuenta las penalizaciones en los giros para aproximar los modelos matemáticos a los problemas de la vida real. Para el caso de un solo vehículo, se ha unificado el modelo para el estudio de problemas de rutas sobre arcos y sobre vértices. En este artículo generalizamos ese modelo unificado al caso capacitado. Presentamos el Problema General de Rutas Capacitado sobre Grafos Mixtos teniendo en cuenta penalizaciones en los giros y giros prohibidos. Mediante una transformación polinómica a problemas más sencillos, podemos resolver el problema original tanto de forma óptima como heurística usando algoritmos conocidos.