Shortest city tour (solution)#

Links: notebook, html, PDF, python, slides, GitHub

Find the shortest path through a set of streets, solution of the first example.

%matplotlib inline
import matplotlib.pyplot as plt
plt.style.use("ggplot")
from jyquickhelper import add_notebook_menu
add_notebook_menu()

Problem definition#

from ensae_projects.datainc.data_geo_streets import get_seattle_streets, shapely_records
from ensae_projects.datainc.data_geo_streets import seattle_streets_set_small, folium_html_street_map

name = get_seattle_streets()
shapes, records, fields = shapely_records(name)
edges_index, edges, vertices, distances = seattle_streets_set_small(shapes, records)
folium_html_street_map(edges_index, shapes, html_width="80%", zoom_start=15)

We display a simplified map.

from ensae_projects.datainc.data_geo_streets import plot_streets_network
plot_streets_network(edges_index, edges, vertices, shapes, figsize=(10,10));
../_images/city_tour_1_solution_6_0.png

Eulerian path#

A solution is a set of indices of edges. Let’s try edges_index without one edge as a solution.

from ensae_projects.challenge.city_tour import best_euler_path
couples, solution, distance = best_euler_path(edges_index=edges_index, edges=edges,
                                              distances=distances, vertices=vertices, fLOG=print)
"distance", distance
[best_euler_path] distance_vertices #edges=24
[best_euler_path] bellman_distances
[bellman_distances] iteration=1 modif=74 #dist=122 sum_values=0.26812913941842903 avg=0.0021977798312985985
[bellman_distances] iteration=2 modif=102 #dist=214 sum_values=0.6638654574495177 avg=0.0031021750348108304
[bellman_distances] iteration=3 modif=130 #dist=298 sum_values=1.3475652021993083 avg=0.004522030879863451
[bellman_distances] iteration=4 modif=100 #dist=306 sum_values=1.3653257205807 avg=0.004461848760067647
[bellman_distances] iteration=5 modif=64 #dist=306 sum_values=1.2780455413890799 avg=0.0041766194163041824
[bellman_distances] iteration=6 modif=42 #dist=306 sum_values=1.2282394949878546 avg=0.0040138545587838385
[bellman_distances] iteration=7 modif=24 #dist=306 sum_values=1.207369883828586 avg=0.003945653215126098
[bellman_distances] iteration=8 modif=12 #dist=306 sum_values=1.1964121229039824 avg=0.003909843538901903
[bellman_distances] iteration=9 modif=10 #dist=306 sum_values=1.1840886861931539 avg=0.0038695708699122678
[bellman_distances] iteration=10 modif=6 #dist=306 sum_values=1.1840669671109263 avg=0.0038694998925193668
[bellman_distances] iteration=11 modif=2 #dist=306 sum_values=1.1840669671109263 avg=0.0038694998925193668
[bellman_distances] iteration=12 modif=2 #dist=306 sum_values=1.1840644116345598 avg=0.003869491541289411
[bellman_distances] iteration=13 modif=0 #dist=306 sum_values=1.1840644116345598 avg=0.003869491541289411
[best_euler_path] degrees and distances between odd vertices
[best_euler_path] matching #odd=6, #odd_dist=30
[best_euler_path] build solution
[best_euler_path] order edges to get the path #edges=31
[best_euler_path] done.
('distance', 0.04360778144581235)
from ensae_projects.challenge.city_tour import euler_path
plot_streets_network(edges_index, edges, vertices, shapes, order=solution, figsize=(10,10));
../_images/city_tour_1_solution_9_0.png