If you want a one-time answer, the cheapest route is E2 > P4 > I2 > D2 at a cost of $1,452.
The method I used was not elegant. I made a table of every possible option, used INDEX and MATCH to look up the cost of each of leg of the trip, and then sorted by total cost ascending. Here's what my sheet looks like:
The data on the left is what I copied from your spreadsheet. The table on the right is what I created. For each of the fields E, P, I, & D, I just manually typed them in groups. D1, D2, D3, D4, D5. Copy those five and paste them down a lot. I1, copy down for a set of D's, I2, copy down for a set of D's, etc. until the table was filled. For the field $EP, I combined INDEX and MATCH to lookup the cost of traveling from E(whatever) to P(whatever).
=1/(1/INDEX($B$3:$E$5,MATCH([@E],$A$3:$A$5,0),MATCH([@P],$B$2:$E$2,0))) INDEX takes in an array and returns a cell from somewhere within that array. To find the row I wanted, I used MATCH to find where the E value was in the range A3:A5. To find the column, I looked for the P value in B2:B4. That gave me the cost of going from E to P. I added the 1/(1/...) wrapper around the entire thing so it would return an error if the leg of the trip was zero, indicating that it was not available.
I then copied that formula to the fields $PI and $ID, adjusting each to reference the correct ranges. Finally, the Total Cost field simply added those three legs together. I sorted ascending and found the cheapest route. All the errors - the ones using unavailable routes - were sent to the bottom.
If you want an ongoing system where you want to keep track of how many transports are current en route for each leg of the trip so you can select the cheapest route based on what's currently available, you may want to look at a database solution. Alternatively, you can use the sorted list and just start at the top, working down until you find a route where each leg is currently available.
