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?
-
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
Please sign in to leave a comment.
Comments
3 comments