Academic literature on the topic 'Timetable routing'

Periodic timetabling is an important, yet computationally challenging, problem in public transportation planning. The usual objective when designing a timetable is to minimize passenger travel time. However, in most approaches, it is ignored that the routes of the passengers depend on the timetable, so handling their routing separately leads to timetables that are suboptimal for the passengers. This has recently been recognized, but integrating the passenger routing in the optimization is computationally even harder than solving the classic periodic timetabling problem. In our paper, we develop an exact preprocessing method for reducing the problem size and a heuristic reduction approach in which only a subset of the passengers is considered. It provides upper and lower bounds on the objective value, such that it can be adjusted with respect to quality and computation time. Together, we receive an approach that is applicable for real-world problems. We experimentally evaluate the performance of the approach on a benchmark example and on three close-to-real-world instances. Furthermore, we prove that the ratio between the classic problem without routing and the problem with integrated routing is bounded under weak and realistic assumptions.

<p><strong>Abstract.</strong> Most of the existing public transit routing algorithms were developed on the basis of graph theory. Recently, algorithms are being developed that can compute for O-D public transit paths by using timetable information only, not using network structure consisting of nodes and links. The timetable-based public transit routing algorithm produces one shortest path to destination, using departure time and arrival time by stop. But it has limitations in reflecting additional factors, such as transfer penalty and alternative path selection, in the process of path calculation. In addition, since public transit passengers tend to choose one among various alternative paths, it is necessary to calculate multiple paths rather than a single path as in the existing methods. Therefore, this study proposes an improved RAPTOR algorithm that can consider transfer penalty and produce multiple paths, while it is based on RAPTOR, the existing timetable-based public transit routing algorithm. The transfer penalty was applied at the point of transfer, and differently according to transfer types. As a result of analyzing computed paths of the algorithms before and after improvement, it was found that computed paths with the improved RAPTOR algorithm proposed by this study were more similar to Seoul public transit passengers' actual travel paths than computed paths by the existing RAPTOR alone.</p>

As an important means of transportation, urban rail transit provides effective mobility, sufficient punctuality, strong security, and environment-friendliness in large cities. However, this transportation mode cannot offer a 24-h service to passengers with the consideration of operation cost and the necessity of maintenance, that is, a final time should be set. Therefore, operators need to design a last train timetable in consideration of the number of successful travel passengers and the total passenger transfer waiting time. This paper proposes a bi-level last train timetable optimization model. Its upper level model aims to maximize the number of passengers who travel by the last train service successful and minimize their transfer waiting time, and its lower level model aims to determine passenger route choice considering the detour routing strategy based on the last train timetable. A genetic algorithm is proposed to solve the upper level model, and the lower level model is solved by a semi-assignment algorithm. The implementation of the proposed model in the Beijing urban rail transit network proves that the model can optimize not only the number of successful transfer directions and successful travel passengers but also the passenger transfer waiting time of successful transfer directions. The optimization results can provide operators detailed information about the stations inaccessible to passengers from all origin stations and uncommon path guides for passengers of all origin–destination pairs. These types of information facilitate the operation of real-world urban rail transit systems.

In recent years, the government of China has paid increasing attention to environmental protection issues and has frequently emphasized the importance of ecological civilization. The high-speed railway transportation mode has outstanding advantages in terms of land utilization, energy conservation and environmental protection. China’s high-speed railway networking features are increasingly prominent and are constructed based on the rapid passenger transport network. Additionally, they save resources and are environmentally friendly while meeting safety, punctuality and profitability standards. Electric multiple unit (EMU) routing plan optimization is an important issue for improving operational EMU efficiency and reducing operational costs. At present, the Chinese EMU routing plans for holidays and weekdays are prepared separately because the holiday train timetable requires more EMUs and maintenance tasks. Different integrative optimization measures are considered, and a model is constructed to integrate an optimized weekday and holiday EMU routing plan problem and minimize the EMUs used and EMU maintenance tasks. The proposed model is based on the branch-and-price algorithm, and a real-world case study is conducted. The real-world numerical experiment shows that the amount of EMU maintenance can be reduced to some extent through the integrated optimization of tasks, but it is difficult to reduce the number of EMUs due to the structure of the train operational timetable.

