{"id":{"repo_id":"passau-thes","oai_identifier":"oai:kobv.de-opus4-uni-passau:2090"},"canonical_url":"https://search.dev.ndltd.org/etd/passau-thes/oai:kobv.de-opus4-uni-passau:2090","repository":{"repo_id":"passau-thes","name":"Universität Passau","base_url":"https://opus4.kobv.de/opus4-uni-passau/oai"},"display":{"title":"Studies of Complex Routing Problems with Synchronization and Stochastic Information","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Rocha, Luis Aurelio"],"institution":"Universität Passau","degree_name":null,"degree_level":"thesis.doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Otto, Alena","Liers, Frauke"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026-04-22","date_published":"2026-04-22","updated_at":"2026-07-24T03:45:12Z","subjects":["VRP","PDP","synchronization","uncertainty","specimen collection"],"languages":[],"rights":["Standardbedingung laut Einverständniserklärung"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://opus4.kobv.de/opus4-uni-passau/frontdoor/index/index/docId/2090","outbound_label":"Repository record","outbound_source":"source_url"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Otto, Alena","Liers, Frauke"]},{"key":"dc:creator","label":"Author","values":["Rocha, Luis Aurelio"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:publisher","label":"Institution","values":["Universität Passau"]},{"key":"dc:type","label":"Dc Type","values":["doctoralThesis"]},{"key":"thesis:degree_level","label":"Degree Level","values":["thesis.doctoral"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Universität Passau"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["VRP","PDP","synchronization","uncertainty","specimen collection"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["Standardbedingung laut Einverständniserklärung"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Studies of Complex Routing Problems with Synchronization and Stochastic Information"]}]}],"canonical_facts":{"dc:contributor":["Otto, Alena","Liers, Frauke"],"dc:creator":["Rocha, Luis Aurelio"],"dc:description.abstract":["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."],"dc:format.medium":["application/pdf"],"dc:publisher":["Universität Passau"],"dc:rights":["Standardbedingung laut Einverständniserklärung"],"dc:subject":["VRP","PDP","synchronization","uncertainty","specimen collection"],"dc:title":["Studies of Complex Routing Problems with Synchronization and Stochastic Information"],"dc:type":["doctoralThesis"],"thesis:degree_level":["thesis.doctoral"],"thesis:institution_name":["Universität Passau"]},"updated_at":"2026-07-24T03:45:12Z"}