Node visit with time-window

[Daniel Mota]

Hello guys, allow me to propose a discussion, maybe someone already engaged in this topic.

I am working on a classic "Shortest Path Problem", but I would like to model the following constraint:

Let's say shortest path from A to D is: "A -> B -> C -> D" and arrival time at nodes are:

A (0), B (10), C (15), D (40), meaning weight of edges as time. Hence, edge A-B took 10, B-C took 5, and C-D took 25.

However, C is just available after 17... so the algorithm should return : A (0), B (10), C (15), D (42) (because they arrived at 15 but waited until 17 to start the journey to D, still spending 25, or find another path.

 Does it make any sense for any of you? Let's dive deep in this discussion?

Waiting for comments

best regards

DMota

--

[Craig Schmidt]

Hi DMota,

That sounds like you are trying to solve the Shortest Path Tour Problems with Time Windows.  It is a fairly well studied problem.  Google that term and you’ll find a number of papers. 

-Craig

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CAFZco0eeo8ozBXJ%2Bhet%3DAVWV5fRZ516yFN71vwnmR58A27h7uw%40mail.gmail.com.

[Daniel Mota]

Hello Craig,

Thanks for your reply! Yeap, but I couldn't find any using the Networkx library. :)

What I found was the use of the cutoff parameter, but it just applies to the path complete, not for individual nodes.

Any thoughts?

Daniel Mota

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/9628C7CE-6125-43E4-A1FC-713D5C2F2208%40craigschmidt.com.

--

[Tung T. Nguyen]

I am not sure if this helps but wanted to point out that Google developed the Or-tools package to deal with this type of problem. 

https://developers.google.com/optimization/routing/vrptw 

Best wishes, Tung 

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CAFZco0dE4-XHX-uaApfVr8xdcfDHT%2BbHvQok05RbFofziE45SA%40mail.gmail.com.

--

Tung T. Nguyen, Ph.D

Email: tun...@uchicago.edu

Website: https://tungprime.github.io/

[Daniel Mota]

Thanks Dr. Nguyen,

This would definitely solve the problem, but given the volume of data I am using and modeling , I intend to keep using Dijkstra algorithm as solution, thats why, in this case, I don't want to use any external solver (such as OR-Tools, Gurobi or CPLEX).

So, my intention is limit use of Networkx library.

Thanks

DMota

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CAOAGfLXdhf8fqThRSWd5yVNpzQP05MKnS%2Bj8o88ZNgVw%2Bpff%3Dg%40mail.gmail.com.

--

[mike yu]

Hi Daniel Mota,

you are touvhing a most powerful model to represent daily happenings.

so, it is a good idea to do it with networkx.

i briefly read those solutions in google, since Craig mentioned.

in pure networkx solution, if we express the given with more nodes and edges, the solution comes natural.

we split C into 2 member nodes C.time1, C.time2, 

maybe the neighbours of C as well ...

i dont know, ... it is interesting.  

[Starlin Mini]

Try to give weight for each nodes say weights of A,B,C,D goes like 0,0,17,0. First, find all the paths connecting A and D, then sum up the weights of nodes and edges in the path. Finally, Pick the path with least sum,  which gives the shortest path connecting A to D including the time spend in the node.

[David Menéndez Hurtado]

One simple solution is to use the A* algorithm, using the shortest path from the full graph as heuristic. As you expand your route, you can consider the time windows and wait as long as required.

It isn't a function out of the box, but coding it is fairly straightforward, and you can probably draw inspiration from the networkx implementation.

/David 

--