Skip to main content

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

Answered

Comments

3 comments

  • David Torres Sanchez
    Gurobi Staff Gurobi Staff

    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
    Gurobi-versary
    Collaborator
    Curious

    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 Gurobi Staff

    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.