碩士
國立中央大學
土木工程研究所
90
The setting of a good flight schedule for an airline not only has to consider its fleet and related supply, but also has to take into account of passenger reactions on its service. Although little research of medium/long-term flight scheduling in the past has ever dealt with variable passenger demands considering market competitions, almost all past short-term flight scheduling models assumed passenger demands as fixed and used a draft timetable as input to produce the final timetable and schedule, neglecting passenger choice behaviors among different airlines in practice. As a result, the schedule and fleet route offered may not reflect the real demands, decreasing the system performance. Considering both fleet supply and market demands, in this research, we developed a short-term flight scheduling model with variable demands, in order to help an airline solve optimal fleet routes and timetables. We employed network flow techniques to construct the model which includes multiple passengers and fleet flow network. In the passenger flow networks, we introduced a passenger choice model to formulate passenger flows. Considering the loss of waiting passengers in practice, we used generalized networks to formulate passenger flows in terms of time and space. In the fleet flow network, we used integer flow networks to formulate the aircraft routes in terms of time and space. Some side constraints were sat between the passenger and fleet flow network according to the real operating requirements. The model is expected to be a useful planning tool for airlines to determine their short-term fleet routes and timetables. We used mathematical programming techniques to formulate the model as a nonlinear mixed integer program that is characterized as a NP-hard problem and is more difficult to solve than traditional flight scheduling problems that are often formulated as integer linear programs. To efficiently solve the model with practical size problems, we developed an iterative solution framework, in which we repeatedly modify the target airline market share in each iteration and solve a fixed-demand flight scheduling problem with the assistance of the mathematical programming solver, CPLEX. To evaluate the model and the solution framework, we performed a case study using real operating data of domestic passenger transportation from a major Taiwan airline.

碩士
長榮大學
經營管理研究所
94
Recently, high technology industry bloom rapidly in Taiwan, and its’ products are the main exported commodities. Air freight is the most common way for factory owners transporting materials, products, and components to all over the world in short time that result in the demand in air freight increasing. Besides, the price of oil has soared which occupies about 20%~30% operating costs to an airline, therefore, the result of air freighters fleet routing will affect carriers’ profitability in the market. In the past most research on airline scheduling was mainly focused on passenger transportation. In addition, we distribute goods on average among one week and fine tuning the timetable which makes use of the concept of time window. The methodology of this paper is operation research and using OPL Studio software, which uses the CPLEX-MIP Solver as resolving tool. Therefore, given the operating data, including fleet size, airport flight quota and available time slots, related flight cost, on the basis of the airlines’ perspective, this research tries to develop suitable routes and flight schedules, with the objective of minimizing the flight cost, subject to the related operating constraints. Finally, to evaluate the model, we perform we perform a case study using real cargo operating data from a major Taiwan airline.

