Best path from origin to destination with consideration of halt time at nodes

Question

Origin	Destination	Arrival time	Destination time
A	B	12:00	14:00
A	B	13:00	15:00
C	D	00:00	5:00
B	C	8:00	13:00
A	C	16:00	21:00
D	A	13:00	16:00

If a shipment is going from A to D. What could be the best path which will require list amount of time?

It should also consider halt time at various nodes and directional aspect.

For example in above case -

A -> D can be done with following paths

1. A - B - C - D
2. A - C - D

First one can be done with two ways as there are 2 A-B pairs

i) time taken = 2 + (18) + 5 + (8) + 8 = 41 hours

ii) time taken = 2 + (17) + 5 + (8) + 8 = 40 hours

Second one

time taken = 5 + (3) + 5 = 13 hours

here () shows halt times

so, in here the best path is A-C-D considering the halt times also

Answer 1

You only need to transform it into a graph with suitable nodes and then you can use any algorithm for weighted graphs to get your "shortest path". In the construction, you need to add to your graph pairs of location and time. Edges are added for possible connections of two locations and the weight of an edge is the consumed time.

Some nodes and edges of your example:

nodes = [(A, 12:00), (B, 14:00), (A, 13:00), (B, 15:00), ... ]

edges = [((A, 12:00), (B, 14:00), 2)), 
         ((A, 12:00), (A, 13:00), 1), 
         ((A, 13:00), (B, 15:00), 2), ....]

I think you also want to add "loops to the same destination at another day". So you also need to add edges like ((A, 16:00), (A, 12:00), 20)).