Online grocery delivery is an increasingly used service in society and is becoming something people rely on more and more by the day. The main challenge of online grocery delivery problems, as opposed to other kinds of delivery problems, is the requirement for the customer to select a time slot in which they wish to receive their delivery, which the route then has to accommodate. In principle, being able to choose any slot they desire is ideal for customers; however it can lead to the creation of highly inefficient routes. Consider for example a scenario in which there are two deliveries on the same road which have been ordered for delivery windows six hours apart: from a perspective of minimising the distance being travelled, this is not a good situation to be in, as it will involve sending delivery vans to the same road twice in one day.
The aim of this project is to research methods that can help the supermarket decide which delivery slots to offer customers when they place an order on the company website. There are two objectives, which typically conflict: maximising customer choice, and minimising the total driving time. As well as having two objectives, the problem has stochastic and dynamic aspects, since customers visit the web site more or less at random over time. Moreover, the problem has combinatorial aspects, due to the selection of delivery slots and the need to produce routes for the vehicles. In order to solve this highly complicated optimisation problem, heuristic methods are likely to be necessary. It may also be necessary to use simulation, to assess the (expected) performance of various heuristics.