2026-09-23T03:22:16Z https://opus4.kobv.de/opus4-uni-passau/oai

oai:kobv.de-opus4-uni-passau:1564 2025-08-26 bibliography:false doc-type:PhDThesis open_access ddc ddc:330

Studies on optimization problems with dynamically arriving information 0000-0002-0973-1817 Catherine Lorenz M.Sc. 330 Dynamic optimization Online algorithms Competitive analysis Probabilistic performance guarantees Very large-scale neighborhood search In today’s fast-paced world, transportation planning, e-commerce, smart manufacturing, emergency services, and financial markets operate in real-time environments where dynamically arriving information must be integrated on-the-fly into decision-making. Research produced online algorithms ranging from myopic reoptimization (Reopt) to learning-based anticipation methods. However, given the complexity of real-world problems, optimal decision policies remain unknown, and effectiveness is often assessed through simulations against simple benchmarks, leaving improvement potential and robustness uncertain. This dissertation proposes effective online policies using classical and innovative analytical and computational evaluation methods, establishing performance bounds and comparisons to optimal solutions. It designs algorithmic frameworks for two dynamic optimization problems: the Online Order Batching, Sequencing, and picker Routing Problem (OOBSRP) in warehousing and the Traveling Salesman Problem with a Truck and a Drone under Incomplete Information (TSP-DI), for disaster relief. Given the importance of automation in real-time environments, a strong emphasis is placed on robotic solutions. For the OOBSRP with manual and robotic carts, we prove that Reopt is asymptotically optimal with probability one under broad stochastic conditions. From a worst-case perspective, no policy can improve Reopt by more than 50%, as it is shown to be asymptotically two-competitive. A computational study confirms that Reopt’s gaps to the complete-information optimum are small, e.g. averaging less than 5% for a cost-minimization objective. A pattern analysis of Complete-Information Optimal Solutions (CIOSs), generated with dynamic programming algorithms, identifies simple algorithmic enhancements – like eliminating waiting, intervention, or strategic relocation – that further reduce costs and delivery times. These findings suggest limited benefits of anticipatory (including AI-based) algorithms in OOBSRP. Conversely, for TSP-DI, where road blockages reveal dynamically, Reopt performs poorly in the worst case, as we reveal its exponentially growing competitive ratio. We show that policies delaying deliveries for drone surveillance are significantly superior in competitive ratio. A proposed hybrid policy achieves best average and worst-case results in experiments. Using battery-limited drones introduces a challenging static subproblem within these policies, classified as Drone Routing Problems with Energy Replenishment (DRP-E). We develop a Very Large-Scale Neighborhood Search (VLNS) and an exact method for generic DRP-Es. VLNS searches an exponential-sized neighborhood of a promising solution entirely in polynomial runtime, making it ideal for real-time policies or intensification in metaheuristics. This dissertation underscores the importance of analytical guarantees and comparisons to the optimum in online algorithm design, as policy effectiveness often diverges from intuition and varies significantly across problems. Universität Passau Passau Innstrasse 29, 94032 Passau Alena Otto Daniele Vigo 2024-11-28 2025-03-31 PhDThesis Text urn:nbn:de:bvb:739-opus4-15649 application/pdf eng Standardbedingung laut Einverständniserklärung thesis.doctoral Universität Passau Passau Wirtschaftswissenschaftliche Fakultät 1 https://opus4.kobv.de/opus4-uni-passau/oai/container/index/docId/1564 https://opus4.kobv.de/opus4-uni-passau/frontdoor/index/index/docId/1564