On-demand air transportation is a recent trend in the airline industry. It allows the customer to call in days or even hours before to book a ight. Therefore, the scheduling and planning of this type of airline needs to be done daily. Hence, a successful on-demand air transportation requires an e cient ight scheduling system to construct the optimal daily ight schedules. An on-demand air transportation ight scheduling problem that arose in a Southern African industry has been studied. A new solution methodology is proposed. A number of new heuristics are used to combine ight legs for a robust solution. A time-space multi-commodity network is introduced to derive the mathematical model which is then solved using CPLEX. The results obtained are then compared with known results showing much more e cient performances and saving for the industry.

Typescript Includes bibliographical references

No description available.

No description available.

No description available.

No description available.

Kwan, Cheuk Lam. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (p. 115-118). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.9 / Chapter 1.1 --- The Gate Assignment Problem --- p.9 / Chapter 1.2 --- Contributions --- p.10 / Chapter 1.3 --- Formulation of Gate Assignment Problem --- p.11 / Chapter 1.4 --- Organization of Thesis --- p.13 / Chapter 2 --- Literature Review --- p.15 / Chapter 2.1 --- Introduction --- p.15 / Chapter 2.2 --- Formulations of Gate Assignment Problems --- p.15 / Chapter 2.2.1 --- Static Gate Assignment Model --- p.16 / Chapter 2.2.1.1 --- Total Passenger Walking Distance --- p.17 / Chapter 2.2.1.2 --- Waiting Time --- p.20 / Chapter 2.2.1.3 --- Unassigned Flights --- p.21 / Chapter 2.2.2 --- Stochastic and Robust Gate Assignment Model --- p.22 / Chapter 2.2.2.1 --- Idle Time --- p.22 / Chapter 2.2.2.2 --- Buffer Time --- p.23 / Chapter 2.2.2.3 --- Flight Delays --- p.23 / Chapter 2.2.2.4 --- Gate Conflicts --- p.24 / Chapter 2.3 --- Solution Methodologies --- p.25 / Chapter 2.3.1 --- Expert System Approaches --- p.25 / Chapter 2.3.2 --- Optimization --- p.27 / Chapter 2.3.2.1 --- Exact Methods --- p.27 / Chapter 2.3.2.2 --- Heuristic Approaches --- p.28 / Chapter 2.3.2.3 --- Meta-Heuristics Approaches --- p.29 / Chapter 2.3.2.4 --- Tabu Search and Path Relinking --- p.31 / Chapter 2.4 --- Current Practice of Gate Assignment Problems --- p.32 / Chapter 2.5 --- Summary --- p.32 / Chapter 3 --- Tabu Search --- p.34 / Chapter 3.1 --- Introduction --- p.34 / Chapter 3.2 --- Mathematical Model --- p.34 / Chapter 3.3 --- Principles of Tabu Search --- p.36 / Chapter 3.4 --- Neighborhood Structures --- p.38 / Chapter 3.4.1 --- Insert Move --- p.38 / Chapter 3.4.2 --- Exchange Move --- p.39 / Chapter 3.5 --- Short Term Memory Structure --- p.41 / Chapter 3.6 --- Aspiration Criterion --- p.42 / Chapter 3.7 --- Intensification and Diversification Strategies --- p.43 / Chapter 3.8 --- Tabu Search Framework --- p.45 / Chapter 3.8.1 --- Initial Solution --- p.45 / Chapter 3.8.2 --- Tabu Search Algorithm --- p.46 / Chapter 3.9 --- Computational Studies --- p.52 / Chapter 3.9.1 --- Parameters Tuning --- p.52 / Chapter 3.9.1.1 --- Fine-tuning a Tabu Search Algorithm with Statistical Tests --- p.53 / Chapter 3.9.1.2 --- Tabu Tenure --- p.54 / Chapter 3.9.1.3 --- Move Selection Strategies --- p.56 / Chapter 3.9.1.4 --- Frequency of Exchange Moves --- p.59 / Chapter 3.9.2 --- Comparison the Fine-tuned TS with original TS --- p.62 / Chapter 3.10 --- Conclusions --- p.63 / Chapter 4 --- Path Relinking --- p.65 / Chapter 4.1 --- Introduction --- p.65 / Chapter 4.2 --- Principles of Path Relinking --- p.65 / Chapter 4.2.1 --- Example of Path Relinking --- p.66 / Chapter 4.3 --- Reference Set --- p.68 / Chapter 4.3.1 --- Two-Reference-Set Implementation --- p.71 / Chapter 4.3.1.1 --- Random Exchange Gate Move --- p.72 / Chapter 4.4 --- Initial and Guiding Solution --- p.73 / Chapter 4.5 --- Path-Building Process --- p.74 / Chapter 4.6 --- Tabu Search Framework with Path Relinking --- p.78 / Chapter 4.6.1 --- Computational Complexities --- p.82 / Chapter 4.7 --- Computational Studies --- p.82 / Chapter 4.7.1 --- Best Configuration for Path Relinking --- p.83 / Chapter 4.7.1.1 --- Reference Set Strategies and Initial and Guiding Criteria --- p.83 / Chapter 4.7.1.2 --- Frequency of Path Relinking --- p.86 / Chapter 4.7.1.3 --- Size of Volatile Reference Set --- p.87 / Chapter 4.7.1.4 --- Size of Non-volatile Reference Set --- p.89 / Chapter 4.7.2 --- Comparisons with Other Algorithms --- p.94 / Chapter 5 --- Case Study --- p.98 / Chapter 5.1 --- Introduction --- p.98 / Chapter 5.2 --- Airport Background --- p.98 / Chapter 5.2.1 --- Layout of ICN --- p.98 / Chapter 5.3 --- Data Preparation --- p.99 / Chapter 5.3.1 --- Passenger Data --- p.103 / Chapter 5.4 --- Computational Studies --- p.104 / Chapter 5.4.1 --- Experiments without Airline Preference --- p.104 / Chapter 5.4.2 --- Experiments with Airline Preference --- p.106 / Chapter 5.4.2.1 --- Formulation --- p.106 / Chapter 5.4.2.2 --- Results --- p.108 / Chapter 5.5 --- Conclusion --- p.111 / Chapter 6 --- Conclusion --- p.112 / Chapter 6.1 --- Summary of Achievement --- p.112 / Chapter 6.2 --- Future Developments --- p.113 / Bibliography --- p.115 / Appendix --- p.119 / Chapter 1. --- Friedman´ةs Test --- p.119 / Chapter 2. --- Wilcoxon's Signed Rank Test for Paired Observation --- p.120 / Chapter 3. --- Hybrid Simulated Annealing with Tabu Search Approach --- p.121 / Chapter 4. --- Arrival Flight Data of Incheon International Airport --- p.122 / Chapter 5. --- Departure Flight Data of Incheon International Airport --- p.139

