Recently I took up a small project of developing a Python package and deploying the same on PyPI. The package is based on a famous problem in Graph Theory - Mathematics i.e., Travelling Salesman Problem.

Credits of Cover Image - Photo by Nicolas Van Leekwijck on Unsplash

As a programmer or a developer, we usually think of solving this problem by considering a random n number of nodes or cities and assign a random distance or cost value to each node or city respectively. We opt for a Dynamic Programming approach where a certain problem is broken down into sub-problems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its sub-problems. Recursive methods are applied subsequently to solve each sub-problem and thus solving the original problem.

To understand how to implement this programmatically, please read my medium blog where I explain the procedure in detail. I have implemented the same but taken to next level by considering the authentic place coordinates and calculating haversine distance for getting approximate distance between any two places.

The link to my python package is below. The current version of the package is 0.2.2.

You can install the package via pip.

pip install dora-explorer --user

import the package

from dora_explorer.distance_locator import DistanceLocator
from dora_explorer.travel_places import GeoTraveller
from dora_explorer.tiny_explore import DoraTheExplorer

Creating objects

dis_loc = DistanceLocator()
geo_travel = GeoTraveller()

The default distance is taken in km. Allowed options are -

• Miles
• Meters
• Feet and
• Yards

from_place = 'singapore'
to_place = 'new zealand'

Distance checking

## kilometers
from_to_dis_km = dis_loc.get_distance(from_=from_place, to_=to_place)
print("The distance in kms from {} to {} - {} kms".format(from_place, to_place, from_to_dis_km))

## miles
from_to_dis_miles = dis_loc.get_distance(from_=from_place, to_=to_place, in_miles=True)
print("The distance in miles from {} to {} - {} miles".format(from_place, to_place, from_to_dis_miles))

## meters
from_to_dis_meters = dis_loc.get_distance(from_=from_place, to_=to_place, in_meters=True)
print("The distance in meters from {} to {} - {} meters".format(from_place, to_place, from_to_dis_meters))

## feet
from_to_dis_feet = dis_loc.get_distance(from_=from_place, to_=to_place, in_feet=True)
print("The distance in feet from {} to {} - {} feet".format(from_place, to_place, from_to_dis_feet))

## yards
from_to_dis_yards = dis_loc.get_distance(from_=from_place, to_=to_place, in_yards=True)
print("The distance in yards from {} to {} - {} yards".format(from_place, to_place, from_to_dis_yards))

Output

'The distance in kms from singapore to new zealand - 8358.12 kms'
'The distance in miles from singapore to new zealand - 5194.6 miles'
'The distance in meters from singapore to new zealand - 8358116.45 meters'
'The distance in feet from singapore to new zealand - 27422980.08 feet'
'The distance in yards from singapore to new zealand - 9143779.4 yards'

We can also check the distance plot from from_place to to_place in the following way. But before doing this, it is preferred to have MapBox API which can be obtained from the official website. I have saved my API in a mapbox_api.txt file and read the same for further usage.

read() the MapBox API

with open(file='mapbox_api.txt', mode='r') as api_file:
    map_api = api_file.read()

There are two main conditions to get the appropriate distance plot.

If geo_token=map_api then

• If from_place and to_place belong to the same country, then with_map=True and with_directions=True.

## belong to the same country - India
from_place = 'delhi'
to_place = 'bengaluru'

dis_loc.get_distance_plot(
    from_=from_place, 
    to_=to_place, 
    with_map=True, 
    with_directions=True, 
    geo_token=map_api
)

• If from_place and to_place belong to differernt countries, then with_map=True and with_directions=False.

from_place = 'singapore'
to_place = 'new zealand'

dis_loc.get_distance_plot(
    from_=from_place, 
    to_=to_place, 
    with_map=True, 
    with_directions=False, 
    geo_token=map_api
)

If geo_token=None or geo_token="" then with_map=False and with_directions=False.

• The distance plot will be simply a line plot from two coordinates (latitudes and longitudes).

from_place = 'delhi'
to_place = 'bengaluru'

dis_loc.get_distance_plot(from_=from_place, to_=to_place)

Shortest Path to cover the given places

For this, a list of places should be given as input to the package. There are two possible conditions to get the acquired result

• If the list of places belong to the same country considering geo_token=map_api.

Spain country example -

place_list = ["madrid", "barcelona", "alicante", "palma"]
explore = DoraTheExplorer(place_list=place_list)

explore.get_path(
    source_city='palma',
    with_map=True,
    with_directions=True,
    geo_token=map_api
)

Output

'plot is saved successfully ...'
'palma >> barcelona >> madrid >> alicante >> palma'

Note - if geo_token=None and all the places belong to the same country, then a line plot is plotted after joining the coordinates (latitudes and longitudes).

Minimum distance to cover all the places

## kilometers
min_distance_km = explore.get_min_dis(source_city='palma')
print("The minimun distance to cover {} in kms - {}".format(place_list, min_distance_km))

## miles
min_distance_miles = explore.get_min_dis(source_city='palma', in_miles=True)
print("The minimum distance to cover {} in miles - {}".format(place_list, min_distance_miles))

## meters
min_distance_meters = explore.get_min_dis(source_city='palma', in_meters=True)
print("The minimum distance to cover {} in meters - {}".format(place_list, min_distance_meters))

## feet
min_distance_feet = explore.get_min_dis(source_city='palma', in_feet=True)
print("The minimum distance to cover {} in feet - {}".format(place_list, min_distance_feet))

## yards
min_distance_yards = explore.get_min_dis(source_city='palma', in_yards=True)
print("The minimum distance to cover {} in yards - {}".format(place_list, min_distance_yards))

Output

"The minimun distance to cover ['madrid', 'barcelona', 'alicante', 'palma'] in kms - 1372.78"
"The minimum distance to cover ['madrid', 'barcelona', 'alicante', 'palma'] in miles - 853.19"
"The minimum distance to cover ['madrid', 'barcelona', 'alicante', 'palma'] in meters - 1372780.0"
"The minimum distance to cover ['madrid', 'barcelona', 'alicante', 'palma'] in feet - 4504091.18"
"The minimum distance to cover ['madrid', 'barcelona', 'alicante', 'palma'] in yards - 1501821.32"

• If the list of places belong to different countries considering geo_token=map_api or geo_token=None.

Multi-country example -

place_list = ['london', 'madrid', 'bengaluru', 'delhi']
explore = DoraTheExplorer(place_list=place_list)

explore.get_path(
    source_city='london',
    with_map=True,
    with_directions=True,
    geo_token=map_api
)

Output

"Cannot find the shortest path, as the cities ['london', 'madrid', 'bengaluru', 'delhi'] do not belong to the same country."

Minimum distance to cover all the places

min_distance = explore.get_min_dis(source_city='london')
print(min_distance)

Output

"Cannot find the minimum distance to cover the cities ['london', 'madrid', 'bengaluru', 'delhi'], as they do not belong to the same country."

That is it ...

• The package is still under development. Quite a few features and bugs need to be resolved.
• If you have liked my package, you can star it on the GitHub project page.
• If you would like to contribute and want to add new features, you are welcome.
• If you would like to report an issue, I would be happy to check and resolve the same.