An Optimization Approach to the Ordering Phase of an Attended Home De...

Attended Home Delivery (AHD) systems are used whenevera supplying company offers online shopping services which require thatcustomers must be present when their deliveries arrive. Therefore, thesupplying company and the customer must both agree on a time win-dow, which ideally is rather short, during which delivery is guaranteed.Typically, a capacitated Vehicle Routing Problem with Time Windowsforms the underlying optimization problem of the AHD system. In thiswork we consider an AHD system that runs the online grocery shoppingservice of an international grocery retailer.The  ordering  phase,  during  which  customers  place  their  ordersthrough the web service, is the computationally most challenging partof the AHD system. The delivery schedule must be build dynamicallyas new orders are placed. We propose a solution approach that allowsto determine which delivery time windows can be offered to potentialcustomers. We split the computations of the ordering phase into fourkey steps. For performing these basic steps we suggest both a heuristicapproach and a hybrid approach employing Mixed-Integer Linear Pro-grams. In an experimental evaluation we demonstrate the efficiency ofour approaches.