Last week was hackathon day at cVation, a good chance to play around with new tech or ideas. But while it is fun to try new stuff, it is also sometimes fun to revisit something old. I had the chance to do both as I used the Group Seat Reservation Knapsack Problem (GSR-KP), to introduce a small team to the wonderful world of combinatorial optimization.
The GSR-KP considers a train with a certain number of seats (assumed to be on a single line), to be filled by reservation requests each having several persons travelling together for a pre-determined part of the train’s route. All members of the reservation must be placed adjacently and cannot change seats while travelling.
The goal of the problem is to choose which reservations to include, such that the utilization of the train (determined as occupied seats per station) is as high as possible.
To solve the problem, we used LocalSolver, a mathematical optimization solver based on local search and constraint programming paradigms.
During the hackathon we had time to implement two different models and pit them against each other to see which model would give the best results on instances from the original research paper.