This thesis examines the university timetable generation problem. It begins with a discussion on the conflicting terminology used and differentiates between the terms scheduling and timetabling. This discussion integrates with an overview of the problem itself both from practical and academic perspectives. This is followed by a summary of the apparently effective timetable solution generation algorithms. The literature is then examined in detail from that perspective. This literature review is then summarised in a form to highlight the use of these different solution algorithms. A classification schema is developed and the summary of the literature presented within the framework of this schema. Trends in the research literature result from this presentation and an extrapolation to future research trends are suggested. An information system based upon the need to support timetable production and maintenance is presented. Given the very practical outcomes expected of timetable research, the information system was designed to enable the whole range of administrative functions performed by teachers to be either directly supported or readily modified to prove such support. The implementation of this particular system is given and resulting timetables are presented and discussed. The system generated manual and automated timetables and these were produced by trailing a number of objective functions. It was noted that the determination of the optimal objective function is dominated by specific individual institutional criteria. It is suggested that this would make a more than significant project for future information systems research. From the literature it is noted that the timetable generation problem, as reported time and time again in the literature, has been solved. Such claims lead to a benchmark which is proposed to enable an initial comparison of the effectiveness of proposed solutions by different researchers. The thesis then presents a summary of the work that was carried out and offers direction for future research. It is noted that despite the fifty years of research conducted into this area there exists a significant number of research avenues still to be pursued.

