They already have to wear uncomfortable clothes and work long hours on their feet. Cut them some slack and let them choose their own footwear. It also would probably reduce the medical expenses for a company in long term.

Edit: as a sneaker freak myself I'd insist them to be pristine!