ABSTRACT Title of Thesis: Scheduling Under Uncertainty for a Single-Hub Intermodal Freight System Degree Candidate: Nikola Markovi? Degree and Year: Master of Science, 2010 Thesis directed by: Paul Schonfeld Professor Department of Civil and Environmental Engineering This thesis addresses the optimization of an intermodal system with freight transfers at a single hub. It investigates the transportation processes and constraints that arise in a system?s recovery after a major disruption during which backlogs have accumulated along the routes. When dealing with the backlogs, the system operator must coordinate the transportation processes and control the inflow of freight to the terminal in order to avoid overloading its storage facilities, which might reduce the throughput of the system. The coordination of transportation processes during the system?s recovery can further improve the overall system performance by reducing the dwell time, increasing vehicle utilization and reducing late delivery penalties. This work focuses on the scheduling problem and develops an approach that would help the ? ? ? system operator reduce the overall system cost while taking into account the constraints arising in actual intermodal and intra-modal systems. Assuming that the schedule on some routes is exogenously determined and inflexible, we seek to optimize the schedules of vehicles on remaining routes. Models are developed that minimize the total cost of operating an intermodal system with freight transfers at one hub by optimizing the departure times of vehicles on the routes with flexible schedules. This model can be solved numerically without the approximations of alternative methods such as simulation. Moreover, it can be successfully applied to situations when statistical or queuing analyses are not applicable due to the small number of events (vehicle arrivals). We specifically analyze an intermodal system consisting of multiple feeder truck routes and multiple main airline routes. The specific example of two transportation modes was used to make the development and application of the model easier to understand. However, the mathematical model developed in this thesis is applicable to any other combination of transportation modes using discrete vehicles. ? ? ? ? Scheduling Under Uncertainty for a Single-Hub Intermodal Freight System By Nikola Markovi? ? Thesis?submitted?to?the?Faculty?of?the?Graduate?School?of?the? University?of?Maryland?at?College?Park?in?partial?fulfillment? of?the?requirements?for?the?degree?of? Master?of?Science? 2010? Advisory Committee: Professor Paul M. Schonfeld, Chairman/Advisor Associate Professor Elise Miller-Hooks Assistant Professor Cinzia Cirillo ? ii? ? Table of Contents Section Page List of Tables iv List of Figures v Chapter 1. Introduction 1 1.1 Problem Statement 2 1.2 Objective 5 1.3 Organization of the Thesis 6 Chapter 2. Literature Review 8 2.1 Machine Scheduling 8 2.2 Scheduling in Freight Systems 12 Chapter 3. Model Formulation Assuming Flexible Truck Departures 16 3.1 Storage Cost 16 3.1.1 Expected Primary Dwell Time E[PDT] 17 3.1.2 Additional Dwell Time ADDT 21 3.1.3 Formulation of the Storage Cost 26 3.2 In-Terminal Operation Cost 26 3.3 Penalty Cost 27 3.4 Airline Cost 29 ? iii? ? Table of Contents, cont. Section Page 3.5 Constraints 29 3.6 Mathematical Formulation of the Model 30 Chapter 4. Model Performance Assuming Flexible Truck Departures 32 4.1 Case with a Single Airplane Route 33 4.2 Case with Multiple Airplane Routes 39 Chapter 5. Model Formulation Assuming Flexible Takeoff Times 43 5.1 Expected Primary Dwell Time 43 5.2 Additional Dwell Time 45 5.3 Mathematical Formulation of the Model 48 Chapter 6. Model Performance Assuming Flexible Takeoff Times 50 6.1 Case with a Single Aircraft Route 50 6.2 Case with Multiple Aircraft Routes 54 Chapter 7. Conclusions 57 References 59 ? ? iv? ? List of Tables Number Page 4.1 Cost and Capacities 33 4.2 Exponentially Distributed Roundtrip Durations 34 4.3 Optimized Truck Schedule and Total Cost 34 4.4 Optimization Summary for Different Penalty Cost 36 4.5 Optimization Summaries for Different Penalty Cost and Relaxed Storage Capacity Constraint 37 4.6 Input Data 30 4.7 Exponentially Distributed Truck Duration 41 4.8 The Amount of Freight Carried in Each Roundtrip and its Connecting Main Route 41 4.9 Optimization Summary 42 6.1 Input Data 51 6.2 Optimized Schedule and Cost 52 6.3 Input Data 55 6.4 Exponentially Distributed Truck Roundtrip Duration Airplane Route 56 6.5 Optimization Summary 56 ? v? ? List of Figures Number Page 1.1 Intermodal Freight System 2 3.1 PDF of a Roundtrip Assigned to Truck ? 18 3.2 PDF?s of the First, Second and ??-th Arrival of Truck ? 20 4.1 Undelivered Amount of Freight vs. Penalty 35 5.1 PDF?s of the First, Second and ??-th Arrival of Truck ? 44 6.2 Sensitivity Analysis 53 ? 1? ? Chapter 1 Introduction Intermodal freight transport has many advantages which have encouraged its development during the last century. Reduced storage requirements and better utilization of infrastructure and transportation vehicles are just some of the characteristics that enable intermodal transport to outperform other transportation concepts. Intermodal freight systems include many interrelated operations and often require mechanization and human labor that tend to be expensive. Thus, even small changes in the ways such systems function can considerably influence the entire transportation process and thereby the overall system cost. Here we examine a way to reduce the overall cost of a system that has suffered a major disruption and focus on the vehicle scheduling problem. In this thesis we study a single-terminal intermodal freight system and analyze the system?s recovery after a major disruption. Assuming that the schedule on some routes might be exogenously determined, we identify the set of routes with fixed schedules and the set of routes with flexible schedules. We focus on scheduling vehicle departure times on the routes with flexible schedules. ? 2? ? Figure 1.1 Intermodal Freight System 1.1 Problem Statement Let us consider the intermodal freight system in Figure 1.1, whose operations can be described as follows. Trucks gather the freight from various locations in the region around the terminal and unload it in the terminal?s storage facilities. At the terminal, the freight is further loaded into airplanes which transport it to multiple destinations. Moreover, when the takeoff on route ? is scheduled at time ?? ?, we load into the airplane as much freight connecting to route ? as the airplane?s capacity allows. If an airplane?s capacity is exceeded, the remaining freight must wait for the next ? 3? ? connecting flight with available capacity. Conversely, if prior to the takeoff there is little freight connecting to route ?, the airplane?s capacity is underused and an additional flight might be needed later. Suppose that the system in Figure 1.1 has suffered a major disruption and that a lot of freight has accumulated at locations spread around the terminal. In order to dissipate the backlogs the system operator assigns to each truck certain number of roundtrips that should be carried out consecutively. The question that arises is when we should schedule the departure times on the routes with flexible schedules, in order to minimize the overall system costs. Determining which routes have flexible schedules is related to both technological characteristics of the observed transportation system as well the issue of ownership (e.g. the problem can be considered from a perspective of a trucking or an airline company, or a company controlling both truck and airline routes). Thus, two models are developed to optimize the schedules on flexible routes. The first model assumes that the schedules on airline routes are fixed and optimizes truck departure times. Conversely, the second model develops a method to optimize the number of takeoffs and their schedules for the given truck departures. If we assume that the schedules on airline routes are fixed, the question that arises is when the trucks should begin their roundtrips. On the one hand, the operator would like to transport to the terminal as much freight as soon as possible and have it ? 4? ? connect to the first airplane with available capacities in order to avoid late delivery penalty. On the other hand, storing the freight at terminal?s storage while waiting for the connection represents an additional cost which could be reduced if freight arrives slightly prior to the takeoff. Moreover, the probabilistic duration of truck roundtrips and possibility of overloading the storage further complicate operator?s decisions about when to schedule the truck departures. Although air transportation may be less flexible than other transportation modes, when a system recovers from a major disruption the system operator may dispatch the trucks as soon as the system becomes operational and then schedule the flight departure times. Assuming that the airline schedule is flexible, there exists a similar tradeoff in costs. The earlier one schedules the takeoff, the lower are storage and penalty cost associated with the freight that successfully connects. However, the earlier we schedule the takeoff, the greater are chances that airplane?s capacity will remain unused due to late truck arrivals. Having airplanes operate below capacity may require running additional flights, thereby increasing the airline cost. This thesis will analyze the case with flexible schedules on truck routes and fixed takeoff times, as well as the case with the fixed truck departures and flexible numbers and schedules of flights. Therefore two distinct models will be developed and analyzed through the case studies. ? 5? ? 1.2 Objective The objective is to develop a model that will optimize the departure times on the routes with flexible schedules. When optimizing the schedules, the following assumptions are made: 1. The number of roundtrips that a truck is assigned is given, as well as the randomly distributed duration of each roundtrip and the sequence of the roundtrips. 2. The expected amount of freight in the terminal must never exceed the preset multiple of a terminal storage capacity (i.e. 80% of the storage capacity). 3. The system is cyclic since the trucks are assigned consecutive roundtrips all ending at the terminal. 4. Durations of truck roundtrips are independent. 5. Flow is unidirectional, which is typical for evacuation models. We seek to find the schedules that minimize total system cost while considering the constraints and assumptions listed above. In calculating total cost the following is considered: 1. Storage cost, which refers to the cost of storing freight in terminal?s storage facilities while waiting for a connection. ? 6? ? 2. Cost of in-terminal operations that includes the cost of unloading and loading the freight. The cost of in-terminal operations is lower when a truck arrives slightly prior to the takeoff and unloads directly on the airplane. 3. Penalty for late delivery, reflecting that the freight?s value decreases as delivery is delayed. Instead of using a time value function, we introduce a penalty function which depends on the time of the takeoff to which the freight connects. 4. Airline service cost that includes both airplanes and airport services. This type of cost is not sensitive to the truck departure times since it solely depends on the given number of takeoffs. Therefore this type of cost will represent a constant in the model which assumes fixed schedules and number of takeoffs. However, this type of cost will not be a constant in the second model which assumes flexible number of takeoffs. To find the schedule that minimizes the overall system cost, we formulate the total cost as a function of the departure times. Later we use a genetic algorithm (GA) to minimize the total system cost. 1.3 Organization of the Thesis The rest of this thesis is organized into four chapters. Chapter 2 provides the review of some related optimization problems. The model assuming flexible truck departures is developed in chapter 3 and tested on a case study in chapter 4. Chapter 5 ? 7? ? provides a model that optimizes the schedule and number of takeoffs assuming fixed truck departures. This model is tested on the case studies in Chapter 6. Finally, Chapter 7 provides conclusions. ? 8? ? Chapter 2 Literature Review The scheduling problem is a classical problem of operations research. Thus, a fair amount of research has been devoted to solving different variations of scheduling problems, but all under different assumptions from those considered in this thesis. The literature review is divided into two parts where we explain some of the related research. We also point out the differences in assumptions and problem settings of existing work, compared to the problem statement of this thesis. 2.1 Machine Scheduling The problem statement of this thesis is analogous in some ways to a scheduling problem for parallel machines with stochastic duration of jobs and deterministic due dates. In the machine scheduling problem there are typically ? jobs to be processed on ? machines. The objective is to find the sequence of jobs to be processed in order to achieve overall system objective for the given due date(s). Different variations of the parallel machine scheduling problem include different assumptions, such as deterministic or stochastic job processing, identical or non-identical machines and durations of jobs, common or individual due dates for jobs, deterministic or stochastic ? 9? ? due date(s), deterministic or stochastic release dates, processing with or without preemption etc. Moreover, different objectives are found in literature. Some authors minimize the expected tardiness while others minimize the expected earliness or the weighted combination of the two. Here are considered a few publications on stochastic and deterministic parallel machine scheduling which include: Pinedo (1983), Lee & Pinedo (1997), Dessouky and Marcellus (1998), and Zied Bouyahia, Monia Bellalouna, Patrick Jaillet & Khaled Ghedira (2010). Pinedo (1983) considers stochastic scheduling problems in which processing times of jobs are independent exponentially distributed random variables, the release dates are random variables with an arbitrary joint distribution, and the due dates are random variables with a joint distribution that satisfies certain conditions. Pinedo analyzes four models and develops simple policies which minimize the expected weighted sum of completion times and the expected weighted number of late jobs. The following problems, including both single and parallel machine scheduling, are studied: 1. Minimization of the expected weighted sum of job completion times on a single machine when jobs have different release dates. 2. Minimization of the expected weighted sum of job tardiness on a single machine when jobs have different due dates. ? 10? ? 3. Minimization of the expected weighted number of late jobs on a single machine when the jobs have different due dates. 4. Minimization of the expected weighted number of late jobs on parallel machines when the jobs have different due dates. After stating that the deterministic counterparts of the four problems are NP-hard, he provides four simple policies and proves that they provide the optimal solutions for the stochastic version of the problems. The results in this paper contrast with the lack of any known polynomial time algorithms for the deterministic counterparts of the four models considered. The author lists some other scheduling problems with random duration jobs that are easier to solve than their deterministic counterparts. Lee & Pinedo (1997) consider parallel machine scheduling problem with uniform machines, deterministic duration of jobs, and sequence dependent setup times. A job has a processing time, weight and due date. To minimize the sum of the weighted tardiness, the authors develop a three phase heuristic. In the first phase they compute certain statistics which help them construct the sequence of jobs using a dispatching rule in the second stage. In the third and final stage the simulated annealing method is applied starting from the seed solution which represents the result of the second stage. The application of heuristics is justified in the paper?s introduction by stating that minimizing the sum of the weighted tardiness for a single machine with all weights ? 11? ? being equal is an NP-hard problem. Finally, the authors state that variations of their algorithm are used in a number of factories and mention an implementation in the liquid packaging industry where the algorithm provided satisfactory schedules. Dessouky and Marcellus (1998) address the scheduling of identical jobs on uniform parallel machines with random processing times. Scheduling identical jobs on a set of uniform parallel machines occurs when a batch of identical products need to be processed by a set of machines with different efficiencies. The authors do not consider the precedence constraint, nor preemption. They provide methods for optimizing the expected sum of weighted completion times and the probability of meeting a common due date. A relatively small example of solving 12 jobs on 5 machines is provided and the results are discussed. Bouyahia et al. (2010) contribute to the parallel machine scheduling problem by addressing long-term robust optimization. Their goal is to design robust a priori schedules which on the long term horizon are optimal or suboptimal with respect to total weighted flow time. They consider designing a schedule without knowing in advance which jobs need to be processed. Hence, they treat the number of jobs to be processed as a random variable, and to each job they assign a probability that it will need to be processed. They show through both theoretical and experimental studies that simple strategies can provide upper bounds tight to known lower bounds. They discuss ? 12? ? two strategies, reoptimization and a priori strategy. In the experimental study they solve problems including 2, 4 and 6 machines, and 100, 200, 500 and 1000 jobs to be processed, and assess the quality of the a priori strategy. In comparing parallel machine scheduling to our problem, we can treat each truck as a machine which is assigned certain number of jobs, which in our case represent randomly distributed roundtrips. The due dates in our intermodal freight system represent the connection times, while the earliness and tardiness penalties typical of machine scheduling can be observed as storage costs and late delivery penalties. However, the main difference is that we assume the sequence of roundtrips (jobs) for each truck (machine) to be given, and we seek to optimize truck departure times (starts of production), and schedule of takeoffs (due dates). Moreover, we assume multiple due dates for each job which represent connections. Finally, we develop a more sophisticated way to compute the earliness penalty (storage cost) than in the aforementioned literature on parallel machine scheduling. 2.2 Scheduling in Freight Systems Truck scheduling for ground to air connectivity has been studied by Randolph Hall (2001). He lists 11 steps in express transportation and points out the sorting ? 13? ? process at the origin airport as being particularly critical since it is susceptible to random delays in the arrival of work, and because it requires relatively large investments in facilities and labor. He further explains that the facilities and labor are only needed within concentrated time periods, which sometimes makes it uneconomical to provide sufficient capacity to process shipments as quickly as they arrive. The work focuses on scheduling the start time for the sorting process. The airport terminal is modeled as a queuing process with random bulk arrivals, and predictions are provided for expectation and standard variation of arrived work. The key concept behind the model is conversion of truck schedules into forecasts for the expected arrival of work, and forecasts for the standard deviation in the arrival of work. These pieces of information make it possible to predict the occurrence of starvation and the end time for a sort. The methods developed in this paper provide a tool for representing the trade-off between sort productivity and the objective of completing the sort as early as possible. Ting and Schonfeld (1997) analyze the transfer coordination in transit networks with deterministic and stochastic travel times. Total system cost is used to evaluate the performance of the coordination under different demand and arrival distributions. The authors study three different policies: uncoordinated, fully coordinated and partially coordinated operations. Two heuristic algorithms are applied to optimize both headways and slack times using integer multiples of base cycle, which are a round fraction of 60 ? 14? ? minutes. The results show that the coordination with integer-ratio headways is more advantageous than with a single common headway when the demand in the system is low, and the increasing variance of vehicle arrivals is caused by each route?s independently optimized headway. In addition, the integer-ratio approach based on integer multiples of a base cycle should be applied when the headway of each route is significantly different. The work of Ting and Schonfeld was extended to freight systems by Chen and Schonfeld (2010) who developed a hybrid GA-SQP method to optimize the headways. Several authors have addressed the airline scheduling problem under stochastic demand. Teodorovi? (1988) develops models to measure the level of service by minimizing the time difference between actual and desired departure times. In the first model, he demonstrates that the time difference can be approximately expressed as a function of flight frequency only, without regard to the departure times during the day. In the second model and numerical example, he finds the optimal departure times with respect to minimal average schedule delay for a known demand and preassigned frequency on a route between two cities. The work of Teodorovic is extended by Chang and Schonfeld (2001) through an integrated model that allows variability in flight departure times while resolving trade-offs between efficient fleet operation and quality of service. ? 15? ? Finally, the models developed in this thesis are not directly related to other models found in the literature. This work bases the intermodal system analysis on the randomly distributed duration of vehicle roundtrips. This approach is deemed to provide greater precision than some other models found in literature. The advantages and disadvantages of such a method will be examined in this thesis. ? 16? ? Chapter 3 Model Formulation Assuming Flexible Truck Departures In this chapter a model is developed that optimizes the truck departure times given fixed takeoff schedules. The mathematical program is developed by comprehensively deriving the cost components and constraints. In sections 3.1-3.4 the cost components listed in the problem statement are formulated. After deriving the constraints in section 3.5, the model?s formulation is presented in section 3.6. Please note that when computing the storage cost in 3.1 we develop two mathematical expectations and an algorithm which will also be used when formulating the in-terminal operation cost and the penalty for late delivery. 3.1 Storage Cost To determine the storage cost we need to estimate the amount of time that freight spends dwelling in the terminal storage. To facilitate the computation, we separate the in-terminal dwell time into two parts. The first part refers to the dwell time from the moment the freight arrives to terminal till the first connection upon its arrival, regardless of whether the airplane has enough capacity to take the connecting freight. We call this primary dwell time and compute its expectation in section 3.1.1. The ? 17? ? second part refers to the dwell time from the first connection upon the arrival of freight until the moment the freight is actually loaded into the airplane with available capacities. We call it additional dwell time and compute its expected value in section 3.1.2. 3.1.1 Expected Primary Dwell Time ?????? We first formulate the primary dwell time ??? which represents a random variable. Then we find its mathematical expectation ?????? which is a function of truck departure times and given duration of roundtrips and connection times. We comprehensively derive ?????? by starting from the simplest case and gradually developing it into its generic form. Suppose that truck ? is assigned a single roundtrip whose duration (including loading, unloading and a short break for the driver) is represented by a random variable ??,? with probability density function (PDF) ????,?, ??? , where ?? represents the truck?s departure time which we seek to determine. Moreover, let?s assume that the truck?s starting and end point is the terminal where the truckload should connect to one of ?? flights on route ? taking off at times ??? , ??? ????? ? . Let?s further assume that if a truck misses all ?? takeoffs, its cargo must wait for the connection at time ?? on the ? 18? ? following day. Finally, let?s suppose that the probability that the truck will arrive at the terminal after time ?? is negligible, ????,? ? ??? ? 0 Figure 3.1 PDF of a Roundtrip Assigned to Truck k Primary dwell time represents a random variable which depends on the departure time and the duration of roundtrip ??,?, as well as connection times ??? , ??? ????? ? and ??. Since a truck?s departure may be scheduled after the takeoff at ??? , let?s define ???? such that it represents the index of the first takeoff after ??. In another words, let ???? ? ??????? ? ? ??????? ? ? ???. We denote the primary dwell time of the freight ??,? ? carried by truck ? and connecting to route ? as ????,? ? and define it as follows: ?????????????????????????????????? ? ??????????????? ? ???????????????????? ? ??????????????????????????????????????????????????????????????????? ????,?, ??? ? 19? ? ????,? ? ? ? ? ? ? ???,? ? ?????? ? ????,???????? ? ??,? ? ????? ? ????????????? ? ??,? ? ??? ? ????,??????????????? ? ? ??,? ? ?? ????????????????? ? ??,? ? ??? ????,????????????? ? ? ??,? ? ??????????????????? (1) Having defined ????,? ? , we can compute its expectation by the application of the law of the unconscious statistician (Allen 2010). If we denote ??????? ? ? ?? and ????? ? ? ?? , the expected in-terminal dwell time of freight carried by truck ? and connecting to route ? is: ??????,? ? ? ? ??,? ? ? ? ??? ? ? ??,???????,?, ???????,?? ?? ? ???? ? ???? ?????? (2) Now we can extend previous analysis to a more complex case in which a truck makes multiple roundtrips. So let?s consider the case when truck ? is assigned ?? consecutive roundtrips, all starting and ending at the terminal. If we denote as ??,? a random variable which describes the duration of the ??? roundtrip made by truck ?, the random variable ??,? which describes the ??? truck arrival at the terminal is given with the following sum: ??,? ? ??,? ? ??,? ? ?? ??,??? ? ??,? (3) The PDF of a variable ??,? is defined as the convolution of PDF?s describing duration of ? roundtrips: ? 20? ? ????,?, ??? ? ????,?, ??? ? ????,?? ? ??? ????,???? ? ????,?? (4) Figure 3.2 PDF?s of the First, Second and ??-th Arrival of Truck ? Bearing in mind equations (2), (3) and (4), we can define the expected primary dwell time of the freight ??,? ? carried by truck ? in the ??? roundtrip and connecting to main route ?: ??????,? ? ? ? ??,? ? ? ? ??? ? ? ??,???????,?, ???????,?? ?? ? ???? ? ???? ?????? (5) The primary dwell time of cargo connecting to route ? and transported by truck ? in ?? roundtrips is given in (6). The probability of the last roundtrip ending after the takeoff scheduled on the following day is assumed to be negligible, ????,?? ? ? ?? ? 0 ?????????????????????????????????? ? ??????????????????? ? ???????????????????? ? ??????????????????????????????????????????????????????????????? ????,?, ??? ????,??, ??? ????,?, ??? ? 21? ? ?????? ?? ? ? ??????,? ? ?????? (6) We can now compute the expected primary dwell time of freight connecting to airline route ? and being transported by multiple trucks making multiple roundtrips. This can be easily done by summing (6) for all ? trucks in the intermodal freight system. ??????? ? ? ?????? ?????? (7) Finally, we can compute the expected dwell time for cargo connecting to all ? aircraft routes. ?????? ? ? ??????????? (8) 3.1.2 Additional Dwell Time ???? Since the calculation in 3.1 does not consider the possibility that freight might wait longer than period ??? ? ? ??,?? due to the limited capacity of airplanes, we need additional calculations. For example, if the expected amount of freight arriving in interval ????? ? , ?? ?? and connecting to route ? is greater than the capacity of airplane taking off at moment ?? ?, we must consider additional dwell time of cargo that cannot fit in the plane. The additional dwell time represents the amount of time that freight spends dwelling in the terminal after the first connection upon its arrival. ? 22? ? In order to calculate the additional dwell time we must compute the expected amount of freight connecting to route ? and arriving in each of ????? ? , ?? ?? intervals. The aforementioned expectation will be calculated in 3.2.2 based on the expected amount of freight arriving in ?0, ?? ?? interval, which we derive in section 3.2.1. Please note that 0 denotes the beginning of the observed period of time. Finally, in section 3.2.3 we provide an algorithm which computes additional dwell time ????. 3.1.2.1 Expected Amount of Freight Arriving in Interval ??, ?? ?? and Connecting to Route ? Again, we derive this expectation starting from the simplest case which includes a single truck. So let?s suppose again that truck ? is assigned ?? consecutive roundtrips and that we must calculate the expected amount of freight arriving in interval ?0, ?? ?? and connecting to route ?. To do so, we must first find the probability that ? arrivals occur within the ?0, ?? ?? interval. In other words, we need to calculate the probability that the first ? roundtrips end prior to ?? ?, while the subsequent roundtrip ends after ?? ?. ???? ? ????,? ? ?? ?; ? . . .?? ; ??,? ? ?? ??,? ? ?? ?; ??,? ? ?? ??,??? ? ?? ?? (9) The aforementioned probability is given with an ?? ? 1?-dimensional integral: ? 23? ? ???? ? ? ???,?. . ? ???,? ?? ????,????????,??? ? ?? ? ?? ? ????,?, . . , ??,???, ??? ?? ?? ????,????????,? ???,??? (10) Note that ????,?, ? , ??,???, ??? from the above equation represents joint probability density function of random variables ??,?, ? , ??,??? . Since durations of roundtrips are independent here, one can obtain the joint PDF by simply multiplying ? ? 1 probability density functions. (Please note that arrivals are mutually dependent; however the durations of individual roundtrips are independent.) ????,?, ? , ??,???, ??? ?? ????,?, ???? ????,?? ??? ??? (11) After having computed the probability of ? arrivals in interval ?0, ?? ?? , we can calculate the expected amount of freight connecting to route ? that truck ? delivers to terminal in the aforementioned interval as: ???? ??0, ?? ??? ? ? ??????,? ??? ??? (12) Now, we can consider the general case including multiple trucks making multiple roundtrips. For this case, the expected amount of freight connecting to route ? and arriving at the terminal in interval ?0, ?? ?? can be obtained by simply summing (12) for all v trucks. ? 24? ? ?????0, ?? ??? ? ? ???? ??0, ?? ??????? (13) 3.1.2.2 Expected Amount of Freight Arriving in Interval ????? ? , ?? ?? and Connecting to Route ? In section 3.1.2.1 the expected amount of freight connecting to route ? and arriving at the terminal in interval ?0, ?? ?? was computed. Based on that result, we are able to calculate the expected amount of freight connecting to route ? and arriving at the terminal in interval ????? ? , ?? ??, denoted as?????????? ? , ?? ???. This ????????? ? , ?? ??? equals the expected amount of freight arriving at the terminal in ?0, ?? ?? minus the expected amount of freight arriving in ?0, ???? ? ?. ????????? ? , ?? ??? ? ?????0, ?? ??? ? ?????0, ???? ? ?? (14) Having derived the previous expectation, we are now able to determine the expected amount of freight arriving between consecutive flights and thereby estimate the additional dwell time that occurs due to limited airplane capacity. ? 25? ? 3.1.2.3 Algorithm for Computing Additional Dwell Time ???? The algorithm for computing additional dwell time for cargo connecting to route ? uses the previously derived expectation?????????? ? , ?? ???. For the given takeoff times, it examines the expected amount of freight arriving between consecutive flights and determines whether this amount exceeds the airplane?s capacity ??. If it exceeds ??, the algorithm computes associated additional dwell time and adds it to ????? Let?s denote as ?? ? the amount of freight connecting to route ??left in storage after the ??? takeoff, and assign initial values of zero to ?? ? and ????? . Now, we can compute the additional dwell time for the cargo connecting to route ? with the recursive formula given in equations (15)-(18). ????? ? 0;???? ? 0 (15) ????? ? 1?????? (16) ?? ? ? ????0, ???? ? ? ????????? ? , ?? ??? ? ??? (17) ????? ? ????? ? ?? ?????? ? ? ?? ?? (18) Finally, after having computed additional dwell for cargo connecting to route ?, we can calculate total additional dwell time by simply summing (18) for all ? main routes. ? 26? ? ???? ? ? ????? ? ??? (19) 3.1.3 Formulation of the storage cost Since we know how to calculate the expected primary dwell time as well as the additional dwell time, we can compute the expected ton-hours of dwell time in terminal storage by summing two expectations. To obtain the storage cost, we multiply the sum of two expectations with unit storage cost ???. ?? ? ??????? ? ???????? (20) 3.2 In-Terminal Operation Cost As previously argued, the cost of in-terminal operations can be reduced when a truck arrives at the terminal slightly prior to the takeoff and takes its truckload directly to the aircraft. Thus, cost of in-terminal operations is sensitive to the schedule of takeoffs and should be considered in the optimization. Since we can formulate the expected amount of freight connecting to ? and arriving in a certain interval (14), we can estimate the expected amount of freight unloaded directly onto aircraft. We first denote as ??, the time interval such that a truck arriving within the ??? ? ? ??, ?? ?? will unload directly onto the airplane departing at ?? ?. We can now define the expected amount of freight connecting to route ? that will be transferred directly from truck to airplane. ? 27? ? ?? ? ? ? ??????? ? ? ??, ?? ???? ? ??? (21) To find the total amount of freight loaded directly to airplanes, we sum (21) for all ? airplane routes: ?? ? ? ? ??????? ? ? ??, ?? ???? ? ??? ? ??? (22) It is clear that remaining freight will be processed regularly and that another cost will be associated with it. Let us now denote as ???? the unit cost of in-terminal operations for the case when truck takes its truckload directly to the airplane. Moreover, let?s denote as ????the unit cost of in-terminal operations when the freight is processed regularly. Finally, if we denote as ? the overall amount of freight, then the total in- terminal operation cost is: ?? ? ??????? ? ?? ? ?????? (23) 3.3 Penalty Cost In order to estimate the late delivery penalty, we formulate the time-dependent penalty function ????? ?? and assume that the takeoff time ?? ? is relevant for calculating the penalty. For example, if ?? ? tons of freight are loaded on the flight taking off at ?? ?, the ? 28? ? corresponding penalty will be ?? ?????? ??. The penalty cost associated with freight carried on all ?? ? 1 flights on route ? is given in equation (24). Please note that ????? ? ? ?? ??? ? ? ?? ?????? ??? ??? ??? (24) However, the problem with the equation (24) is that we do not know in advance how much freight will be loaded in the airplane departing at ?? ?. Therefore, we need an algorithm that computes the penalty cost for the given ?? ??s. Similarly to the algorithm from the previous section, we compute the penalty cost using a recursive formula given in (25)-(28). We use again the expected amount of freight connecting to ? and arriving in the ????? ? , ?? ?? interval. ??? ? 0;???? ? 0 (25) ?????? ? ?1?????? ? 1 (26)? ?? ? ? ??????, ???? ? ? ????????? ? , ?? ???? (27) ??? ? ??? ? ?? ?????? ?? (28) To calculate the total penalty cost associated with truckloads carried at all ? main routes, we need to sum (28) for all airplane routes: ?? ? ? ??????? (29) ? 29? ? 3.4 Airline Cost The last type of cost we consider is the airline service cost which refers to the use of both airplanes and airport facilities. Let?s denote as ?? ? the cost of the ???flight on route ?. Then the airline service cost for all routes is: ?? ? ? ??????? ? ? ? ?? ??? ??? ? ??? (30) 3.5 Constraints The airplane capacity constraint has already been considered by calculating the additional dwell time ???? . However, the constraint regarding maximum storage capacity has not yet been included. Moreover, since the takeoff times might be restricted to certain intervals, we consider time windows for takeoffs. Finally, to represent possible airport capacity limits, we include minimum headway constraints for takeoffs. We must first ensure that the expected amount of freight never exceeds storage capacity. We define a vector ? such that its elements represent takeoff times on all ? main routes organized in ascending order. Element ?? represents the ??? takeoff from the terminal. Let?s denote ?? the total amount of freight left in terminal after the ??? takeoff, ? 30? ? similarly to ?? ? in the algorithm in (15)-(18). If we denote ? the total number of takeoffs from terminal and ????????, ???? the expected total amount of freight arriving between two consecutive flights, the storage constraint is given in (31). Please note that ?? ? 0, ?? ? 0, storage capacity is given as ?? and the storage multiplier is ?? ???? ? ????????, ???? ? ??????????? ? 1,? , ??? (31) General working agreements may allow a trucking company to schedule truck departures only within certain time windows (e.g. not at midnight). ?? ? ?? ? ??????? ? 1,? , ? (32) 3.6 Mathematical Formulation of the Model In sections 3.1-3.5 we explained the types of costs and constraints considered. Now we can provide the mathematical formulation of the model (33)-(35), which represents a stochastic mathematical program. ?????? ? ??? ? ?? ? ?? ? ?? (33) Subject to: ???? ? ????????, ???? ? ??????????? ? 1,? , ? (34) ? 31? ? ?? ? ?? ? ??????? ? 1,? , ??? (35) It should be noted that formulation (33)-(35) is given in the compact form and includes all the results from sections 3.1-3.5. ? 32? ? Chapter 4 Model Performance Assuming Flexible Truck Departures In order to test the mathematical formulation proposed in Chapter 3, we design two numerical examples. The first case includes a single aircraft route, while the second case deals with multiple aircraft routes. For the first case we also provide a sensitivity analysis where we study the tradeoffs in types of costs discussed in the Introduction of this thesis. For both cases we use a genetic algorithm (Goldberg 1995 and Michalewicz 1995) to optimize the schedules. An off-the-shelf GA toolbox (Global Optimization Toolbox) was used to optimize the schedules. In order to decrease the chances of getting the GA stuck in a local minimum, each optimization was performed multiple times with different input parameters such as initial population, population size and crossover function. The population size was varied between 10 and 15 individuals, while for the crossover function we tested several available options: scattered, one-point and two-point. Finally, since the GA is not guaranteed to find an optimal solution, we refer to the resulting schedules as ?optimized? rather than ?optimal?. ? 33? ? 4.1 Case with a Single Main Route A numerical example is developed that includes eleven truck roundtrips performed by four trucks. A truck with a capacity of 20 tons is assigned two roundtrips, while three trucks with 5 ton capacity are assigned three roundtrips each. All truck roundtrip times are exponentially distributed with average durations given in Table 4.2. The freight carried by trucks can connect to two flights during the current day or to the flight on the following day. Assuming the inputs from Table 4.1 and Table 4.2, we seek to optimize the truck schedule. Table 4.1 Cost and Capacities airplane capacity ??? 40 tons airplane capacity ??? 45 tons aircraft cost ??? 11000 mu/flight aircraft cost ??? 12000 mu/flight terminal storage capacity Sc 65 tons storage capacity multiplier ?? 0.80 storage cost SC 8 mu/ton hr amount of time ?t 15 min in-terminal operation cost ??? 30 mu/ton in-terminal operation cost ??? 10 mu/ton penalty function ????? 0 if t?2 mu/ton 25t-50 if 210 mu/ton takeoff time ??? 5.4 hrs takeoff time ??? 9.1 hrs time of the last takeoff ?? 25 hrs time windows ???, ??? [0,5] hrs ? 34? ? Table 4.2 Exponentially Distributed Roundtrip Durations truck truckload capacity [ton] 1st roundtrip [hr] 2nd roundtrip [hr] 3rd roundtrip [hr] 1 20 1/? = 2.1 1/? = 1.9 NA 2 5 1/? = 0.9 1/? = 0.6 1/? = 1.2 3 5 1/? = 1.0 1/? = 0.7 1/? = 1.4 4 5 1/? = 0.5 1/? = 1.1 1/? = 0.8 The optimized schedule for four trucks is given in Table 4.3. It provides the optimized start times of truck assignments and total system cost. The optimization time of approximately 2 hours was needed for the GA to converge within 25 to 35 generations for different input parameters. Table 4.3 Optimized Truck Schedule and Total Cost truck truck departure time optimized total cost 1 ?? ?2.84 ?? ?38748 2 ?? ?4.24 3 ?? ?4.25 4 ?? ?4.58 To verify the model and the tradeoff in types of costs that was explained in problem statement, we reoptimize the system varying the penalty for the freight that does not connect to the second flight and needs to wait for the connection on the next day. In another words, we reoptimize the system while varying ????? for ? ? 10 . In ? 35? ? Figure 4.1 we plot the penalty versus amount of freight that was not delivered during the current day. As the penalty increases, the amount of undelivered freight decreases until it reaches about 3.5 tons. Figure 4.1 Undelivered Amount of Freight vs. Penalty To investigate the reason why the undelivered amount of freight does not drop below some 3.5 tons even for the penalty as high as 100000 mu/ton, we analyze the expected amount of freight arriving to terminal on ?0, ?11?, ??11, ?21?, and ??21, ?1?. In Table 4.4 we show optimization summary for different values of penalty cost. 0 1 2 3 4 5 6 7 8 Freigh t[ to ns ] Penalty [mu] Sensitivity Analysis ? 36? ? Table 4.4 Optimization Summary with Different Penalties Penalty ????? for ? ? 10 Optimized schedule Total cost Expected amount of freight on ?0, ???? Expected amount of freight on ????, ???? Expected amount of freight on ????, ??? 200 2.84 4.24 4.25 4.58 38748 40.01 38.27 6.72 300 1.93 4.40 3.94 4.84 39360 44.08 35.58 5.34 400 1.07 4.00 3.61 4.68 39816 51.99 29.04 3.97 500 1.07 4.00 3.61 4.68 40213 51.99 29.04 3.97 800 0.01 4.98 3.43 4.42 41347 52.00 29.48 3.52 1100 0.01 4.98 3.43 4.42 42404 52.00 29.48 3.52 1400 0.01 4.98 3.43 4.42 43460 52.00 29.48 3.52 1700 0.01 4.98 3.43 4.42 44516 52.00 29.48 3.52 2000 0.01 4.98 3.43 4.42 45572 52.00 29.48 3.52 10000 0.01 4.98 3.43 4.42 73738 52.00 29.48 3.52 100000 0.01 4.98 3.43 4.42 390604 52.00 29.48 3.52 From Table 4.4 we can conclude that the expected amount of freight arriving on ?0, ?11? approaches the multiple of terminal storage capacity of 0.8?65=52 tons for penalties higher than 300 mu/ton. Thus, we can assume that the storage capacity constraint is binding for penalties higher than 300 mu/ton and insures that at least 3.52 tons are delayed to the following day. In other words, there exists no feasible schedule that would enable more freight to be delivered during the current day. To examine this assumption we run additional optimizations, but this time we relax the problem by disregarding the storage capacity constraint. We wish to see whether the amount of freight that overflows to the next day could be further reduced if the storage capacity ? 37? ? was unlimited. The optimization summaries for different penalties and relaxed storage capacity constraints are presented in Table 4.5. Table 4.5 Optimization Summaries for Different Penalties and Relaxed Storage Capacity Constraints Penalty ????? for ? ? 10 Optimized schedule Total cost Expected amount of freight on ?0, ???? Expected amount of freight on ????, ???? Expected amount of freight on ????, ??? 200 2.84 4.24 4.25 4.58 38748 40.01 38.27 6.72 300 1.93 4.40 3.94 4.84 39360 44.08 35.58 5.34 400 1.12 3.95 3.50 4.28 39807 54.52 26.70 3.78 500 0.53 4.02 3.02 3.66 40146 60.21 21.83 2.96 800 0.00 2.95 1.95 3.19 40840 69.03 13.95 2.02 1100 0.00 2.45 1.76 3.00 41432 70.83 12.27 1.90 1400 0.00 2.40 1.30 2.90 41991 71.67 11.49 1.84 1700 0.00 1.50 0.50 2.50 42533 74.23 9.10 1.67 2000 0.00 2.00 0.65 1.50 43048 74.77 8.58 1.65 10000 0.00 0.00 0.00 0.13 55433 77.16 6.32 1.52 100000 0.00 0.00 0.00 0.00 192101 77.19 6.29 1.52 Optimization results from Table 4.5 support our hypothesis that the storage capacity constraint was delaying about 3.5 tons to the next day. Comparing Table 4.4 and 4.5, we can conclude that optimized schedule and the cost is the same for both original and relaxed problem when the penalty is up to 300 mu/ton. This outcome was expected since the storage capacity constraint was not used up in these cases (the expected amount of freight arriving between consecutive flights was always less than ? 38? ? the maximum allowed 52 tons). Furthermore, we can conclude from Table 4.5 that the expected amount of freight on ?0, ?11? exceeds 52 tons for a penalty above 300 mu/ton, implying that the storage capacity constraint was binding in these cases. The optimized cost is also lower for the relaxed version of the problem when the penalty exceeds 300 mu/ton. This outcome was expected since relaxation should yield a solution that is at least as good as the solution to the original problem. This claim comes from the definition of the relaxation (Wolsey 1998). Moreover, from the last column in Table 4.5 we can conclude that the expected amount of freight does not drop to 0, even when all the trucks are scheduled at the beginning of the observed period of time. The explanation for this lies in the infinite tails of the exponentially distributed durations of vehicle roundtrips. Finally, the sensitivity analysis was intended to examine the behavior of the model and verify the anticipated tradeoff in types of cost, as well as the mathematical formulation of the model. The sensitivity analysis showed that leaving more freight to be delivered on the subsequent day yields better solution for relatively low penalty. As the penalty increases while the storage cost remains the same, the amount of freight left undelivered decreases. The undelivered amount of freight drops as much as the storage capacity constraint allows it, or as much as possible considering the infinite tails of exponential distributions. The sensitivity analysis also showed effects of the storage ? 39? ? capacity constraint on the optimized schedule and total cost. By comparing the optimization summary for the original and relaxed version of the problem, we showed that the storage capacity constraint was binding for higher penalty cost. Thus we can conclude that similar sensitivity analysis can be used to optimize the storage capacity. 4.2 Case with Multiple Main Routes Here we design a numerical example including two aircraft routes and the input data from Table 4.6. Table 4.7 provides means for truck roundtrip durations, as well the connecting airplane routes for the freight carried. Again, all the roundtrip times are exponentially distributed. This time, we consider a case with eight trucks making twenty-two roundtrips and freight connecting to two airplane routes. The amount of freight connecting to airplane routes is given in Table 4.8. ? ? 40? ? Table 4.6 Input Data airplane capacity, route 1 ??? 40 tons airplane capacity, route 1 ??? 45 tons airplane capacity, route 2 ??? 45 tons airplane capacity, route 2 ??? 50 tons aircraft cost, route 1 ??? 11000 mu/flight aircraft cost, route 1 ??? 12000 mu/flight aircraft cost, route 2 ??? 14000 mu/flight aircraft cost, route 2 ??? 15000 mu/flight terminal storage capacity Sc 85 tons storage capacity multiplier ?? 0.80 storage cost SC 8 mu/ton hr amount of time ?t 15 min in-terminal operation cost ??? 30 mu/ton in-terminal operation cost ??? 10 mu/ton penalty function ????? 0 if t?2 mu/ton 25t-50 if 210 mu/ton takeoff time on route 1 ??? 5.7 hrs takeoff time on route 1 ??? 9.4 hrs time of the last takeoff on route 1 ?? 26 hrs takeoff time on route 2 ??? 4.9 hrs takeoff time on route 2 ??? 8.8 hrs time of the last takeoff on route 2 ?? 27 hrs time window for truck 1 ???, ??? [2,3] hrs time window for truck 2 ???, ??? [0,4.5] hrs time window for truck 3 ???, ??? [2,3] hrs time window for truck 4 ???, ??? [0,4.5] hrs time window for truck 5 ???, ??? [4,4.5] hrs time window for truck 6 ???, ??? [0,4.5] hrs time window for truck 7 ???, ??? [0,4.5] hrs time window for truck 8 ???, ??? [0,4.5] hrs ? ? ? 41? ? Table 4.7 Exponentially Distributed Truck Roundtrip Duration truck truckload capacity [ton] roundtrip #1 in hours roundtrip #2 in hours roundtrip #3 in hours 1 20 1/? = 2.13 1/? = 1.95 NA 2 5 1/? = 0.76 1/? = 1.27 1/? = 1.59 3 5 1/? = 0.58 1/? = 0.96 1/? = 0.62 4 5 1/? = 1.39 1/? = 1.83 1/? = 0.76 5 20 1/? = 2.09 1/? = 2.47 NA 6 5 1/? = 0.51 1/? = 1.52 1/? = 1.09 7 5 1/? = 1.19 1/? = 1.11 1/? = 1.10 8 5 1/? = 0.94 1/? = 1.64 1/? = 1.76 Table 4.8 Amount of Freight Carried in Each Roundtrip and its Destination truck roundtrip #1 roundtrip #2 roundtrip #3 l=1 l=2 l=1 l=2 l=1 l=2 1 ??,?? ?5.6 ??,?? ?14.4 ??,?? ?15.1 ??,?? ?4.9 NA NA 2 ??,?? ?1.4 ??,?? ?3.6 ??,?? ?5.0 ??,?? ?0.0 ??,?? ?1.6 ??,?? ?3.4 3 ??,?? ? 5.0 ??,?? ? 0.0 ??,?? ?1.9 ??,?? ?3.1 ??,?? ?2.2 ??,?? ?2.8 4 ??,?? ?3.0 ??,?? ?2.0 ??,?? ? 0.0 ??,?? ?5.0 ??,?? ?2.3 ??,?? ?2.7 5 ??,? ? ?8.7 ??,? ? ? 11.3 ??,? ? ?9.8 ??,? ? ?10.2 NA NA 6 ??,?? ?0.0 ??,?? ? 5.0 ??,?? ?1.1 ??,?? ?3.9 ??,?? ?5.0 ??,?? ?0.0 7 ??,?? ?3.9 ??,?? ?1.1 ??,?? ?0.0 ??,?? ? 5.0 ??,?? ?2.5 ??,?? ?2.5 8 ??,?? ?0.0 ??,?? ? 5.0 ??,?? ?2.4 ??,?? ?2.6 ??,?? ?4.5 ??,?? ?0.5 Table 4.9. provides optimization summary for the case including two airplane routes. It presents optimized departure times and total system cost. ? 42? ? Table 4.9 Optimization Summary truck truck departure time truck truck departure time optimized total cost 1 ?? ?2.11 5 ?? ?4.00 ?? ?83709 mu 2 ?? ?3.43 6 ?? ?4.14 3 ?? ?3.00 7 ?? ?3.09 4 ?? ?2.47 8 ?? ?4.21 ? 43? ? Chapter 5 Model Formulation Assuming Flexible Takeoff Times In this chapter a model is developed that optimizes the number and schedule of takeoffs assuming fixed truck departure times. Here it is assumed that trucks begin with their roundtrips as soon as the system becomes operational (e.g. at time 0) and the operator?s objective is to determine (1) number of takeoffs on each airplane route and (2) corresponding schedule. In this chapter it is assumed that the truck fleet is homogenous and we work with truckloads rather than tons. Section 5.1 provides the formulation of the expected primary dwell time ??????, which is derived somewhat differently than in Chapter 3. The section 5.2 contains the formulation of the additional dwell time ???? arising from limited airplane capacity. As in the model in Chapter 3, both ?????? and ???? are needed for computing storage cost and are included in the formulation of the model provided in section 5.3. 5.1 Expected Primary Dwell Time ?????? We formulate ?????? using the same notation introduced in Chapter 3. Clearly, this time we do not go through all the details but point out the main differences in ? ? computation distribution F So th roundtrip: ??????,? ? ? ? If a expected pr (36) for all some round parameter ? . Since the for the first igure A1 PD e expected ? ? ?? ? ???? ? ???? ??? truck was imary dwel the truckloa trips might ?,? ? which is ??????????? ? ???????? trucks begin roundtrip. M F?s of the F primary dw ??? ? ? ??,?? carrying tru l time of ca ds carried in not be con 1 if truckloa ????,?? ???????????????????? ????,? 44? their roun oreover, w irst, Second ell time of t ????,?????? ckloads con rgo from tr ?? roundtri necting to d carried by ? ? ???????????????????? ? dtrips and ti e integrate s and ??-th A he truckload ,?? necting to uck ? would ps. Howeve airline rou truck ? in ???? ????????? ? ??????????? me 0, we d tarting from rrival of Tr carried by route ??in al be calcula r, since truc te ? , we int the ??? roun ,??? ?????????????????????? o not use sh 0 instead o uck ? truck ? in th l roundtrips ted by sum kloads carri roduce a b dtrip connec ?????? ifted f ??. e ??? (36) , the ming ed in inary ts to ? 45? ? route ?, and 0 otherwise. The dwell time of cargo from truck k connecting to route ? is given in (37). The probability of the last roundtrip ending after the takeoff scheduled on the following day is assumed to be negligible, ????,?? ? ? ?? ? 0. ?????? ?? ? ? ??,? ? ??????,? ? ?????? (37) Finally, we can compute expected primary dwell time for cargo carried by all ? trucks and connecting to all ? outbound aircraft routes. ?????? ? ? ? ?????? ?????? ? ??? (38) 5.2 Additional Dwell Time ???? Again, to compute ???? we need to find the expected number of truckloads arriving in interval ????? ? , ?? ?? and connecting to route ? . We begin by finding the aforementioned expectation on ?0, ?? ?? . Then we extended to interval ????? ? , ?? ?? and finally provide the algorithm for computing ????. ? 46? ? 5.2.1 Expected Number of Connecting Truckloads Arriving in Interval ??, ?? ?? The probability that first ? roundtrips end prior to ?? ? is computed similarly like in Chapter 3, but with different boundaries for the multidimensional integral. This time the first roundtrip is integrated starting at time 0 instead of ??. ???? ? ? ???,? ?? ???,? ?? ????,????????,??? ? ?? ? ? ? ????,?, ? , ??,???? ?? ?? ????,????????,? ???,??? (39) The joint PDF in (39) is defined as follows: ????,?, ? , ??,???? ?? ? ????,?? ??? ??? (40) After having computed the probability of ? arrivals in interval ?0, ?? ??, we can calculate the expected number of arrivals of truck ? in the aforementioned interval as: ? ?????????? (41) However, truck ? may not be carrying freight connecting to route ? in all ?? roundtrips. Thus, we should not multiply ???? with the number of arrivals in order to calculate the expected number of arriving truckloads connecting to route ?. Instead, we use again binary parameter ??,? ? and express the expected number of truckloads delivered by truck ? in interval ?0, ?? ?? and connecting to route ? as follows: ? 47? ? ????? ? ?0, ?? ??? ? ? ????? ??,? ?? ??? ?? ??? (42) Now, we can consider the general case including multiple trucks making multiple roundtrips. For this case, the expected number of truckloads connecting to route ? and arriving at the terminal in interval ?0, ?? ?? can be obtained by simply summing (42) for all v trucks. ??????0, ?? ??? ? ? ????? ? ?0, ?? ??????? (43) 5.2.2 Expected Number of Connecting Truckloads Arriving in Interval ????? ? , ?? ?? The expected number of truckloads connecting to route ? and arriving at the terminal in interval ????? ? , ?? ?? equals the expected number of truckloads arriving at the terminal in ?0, ?? ?? minus the expected number of truckloads arriving in ?0, ???? ? ?. ?????????? ? , ?? ??? ? ??????0, ?? ??? ? ??????0, ???? ? ?? (44) 5.2.3 Algorithm for Computing Additional Dwell Time ???? The algorithm for computing the additional dwell time is exactly the same as for the model assuming the flexible truck departures and thus we do not repeat it here. ? 48? ? 5.3 Model Formulation As previously stated, our objective is to minimize total system cost while satisfying certain constraints. Since the constraints are slightly different than the ones considered in the model assuming flexible truck departures, we focus more on them. 5.3.1 Total Cost The total cost function can be computed according to the procedure described in Chapter 3 and using the two modified expectations provided in 5.1 and 5.2. Thus we avoid repeating the equations and simply provide the objective function in its compact form. ?? ? ??? ? ?? ? ?? ? ????? (45) 5.3.2 Constraints The storage capacity constraint is the same as in the model in Chapter 3: ???? ? ?????????, ???? ? ??????????? ? 1,? , ??? (46) ? 49? ? We consider the time window constraint for takeoffs. Utilization of airport facilities is often restricted to certain time slots. Therefore each one of ? takeoff times must occur within corresponding time window. Moreover, time windows might be restricted by the preferred delivery times. ?? ? ?? ? ?????????? ? 1,? , ? (47) Finally, we assume that limited airport capacity might require a minimum time interval between any two takeoffs. ?? ? ???? ? ???????????? ? 2,? , ?? (48) 5.3.3 Mathematical Formulation of the Model The formulation of the problem is given in (49)-(52). ?????? ? ??? ? ?? ? ?? ? ??? (49) Subject to: ???? ? ?????????, ???? ? ??????????? ? 1,? , ? (50) ?? ? ?? ? ?????????? ? 1,? , ?????????????????????????????? (51) ?? ? ???? ? ???????????? ? 2,? , ? (52) ? 50? ? Chapter 6 Model Performance Assuming Flexible Takeoff Times A genetic algorithm (GA) is used to optimize (49)-(52). Similarly to the previous analysis, we repeat each optimization several times in order to decrease the chances of the GA getting stuck in the local optimum. Again, we analyze the case with a single and multiple aircraft routes. 6.1 Case with a Single Aircraft Route We develop a numerical example that includes twelve truck assignments conducted by four trucks. Each truck is assigned three consecutive roundtrips, all exponentially distributed with average durations given in Table 6.1. Assuming the remaining inputs from Table 6.1, we seek to optimize the number of takeoffs and corresponding schedule. ? 51? ? Table 6.1 Input Data airplane capacity Ac 5 truckloads aircraft cost CA1 2000 mu/flight multiple of storage capacity mcSc 8 truckloads storage cost SC 40 mu/truckload?hr amount of time ?t 15 min in-terminal cost Ctr 150 mu/truckload Ctd 50 mu/truckload time of the last takeoff e1 30 hrs penalty function ????? 0 if t?2 mu/truckload 125t-250 if 210 mu/truckload Exponentially Distributed Truck Roundtrip Durations: truck 1st roundtrip [hr] 2nd roundtrip [hr] 3rd roundtrip [hr] 1 1/? = 1.5 1/? = 1.3 1/? = 0.8 2 1/? = 0.9 1/? = 0.6 1/? = 1.2 3 1/? = 1.0 1/? = 0.7 1/? = 1.4 4 1/? = 0.5 1/? = 1.1 1/? = 1.3 The optimization results for 3, 4, 5, 6 and 7 takeoffs are presented in Table 6.2. We present optimized schedule for five different numbers of takeoffs and corresponding costs. Please note that in ?other costs? we consider storage, penalty, loading & unloading cost. Moreover, by marginal savings in other costs we consider savings in storage, penalty, loading & unloading cost due to introducing an additional flight. ? 52? ? Table 6.2 Optimized Schedule and Costs Number of Flights Total Aircraft Cost Other Cost Marginal Savings in Other Cost Total Cost Takeoff Times 3 6000 7042 NA 13042 1.21 3.45 30 4 8000 4598 2444 12598 1.21 3.13 6.14 30 5 10000 3938 660 13938 1.21 2.47 4.19 7.10 30 6 12000 3561 377 15561 0.84 2.00 3.22 4.98 7.61 30 7 14000 3327 234 17327 0.80 2.00 2.80 3.98 5.56 8.10 30 The results presented in Table 6.2 show that the total cost was minimized in the case with four takeoffs. Therefore we conclude that at the cost of 2000 mu/roundtrip, one more flight than necessary to satisfy the demand should be introduced. Moreover, we can observe that storage, penalty and loading/unloading cost decrease with the increase in the number of takeoffs. This outcome was expected and it confirmed the tradeoff between types of cost that we explained in the problem statement. We can also note that the marginal savings in storage, penalty and loading/unloading cost decrease with the number of aircraft roundtrips, which is another outcome we anticipated. Based on the values for storage, penalty and loading/unloading cost we can explore how different flight costs affect the optimized number of takeoffs and hence the schedule. In Figure 6.1 we plot total cost for 3, 4, 5, 6 and 7 flights vs. flight cost. In Figure 4 can be seen four threshold values for airplane roundtrip cost which determine the optimized number of takeoffs. Those values are 234, 377, 660 and 2444 monetary ? 53? ? units respectively. Clearly, for a relatively low aircraft roundtrip cost, the total system cost is optimized by scheduling more takeoffs than necessary to satisfy the demand. As the airline cost increases, the optimized number of takeoffs decreases until it eventually drops to the minimum number needed to satisfy the demand. Figure 6.1 Sensitivity Analysis 0 5000 10000 15000 20000 25000 30000 0 15 0 30 0 45 0 60 0 75 0 90 0 10 50 12 00 13 50 15 00 16 50 18 00 19 50 21 00 22 50 24 00 25 50 27 00 28 50 30 00 To ta lC os t Flight Cost in MU Sensitivity Analysis 3 Flights 4 Flights 5 Flights 6 Flights 7 Flights ? 54? ? 6.2 Case with Multiple Aircraft Routes Here we design a numerical example including multiple aircraft routes. In Table 6.3 we provide the mean for truck roundtrip duration, as well the connecting airplane route for the carried truckload. Again, all the roundtrips are exponentially distributed. This time, we consider the case with twelve trucks making three roundtrips and freight connecting to three air routes. Adopting the inputs from Table 6.3 and 6.4 we optimize six takeoff times on three outbound airplane routes, while considering the maximum terminal storage capacity, minimum time between takeoffs and time windows for two takeoffs. Table 6.4 provides optimization results. It should be noted that by ?other cost? in Table 6.4, we consider storage, penalty, loading and unloading cost. ? 55? ? Table 6.3 Input Data flight cost on route ? CA1 4000 mu/flight CA2 4800 mu/flight CA3 4500 mu/flight multiple of storage capacity m?S? 15 truckloads storage cost SC 40 mu/truckload?hr in-terminal cost Ctr 150 mu/truckload Ctd 50 mu/truckload penalty function ????? 0 if t?2 125t-250 if 210 last takeoff on route ? ?? 30 hrs ?? 31 hrs ?? 32 hrs minimum time between two takeoffs ???? 0.5 hrs amount of time ?t 15 min time window for the first takeoff on route 1 (a, b) (2, 3) hrs time window for the first takeoff on route 2 (a, b) (1.5, 2.1) hrs ? 56? ? Table 6.4 Exponentially Distributed Truck Roundtrip Duration and Connecting Airplane Route 1st roundtrip [hr] connecting route ? 2nd roundtrip [hr] connecting route ? 3rd roundtrip [hr] connecting route ? truck 1 1/? = 1.13 2 1/? = 1.65 3 1/? = 1.47 2 truck 2 1/? = 0.76 3 1/? = 1.27 2 1/? = 1.59 1 truck 3 1/? = 0.58 2 1/? = 0.96 1 1/? = 0.62 2 truck 4 1/? = 1.39 1 1/? = 1.83 3 1/? = 0.76 1 truck 5 1/? = 1.53 2 1/? = 0.99 3 1/? = 1.33 1 truck 6 1/? = 0.51 3 1/? = 1.52 1 1/? = 1.09 3 truck 7 1/? = 1.19 1 1/? = 1.11 3 1/? = 1.10 1 truck 8 1/? = 0.94 1 1/? = 1.64 3 1/? = 1.76 3 truck 9 1/? = 1.56 2 1/? = 1.96 2 1/? = 1.70 1 truck 10 1/? = 1.42 2 1/? = 1.95 1 1/? = 1.07 3 truck 11 1/? = 0.94 3 1/? = 1.63 2 1/? = 1.99 1 truck 12 1/? = 1.68 3 1/? = 1.77 3 1/? = 1.14 2 Finally, the optimized takeoff times and corresponding costs on three airline routes are given in Table 6.5. Table 6.5 Optimization Summary Aircraft Route ? Number of Flights on ?? Aircraft Cost on ? Other Cost on ? Takeoff times on route ?? Total Cost 1 3 12000 8180 2.37 5.10 30 63770 2 3 14400 6447 1.87 4.60 31 3 3 13500 9243 1.37 3.74 32 ? 57? ? Chapter 7 Conclusions Models are developed to optimize the departure times on routes with flexible schedule in a single-terminal intermodal freight system. The models are designed to minimize the total cost of a system that has suffered a major disruption during which backlogs have accumulated. They can be applied to very general cases but seem especially suitable for applications with relatively few vehicle arrivals on truck routes. The models? complex and exact mathematical formulation improve their precision but decrease the solvable problem size. Therefore these proposed models are most suitable for optimizing intermodal systems in situations when statistical or queuing analyses are less preferable due to the small number of events (vehicle arrivals), or when high variance appears in simulation analysis (Law 2007). An off-the-shelf genetic algorithm was used to solve the stochastic programs and optimize the schedules in case studies. The canned genetic algorithm performed well for the analysis of the observed intermodal systems with relatively few arrivals on truck routes. However, the development of a customized GA would be preferable for the analysis of larger intermodal systems. ? 58? ? Sensitivity analyses were performed to examine the behavior of two suggested models. In Chapter 4, multiple optimizations were conducted for different penalty cost and both the original and relaxed versions of the problem were studied. The sensitivity analysis showed that storage capacity constraint affected the optimized schedule and that suggested model could be used to optimize the terminal storage capacity in addition to truck departures. The sensitivity analysis in Chapter 6 examined the influence of flight cost on the optimized number of takeoffs and the corresponding schedule. It also determined the thresholds for introducing additional flights. Finally, this thesis focused on the integration of truck and air operations. However, the mathematical models developed in this thesis are general and can be applied to other combinations of transportation modes with discrete vehicles. ? 59? ? References 1. Allen, T., Introduction to Engineering Statistics and Lean Sigma. Springer-Verlag, London 2010. 2. Birge, J., Louveuax, F., Introduction to Stochastic Programming. Springer-Verlag, New York 1997. 3. Bouyahia, Z., Bellalouna, M., Jaillet, P., Ghedira, K. A Priori Parallel Machine Scheduling, Computers & Industrial Engineering 58 (2010) 488?500. 4. Chang, S.W. and Schonfeld, P. Optimized Schedules for Airline Routes. Journal of Transportation Engineering, ASCE, 130-4, 2004, pp. 412-418. 5. Chen, C.C. and Schonfeld, P. ?Modeling and Performance Assessment of Intermodal Transfers at Cargo Terminals,? Annual TRB Meeting, January 2010, (10-2924). 6. Dessouky, M. I., Marcellus, R. L., Zhang, L. Scheduling Identical Jobs on Uniform Prallel Machines with Random Processing times, 23rd International Conference on Computers and Industrial Engineering, Vol. 35, 1998, p.p. 109-112. 7. Global Optimization Toolbox, Math Works http://www.mathworks.com/products/global-optimization/index.html ? 60? ? 8. Goldberg, D. E. Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, 1995. 9. Hall, R., W. Truck Scheduling for Ground to Air Connectivity, Journal for Air Transport Management, 2001, pp. 331-338. 10. Law, A. Simulation Modeling and Analysis. McGraw-Hill, New York, NY 2007. 11. Lee, Y. H., Pinedo, M. Scheduling Jobs on Parallel Machines with Sequence Dependent Setup Times. European Journal of Operations Research, 1997, p.p 464- 474 12. Michalewicz, Z. Genetic Algorithms + Data Structure = Evolution Programs, 3th Edition, Springer, 1995. 13. Pinedo, M. Stochastic Scheduling with Release Dates and Due Dates. Operations Research, Vol. 31, No. 3 (May - Jun., 1983), pp. 559-572 14. Prekopa, A. Stochastic Programming. Kluwer Academic Publishers, Norwell, MA 1995. 15. Somnuk, N. Optimal Time Transfer in Bus Transit Route Design Using A Genetic Algorithm, M.S. Thesis, Department of Civil Engineering, University of Maryland, College Park, MD, USA, 2000. 16. Ting, C. J., Schonfeld, P. Schedule Coordination in a Multiple Hub Transit Network, Journal of Urban Planning and Development, Vol. 131 2005, pp. 112- 124. ? 61? ? 17. Teodorovi?, D. Simultaneous Determining Departure Time and Flight Frequency on a route. Airline Operations Research, Gordon and Breach Science, New York, 1988, 131-145. 18. Wolsey, L., Integer Programming. John Wiley & Sons, New York, NY, 1998