[AlvaroGC]

Buenas tardes.

Estoy intentando desarrollar un modelo similar a los típicos modelos de planificación de ruta de vehículos (salir desde un nodo, recorrer todos los demás nodos sólo una vez y volver al nodo de salida), pero con la salvedad de que el coste de pasar desde un nodo \( n_k \) a otro nodo \( n_{k + 1} \) varía en función de los nodos que se hayan visitado previamente. Esto es debido a que en mi función objetivo tengo en cuenta el coste de carburante del vehículo derivado de la carga que soporta, porque consumirá más carburante cuanto más cargado vaya..

Debido a ello, el coste de pasar de un nodo a otro será diferente si es el primer eje recorrido que si es otro posterior. He estado haciendo revisión bibliográfica pero no encuentro nada parecido y no se si se me está pasando algo muy evidente por alto. Espero que, si alguien se ha topado con este problema anteriormente, pueda iluminarme un poco.

Muchas gracias de antemano!

[martiniano]

Hola.

Yo no conozco ningún algoritmo concreto para el problema que propones. No obstante, parece posible aplicar alguna técnica de backtracking. Los algoritmos que se obtienen mediante esta técnica no suelen ser polinómicos, pero no creo que eso importe. Entre otras cosas porque, si he entendido bien tu problema, resolverlo implica probar que el grafo es hamiltoniano, y tener un algoritmo polinomial para eso significa responder a la famosa pregunta de si \[ \mathcal {P=NP}  \]. De hecho, creo recordar que está demostrado que algunas variantes del problema del viajante no admiten algoritmos polinómicos.

Un saludo.

[AlvaroGC]

Hola martiniano!

Muchas gracias por tu respuesta. Voy a intentar responderte por partes, y disculpa si algo digo mal porque no soy matemático y puedo meter la pata.

- El grafo de planteamiento del problema es hamiltoniano porque se puede ir a cualquiera de los nodos desde cualquiera de los demás.
- En cuanto al backtracking. Creo que eso es lo que estoy haciendo de hecho: se puede generar un árbol de decisiones y obtener el óptimo repulsivamente, pero eso es precisamente lo que querría evitar, intentando resolverlo mediante un modelo más usual.

El problema que veo para poder representarlo con un modelo como digo es el hecho de que el coste de los arcos depende de la solución escogida.

Un saludo.

[martiniano]

Hola.

- El grafo de planteamiento del problema es hamiltoniano porque se puede ir a cualquiera de los nodos desde cualquiera de los demás.

Vale. Eso se me había escapado. Aún así, no creo que exista un algoritmo polinomial conocido.

- En cuanto al backtracking. Creo que eso es lo que estoy haciendo de hecho: se puede generar un árbol de decisiones y obtener el óptimo repulsivamente, pero eso es precisamente lo que querría evitar, intentando resolverlo mediante un modelo más usual.

El problema que veo para poder representarlo con un modelo como digo es el hecho de que el coste de los arcos depende de la solución escogida.

Ya, claro, habría que ver de qué forma varían los costes pero yo también lo veo complicado. De todas formas, yo creo que el backtracking te va a funcionar muy bien. Es cierto que el coste de los algoritmos obtenidos con esta técnica suelen ser costosos. No obstante, yo pienso que con unos buenos criterios de poda y de selección la cosa te va a funcionar bastante bien. ¿Son muy grandes los grafos a los que vas a tener que aplicar el algoritmo?

Un saludo.

[AlvaroGC]

Hola martiniano!

Simplificando el problema al máximo, el coste sólo dependería de la carga que lleva el vehículo y la distancia entre las ciudades a visitar. Te cuento lo que yo estoy haciendo ahora mismo:

• Genero un árbol de decisiones "simplificado". Con esto quiero decir que hay nodos del árbol de decisiones que representan la misma situación. Como ejemplo: supón un problema sencillo en el que partimos de una ciudad \( s \), y tenemos que repartir a 4 ciudades diferentes (1, 2, 3 y 4), para volver a la ciudad \( s \). En el árbol de decisiones habrá un nodo que represente haber hecho parte del recorrido de la forma \( s-1-2-3 \), mientras que habrá otro nodo, en distinta rama, que represente el recorrido \( s-2-1-3 \).
• Esos dos nodos que muestro de ejemplo, en realidad representan la misma situación en el árbol, porque el vehículo está ubicado en la ciudad 3, con la misma carga dado que ha descargado en las ciudades 1, 2 y 3 (sólo importa el orden de la última ciudad en la que ha descargado).
• De esta forma simplifico el grafo, que se cierra en un nodo único que representa volver a la ciudad de origen, y lo resuelvo como un problema de camino de coste mínimo mediante el algoritmo de Dijkstra.

La resolución en sí misma no es un problema, porque Dijkstra es muy eficiente, pero planteándolo de esta forma es una locura intentar modificar el problema por ejemplo con ventanas de tiempo o con más de un vehículo, modificaciones que son muy sencillas de introducir en los modelos de programación entera usuales.

Respecto al tamaño que me preguntas: no he sacado una expresión analítica que pueda decirte para este caso concreto del VRP, pero en problemas similares que he estado tratando hablamos de árboles de decisión simplificados del orden de \( 2^m \), siendo \( m \) el número de "elementos" a ordenar (las ciudades a visitar en este ejemplo). De todas formas ya te digo, el grueso del tiempo es debido al cálculo de los costes de los arcos del árbol de decisión, y no a la propia obtención de la solución óptima.

Supongo que tendré que seguir por esta vía, al menos me quedo más tranquilo hasta cierto punto de ver que no se me ha pasado una forma mucho más simple de resolverlo.

Muchas gracias!

[homohabilis]

Para el  TSP problem en sus distintas variantes en grafos planos funciona muy bien "simulated annealing". Siempre y cuando estemos hablando de una solución en la práctica, y no de un estudio teórico del mismo.