Είναι πολύ συχνή η ανάγκη κατασκευής ωρολογίων προγραμμάτων για εκπαιδευτικούς οργανισμούς, για μέσα μαζικής μεταφοράς, για τεχνικές εταιρίες κ.α. Η κατασκευή ωρολογίων προγραμμάτων (timetabling) εντάσσεται στη γενικότερη κατηγορία προβλημάτων που είναι γνωστά ως προβλήματα χρονοδρομολόγησης (scheduling). Ένα πρόβλημα χρονοδρομολόγησης έχει γενικά σαν σκοπό να τοποθετήσει μέσα στο χρόνο ένα σύνολο από δραστηριότητες δεδομένου ενός συνόλου πόρων που αυτές οι δραστηριότητες χρειάζονται για να πραγματοποιηθούν. Ειδικά για τα σχολικά προγράμματα με τα οποία ασχολείται η παρούσα εργασία πολλές μέθοδοι και αλγόριθμοι έχουν εφαρμοστεί με στόχο την δημιουργία βέλτιστων προγραμμάτων. Παρόλα αυτά δυστυχώς η πράξη αποδεικνύεται να ανατρέπει πολλές από αυτές τις λύσεις. Έτσι η χρήση της μεθόδου των έμπειρων συστημάτων, που δεν φαίνεται να έχει χρησιμοποιηθεί ευρέως στο πρόβλημα αυτό, είναι μια υποψήφια μέθοδος για να μας δώσει πιο γενικά αποδεκτές λύσεις, που να συμβαδίζουν καλύτερα με την πραγματικότητα, αφού βασική τεχνική είναι η προσομοίωση ενός έμπειρου προγραμματιστή. Η παρούσα εργασία ασχολείται με την δημιουργία ενός έμπειρου συστήματος για την σχεδίαση εβδομαδιαίου προγράμματος μαθημάτων για το Ελληνικό Γυμνάσιο. Για την δημιουργία του έμπειρου συστήματος απευθυνθήκαμε σε ειδικούς σχεδίασης προγραμμάτων σε ελληνικά σχολεία (προγραμματιστές) οι οποίοι μας έδωσαν πλήρη περιγραφή των κανόνων και διαδικασιών που χρησιμοποιούν ώστε να εκδοθεί ωρολόγιο πρόγραμμα. Στη συνέχεια έγινε ανάλυση και εξαγωγή των στόχων και των περιορισμών του προβλήματος καθώς επίσης ορίστηκε και ο τρόπος καταχώρησης των δεδομένων. Στη συνέχεια έγινε σχεδιασμός εφαρμογής για εξαγωγή προγραμμάτων του Ελληνικού Γυμνασίου και επιλέχθηκαν οι τεχνολογίες που είναι πιο κατάλληλες για την υλοποίηση της εφαρμογής. Οι τεχνολογίες που εφαρμόσαμε ώστε να επιτευχθεί η υλοποίηση του πληροφοριακού συστήματος έκδοσης ωρολογίου προγράμματος για το Γυμνάσιο ήταν (α) το εργαλείο CLIPS (1) για την πραγμάτωση του έμπειρου συστήματος, (β) η χρήση PHP (3) και MYSQL (4) για την καταχώρηση των βασικών παραμέτρων του προγράμματος με χρήση του WEB, (γ) το εργαλείο PHLIPS (2) για την σύνδεση του CLIPS με PHP, με στόχο την εξαγωγή στο WEB των αποτελεσμάτων. Έτσι δημιουργήθηκε πληροφοριακό σύστημα όπου κάθε προγραμματιστής σχολείου μπορεί να καταχωρήσει τα στοιχεία του σχολείου, των καθηγητών, τις διαθέσιμες ώρες τους κ.α. με την ευκολία του περιβάλλοντος WEB για ένα η περισσότερα σχολεία που έχει αναλάβει. Η χρήση του WEB δίνει την ευκολία διαχείρισης του προγράμματος από οποιοδήποτε σημείο έχει πρόσβαση με το διαδίκτυο και ταυτόχρονα την χρήση γραφικού περιβάλλοντος για επίτευξη καλύτερης διαχείρισης των πληροφοριών του. Επίσης μπορεί ο χρήστης εύκολα με αλλαγή των παραμέτρων να λαμβάνει διαφορετικά αποτελέσματα και να αποφασίζει σύμφωνα με τις ανάγκες του ποια λύση θεωρεί πιο εφικτή με βάση την καθημερινή πρακτική. Η χρήση του CLIPS για επίτευξη έξυπνων έμπειρων συστημάτων και η σύνδεση μέσω του προτύπου ανάπτυξης συστημάτων PHLIPS δίνει μεγάλες δυνατότητες για τον συνδυασμό της τεχνικής νοημοσύνης με τις τεχνολογίες διαδικτύου. Η εφαρμογή δοκιμάστηκε σε αρκετά γνωστά σετ δεδομένων και πραγματικά δίνει αξιόπιστες και ανταγωνιστικές λύσεις με την καινοτομία όμως ότι είναι πιο αποδεκτές στην καθημερινή πρακτική από άλλες που δίνουν άλλες μέθοδοι τεχνικής νοημοσύνης που αναζητούν βέλτιστες λύσεις με βάση απλά ποσοτικοποιημένα κριτήρια όπως το σύνολο των κενών ορών, η καλύτερη επίτευξη των απαιτήσεων των καθηγητών κ.α. / There is a common need for the construction of timetables for educational organizations, public transportation, for construction companies, etc. The construction of timetables (timetabling problem) is part of a general category of problems known as scheduling problems. The task of a scheduling problem generally is to have a set of activities distributed through time given a set of resources which are needed in order to have these activities to be accomplished. This postgraduate thesis deals with a school timetabling problem. A variety of methods and algorithms have been implemented in order to create optimized timetables. Nevertheless, real life has shown that many of these solutions cannot be realistic. Thus the use of expert systems method, which seems not to have often used in such problems, is a good candidate to gives a more realistic and acceptable solutions, given that it tries to simulate the way an expert school timetabling maker works. This Thesis deals with the creation of an expert system that designs weekly timetables for the Greek High School. To create the expert system, we interviewed experts in designing school timetables in Greek schools, who gave us full description of the rules and procedures they use in order to construct a school timetable. Then we analyzed and extracted the objectives and constraints of the problem and we defined the method of storing the data. Then, we developed an application which produces timetables for the Greek High schools. We chose the appropriate technologies needed and were most suitable to construct the application. The technologies we have used to achieve the implementation of a computerized system for exporting timetables for the high school were, (a) the CLIPS programming tool for the creation of the expert system, (b) the PHP and MYSQL to record the key parameters of the program in a WEB environment, (c) the PHLIPS tool for the connection of CLIPS with PHP, to be able to export the results back into the WEB environment. Thus we created a computerized system where every school timetable maker can register the data concerning the school, the teachers, the available hours and dates etc. with the ease of the WEB environment for one or more schools. The potential of using the WEB environment provides the user with ease of managing the program from anywhere with access to the Internet, while using the graphical user interface for obtaining the best data management. We can easily change the parameters to obtain different results and act in accordance with our needs the most feasible solution based on daily practice. Using CLIPS to create an expert system, and the connection through the PHLIPS development standard gives great potential for the combination of artificial intelligence and internet technologies. The application was tested on several well-known data sets and really gives a reliable and competitive solutions but with the innovation, that is more acceptable in daily practice than other methods of artificial intelligence that seek optimal solutions based on simple but politicized criteria such as the total of empty hours ,to meet the requirements of teachers, etc.

Relevant path planning using public transport is limited by reliability of the transportation network. In some cases it turns out that we can plan paths with respect to expected delays and hereby improve the reliability of the resulting path. This study focuses on prediction of the delays in public transport systems using data from vehicle tracking systems -- known as the AVL data. These data are typically collected by the transit operators. Various algorithms are compared using real data from Prague trams tracking system. The study also includes a discussion about a possible utilization of the information gained from the used methods in passenger information systems. Powered by TCPDF (www.tcpdf.org)