博士
國立中央大學
土木工程研究所
88
Fleet routing and flight scheduling are important in airline operations. In particular, they always affect the usage efficiency of facilities, the establishment of timetables and the crew scheduling. As a result, they are essential to carriers’ profitability, level of service and competitive capability in the market. Most of the airlines in Taiwan currently adopt a trial-and-error process for fleet routing and flight scheduling practices. They iterate the schedule construction and evaluation phases through manual operations. Such an approach is considerd to be less efficient when the flight network become larger, and can possibly result in an inferior feasible solution. Recently, there are research developing mathematic models and solution algorithms to solve the problem through the use of an indispensible medium called “draft timetable.” These mathematic approaches were anticipated to be comparatively more systematic and efficient than the traditional trial-and-error method. Nevertheless, not only “draft timetable” itself involves too much subjective judgement and decision in its constructing process, but also such approaches are incapable of directly and systematically managing the interrelationship between supply and demand. This research therefore developed an integrated model and a solution algorithm to help carriers simultaneously solve for better fleet routes and proper timetables. In order to directly manage the interrelationships between trip demand and flight supply, a time-space network technique was applied to modeling the movements of aircraft and passenger flows. Mathematically, the model was formulated as a special integer multiple commodity network flow problem which was categorized as an NP-hard problem. A Lagrangian relaxation-based algorithm was developed to efficiently solve the problem on the basis of Lagrangian relaxation, the sub-gradient method, the network simplex method, the least cost flow augmenting algorithm and the flow decomposition algorithm. To show how well the model and the solution algorithm could be applied in the real world, a case study regarding the domestic operations of a major Taiwan airline was performed by using the C computer language. The admirable outcome has shown the model’s good performance. Presumably, the results are practically helpful for airlines in Taiwan to improve their operations.

碩士
國立中央大學
土木工程研究所
91
Cargo Fleet routing and flight scheduling are essential to airline cargo operations. In particular, they always affect the usage efficiency of facilities, the establishment of timetables and the crew scheduling. As a result, they are essential to carriers’ profitability, level of service and competitive capability in the market. However, most of the airlines in Taiwan currently adopt a trial-and-error process for cargo fleet routing and flight scheduling practices. Such an approach is considered to be less efficient when the flight network become larger, and can possibly result in an inferior feasible solution. In the past most research on airline scheduling was mainly focused on passenger transportation, which is fundamentally different from air cargo transportation. In particular, airport selecting in service network design is typically in the stage of long-term plan in passenger transportation, but in cargo transportation, due to possibly significant demand changes in short-term operations, carriers may perform their airport selecting, fleet routing and timetable setting together in the stage of short-term plan, according to considerations of demand and profit. Moreover, passengers are more sensitive to time than cargos. Too many transfers in a transport service may result in significant loss of passengers, but not much loss of cargos. Besides, cargos with the same OD may be sensitive to different times, which can be incorporated into fleet routing systematically in order to find the most effective transport plan. In this research, given the operating data, including fleet size, airport flight quota and available time slots, cargo handling cost at airports and flight cost, on the basis of the carrier’s perspective, we develop an integrated scheduling model by combining airport selecting, fleet routing and timetable setting, with the objective of maximizing the operating profit, subject to the related operating constraints. The model is a useful planning tool for cargo airlines to determine suitable service airports, fleet routes and timetables in their short-term operations. We employ network flow techniques to construct the model, which include multiple cargo- and fleet-flow networks in order to formulate the flows of cargos and fleet in the dimensions of time and space. In the cargo-flow networks, different from that in the past research, we construct multiple OD-time-pair time-space networks on the base of cargos’ timeliness. In the fleet-flow networks, we use an integer flow network to formulate the periodical fleet routes. Some side constraints set between the cargo- and fleet-flow networks according to the real operating requirements. The model formulated as a mixed integer program that is characterized as an NP-hard problem. We employ a mathematical programming solver and develop a heuristic to solve the problem. Finally, to evaluate the model and the solution algorithm, we perform a case study using real cargo operating data from a major Taiwan airline.

