AE: Duda letra obligatorio

Buenas tardes, como están?

Con mi compañero tenemos algunas dudas sobre la letra del obligatorio:

1) En la descripción del problema se dice que el algoritmo debe encontrar rutas correspondientes a cada camión.

"Todas las rutas (secuencias de nodos asignadas a cada vehículo) empiezan y terminan en el nodo 0"

La duda surge cuando se detalla la salida esperada del algoritmo. Dice que se espera que en la primera linea se debe codificar una única ruta.

"En la primera línea se deberá codificar la ruta de la mejor solución hallada mediante una tira de caracteres numéricos separados por espacios"

Nosotros entendemos que en la primera linea deberían ir tantas rutas como camiones hayan. Quizás estemos entendiendo mal el problema, pero no nos estamos dando cuenta de que parte de la letra estamos interpretando mal.

2) Tenemos dudas sobre como trabajar con el tiempo que demora un camión en recorrer la distancia entre dos nodos. Se nos ocurre que una posibilidad es definir una constante de velocidad y calcular el tiempo que demora un camión en ir de un nodo a otro.

Esto sería correcto?

Saludos, Ignacio

Re: Duda letra obligatorio

de Sebastian Volti Diano - miércoles, 2 de septiembre de 2020, 18:27

Buenas,

cómo va?

Respecto al punto (2), si no entendí mal, la letra indica que el tiempo que demora el camión en pasar de un nodo a otro, corresponde a la distancia euclidiana ente los nodos.
Para obtener los costos solo hay que utilizar esa distancia y el salario que cobra el conductor del camión, que está en la letra.

El punto (1) también me genera dudas el orden de salida esperado.
Si bien actualizaron la letra y agregaron una línea de salida, por lo que yo entiendo para una instancia de clientes dada, una ruta óptima seguramente pueda ser realizada por 1 o más camiones, trabajando de manera simultanea.
Entonces por ejemplo:
Disponemos de 5 clientes (p1,p2,p3,p4,p5), y utilizamos 2 camiones para atenderlos (c1, c2)
c1 reparte a los siguientes clientes, en el siguiente orden: p1 -> p2 -> p3 -> depósito
c2 reparte a los siguientes clientes, en el siguiente orden: p4 -> p5 -> depósito

Tanto "c1" como "c2" reparten de manera simultanea, por lo que el orden de la salida final va a depender de que cliente es atendido primero, una salida válida podría ser:
# p1 p4 p5 p2 deposito p3 deposito
# - - - - - - -
# costos

Es correcto el planteo?

Gracias, saludos!!!

Re: Duda letra obligatorio

de Santiago Iturriaga - jueves, 3 de septiembre de 2020, 01:23

Hola:

Sebastián está en lo correcto sobre el punto (1). Alcanza con la distancia, no es necesario inventarse una velocidad.

Sobre el punto (2). La salida está fuertemente ligada a la codificación en memoria de sus soluciones. La salida/codificación que propone Sebastián no está del todo mal pero tiene un problema: representa fácilmente soluciones no factibles (p.ej. p1 p4 deposito deposito p5 p2 p3)

Siempre que sea posible, lo recomendable es evitar representar soluciones no factibles. Para reducir el espacio de búsqueda y para evitar aplicar técnicas como penalización, corrección, etc. Entonces el desafío es lograr una buena codificación.

Les dejo una cuestión planteada: ¿que tan deseable podría ser que un vehículo retorne al depósito sin haber repartido la máxima cantidad de insumos dada por la capacidad del vehículo? ¿vamos a querer esto alguna vez?

Saludos,

Santiago.

Re: Duda letra obligatorio

de Vicente Martin Ferreyra Arrillaga - jueves, 3 de septiembre de 2020, 11:43

Buenas

No entiendo cómo a partir de esa solución se podría deducir qué ruta hace cada camion. No veo una ruta definida en esa forma de expresar el resultado, sino que veo el orden cronológico en que los clientes fueron visitados.

La solución que se me ocurre es algo así:

0 1 2 3 0 - 0 4 5 0

Donde el camion 1 recorrería los clientes 1, 2 y 3 y el camion 2 los clientes 4 y 5 (utilizando el mismo ejemplo mencionado anteriormente). Se esta agregando un guion para separar las rutas de los distintos camiones.

Saludos,

Vicente

Re: Duda letra obligatorio

de Santiago Iturriaga - viernes, 4 de septiembre de 2020, 12:43

Hola a todos:

Renzo y Sergio me dijeron que quizás mi post haya quedado un poco confuso así que voy a intentar aclararlo.

Mi intención no es que descarten de plano la representación que propone Sebastián, sino que simplemente intenté criticarla. Desde mi punto de vista existen diferentes alternativas para la representación, cada una con sus problemas particulares. Nuestra idea es que discutan estas alternativas y elijan una a conciencia.

