Sweeping the entire Albert Heijn floor. Sounds simple. And should’ve been simple.
But I’m a Computer Science student, with a problem: I can’t stop trying to optimize things that (probably) don’t need optimizing.
So instead of just doing my job and, well… sweeping… I did what any “reasonable” person would do: I turned the supermarket floor plan into a grid graph, built a visual editor and wrote a C++ path optimizer using simulated annealing.
But before we dive into how this went spectacularly wrong, and how this made me realize how this makes everyone miserable, I need you to answer a quick question:
If you were to take over my job for one day (I wouldn’t recommend it but hypothetically speaking) and needed to sweep the entire Albert Heijn floor, would you take path A or B?
Path A (top) and path B (bottom).
Seriously. Look at them. Which one seems more efficient for sweeping a supermarket floor?
If you picked path A: congratulations, you think like an algorithm and are most likely a robot. (Good luck with CAPTCHA questions.)
But you are technically right. Path A is shorter by distance. It is absolutely useless however.
Look at those turns. Actually imagine for a second that you would walk around taking those turns. You’d look insane, like some Roomba having a seizure.
... continue reading