In the UK we also have very narrow delivery windows e.g. Be at Tesco in this 30 minute slot or pay a steep penalty. Scheduling a charging slot will not add much difficulty.

Logistics researchers have also been working on this problem for years. You can find paper after paper in the literature.