How to use shortest path algorithm to randomly generate a new data set?

Answered

Jingyue Zhang

March 14, 2022 14:34 Edited

• 
• 
• 

I 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?

 

0

• 

  David Torres Sanchez

  • Gurobi Staff

  March 18, 2022 16:20

  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
• 

  Jingyue Zhang

  March 21, 2022 02:16

  • 
  • 
  • 

  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
• 

  David Torres Sanchez

  • Gurobi Staff

  March 21, 2022 16:35

  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.