Frohner, N., Raidl, G., & Chicano, F. (2023). Multi-Objective Policy Evolution for a Same-Day Delivery Problem with Soft Deadlines. In GECCO ’23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation (pp. 1941–1949). Association for Computing Machinery. https://doi.org/10.1145/3583133.3596381
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.
