How to use shortest path algorithm to randomly generate a new data set?
AnsweredI heard that in Python with gurobi, there's a way to use the shortest path algorithm to randomly generate a new data set. However, I don't quite get how to make it applicable. Is there anything I could try?
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Hi,
I am not sure what you mean, could you can elaborate a bit more?
You can model the shortest path as a MIP using a binary variable for each edge and flow balance constraints (a quick google search yields this example).
With regards to data there are many open data sets (e.g. DIMACS).
Best,
David
0 -
-
Hi David,
Specifically, I'm trying to use the shortest path method to create a timetable for flight schedule design. I thought it might be feasible. I read the example you provided, maybe I could use the duration time of a flight as the 'cost' in the example?
0 -
-
-
Hi Jingyue,
Yes, of course if you'd like to find the shortest path in terms of flight time. But you can use a cost proportional to how attractive the flight is (e.g. may be delayed). The added benefit of solving using Gurobi is that you can then add problem-specific constraints as well (e.g. capacity).
If you only want to solve a standard shortest path problem (without additional constraints) I would recommend using a dedicated algorithm. Specifically, if the resulting network is acyclic (as is the case with time-space networks, sometimes used in flight schedule design), the algorithm is polynomial (number of edges).
Best,
David
0 -
Post is closed for comments.
Comments
4 comments