Model-based delivery cost approximation in attended home services

• Four linear mixed-integer programming-based approaches are proposed.
• They can be incorporated – like a plug-in – into existing optimization models.
• Computational experiments are conducted using standard optimization software.
• Delivery cost approximations are shown to be very accurate compared to a benchmark.
• Model recommendations are provided depending on the conditions in practice.

Most commonly, attended home services are designed such that a booking period precedes the actual service period which is subdivided in several predefined time windows. During the booking period, the provider and each of her customers agree upon one of the time windows for service delivery. Providers try to influence the customers’ choices by restricting the availability of time slots or asking for time slot dependent fees in order to minimize the resulting delivery costs. Several integrated optimization models which simultaneously consider both periods have been proposed in the literature for the case where delivery costs are mainly due to routing costs of service vehicles. Usually, these models consider decisions in the booking period on a very detailed level, whereas the resulting routing costs in the service period are approximated on a rather rough level. To get better approximations, we propose four new linear mixed-integer programming models which can be combined with the existing approaches for modelling the booking period. The basic idea consists in generating a pool of possible routes, subsets of which are selected using a set-covering approach to get feasible routings. Following this idea, standard solvers can be used for the resulting integrated models, a requirement becoming more common in practice. Computational experiments show that the approximated costs are sufficiently close to the real ones.