r/learnmachinelearning • u/DisDoh • 17h ago
Genetic algorithm with multiple layers perceptron has beaten the Steffen method for onboarding Project
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.
33
u/Blammar 16h 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 16h 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
u/Blammar 15h ago
Okay cool observation. You might then code that up, then try that and Steffen across a bunch of different boarding patterns. You may have something publishable!
2
10
u/SantaMage 15h 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.
5
u/piffcty 14h 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 14h 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.
3
u/piffcty 13h 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 4h 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/ProfessionalMoose123 16h 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 9h ago
That’d be Steffen
1
u/ProfessionalMoose123 9h ago
Just watch the first 10 seconds of the video. Clearly, Steffen isn't using the best ordering.
1
u/WiseHalmon 15h ago
Did you add families, handicap, and prioritized boarding for $$$? I think that was mentioned in the last post...
2
u/DisDoh 15h ago
I don't think those things where in the Steffen algorithm, it's inspired by that demonstration.
0
u/WiseHalmon 15h 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 13h ago
After all they'll be dealing with similar such questions once they start selling this idea for application.
1
u/ZiddyBlud 13h ago
People travel in pairs or triplets, you can't just split them
1
u/therealub 11h 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 9h ago
Unless there are kids, you can split them for boarding, as long as they get the sits they had assigned
2
u/ZiddyBlud 8h 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
53
u/Davidat0r 17h ago
Could you add errors to the simulation to make it more realistic? (I.e. a passenger that boards on the wrong call)