[Gvsig_usuarios] extension redes origen y matriz origenes destinos
Francisco José Peñarrubia
fpenarru en gmail.com
Lun Feb 14 16:21:09 CET 2011
Hola Chiara.
Ese problema es conocido, y se puede complicar bastante. Por ejemplo,
con ventanas de tiempo o múltiples depots.
El problema tuyo parece uno dentro de los "simples", pero más complejo
que un TSP. Se llama "Vehicle Routing Problem" (VRP). Con vario
almacenes sería un MDVRP (Multiple Depot VRP).
Con ventanas de tiempo sería un TVRP, etc.
Más información:
http://es.wikipedia.org/wiki/Problema_de_rutas_de_veh%C3%ADculos
Hace tiempo hice cosas de estas, y son divertidas, pero te puedes
encontrar que la realidad siempre supera a la teoría.... ;-)
Saludos.
Fran.
PS: gvSIG se puede usar como base para una solución de este tipo, pero
con gvSIG Redes no te basta. Puedes obtener una buena solución gracias a
que el operador vaya jugando con las rutas, pero no tendrás una solución
automática.
El 14/02/2011 15:42, Chiara Porcu escribió:
> muchas gracias a Francisco y Adrian,
> efectivamente estos días estuvimos reflexionando sobre el problema del
> viajante. Os explico, suponemos de haber una empresa de recogida de
> aceites usados. cada camión tiene una ruta diaria en la que recoge
> aceite por 20 puntos distintos que se encuentran a distancias varias y
> a lo mejor en distintos ayuntamientos. El problema es calcular una
> ruta que permite a cada camión de recoger aceite en todos los puntos
> con el mínimo recorrido posible. Eso es, utilizando la extensión de
> redes y pidiendo que me orden las paradas, que fiabilidad tengo de que
> sea efectivamente el recorrido minimo?
> además me parece un problema teórico muy interesante...
> Chiara
>
> --- El *lun, 14/2/11, Francisco José Peñarrubia
> /<fpenarru en gmail.com>/* escribió:
>
>
> De: Francisco José Peñarrubia <fpenarru en gmail.com>
> Asunto: Re: [Gvsig_usuarios] extension redes origen y matriz
> origenes destinos
> Para: "Lista de Usuarios de gvSIG" <gvsig_usuarios en listserv.gva.es>
> Fecha: lunes, 14 de febrero, 2011 10:45
>
> Hola Adrián.
>
> Al calcular la matriz de distancias (y tiempos), se usa la
> distancia real, usando la red. Creo que sextante tiene un
> geoproceso para distancia euclídea.
> El algoritmo que se emplea es Dijkstra, y para obtener la matriz,
> se calculan todas las rutas mxn. Si tu fichero de orígenes es un
> solo punto, tienes 1-> n. Eso sí, solo se guarda la distancia y el
> tiempo, no se crean las rutas una por una.
>
> No estoy de acuerdo en que sea más sencillo hacer un cálculo del
> problema del viajante (ruta pasando por varios puntos y ordenar
> esos puntos para que sea óptimo=>TSP) que el cálculo 1->n. De
> hecho, el TSP lleva un cálculo previo de la matriz de distancias,
> y luego un proceso de optimización posterior. Es bastante más
> complejo el TSP que la matriz OD.
>
> Para terminar, si necesitas ver las rutas 1-> n, en lugar de usar
> MatrizOD, puedes usar la opción de "Evento más cercano". Aquí se
> vuelve a usar Dijkstra, pero esta vez sí se muestran las rutas a
> uno u otro punto. Así que podría servir para lo que tú comentas,
> aunque no estoy seguro de que eso sea lo que necesita Chiara. En
> el manual puedes ver una descripción de esta opción:
>
> http://www.gvsig.org/web/docusr/redes-userguide/evento-mas-cercano
>
> El manual completo está aquí, por si no tienes instalado el plugin
> de redes y te interesa saber las opciones que tiene la extensión:
>
> http://www.gvsig.org/web/docusr/redes-userguide
>
> y algo de la documentación del desarrollo, aunque esto ya está
> algo anticuado:
>
> http://www.gvsig.org/web/docdev/docs/desarrollo/plugins/redes/components/solvers/solvers/
>
>
> Saludos.
>
> Fran.
>
>
>
> El 12/02/2011 14:03, Adrian Eiris escribió:
>> Me imagino que a lo que se refiere Chiara es a hacer el cálculo y
>> representación gráfica de múltiples rutas, tanto de un origen a
>> múltiples destinos como de múltiples orígenes a un destino, que
>> es algo más complejo que la utilidad básica de hacer calculo de
>> una ruta a través de múltiples puntos.
>>
>> No he visto las funcionalidades más recientes de redes, pero creo
>> que esto de cálculo de múltiples rutas a la vez para un
>> destino/origen (1->n / n->1) es una funcionalidad que no tiene la
>> extensión de redes, y que, cuando uno intenta hacer análisis más
>> complejos resulta muy útil.
>>
>> Luego otra cosa es que el cálculo de distancias sea la euclídea o
>> la distancia real a través de red. Ahí ya no se como está, tengo
>> las siguientes dudas:
>>
>> - ¿Cuál de las distancias calcula la función matriz OD?
>> ¿euclidea, real o ambas?
>> - ¿Se representan gráficamente los resultados de la matriz OD?
>>
>> Dist-Elementos-Origenes.png
>>
>> Galicia-Rutas-pob-El.png
>>
>> 2011/2/11 Francisco José Peñarrubia <fpenarru en gmail.com
>> </mc/compose?to=fpenarru en gmail.com>>
>>
>> Hola Chiara.
>>
>> El punto 1 no lo entiendo. Si es cálculo de ruta pasando por
>> varios puntos, desde el gestor de paradas puedes cargar una
>> capa de puntos y luego activar, desactivar, reordenar, etc.
>>
>> http://www.gvsig.org/web/docusr/redes-userguide/gestor-de-paradas/introduccion/
>>
>> El punto 2:
>>
>> http://www.gvsig.org/web/docusr/redes-userguide/matri-origenes-destinos
>>
>> Espero que te sirva.
>>
>> Saludos.
>>
>> Fran.
>>
>> El 11/02/2011 13:06, Chiara Porcu escribió:
>>> Buenos dias!
>>> estoy investigando la extensión de redes , trabajando con el
>>> gvsig 1.10. Tengo un par de dudas que no han encontrado
>>> solución en el manual o en internet en general, así que os
>>> las propongo, seguro que son tonterías....!
>>> 1. Si por ejemplo tengo una empresa de recogida de aceites,
>>> que cada día percorre una ruta distinta, y quiero calcular
>>> todas las rutas ponendo pero siempre la misma origen de
>>> default, como puedo hacer? para no tener que introducir
>>> siempre el punto de origen. Entendí que se puede utilizar
>>> una matriz origenes/destinos, pero no entendí bien como
>>> funciona y como se crea....
>>> 2. probé a exportar el informe de las distancias desde la
>>> origen. pero en el fichero que se crea me aparecen cuatro
>>> columnas, en dos me pone valor 0 y en las otras dos
>>> distintos valores. mi pregunta es, como se cual es la
>>> columna con la distancia que quiero saber?
>>>
>>> muchas gracias,
>>> saludos
>>> Chiara
>>>
>>>
>>>
>>> _______________________________________________
>>> gvSIG_usuarios mailing list
>>> gvSIG_usuarios en listserv.gva.es </mc/compose?to=gvSIG_usuarios en listserv.gva.es>
>>>
>>> Para ver histórico de mensajes, editar sus preferencias de usuario o darse de baja en esta lista, acuda a la siguiente dirección:
>>>
>>> http://listserv.gva.es/cgi-bin/mailman/listinfo/gvsig_usuarios
>>
>> --
>> Fran Peñarrubia
>> Scolab
>> www.scolab.es <http://www.scolab.es>
>>
>> Asociación gvSIG
>> www.gvsig.com <http://www.gvsig.com>
>>
>>
>> _______________________________________________
>> gvSIG_usuarios mailing list
>> gvSIG_usuarios en listserv.gva.es
>> </mc/compose?to=gvSIG_usuarios en listserv.gva.es>
>>
>> Para ver histórico de mensajes, editar sus preferencias de
>> usuario o darse de baja en esta lista, acuda a la siguiente
>> dirección:
>>
>> http://listserv.gva.es/cgi-bin/mailman/listinfo/gvsig_usuarios
>>
>>
>>
>>
>> --
>>
>> Adrián Eirís Torres
>> Administrador de Sistemas
>> Cartolab - Laboratorio de Ingeniería Cartográfica
>> http://www.cartolab.es
>>
>> ETS Ingeniería de Caminos, Canales y Puertos
>> Universidade da Coruña
>> Campus de Elviña - 15071 A Coruña (España)
>> (34)981167000 ext. 5493
>>
>>
>> _______________________________________________
>> gvSIG_usuarios mailing list
>> gvSIG_usuarios en listserv.gva.es </mc/compose?to=gvSIG_usuarios en listserv.gva.es>
>>
>> Para ver histórico de mensajes, editar sus preferencias de usuario o darse de baja en esta lista, acuda a la siguiente dirección:
>>
>> http://listserv.gva.es/cgi-bin/mailman/listinfo/gvsig_usuarios
>
> --
> Fran Peñarrubia
> Scolab
> www.scolab.es <http://www.scolab.es>
>
> Asociación gvSIG
> www.gvsig.com <http://www.gvsig.com>
>
>
> -----Adjunto en línea a continuación-----
>
> _______________________________________________
> gvSIG_usuarios mailing list
> gvSIG_usuarios en listserv.gva.es
> </mc/compose?to=gvSIG_usuarios en listserv.gva.es>
>
> Para ver histórico de mensajes, editar sus preferencias de usuario
> o darse de baja en esta lista, acuda a la siguiente dirección:
>
> http://listserv.gva.es/cgi-bin/mailman/listinfo/gvsig_usuarios
>
>
>
> _______________________________________________
> gvSIG_usuarios mailing list
> gvSIG_usuarios en listserv.gva.es
>
> Para ver histórico de mensajes, editar sus preferencias de usuario o darse de baja en esta lista, acuda a la siguiente dirección:
>
> http://listserv.gva.es/cgi-bin/mailman/listinfo/gvsig_usuarios
--
Fran Peñarrubia
Scolab
www.scolab.es
Asociación gvSIG
www.gvsig.com
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: http://listserv.gva.es/pipermail/gvsig_usuarios/attachments/20110214/c7f9e7d2/attachment.htm
------------ próxima parte ------------
Se ha borrado un mensaje que no está en formato texto plano...
Nombre : no disponible
Tipo : image/png
Tamaño : 52046 bytes
Descripción: no disponible
Url : http://listserv.gva.es/pipermail/gvsig_usuarios/attachments/20110214/c7f9e7d2/attachment.png
------------ próxima parte ------------
Se ha borrado un mensaje que no está en formato texto plano...
Nombre : no disponible
Tipo : image/png
Tamaño : 26384 bytes
Descripción: no disponible
Url : http://listserv.gva.es/pipermail/gvsig_usuarios/attachments/20110214/c7f9e7d2/attachment-0001.png
Más información sobre la lista de distribución gvSIG_usuarios