Studies on optimization problems with dynamically arriving information

In real-time environments like transportation planning, e-commerce, smart manufacturing, or emergency services, dynamically arriving information must be integrated on-the-fly into decision-making. This dissertation proposes effective online algorithms using classical and innovative analytical and computational evaluation methods, performance bounds, and comparisons to optimal solutions. It focuses on 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. 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 we show its asymptotical two-competitiveness. A computational study validates Reopt’s small gaps to the complete-information optimum (e.g. averaging at most 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 with dynamically revealing road blockages, we prove that Reopt performs poorly in the worst case, with an exponentially growing competitive ratio. We propose policies delaying deliveries for drone surveillance that are significantly superior in competitive ratio and average results. Scheduling replenishment of battery-limited drones introduces a challenging static subproblem within these policies, which we address with a novel Very Large-Scale Neighborhood Search(VLNS) and an exact method. VLNS efficiently explores exponential-sized neighborhoods in polynomial runtime, making it an attractive subroutine for online policies and metaheuristics. This dissertation underscores the importance of analytical guarantees and comparisons to optima in online algorithm design, as policy effectiveness often diverges from intuition and varies significantly across problems.