¿Cómo puedo calcular las rutas óptimas al momento de tocar todas las carreteras en una red?

Question

Para la preparación de la temporada de invierno queremos calcular las rutas más óptimas para la pizca de sal en las carreteras. El análisis se conoce con los siguientes criterios: - vehículos de inicio y parada en un solo punto de carga - todas las carreteras deben ser espolvoreados con sal - una ruta puede tomar no más de una certin tiempo (supongamos 2 horas) - debido a la limitada carga de sal por cada vehículo, la distancia de una ruta se limita a la cantidad de sal disponible. (vamos a suponer 10 km)

Network analyst de ArcGIS (10.0) se supone que tiene un inicio y un punto final para calcular la ruta. Sin embargo, en este caso no se trata de calcular la ruta más rápida desde el origen al destino, pero acerca de las rutas más óptimas para cubrir tanta distancia de camino como sea posible dentro de un marco de tiempo limitado.

Junto con un colega estamos pensando en soluciones, pero le agradecería si pudiera dar información sobre este interesante desafío. Ahora estamos pensando en el cálculo de los promedios para cada tramo de carretera y el uso de esos destinos para calcular la ruta. Si alguien tiene mejores sugerencias, por favor compartir!!!

Saludos,

Marca

Answer 1

Creo que algunas de las respuestas dependerá del diseño de la red de carreteras, y esta pregunta podría ser vale la pena publicar en las Matemáticas de Intercambio de la Pila (http://math.stackexchange.com/) como se parece como una teoría de grafos problema. No creo que esta va a ser la solución óptima, pero podría ayudar a acercarse.

Se podría dividir la red de carreteras en las regiones naturales, donde la suma de la longitud de los segmentos será aproximadamente igual a la cantidad que un camión pueda cubrir con una carga dada. A continuación, para cada región podría ejecutar un eularian tour para obtener la ruta que toque todos los segmentos. Ejemplo de código en python

def eulerian_tour(network_graph):
    graph = network_graph[:]
    route = []
    def find_route(start):
        for (i, j) in graph:
            if i == start:
                graph.remove((i, j))
                find_route(j)
            elif j == start:
                graph.remove((i, j))
                find_route(i)
        route.append(start)

    find_route(graph[0][0])
    route.reverse()
    return route

Usted podría considerar la posibilidad de enrutamiento entre las regiones y el depósito, y romper la ruta de acceso en segmentos lógicos para los camiones disponibles. Espero que esto ayude.