Vehicle Routing and Time Slot Management in Online Retailing

Online retailing continues to grow, and consumers, but also small businesses, purchase more and more products online. Many of these products require attended delivery for which the customer needs to stay at home to receive their purchases. To decrease the chances of costly delivery failures and to provide customers with a high level of service, many online retailers offer their customers a menu of delivery time slots. The management of these time slots can be challenging, as the customer demand can vary heavily, and the amount of available delivery vehicles and drivers may be limited. Dynamic Time Slot Management (DTSM) is a class of methods which dynamically construct time slot offers based on previously placed customer orders. Our focus is the use of vehicle routing heuristics within DTSM to help retailers manage the availability of time slots in real time.
In this dissertation, we explore several challenges that hinder the widespread adoption of DTSM in practice. As vehicle routing is used in real time, the compu- tation time plays a crucial role. We study pre-calculation techniques for a particular class of vehicle routing problems, and illustrate the trade-off between computation time and memory use. Furthermore, as multiple customers arrive and interact with the DTSM system simultaneously, several previously unstudied issues arise. We model such simultaneous interactions and study their impact on the real-time per- formance of the system in terms of response times and number of accepted cus- tomers. Finally, we explore a novel variant of DTSM in which routes and time slots are assigned a priori in a strategical phase to simplify their real-time management. Although this reduces the number of different time slots that can be offered to cus- tomers, advantages include smoothing of fulfillment center operations and delivery consistency.