Don't underestimate the equally intense downward pressure on staffing that minimum-wage hikes have provided (for instance, in California). I won't speculate if it's been "worth it" since it'll devolve into an off-topic political debate, but basic economics does predict that since labor costs twice what it did 10 years ago, they'll do everything to minimize how much labor they buy. Couple that with what you said, basically, using "Moneyball" techniques to finesse everything with all these optimizations, we get the operations we see now in all retail establishments.
And even if there are states that haven't done the minimum wage changes, the markets that have are so big. The national businesses that have adapted to it have proven out their barebones-labor model there - why wouldn't they roll out most of the changes nationwide?
I think if someone launched a fast-food place or a drugstore in 1995 that operates with the type of skeleton crew they use today, it would fail overnight due to people having a choice. But today, since essentially 100% of retail operates this same way, they don't experience any pressure to do better.