Python Networkx route though all nodes

Question

I'm trying to write a small route planning application in python just to learn about graphs. In the end, the user should be able to pass in his "home" location and enter some locations he wants to stop by. The application will then calculate the optimal path that starts and ends in his home while visiting every location. So far I've got the API requests all sorted out and a Network with all possible routes between all nodes and corresponding weights is automatically created. Now I'm stuck with a 'G' and don't know how to proceed. I've looked into the Networkx documentation about the shortest paths and cannot find a function that seems to do what I want. The best results I got when searching where Wikipedia articles about Dijkstra and the all_pairs_shortest_path() function, which, too, do not yield the answers I'm searching for.

Maybe there is someone out there who stumbled upon the same problem as I have and knows a solution that I cannot find.

Answer 1

This is the "pickup problem".

A delivery driver must pickup passengers at several locations and deliver them to a destination.

I have a c++ implementation of an application to calculate reasonable solutions to this problem when there is a link between every location costing the euclidean distance between the locations. Documentation at https://github.com/JamesBremner/PathFinder/wiki/Pickup

You will have to modify this for your problem, by calculating the cost of the cheapest path between every location ( Dijkstra ) and linking every pair of locations with that cost.

Note that the algorithm will fail if the direct distance between any two nodes is greater than the distance between them via a third node.

Example: One pickup driver has to pickup 6 cargoes and deliver them to a designation. The input file looks like this

format pickup
d 1 3 start
e 6 5 end
c 1 1 c1
c 5 5 c2
c 3 3 c3
c 4 4 c4
c 2 2 c5
c 6 6 c6

and the result looks like this

The example is very simple, just to show how this works. However this is a high performance application using an efficient implementation of the travelling salesman algorithm ( no brute force searching through permutations! ;-) I have used it for the allocation and routing of drivers to restaurant deliveries in a big city where the requirement was to handle thousands of orders in a few seconds. This plot shows the performance that was achieved.

Answer 2

Like @AKX mentioned, analyzing the different permutations of the stops I want to make was the way to go. For anybody who might encounter a similar problem in the future I post my approach, although it's far from being optimized or even moderately clean code.

First of all, instead of saving all possible routes into the graph, I saved them to an array called routes = []. To calculate the sub-routes, I then create a copy of the routes array which does not include routes to the starting (or ending) location:

strippedRoutes = []
    for route in routes:
        if route[0] == 0 or route[1] == 0:
            pass
        else:
            strippedRoutes.append(route)
subroutes = sortAllPermutations(strippedRoutes, len(addressen) - 1)

I pass all the subroutes into a new function, which will calculate the 'cost' of all the permutations:

def findCost(nodesToTraverce, startNode, endNode):
    ## lookup the cost
    cost = 0
    for edge in nodesToTraverce:
        if edge[0] == startNode and edge[1] == endNode:
            cost = edge[2]['weight']
            break
    return cost

def sortAllPermutations(nodesToTraverce, numberOfNodes):
    nodes = []
    for i in range(1, numberOfNodes +1):
        nodes.append(i)
    perms = list(itertools.permutations(nodes))
    buffer = []
    for p in perms: #calculate cost of route
        cost = 0
        for s in range(0, numberOfNodes-1): #calculate cost of subroute
            cost += findCost(nodesToTraverce, p[s], p[s+1])
        toAdd = []
        for j in range(0, len(nodes)):
            toAdd.append(p[j])
        toAdd.append(cost)
        buffer.append(toAdd)
    #sort buffer by cost
    buffer.sort(key= lambda x: x[4])
    return buffer

Because I fetch all the costs for my routes from an API, finding the cost of each sub-route is relatively easy and no more than searching in a lookup table. The first lines of the sortAllPermutations() function are used to create a permutation table. In the for-loop, the cost of each permutation is calculated by looking up the cost of the different edges that are saved inside the "nodesToTraverce" array, which is passed into the function. The first nested for-loop that iterates s is used for exactly that. The last lines of the perm for-loop are used to store the permutation and it's cost into the buffer, which is sorted (unnecessarily) once the for loop terminates and then returned. Back in the main function, merely the cost of getting to each starting point of the sub-route and going back home from the last stop are calculated, and the route of the overall lowest cost is saved:

subroutes = sortAllPermutations(strippedRoutes, len(addressen) - 1)

mostEfficient = []
iteration = 0
for perm in subroutes:
    cost = perm[4]
    cost += findCost(routes, 0, perm[0])
    cost += findCost(routes, perm[3], 0)
    if iteration == 0 or cost < mostEfficient[6]:
        mostEfficient = []
        mostEfficient.append((0))
        for i in range(0, len(perm)-1):
            mostEfficient.append(perm[i])
        mostEfficient.append(0)
        mostEfficient.append(cost)
    iteration += 1
print(mostEfficient)

And with that, the most efficient sightseeing roundtrip is calculated:

>>> [0, 1, 2, 4, 3, 0, 164044.1]

I'm not sure if here is the right place to discuss this, but I've got some closing thoughts on the project. If the project should not be used to plan roundtrips sights but in a professional environment, where you want to calculate most efficient routes, you would not optimize for shortest distance or least time needed, but for both criteria and more. I really want to try this, with some route-stops meeting deadlines or having a higher priority than others, but I have absolutely no clue how I would go about implementing several dimensions of optimization. I'm closing this thread now, but if someone who reads this has articles on this feel free to answer or pin me.

Thanks for all your help!

Answer 3

If you have a graph G and want to find the route from A (home) to B to C to D (final destination) in order, you'd call dijkstra_path on it for (A, B), (B, C) and (C, D), and concatenate the paths generated.