碩士
長榮大學
航運管理研究所
95
In recent years the oil price unceasing rise, it has soared which occupies about 50%~60% operating costs to an airline, therefore, the result of air freighters fleet routing will affect carriers’ profitability in the market. Therefore, given the operating data, including fleet size, airport flight quota and available time slots, related flight cost, on the basis of the carrier’s perspective, this research tries to develop a scheduling model by integrating, cargo and freight flight schedules, with the objective of minimizing the operating profit, subject to the related operating constraints. The model is a useful planning tool for cargo airlines to determine suitable service airports, fleet routes and timetables in their short-term operations. We employ network flow techniques to construct the model, which include multiple cargo- and fleet-flow networks in order to formulate the flows of cargos and fleet in the dimensions of time and space. In the cargo-flow networks, different from that in the past research, we construct multiple OD-time-pair time-space networks on the base of cargos’ timeliness. In the fleet-flow networks, we use an integer flow network to formulate the periodical fleet routes. The model is formulated as an integer multiple commodity network flow problem that is characterized as an NP-hard problem. Since the real problem size is huge, this model is harder to solve than the conventional passenger flight scheduling problems in the past. Therefore, this research composes by the C++ language, develops the algorithm solution with the heuristic solution – genetic algorithm. Finally, to evaluate the model, we perform we perform a case study using real cargo operating data from a major Taiwan airline.

碩士
國立中央大學
土木工程研究所
92
Fleet routing and flight scheduling are important in airline operations. They always affect the usage efficiency of facilities and crew scheduling. Furthermore, they are essential to carriers’ profitability, level of service and competitive capability in the market. Recently, besides passenger flights and cargo flights, some airlines introduced combi flights in their flight scheduling. The combi flights combine passengers and cargos in one flight and can supple passenger flights and cargo flights during a carrier’s regular operation. However, the carriers in Taiwan currently adopt a try-and-error method to determine the schedules of passenger flights, cargo flight and combi flights. The method starts by manually determining the passenger and combi flight schedules together. Based on the passenger and combi flight schedules and the projected cargo demand, the cargo flight schedule is then determined. Thereafter, the combi flight schedule is modified by considering the cargo flight schedule and the passenger flight schedule is revised in accordance with the combi flight schedule. The process is repeated until the final fleet routing and timetables are obtained. Since such a method without systemic analyses cannot effectively manage the interrelationship among the passenger, cargo and combi flight schedules, the performance of the obtained schedules would easily decrease as the system scale is enlarged. As a result, the operating performance could possibly be inferior. Therefore, given the operating data, including fleet size, airport flight quota and available time slots, related flight cost, on the basis of the carrier’s perspective, this research tries to develop a scheduling model by integrating passenger, cargo and combi flight schedules, with the objective of maximizing the operating profit, subject to the related operating constraints. The model is a useful planning tool for airlines to determine a suitable fleet routing and timetables in their short-term operations. We employ network flow techniques to construct the model, which include passenger-flow, cargo-flow and fleet-flow networks in order to formulate the flows of passengers, cargos and fleet in the dimensions of time and space. The model is formulated as an integer multiple commodity network flow problem that is characterized as an NP-hard problem. Since the real problem size is huge, this model is harder to solve than the conventional passenger flight scheduling problems in the past. A Lagrangian relaxation-based algorithm, coupled with a subgradient method, the network simplex method and a heuristic for upper bound solution, is suggested to solve the problem. Finally, to evaluate the model and the solution algorithm, we perform a case study by using the real operating data from a major Taiwan airline.

