# How to find least cost path subject to distance constraint?

I have a raster with each cell representing a travel cost. I need to find the least cost path from one point on the raster to another point on the raster. One additional twist: the path cannot exceed 50% of the distance of the most direct route.

I'm using numpy and scikit for managing my graph, but I'm open to other solutions (except non-free software such as ArcGIS).

Example costs:

``````[ 2,  2,  2,  2,  2,
10,  9,  2,  7,  2,
11, 12, 13, 14,  2,
20, 19, 18, 17,  2,
2,  2,  2,  2,  2 ]
``````

If I'm evaluating a route from the top left to the bottom left, the absolute least cost route follows the edges along the top, right, and bottom of the graph (total cost=26):

``````[ 1,  1,  1,  1,  1,
0,  0,  0,  0,  1,
0,  0,  0,  0,  1,
0,  0,  0,  0,  1,
1,  1,  1,  1,  1 ]
``````

The shortest distance is 5 cells:

``````[ 1,  0,  0,  0,  0,
1,  0,  0,  0,  0,
1,  0,  0,  0,  0,
1,  0,  0,  0,  0,
1,  0,  0,  0,  0 ]
``````

In this case, the absolute least cost path is too long (13 cells compared with 5). The answer I'm looking for would be:

``````[ 1,  1,  0,  0,  0,
0,  0,  1,  0,  0,
0,  1,  0,  0,  0,
0,  0,  1,  0,  0,
1,  1,  0,  0,  0 ]
``````

Total cost: 40, total distance: 7 cells. This is the minimum cost within the allowable path distance (5 cells * 150% = 7.5 cells).

Are there packages that offer algorithms to solve this?

I don't see anything out of the box in scikit.

Short of calculating every possible shortest path, what is a good strategy for solving this problem?

• Travel the shortest distance down and you'll get better solution than 46, 7. It will be 45, 5 – FelixIP Apr 23 '17 at 10:02
• @FelixIP good catch. I tweaked the grid to make my solution the correct one at a cost of 40 and 7 cells. – spencerrecneps Apr 24 '17 at 0:35