Multi-Objective Policy Evolution for a Same-Day Delivery Problem with Soft Deadlines

Abstract

Same-day delivery problems (SDDPs) deal with efficient near-term satisfaction of dynamic and stochastic customer demand. During the day, a sequence of decisions has to be performed related to delivery route construction and driver dispatching. Formulated as Markov decision process, the goal is to find a policy that maximizes the expected reward over a specified class of instances. In the literature, scalar reward functions have dominated so far, by either considering only one objective or several objectives transformed into one using a weighted sum or lexicographic order. In this work, we consider a vector-valued reward with two dimensions, tardiness and costs, for a real-world inspired SDDP with tight soft deadlines within hours. The goal is to evolve non-dominated sets of policies for typical days with a certain stochastic load pattern and geographical order distribution in advance and let the decision maker select which one to deploy. We achieve this utilizing classical multi-objective genetic algorithms, NSGA-II and SPEA2, and by parallelization of the computationally intensive policy evaluations. Based on the experimental results, we observe that accepting a small amount of additional tardiness initially leads to a substantial return in terms of reduced mean delivery times per order.