Shortest city tour#

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

This notebooks introduces an algorithmic challenge which consists in finding the shortest path through a set of streets. It gives examples and functions to test a solution.

%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)

Somebody must walk through all the blue streets and only these streets. What is the shortest way?

Inputs:

  • A list of vertices (crossroads).

  • A list of edges/streets (a,b): it goes from vertices[a] to vertices[b].

  • The distances, the distance measure the street length which is longer than the length of the straight line between its extremities.

Outputs:

  • a list of edges

We introduce a last array edges_index which contains the indices of the streets in Seattle database. A list of edges can be defined by a list of couples (a,b) or a list of indices taken from this database. Let’s see an example:

vertices

[(-122.34991548199997, 47.46763155800005),
 (-122.34991155699998, 47.468532819000075),
 (-122.349907514, 47.469446668000046),
 (-122.34855159499995, 47.47036031400006),
 (-122.34722154299999, 47.46765986400004),
 (-122.34721743899996, 47.46856001400005),
 (-122.34721337199994, 47.466759281000066),
 (-122.34721334599999, 47.46946425100003),
 (-122.34717558599999, 47.47218021800006),
 (-122.34695634299999, 47.47037913100007),
 (-122.34651954599997, 47.46947199700003),
 (-122.34602084699998, 47.46857181000007),
 (-122.34577976599996, 47.47219822000005),
 (-122.34577761299994, 47.470393184000045),
 (-122.34552556999995, 47.46767758400006),
 (-122.34451462099997, 47.46858890800007),
 (-122.34451260399999, 47.46949338600007),
 (-122.34451061099998, 47.47040481700003)]

edges

[(10, 7),
 (5, 4),
 (4, 0),
 (10, 11),
 (9, 10),
 (7, 2),
 (17, 16),
 (5, 1),
 (11, 5),
 (17, 13),
 (16, 15),
 (14, 4),
 (15, 11),
 (1, 0),
 (4, 6),
 (8, 9),
 (13, 9),
 (7, 5),
 (11, 14),
 (16, 10),
 (2, 1),
 (12, 8),
 (9, 3),
 (12, 13)]

distances

[0.0006938432391730961,
 0.0009001593555190061,
 0.0026940877056109824,
 0.0010290953928001187,
 0.0010111922517731158,
 0.0026942253755745885,
 0.0009114331789785205,
 0.002694255252624058,
 0.001196650141037562,
 0.0012670554031294153,
 0.000904480248963228,
 0.001696065569270049,
 0.0015063230412799549,
 0.0009012695466891699,
 0.0009006200670015617,
 0.0018143819538848289,
 0.0011788137680839225,
 0.0009042462633556375,
 0.0010222227965844966,
 0.0020070559761853316,
 0.0009138579433356185,
 0.001395936081803295,
 0.0015953629752697774,
 0.0018050372840282547]

The last array represents the edges indices related to the whole database describing streets in Seattle. The database is used to compute the length of the streets and their locations. The location is used to draw maps. edges_index defines a set of indices of streets in Seattle. A street is always identified by its index in this database. They do not change whatever the subset of street is as opposed to the set vertices which is built from this subset of streets.

edges_index

[0,
 4994,
 11394,
 9989,
 1670,
 11274,
 17680,
 3353,
 9118,
 30370,
 15023,
 6712,
 8378,
 29114,
 4553,
 1101,
 6488,
 107,
 1003,
 12783,
 2418,
 2803,
 2808,
 6265]

The array shapes defines the streets as a list of segments. They should be needed only to draw maps.

shapes[4994].points

[(-122.34721743899996, 47.46856001400005),
 (-122.34722154299999, 47.46765986400004)]

The array records contains informations about each street. It is not needed to find the shortest tour.

{k[0]:v for k, v in zip(fields[1:], records[4994])}

{'F_INTR_ID': 21670,
 'T_INTR_ID': 21711,
 'SND_ID': 37943,
 'SND_FEACOD': 1,
 'CITYCODE': 0,
 'STNAME_ID': 6,
 'ST_CODE': 0,
 'ARTERIAL_C': 0,
 'SEGMENT_TY': 1,
 'AGENCY_COD': 1,
 'ACCESS_COD': 1,
 'DIVIDED_CO': 1,
 'STRUCTURE_': 1,
 'LEGALLOC_C': 1,
 'VEHICLE_US': 1,
 'GIS_SEG_LE': 328.344652,
 'L_ADRS_FRO': 15000,
 'L_ADRS_TO': 15098,
 'R_ADRS_FRO': 15001,
 'R_ADRS_TO': 15099,
 'ORD_PRE_DI': '',
 'ORD_STREET': '10TH',
 'ORD_STRE_1': 'AVE',
 'ORD_SUF_DI': 'SW',
 'ORD_STNAME': '10TH AVE SW',
 'L_CITY': 'BURIEN',
 'L_STATE': 'WA',
 'L_ZIP': '98166',
 'R_CITY': 'BURIEN',
 'R_STATE': 'WA',
 'R_ZIP': '98166',
 'SNDSEG_UPD': datetime.date(2004, 5, 19),
 'COMPKEY': 0,
 'COMPTYPE': 0,
 'UNITID': '0',
 'UNITID2': '0',
 'SHAPE_Leng': 0.000900159355519}

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_16_0.png

One solution#

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 distance_solution
solution = edges_index[:-1].copy()
try:
    distance_solution(edges_index, edges, distances, solution)
except Exception as e:
    print(type(e), str(e))

<class 'ensae_projects.challenge.city_tour.SolutionException'> Different number of distinct edges:
expected=24 got=23
Did you cover all the edges?

The function distance_solution detected one edge was not covered. Let’s try another one.

solution = edges_index
try:
    distance_solution(edges_index, edges, distances, solution)
except Exception as e:
    print(type(e), str(e))

<class 'ensae_projects.challenge.city_tour.SolutionException'> Are you sure? The path is inconsistent. Some help:
[(1, 3), (3, 1), (6, 1), (7, 3), (13, 3), (16, 3)]

The path is inconsistent. The function could not find a way to go through all of them without jumping. Note that the order of the streets does not have to be specified. The distance is able to tell if somebody can walk through all the street in one go. This means some streets must be present more than one time in the path. Let’s try the following solution:

solution = edges_index + [17680, 30370, 12783, 0, 3353, 9118, 8378, 15023]
distance_solution(edges_index, edges, distances, solution)

0.04481876729332677

Let’s plot the solution. A function will reorder the streets to go through all of them without jumping. The blue number indicates the position of each street in this path.

from ensae_projects.challenge.city_tour import euler_path
path = euler_path(edges_index, edges, solution)
plot_streets_network(edges_index, edges, vertices, shapes, order=path, figsize=(10,10));
../_images/city_tour_1_24_0.png

Now, what is the best path?