Public transit systems are an indispensable part of any metropolitan city. Its success depends on many factors, chief among which is the ease with which users can query for optimal journeys using mobile apps. Conventional approaches model the transit network as a time-expanded or time-dependent graph and run a variant of the Dijkstra's algorithm. However, this method turns out to be too slow for large networks. Furthermore, while planning a journey using public transit, besides travel time, the number of transfers is equally important. To address these problems, several multi-criteria journey planning algorithms such as Round-based Public Transit Routing (RAPTOR), Transfer Patterns, and Trip-based Public Transit Routing (TBTR) have been designed in the past decade. The thesis proposes several modifications to the TBTR algorithm in order to achieve faster queries. Specifically, building on the premise of the range TBTR (rTBTR) problem which finds the optimal journeys departing within a certain time window, we introduce a new One-To-Many rTBTR. Empirical results show that, for one-to-many range queries, our implementation reduces the query times by approximately 70--80\% compared with repeated application of rTBTR. It helps in scenarios where users query for the shortest paths between two geographical locations (instead of two stops) since a location can have multiple nearby stops. Although algorithms such as TBTR and RAPTOR are efficient, they can be speeded up using partitioning-based techniques. To this end, we propose HypTBTR to efficiently solve the bicriteria shortest paths by combining TBTR with a partitioning-based speed-up. We also explore how multi-level partitioning of hypergraphs derived from the transit networks can be used to reduce preprocessing times. The proposed upgrades make the TBTR algorithm practical for large-scale applications. The benefits of our approach are demonstrated using several country-level open datasets. For one-to-one shortest path queries, HypTBTR is 30--40% faster than the TBTR algorithm. Multi-level partitioning in NHypTBTR was found to reduce the preprocessing time by approximately 20--50% on our test networks. The thesis also analyzes the effect of different hypergraph partitioning algorithms such as hMETIS and KaHyPar along with the effect of different weighting schemes on the algorithm's performance. Lastly, the thesis presents an empirical case study demonstrating another real-world application of journey planning algorithms. We study the problem of unreliability in the transit systems, which is one of the main contributing factors behind the decline in transit ridership. We empirically quantify unreliability by evaluating the difference between the scheduled timetables and the actual operations using the Intelligent Transportation System (ITS) data from Bangalore Metropolitan Transport Corporation (BMTC). Our findings can help transit operators create realistic schedules that are easy to adhere to. We also explore how differences in scheduled and actual trips translate to changes in travel time at a source-destination level. Since transit itineraries often involve transfers, departures from schedules can lead to missed connections and longer out-of-vehicle travel times. Using RAPTOR, we queried over a million bi-criteria shortest paths on one day of ITS data. The results show that an average travel time difference of about 17% at the trip level can result in approximately 50% longer journeys for popular source destinations.

