Abstract
In this dissertation, a well-known network design and optimization problem that exists in transportation is considered. The corresponding problem is known as service network design problem (SNDP) in the Operations Research literature and lies somewhere between the tactical and operational planning levels. The service network design problem addresses the questions such as where, when, by which vehicle and how often a transportation service should be performed on the network. SNDPs are usually studied on a time-space (also known as time-expanded) network because the problem seeks answers for the 'when' question. For this reason, the output of an SNDP is a schedule that can be implemented in a finite period of time for a rolling basis in most cases.
This thesis consists of three main parts in which an independent research problem is studied and prepared for the publication. The first part addresses a generic SNDP for the consolidation-based freight carriers on randomly generated networks; however, the second and third parts rely on the same business problem of a major express shipment carrier in the Caribbean.
In the first part (Chapter 2), we study a generalized version of the service network design problem that explicitly incorporates tactical capacity planning for peak demand periods. The objective of the problem is to minimize the overall operational costs by optimally routing and scheduling assets that transport a given set of commodities to be delivered between origin and destination nodes over multiple periods on a transportation service network. We propose an arc-based formulation that employs three alternative approaches for balancing demand and supply in transportation service networks: demand shifting, asset leasing, and outsourcing. We develop valid inequalities to reduce the solution space of the proposed model and present a comprehensive numerical study to assess and demonstrate the computational performance of the model and the contribution of the valid inequalities. We also propose a multi-phase heuristic algorithm, referred to as the dedicate-merge-and-meld algorithm (DMaM), for tackling large size problems. Numerical analysis is carried out to demonstrate that the DMaM algorithm has promising potential for obtaining good solutions in considerably short time windows for large size problems, where the commercial solver fails to initialize the branch-and-bound algorithm due to excessive memory usage.
The second part (Chapter 3) considers strategic (location), tactical (allocation), and operational level (routing and scheduling) decisions within the same network design problem simultaneously. The practical aircraft (feeder) routing and scheduling problem of a major express cargo carrier is modeled as a service network design problem on a hierarchical hub-and-spoke network. The company aims to locate hubs at the bottom level of the hierarchy. We formulate the operational problem as a path-based model and then incorporate the tactical and strategic level decisions into the problem gradually. A multi-step solution procedure is proposed; this first executes an initial data processing that involves data wrangling, route generation, and elimination in order to contain the size of the solution space for the mathematical model. We consider two routing policies, dedicated runs and milk runs, and develop a formulation for each problem setting. These problems take place in the third (optimization) step of the procedure that ends with post-processing to resolve time conflicts between routes. We compare all problem settings and routing policies in terms of operational costs, flight hours, and fleet sizing in the computational experiment.
In the third part (Chapter 4), we address a resilient humanitarian service network design problem considering hurricane disruptions for the same major express shipment carrier that operates a feeder hub-and-spoke network in the Caribbean. The significance of a resilient transportation network- either a public or a private network- arises when a transportation network is utilized for humanitarian purposes immediately after the disaster. The carrier aims to combine non-urgent relief supplies with regular commercial cargo to achieve transportation efficiency as well as meet the humanitarian need of the affected areas in the post-disaster period. We develop a multi-stage stochastic optimization model and propose a two-phase decomposition framework to solve the problem. The solution framework is composed of two distinct models, the outer model and the inner model in each corresponding phase. In the outer model, we employ a multi-stage stochastic programming model that determines the amount of relief and commercial cargo in each period without scheduling decisions. By using the output of the outer model, we aim to solve a service network design model to generate the final schedule for each day (stage). Also, we develop a heuristic approach to decompose the multi-phase stochastic problem into single-phase deterministic problems to overcome the limitations encountered when performing the two-phase procedure. Scenarios are generated for incorporating the endogenous uncertainty that is the status of an impacted airport (node) on the network. The status of any node would be either up or down immediately after the disaster. We conducted the initial experiments in which we obtained the preliminary results for the resilient humanitarian network design problem with one-node disruption cases on the physical network.