Value function approximation for dynamic multi-period vehicle routing

In practical applications like parcel or technician services, customers request service during the day. Service providers decide whether to accept a customer for same-day service or to defer a customer due to resource limitations. Some requests are therefore postponed to the following day. To satisfy customer expectations, service providers aim on a high number of same-day services. Still, acceptance decisions not only affect the performance on the current, but also on the following day. Suitable acceptance, postponement, and routing decisions therefore should anticipate future routing and requests in both the current and the next day(s). The resulting decision problem is a dynamic multi-period vehicle routing problem with stochastic service requests. To approximately solve the Markov decision process of the presented problem, we present an anticipatory dynamic policy based on approximate dynamic programming. This policy estimates the potential of problem states with respect to future same-period services within and over the periods. Our policy draws on value function approximation, state space aggregation, and on a classification of the periods. We compare our policy to several policies from the literature. We analyze how and when multi-period anticipation improves the solution quality significantly and how the newly developed state space classification is essential to achieve anticipation. We finally show how multi-period anticipation changes the acceptance behavior to less discrimination of rural customers and to a fairer geographical distribution of same-day services in comparison to single-period anticipation.