{"id":{"repo_id":"aachen","oai_identifier":"oai:publications.rwth-aachen.de:56862"},"canonical_url":"https://search.dev.ndltd.org/etd/aachen/oai:publications.rwth-aachen.de:56862","repository":{"repo_id":"aachen","name":"RWTH Aachen University","base_url":"https://publications.rwth-aachen.de/oai2d"},"display":{"title":"Netzwerk-Design für zweistufige Transportsysteme und ein Branch-and-Price-Verfahren für das gemischte Direkt- und Hubflugproblem","abstract":"Transportation network design is one of the most important fields of application of Operations Research and Mathematical Optimization. It offers great potential to reduce costs and to improve service quality. For the planning of large-scale regular service networks small daily savings of a few percent can imply substantial overall savings caused by the regular repetition of transportation processes. Subject of this thesis is the modelling and solution of specially structured service network design problems for two-stage transportation systems where services of the inner network are either direct transports between terminals or transports between a terminal and a central hub. Fundamental tactical planning tasks are the selection and the scheduling of services (especially the choice of the terminals of the inner network and the times of transship actions), as well as the unique assignment of transportation requests to services. The newly developed models cover many important planning requirements like individual time windows of requests, opening hours of terminals, times for loading and unloading of means of transport, and complex interdependences between services like re-positioning and limitations of some groups of services. The direct flight problem (DFP) and the mixed direct and hub flight problem (MFP) are presented as practically relevant examples of multi-modal (combined air and ground) service network design problems. They occur as important planning problems in connection with wide area letter mail transportation at Deutsche Post AG. Deutsche Post AG is the main mail and parcel carrier in Germany. The proposed method for the solution of these NP-hard problems is based on Linear Programming. The models which are solved during the solution process possess a huge number of integer variables. Therefore, Dantzig-Wolfe decomposition and column generation techniques are used to dynamically generate additional variables according to the ideas of branch-and-price for integrally solving these problems. In addition to this, a new class of cutting planes may be incorporated. In this case, the overall solution method becomes a sophisticated branch-and-price-and-cut approach. On the one hand, the extensive methodological part of the thesis contains a self-contained presentation of the general methodology. On the other hand, the design of an enhanced branch-and-price-and-cut solution method for DFP and MFP requires the solution of the LP-relaxation of the master program with so called clique-knapsack problems as pricing problems, the definition of compatible branching rules, the development of cutting planes and their corresponding separation algorithms as well as several techniques for acceleration. The same techniques suggested as components within exact optimization algorithms can also be applied to construct a heuristic procedure to approximately solve large-scale problem instances. A prototype of the overall procedure has been successfully implemented. The detailed computations used for empirical analysis are based on data of the decision support system ISBT-Netzplanung of Deutsche Post AG. DFP with up to 400 requests can be tackled successfully with the methods proposed in this thesis. A newly developed clustering procedure for transportation requests makes it possible to compute integer solutions for still much bigger instances with a maximum error typically in the range of a few percent. Instances of the DFP with less than 200 requests are almost always solved to proven optimality. For the MFP it is feasible to compute integer solutions for instances with about 200 requests. Clustered DFP- and MFP-instances of this size cover relevant real-world planning tasks of Deutsche Post AG. Different scenarios about the potential future development of the letter mail network can quickly be analyzed and optimized. From the practical point of view it is remarkable that the use of a central flight hub does not make much sense provided that the objective focuses on transportation costs. A pure direct flight network should be preferred to mixed transportation network with a hub.","abstract_html":"Transportation network design is one of the most important fields of application of Operations Research and Mathematical Optimization. It offers great potential to reduce costs and to improve service quality. For the planning of large-scale regular service networks small daily savings of a few percent can imply substantial overall savings caused by the regular repetition of transportation processes. Subject of this thesis is the modelling and solution of specially structured service network design problems for two-stage transportation systems where services of the inner network are either direct transports between terminals or transports between a terminal and a central hub. Fundamental tactical planning tasks are the selection and the scheduling of services (especially the choice of the terminals of the inner network and the times of transship actions), as well as the unique assignment of transportation requests to services. The newly developed models cover many important planning requirements like individual time windows of requests, opening hours of terminals, times for loading and unloading of means of transport, and complex interdependences between services like re-positioning and limitations of some groups of services. The direct flight problem (DFP) and the mixed direct and hub flight problem (MFP) are presented as practically relevant examples of multi-modal (combined air and ground) service network design problems. They occur as important planning problems in connection with wide area letter mail transportation at Deutsche Post AG. Deutsche Post AG is the main mail and parcel carrier in Germany. The proposed method for the solution of these NP-hard problems is based on Linear Programming. The models which are solved during the solution process possess a huge number of integer variables. Therefore, Dantzig-Wolfe decomposition and column generation techniques are used to dynamically generate additional variables according to the ideas of branch-and-price for integrally solving these problems. In addition to this, a new class of cutting planes may be incorporated. In this case, the overall solution method becomes a sophisticated branch-and-price-and-cut approach. On the one hand, the extensive methodological part of the thesis contains a self-contained presentation of the general methodology. On the other hand, the design of an enhanced branch-and-price-and-cut solution method for DFP and MFP requires the solution of the LP-relaxation of the master program with so called clique-knapsack problems as pricing problems, the definition of compatible branching rules, the development of cutting planes and their corresponding separation algorithms as well as several techniques for acceleration. The same techniques suggested as components within exact optimization algorithms can also be applied to construct a heuristic procedure to approximately solve large-scale problem instances. A prototype of the overall procedure has been successfully implemented. The detailed computations used for empirical analysis are based on data of the decision support system ISBT-Netzplanung of Deutsche Post AG. DFP with up to 400 requests can be tackled successfully with the methods proposed in this thesis. A newly developed clustering procedure for transportation requests makes it possible to compute integer solutions for still much bigger instances with a maximum error typically in the range of a few percent. Instances of the DFP with less than 200 requests are almost always solved to proven optimality. For the MFP it is feasible to compute integer solutions for instances with about 200 requests. Clustered DFP- and MFP-instances of this size cover relevant real-world planning tasks of Deutsche Post AG. Different scenarios about the potential future development of the letter mail network can quickly be analyzed and optimized. From the practical point of view it is remarkable that the use of a central flight hub does not make much sense provided that the objective focuses on transportation costs. A pure direct flight network should be preferred to mixed transportation network with a hub.","abstract_has_math":false,"creators":["Irnich, Stefan"],"institution":"Publikationsserver der RWTH Aachen University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Sebastian, Hans-Jürgen"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2002,"date_issued":"2002","date_published":"2002","updated_at":"2026-07-30T19:42:01Z","subjects":["info:eu-repo/classification/ddc/330","Wirtschaft","Transportplanung","Netzwerkmodell","Simulation"],"languages":["ger"],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-118942%22"],"render_values":[{"text":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-118942%22","href":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-118942%22","code":true}]}]},"links":{"outbound_url":"https://publications.rwth-aachen.de/record/56862","outbound_label":"Repository record","outbound_source":"dc:identifier"},"source_record":{"url":"https://publications.rwth-aachen.de/oai2d?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Apublications.rwth-aachen.de%3A56862","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Sebastian, Hans-Jürgen"]},{"key":"dc:creator","label":"Author","values":["Irnich, Stefan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:coverage","label":"Dc Coverage","values":["DE"]},{"key":"dc:date","label":"Dc Date","values":["2002"]},{"key":"dc:publisher","label":"Institution","values":["Publikationsserver der RWTH Aachen University"]},{"key":"dc:relation","label":"Dc Relation","values":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-3000"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["info:eu-repo/classification/ddc/330","Wirtschaft","Transportplanung","Netzwerkmodell","Simulation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["ger"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/record/56862","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-118942%22"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Transportation network design is one of the most important fields of application of Operations Research and Mathematical Optimization. It offers great potential to reduce costs and to improve service quality. For the planning of large-scale regular service networks small daily savings of a few percent can imply substantial overall savings caused by the regular repetition of transportation processes. Subject of this thesis is the modelling and solution of specially structured service network design problems for two-stage transportation systems where services of the inner network are either direct transports between terminals or transports between a terminal and a central hub. Fundamental tactical planning tasks are the selection and the scheduling of services (especially the choice of the terminals of the inner network and the times of transship actions), as well as the unique assignment of transportation requests to services. The newly developed models cover many important planning requirements like individual time windows of requests, opening hours of terminals, times for loading and unloading of means of transport, and complex interdependences between services like re-positioning and limitations of some groups of services. The direct flight problem (DFP) and the mixed direct and hub flight problem (MFP) are presented as practically relevant examples of multi-modal (combined air and ground) service network design problems. They occur as important planning problems in connection with wide area letter mail transportation at Deutsche Post AG. Deutsche Post AG is the main mail and parcel carrier in Germany. The proposed method for the solution of these NP-hard problems is based on Linear Programming. The models which are solved during the solution process possess a huge number of integer variables. Therefore, Dantzig-Wolfe decomposition and column generation techniques are used to dynamically generate additional variables according to the ideas of branch-and-price for integrally solving these problems. In addition to this, a new class of cutting planes may be incorporated. In this case, the overall solution method becomes a sophisticated branch-and-price-and-cut approach. On the one hand, the extensive methodological part of the thesis contains a self-contained presentation of the general methodology. On the other hand, the design of an enhanced branch-and-price-and-cut solution method for DFP and MFP requires the solution of the LP-relaxation of the master program with so called clique-knapsack problems as pricing problems, the definition of compatible branching rules, the development of cutting planes and their corresponding separation algorithms as well as several techniques for acceleration. The same techniques suggested as components within exact optimization algorithms can also be applied to construct a heuristic procedure to approximately solve large-scale problem instances. A prototype of the overall procedure has been successfully implemented. The detailed computations used for empirical analysis are based on data of the decision support system ISBT-Netzplanung of Deutsche Post AG. DFP with up to 400 requests can be tackled successfully with the methods proposed in this thesis. A newly developed clustering procedure for transportation requests makes it possible to compute integer solutions for still much bigger instances with a maximum error typically in the range of a few percent. Instances of the DFP with less than 200 requests are almost always solved to proven optimality. For the MFP it is feasible to compute integer solutions for instances with about 200 requests. Clustered DFP- and MFP-instances of this size cover relevant real-world planning tasks of Deutsche Post AG. Different scenarios about the potential future development of the letter mail network can quickly be analyzed and optimized. From the practical point of view it is remarkable that the use of a central flight hub does not make much sense provided that the objective focuses on transportation costs. A pure direct flight network should be preferred to mixed transportation network with a hub."]},{"key":"dc:source","label":"Dc Source","values":["Aachen : Publikationsserver der RWTH Aachen University X, 297 S. : graph. Darst. (2002). = Aachen, Techn. Hochsch., Diss., 2002"]},{"key":"dc:title","label":"Title","values":["Netzwerk-Design für zweistufige Transportsysteme und ein Branch-and-Price-Verfahren für das gemischte Direkt- und Hubflugproblem"]}]}],"canonical_facts":{"dc:contributor":["Sebastian, Hans-Jürgen"],"dc:coverage":["DE"],"dc:creator":["Irnich, Stefan"],"dc:date":["2002"],"dc:description":["Transportation network design is one of the most important fields of application of Operations Research and Mathematical Optimization. It offers great potential to reduce costs and to improve service quality. For the planning of large-scale regular service networks small daily savings of a few percent can imply substantial overall savings caused by the regular repetition of transportation processes. Subject of this thesis is the modelling and solution of specially structured service network design problems for two-stage transportation systems where services of the inner network are either direct transports between terminals or transports between a terminal and a central hub. Fundamental tactical planning tasks are the selection and the scheduling of services (especially the choice of the terminals of the inner network and the times of transship actions), as well as the unique assignment of transportation requests to services. The newly developed models cover many important planning requirements like individual time windows of requests, opening hours of terminals, times for loading and unloading of means of transport, and complex interdependences between services like re-positioning and limitations of some groups of services. The direct flight problem (DFP) and the mixed direct and hub flight problem (MFP) are presented as practically relevant examples of multi-modal (combined air and ground) service network design problems. They occur as important planning problems in connection with wide area letter mail transportation at Deutsche Post AG. Deutsche Post AG is the main mail and parcel carrier in Germany. The proposed method for the solution of these NP-hard problems is based on Linear Programming. The models which are solved during the solution process possess a huge number of integer variables. Therefore, Dantzig-Wolfe decomposition and column generation techniques are used to dynamically generate additional variables according to the ideas of branch-and-price for integrally solving these problems. In addition to this, a new class of cutting planes may be incorporated. In this case, the overall solution method becomes a sophisticated branch-and-price-and-cut approach. On the one hand, the extensive methodological part of the thesis contains a self-contained presentation of the general methodology. On the other hand, the design of an enhanced branch-and-price-and-cut solution method for DFP and MFP requires the solution of the LP-relaxation of the master program with so called clique-knapsack problems as pricing problems, the definition of compatible branching rules, the development of cutting planes and their corresponding separation algorithms as well as several techniques for acceleration. The same techniques suggested as components within exact optimization algorithms can also be applied to construct a heuristic procedure to approximately solve large-scale problem instances. A prototype of the overall procedure has been successfully implemented. The detailed computations used for empirical analysis are based on data of the decision support system ISBT-Netzplanung of Deutsche Post AG. DFP with up to 400 requests can be tackled successfully with the methods proposed in this thesis. A newly developed clustering procedure for transportation requests makes it possible to compute integer solutions for still much bigger instances with a maximum error typically in the range of a few percent. Instances of the DFP with less than 200 requests are almost always solved to proven optimality. For the MFP it is feasible to compute integer solutions for instances with about 200 requests. Clustered DFP- and MFP-instances of this size cover relevant real-world planning tasks of Deutsche Post AG. Different scenarios about the potential future development of the letter mail network can quickly be analyzed and optimized. From the practical point of view it is remarkable that the use of a central flight hub does not make much sense provided that the objective focuses on transportation costs. A pure direct flight network should be preferred to mixed transportation network with a hub."],"dc:identifier":["https://publications.rwth-aachen.de/record/56862","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-118942%22"],"dc:language":["ger"],"dc:publisher":["Publikationsserver der RWTH Aachen University"],"dc:relation":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-3000"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:source":["Aachen : Publikationsserver der RWTH Aachen University X, 297 S. : graph. Darst. (2002). = Aachen, Techn. Hochsch., Diss., 2002"],"dc:subject":["info:eu-repo/classification/ddc/330","Wirtschaft","Transportplanung","Netzwerkmodell","Simulation"],"dc:title":["Netzwerk-Design für zweistufige Transportsysteme und ein Branch-and-Price-Verfahren für das gemischte Direkt- und Hubflugproblem"],"dc:type":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]},"updated_at":"2026-07-30T19:42:01Z"}