Discrete optimization approach for holiday travel problem
I’m new to discrete optimization techniques and I’m trying to determine the best or appropriate way to model/attack a specific problem.
I call it the Holiday Travel for Picky Families problem...
Here’s the concept:
- There are a network of airports with various flight paths between each airport.
- There are a fixed number of flights between any two given airports (0..N)
- There’s a list of families requiring traveling for the holidays at exactly the same start and end date, removing the time-dimension from the problem. Each family having a specific pair of endpoint airports.
- Each family is composed of 1..6 members.
- Members of a family must travel together on a flight in a contiguous section of seats.
- If a route for a given family requires more than one leg/hop, the family must be able to sit in the exact same seats on both flights.
- Not all possible flight routes for a given family will be allowed, but there’s a guaranteed 3 potential routes at minimum, with 2 routes being fully diverse.
- Extending #6, every set of family seat assignments on the chosen route must also be reserved for that family on a fully redundant route in the allowed list. Effectively two diverse routes must be saved for each family, with matching seat assignments on both routes.
- Each flight has a maximum seat capacity.
- For the purposes of this problem, the seatmap on a flight should be represented as a linear 1D layout of seats.
I’m guessing this would fall under a class of routing or scheduling problems in Discrete Optimization or Satisfiability. But I’m having trouble figuring out how to get started. Any references or approaches I should look at? I'd like to figure out how to model and represent the constraints to an existing generic solver ideally.