We tackle the problems of workforce sizing and shift scheduling of a logistic operator delivering parcels in the last-mile segment of the supply chain. Our working hypothesis is that the relevant decisions are affected by two main trade-offs: workforce size and shift stability. A large workforce is able to deal with demand fluctuations but incurs higher fixed costs; by contrast, a small workforce might require excessive outsourcing to third-party logistic providers. Stable shifts, i.e., with predictable start times and lengths, improve worker satisfaction and reduce turnover; at the same time, they might be less able to adapt to an unsteady demand. Through an extensive computational campaign based on a novel mathematical formulation, we test these assumptions. We find that extreme shift stability is, indeed, unsuitable for last-mile operations. On the other hand, introducing a very limited amount of flexibility achieves similar effects as moving to a completely flexible system while ensuring a better work-life balance for the workers. Several recent studies in the social sciences have warned about the consequences of precarious working conditions for couriers and retail workers and have recommended—among other things—stable work schedules. Our work provides an actionable decision-support tool to achieve this objective without sacrificing the company’s bottom line.