| With sustained and rapid development of economy, Chinese people have increasingly demands on service-oriented industry. These needs have challenged industry to improve their service for holding a solid market share in the fierce competition.Since the 21st century, flight tickets sales companies (short for FTSC) have emerged because of rapid growth of Civil Aviation of China. FTSC is a kind of service-oriented companies. They earn their profit mainly through selling flight tickets. However, due to the intense competition, these companies have to implement more service items to attract customers. Recently, most FTSCs begin to provide a new service item called"Pickup and Delivery Service to Airport" (short for PDSA) for the customers ordering tickets. On one hand, this service brings customers a more convenient and lower-cost trip. On the other hand, it attracts more and more potential customers for FTSCs. Meanwhile, it also leads to an unpleasant outcome-higher operations cost. Obviously, this service can not earn profit for FTSCs directly. So low operations cost has become the key factor that decides whether the implementation of PDSA can succeed or not.This research was financially supported by National Science Fund for Distinguished Young Scholars(70625001), Innovative Research Groups(70721001), National Basic Research Program of China (2009CB320601) and PhD program of MOE (20060145009). PDSA is described as the Vehicle Allocation and Scheduling Problem (short for VASP) in this paper. From the modeling perspective, PDSA can be viewed as Vehicle Routing and Scheduling Problem (short for VRSP). VRSP is a typical optimization problem in operations management field. By analyzing PDSA, this dissertation studies several crucial problems of VASP based on minimizing cost. The major research results of this dissertation fall on five aspects as follows:1) According to the characteristics of PDSA, the customers’satisfaction is quantified by the time of arriving at airport, and the transportation cost depends on the fixed start-up costs and variable traveling costs. Given one satisfication, the VASP is formulated as a Set-Partition Problem (short for SPP) with minimizing cost. Then, an exact algorithm and a heuristic based on Set-Partition are developed for small instances and large instances, respectively. At last, several experiments are conducted to show the effectiveness of the proposed model and algorithms.2) The VASP with maximum ride time for each customer is studied. Considering the same type of customer’s satisfaction, a vehicle flow model with minimizing cost is formulated. The customers’satisfaction and maximum ride time are considered simultaneously as constraints. Then, a sequential Cheapest Insertion (CI) heuristic based on a new appraisal-factor was developed to solve this model. Compared with CW saving algorithm, computational results show the effectiveness of the proposed model and algorithm. At last, the vehicle scheduling problem for a fixed route is studied to improve customer’s satisfaction.3) According to rapid growth of Civil Aviation of China, FTSC will add vehicles with large capacities in the future. A Fleet Size and Mix VASP (short for FSMVASP) with small cars and large buses is studied. A cost minimizing model is given with customers’satisfaction. For diversity, customers’satisfaction is qualified by the time of departing from each customer node. Then, an adaptive neighborhood search with reinsertion-remove heuristics is developed, which includes three insertion heuristics, three remove herisrics, and a multi-start Deterministic Annealing structure. Computational results show that the proposed algorithm produces high quality results within a reasonable computing time. The variable cost is analyzed at last. With these results, FTSC can easily make a sound decision on vehicle types when buying new vehicles.4) According to the short tours of PDSA in the urban areas, the Multi-trips VASP (short for MVASP) where per vehicle or driver performs more than one route in the given period is studied. A cost minimizing model with maximum driver shift time, customers’satisfaction of arriving airport and maximum ride time for per customer is given in a Dial-a-ride Problem (short for DARP) formulation. Then, a heuristic combining saving and insertion is developed to solve this model. It focuses on comparing and analyzing cost when adopting different transportation modes for the same problem:compared with VASP, computational results show the effectiveness of MVASP in saving cost and time; compared with DARP, computational results show how to guide FTSC to select transportation modes.5) Under the complex and multiple scheduling constraints, it is hard to determine the feasibility of a given route. The feasibility testing algorithm of a given route is studied. The main results include three aspects as follow:a) The feasibility problem of DARP with the maximum waiting time and maximum ride time constraints is studied. The flaw of the three-pass feasibility testing algorithm proposed by HunsakerB and Savelsbergh M[1] in checking ride time limits is point out, and a revised procedure with O(n∧2) time is developed.b) The feasibility problems of VASP with customer’s satisfaction of arriving at airport and arriving at per customer node for a given route are studied respectively. Two O(n) time algorithms are developed.c) The feasibility problem of MVASP of a fixed route is studied and one O(n) time algorithm is developed. |
PDF Full Text Request