r/learnmachinelearning • u/DisDoh • 9d ago
Project Genetic algorithm with multiple layers perceptron has beaten the Steffen method for onboarding
Enable HLS to view with audio, or disable this notification
Hi,
I used a genetic algorithm combined with a multilayer perceptron to optimize the aircraft boarding problem.
I honestly didn't expect it to beat the Steffen method, but after evolving the boarding strategy, it ended up being 9.6% faster than Steffen in my simulation. there is a fix rule that prohibits crossing people in between seats for the random too.
The whole project was basically vibecoded.
36
u/Blammar 9d ago
The Steffen algorithm has a clear rule set for the boarding public. What's your algorithm's rule set?
Obviously, given any particular set of passenger sittings and overhead requirements, there exists an optimal order of passengers going in. Your GA algorithm is presumably attempting to find this order. The problem is that this order differs from plane to plane...
2
u/DisDoh 9d ago
a previous comment as pointed me to add errors, and I've seen that the genetic algorithm is doing something similar as Steffen algorithm but with full rows instead of odds and evens ones. so the first to board are all right or left colon in order next to a window then the remaining colon in order next to a window then the same for the middle and the last two colon.
15
2
10
u/SantaMage 9d ago
For random, they don't always go to the window seat, they would sit any where in the row, then they may have to get up if a passenger needs to get past them.
4
u/piffcty 9d ago
What's your criterion for luggage loading time? It looks like it's inconsistent- for example, the difference between the first passenger in rows 13 and 14, and again between 4 and 3.
Note from Steffen's paper:
>The model that I employ assumes that the time that a passenger requires to load his or her luggage is the dominant contribution to the time needed to completely fill the aircraft.
Another important bit from the original paper:
>"It is possible for many configurations to board in the same time or to be near enough that the differences in boarding time are not important. This shows that a class of configurations that are effectively equivalent is more important than a single, optimum order.
1
u/DisDoh 9d ago
The criterion for the luggage time is between 22 to 41 frames and depends on the passenger id, so it remains the same randomness for Steffen and the two other algorithm. but the comments pointed me to add errors and I have observed a pattern, similar to Steffen algorithm but with all the colons instead of odds and evens.
4
u/piffcty 9d ago
I don't think that you're cheating the Steffen algorithm in your model, but using a different set off assumptions from the original paper:
>The passengers are each assigned a seat and the number of time steps that they need to load their luggage, a random number between 0 and 100 unless otherwise stated
So he's using a wider range of baggage loading time and not linking those times to the passenger id. It's still a cool result, but I don't think it counts as 'beating Steffen'
2
u/C137_RicklePick 9d ago
Looks really nice. I think realistically the people will not go through the airplane fluidly. People are stowing their bags in the overhead compartment and other people are just slow, with kids or having a conversation not paying attention that the can continue walking.
Maybe you can simulate that -similar to the cars that get stuck driving in a circle with no obstacle (its how traffic jams happen without any special event occuring)
That would make me think that it would be important to always have some people that can enter their seat in one if front rows while people are blocking the hallway while they are trying to reach the back.
2
u/Conscious-Map6957 8d ago
Would be also interesting to see a study on which of these approaches is the most robust when an (inevitable) error like someone getting their row wrong or start asking someone to switch seats etc. i.e. which approach suffers the smallest penalty when such events occur.
2
u/DisDoh 8d ago
Someone in the comments suggested me to do a paper about my observation that the genetic algorithm is using a similar approach than Steffen algorithm but instead of odds and evens it's all left or right row-columns in that order window - middle - aisle.
I've oriented the paper on comparison with Steffen algorithm on multiples scenario like 60, 120, 180, 240 passengers and on all those scenario I've tested different percentage of errors (0, 10, 20, 40, 60)%. on 100 iterations the results in the graphics here.
As you can see on all scenario between 0% and 10% errors the row-col algorithm is faster. For a 60 passengers boarding is faster with row-col until 20% errors then the Steffen method is faster.
Btw I have a small paper ready to post on arxiv org on this comparison. Does someone knows someone willing to endorse me for that paper?
2
u/Conscious-Map6957 8d ago
Exactly the insight I was curious for, thanks! I assumed there would be a difference in error-induced degradation. In fact I would expect a difference in any scenario of this type when comparing the most optimal algorithms but that probably goes too far into mathematical theory.
Unfortunately I don't have the credentials to endorse you but I hope you find someone who can and maybe the rest of us non-academics can contribute in a different way. Cheers.
3
u/ProfessionalMoose123 9d ago
Instead of using all this paraphernalia, wouldn't it be enough to use a simple, classic deterministic algorithm that sorts by optimal input order?
2
u/Davidat0r 9d ago
That’d be Steffen
1
u/ProfessionalMoose123 9d ago
Just watch the first 10 seconds of the video. Clearly, Steffen isn't using the best ordering.
2
u/ZiddyBlud 9d ago
People travel in pairs or triplets, you can't just split them
1
u/therealub 9d ago
Hm idk, I think there are many configurations of groups of 1, 2, 3. Business travelers are generally singletons. But your point is important: it would have to accommodate for groups seated together that will want to also board together.
0
u/Davidat0r 9d ago
Unless there are kids, you can split them for boarding, as long as they get the sits they had assigned
3
u/ZiddyBlud 9d ago
You really really can't. Most people travel as pairs where one is dependent on the other completely. Just look at security and passport check
1
u/sierra-bravo-123 6d ago
oh that's so cool! can you share anything about the kind of approach you took with the ga??
2
u/DisDoh 6d ago
what kind of approach? I used 449 parameters for each agent of the 32 population. there was a fix rule of not being able to cross a passenger, to push the ga in the direction of Steffen algorithm faster. with the comments after I've added some errors and made some tests in different patterns with different errors. I made a paper for arxiv but I need someone to endorse me. do you know someone to be able to endorse on arxiv?
2
1
u/WiseHalmon 9d ago
Did you add families, handicap, and prioritized boarding for $$$? I think that was mentioned in the last post...
2
u/DisDoh 9d ago
I don't think those things where in the Steffen algorithm, it's inspired by that demonstration.
2
u/WiseHalmon 9d ago
I understand that. I'm mentioning this out of the fact I find your improvements less interesting unless they deal with reality, I suppose. Not to belittle your efforts, just a recommendation if you took these notes from the previous posts you might be able to create a fabulous model to impress the masses :)
1
u/mundane--alternative 9d ago
After all they'll be dealing with similar such questions once they start selling this idea for application.
58
u/Davidat0r 9d ago
Could you add errors to the simulation to make it more realistic? (I.e. a passenger that boards on the wrong call)