The objectives of this project were to develop nondestructive methods for detection of internal properties and firmness of fruits and vegetables. One method was based on a soft piezoelectric film transducer developed in the Technion, for analysis of fruit response to low-energy excitation. The second method was a dot-matrix piezoelectric transducer of North Carolina State University, developed for contact-pressure analysis of fruit during impact. Two research teams, one in Israel and the other in North Carolina, coordinated their research effort according to the specific objectives of the project, to develop and apply the two complementary methods for quality control of agricultural commodities. In Israel: An improved firmness testing system was developed and tested with tropical fruits. The new system included an instrumented fruit-bed of three flexible piezoelectric sensors and miniature electromagnetic hammers, which served as fruit support and low-energy excitation device, respectively. Resonant frequencies were detected for determination of firmness index. Two new acoustic parameters were developed for evaluation of fruit firmness and maturity: a dumping-ratio and a centeroid of the frequency response. Experiments were performed with avocado and mango fruits. The internal damping ratio, which may indicate fruit ripeness, increased monotonically with time, while resonant frequencies and firmness indices decreased with time. Fruit samples were tested daily by destructive penetration test. A fairy high correlation was found in tropical fruits between the penetration force and the new acoustic parameters; a lower correlation was found between this parameter and the conventional firmness index. Improved table-top firmness testing units, Firmalon, with data-logging system and on-line data analysis capacity have been built. The new device was used for the full-scale experiments in the next two years, ahead of the original program and BARD timetable. Close cooperation was initiated with local industry for development of both off-line and on-line sorting and quality control of more agricultural commodities. Firmalon units were produced and operated in major packaging houses in Israel, Belgium and Washington State, on mango and avocado, apples, pears, tomatoes, melons and some other fruits, to gain field experience with the new method. The accumulated experimental data from all these activities is still analyzed, to improve firmness sorting criteria and shelf-life predicting curves for the different fruits. The test program in commercial CA storage facilities in Washington State included seven apple varieties: Fuji, Braeburn, Gala, Granny Smith, Jonagold, Red Delicious, Golden Delicious, and D'Anjou pear variety. FI master-curves could be developed for the Braeburn, Gala, Granny Smith and Jonagold apples. These fruits showed a steady ripening process during the test period. Yet, more work should be conducted to reduce scattering of the data and to determine the confidence limits of the method. Nearly constant FI in Red Delicious and the fluctuations of FI in the Fuji apples should be re-examined. Three sets of experiment were performed with Flandria tomatoes. Despite the complex structure of the tomatoes, the acoustic method could be used for firmness evaluation and to follow the ripening evolution with time. Close agreement was achieved between the auction expert evaluation and that of the nondestructive acoustic test, where firmness index of 4.0 and more indicated grade-A tomatoes. More work is performed to refine the sorting algorithm and to develop a general ripening scale for automatic grading of tomatoes for the fresh fruit market. Galia melons were tested in Israel, in simulated export conditions. It was concluded that the Firmalon is capable of detecting the ripening of melons nondestructively, and sorted out the defective fruits from the export shipment. The cooperation with local industry resulted in development of automatic on-line prototype of the acoustic sensor, that may be incorporated with the export quality control system for melons. More interesting is the development of the remote firmness sensing method for sealed CA cool-rooms, where most of the full-year fruit yield in stored for off-season consumption. Hundreds of ripening monitor systems have been installed in major fruit storage facilities, and being evaluated now by the consumers. If successful, the new method may cause a major change in long-term fruit storage technology. More uses of the acoustic test method have been considered, for monitoring fruit maturity and harvest time, testing fruit samples or each individual fruit when entering the storage facilities, packaging house and auction, and in the supermarket. This approach may result in a full line of equipment for nondestructive quality control of fruits and vegetables, from the orchard or the greenhouse, through the entire sorting, grading and storage process, up to the consumer table. The developed technology offers a tool to determine the maturity of the fruits nondestructively by monitoring their acoustic response to mechanical impulse on the tree. A special device was built and preliminary tested in mango fruit. More development is needed to develop a portable, hand operated sensing method for this purpose. In North Carolina: Analysis method based on an Auto-Regressive (AR) model was developed for detecting the first resonance of fruit from their response to mechanical impulse. The algorithm included a routine that detects the first resonant frequency from as many sensors as possible. Experiments on Red Delicious apples were performed and their firmness was determined. The AR method allowed the detection of the first resonance. The method could be fast enough to be utilized in a real time sorting machine. Yet, further study is needed to look for improvement of the search algorithm of the methods. An impact contact-pressure measurement system and Neural Network (NN) identification method were developed to investigate the relationships between surface pressure distributions on selected fruits and their respective internal textural qualities. A piezoelectric dot-matrix pressure transducer was developed for the purpose of acquiring time-sampled pressure profiles during impact. The acquired data was transferred into a personal computer and accurate visualization of animated data were presented. Preliminary test with 10 apples has been performed. Measurement were made by the contact-pressure transducer in two different positions. Complementary measurements were made on the same apples by using the Firmalon and Magness Taylor (MT) testers. Three-layer neural network was designed. 2/3 of the contact-pressure data were used as training input data and corresponding MT data as training target data. The remaining data were used as NN checking data. Six samples randomly chosen from the ten measured samples and their corresponding Firmalon values were used as the NN training and target data, respectively. The remaining four samples' data were input to the NN. The NN results consistent with the Firmness Tester values. So, if more training data would be obtained, the output should be more accurate. In addition, the Firmness Tester values do not consistent with MT firmness tester values. The NN method developed in this study appears to be a useful tool to emulate the MT Firmness test results without destroying the apple samples. To get more accurate estimation of MT firmness a much larger training data set is required. When the larger sensitive area of the pressure sensor being developed in this project becomes available, the entire contact 'shape' will provide additional information and the neural network results would be more accurate. It has been shown that the impact information can be utilized in the determination of internal quality factors of fruit. Until now,