Studies of Complex Routing Problems with Synchronization and Stochastic Information

Routing problems typically assume deterministic parameters and independent vehicle operations. Many real-world logistics systems, however, involve synchronization requirements among resources and uncertainty in system parameters — challenges that are both practically relevant and theoretically difficult. This dissertation addresses both dimensions through a series of complementary contributions. We begin with a literature review of specimen logistics, surveying strategic, tactical, and operational routing problems in laboratory supply chains. We then develop a two-index formulation for the specimen collection problem with synchronized multiple trips and one lab, which solves 55 out of 56 small instances where the state-of-the-art model finds none, proves optimality in up to 30% of larger instances, and outperforms the state-of-the-art ALNS in 8 out of 12 settings with an average gap of 1.12%. In the third chapter, we introduce a compact model for the pickup-and-delivery problem with transfers, strengthened by novel valid inequalities, and extended to a novel branch-and-cut approach, which outperforms existing methods by solving 68 of 90 large benchmark instances and, for the first time, solves instances with up to 50 requests. The fourth chapter addresses a truck-and-drone TSP under vehicle synchronization and edge-traversal uncertainty in disaster relief settings; we derive competitive ratios for common policies, validate them in simulation, and propose an improved hybrid policy exploiting uncertainty through strategic surveillance. Finally, we study a production routing problem with stochastic driver availability. Our new deterministic heterogeneous-vehicle reformulation (HetPRP) outperforms our customized Benders decomposition approach, achieving average optimality gaps of 0.11%–0.97% on benchmark instances with up to 50 retailers and nine periods. We further quantify the value of stochastic solutions — up to 5.23% in non-urban settings — and show through a case study that integrating crowd-sourced drivers can yield cost savings of up to 21.71%. Taken together, these contributions advance the state of the art in synchronized and stochastic routing, offering both theoretical guarantees and practically efficient solution methods.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Passau

Year

2026

Author dc:creator

• Rocha, Luis Aurelio

Contributors dc:contributor

• Otto, Alena
• Liers, Frauke

• VRP
• PDP
• synchronization
• uncertainty
• specimen collection

Statement dc:rights

• Standardbedingung laut Einverständniserklärung

Repository record source_url

https://opus4.kobv.de/opus4-uni-passau/frontdoor/index/index/docId/2090

OAI identifier oai:identifier

oai:kobv.de-opus4-uni-passau:2090