Por ejemplo, otro de los problemas que tiene la representación que propone Sebastián es que no es representable con una permutación y eso puede complicar bastante (vean las slides del Tema 7).

Sobre la pregunta que dejé planteada al final del post, su respuesta puede ser que si por la razón X. Es decir, que pudiera ser deseable que un vehículo retorne al depósito sin repartir el máximo de su capacidad. De vuelta, deberían discutirlo.

Finalmente, sobre la representación que propone Vicente. Creo que es un poco expresiva de más y puede reducirse fácilmente a la que proponía Sebsatián. ¿Que opinan?

Saludos,

Santiago.

Re: Duda letra obligatorio

de Alejandro Gabriel Clara Mariño - martes, 8 de septiembre de 2020, 19:31

Tengo la misma duda que Vicente. En la solución propuesta por Sebastián (más allá de los problemas que puede tener en cuanto a las soluciones inválidas), no vemos dónde queda representado el objetivo del problema que es "definir rutas para los vehículos de forma de satisfacer toda la demanda minimizando el costo total".

Ese "objetivo del problema" nos da a pensar que en la salida tienen que quedar representadas las rutas seguidas por cada camión. Siguiendo esta idea, creo que se ajusta mejor la solución propuesta por Vicente (con algunas variaciones para quitar redundancia).

Re: Duda letra obligatorio

de Sergio Nesmachnow - miércoles, 9 de septiembre de 2020, 16:32

Hola,

Respondo el mensaje de Alejandro haciendo referencia a sus dos párrafos.

El primer párrafo no lo entiendo, ya que una representación de soluciones no tiene como propósito representar al "objetivo del problema". La representación es una forma de codificar soluciones y la semántica de los procesos de codificación/decodificación la deben definir ustedes y pueden utilizar todos los mecanismos que sean convenientes y/o necesarios (aclaro esto último en caso de que la pregunta estuviera orientada a la semántica). Revisen las notas del curso, especialmente donde se presenta "resolviendoun problema: genotipo y fitness", que tienen varios ejemplos de representaciones para problemas reales, con diferentes niveles de complejidad.

El segundo párrafo también refiere al "objetivo del problema", pero aquí entiendo que es claro que "en la salida tienen que quedar representadas las rutas seguidas por cada camión" (como bien indican en el mensaje y como solicita la letra del práctico) y también es correcto que una representación con menor redundancia puede ser una mejor opción.

Saludos

(Editado por Renzo Massobrio - envío original miércoles, 9 de septiembre de 2020, 16:32)

Re: Duda letra obligatorio

de Ignacio Carlos Monzalvo Milan - miércoles, 9 de septiembre de 2020, 17:47

Buenas, como estan?

A mi personalmente me siguen quedando algunas dudas ya que no logro ver como quedan representadas las rutas en la salida que dio Sebastian.

Me da la impresion que en la salida que propone Sebastian, no quedan las rutas definidas de ninguna manera, sino un caso particular del orden en que todos los depositos son visitados sin especificar a que ruta pertenece cada deposito.

Saludos, Ignacio

Re: Duda letra obligatorio

de Renzo Massobrio - miércoles, 9 de septiembre de 2020, 18:50

Hola Ignacio,

Leyendo el mensaje de Sebastián no me queda completamente claro el formato que propone. En particular, la afirmación "... por lo que el orden de la salida final va a depender de que cliente es atendido primero,..." entiendo que solamente aplica a nivel de cada camión, no de la solución en su conjunto.

La propuesta de Alejandro, basada en la solución que proponía Vicente pero quitando algunos elementos redundantes que no aportaban información, parece ser una representación más natural para el problema en cuestión.

Tal vez Sebastián puede ampliar su mensaje original para terminar de entender su propuesta y poder seguir con la discusión de los pros y contras de cada enfoque.

Pueden seguir haciendo sus aportes por acá y recuerden también que mañana tenemos clase de consulta donde podemos ampliar esta discusión.

Un saludo,
Renzo

Re: Duda letra obligatorio

de Sebastian Volti Diano - miércoles, 9 de septiembre de 2020, 19:32

Buenas, cómo les va?

En la solución planteada arriba, se retorna el orden en que fueron atendidos los clientes, en la primer línea de salida.
En esa solución claramente la ruta de cada camión no está representada en la salida (si podríamos tenerla guardada en la estructura interna del código).

Por lo que tengo entendido actualmente, se espera que la representación final de los clientes atendidos no esté dada por orden de atención, sino que quede armada por camión.
Ésto último haría referencia al modelo de solución que plantearon tanto Vicente como Alejandro, sacando las redundancias o particularidades que cada grupo considere pertinente.

Saludos, Sebastián!