I got paid minimum wage to solve an impossible problem

Summary

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. Path A is what happens when you optimize for the wrong thing.Which, spoiler alert, is the entire point of this story. But we’ll get there, let me first explain how we got here:First, I took the Albert Heijn floor plan and converted it into a grid. Each tile is either empty (should be swept) or an obstacle (wall, checkout counter, yoghurt package somebody threw on the ground).I built a visual editor in Processing (a Java tool for people who like making things look cool), so I could easily map out the store and export the resulting graph.Converting the floorplan into the grid structure was therefore quite easy.Grid floorplan of the Albert Heijn supermarket.The tiling of the actual floor helped to subdivide the ar...