For the past two months, I've been working on making Bad Apple with apples. It had a bit of a hardware build but there was some really interesting software problems too so I figure this crowd might be interested :D (also someone is definitely going to tell me a better way I could have done it and I'm all for that)
Another dubious optimization you could do is finding an optimal transport solution to move the apples the least amount of distance, something similar to the Earth Mover's Distance.
I actually tried using TSP to optimize the order of apples moved for a single frame, but what you sent seems like a much better fit (I'll bookmark it for the future). Either way, conveying all the moving information on a single reference picture is hard.