Clustering Algorithms Based On Time Priority For Free Pickup And Delivery To Airport Service

The subject of this paper derives from the free pickup and delivery to airport service in a city. Flight tickets sales companies (short for FTSC) are a new kind of service companies. They earn their profit mainly through selling flight tickets. However, due to the intense competition, most FTSCs begin to provide a new value added service item called "Free Pickup and Delivery Customers to Airport Service"(short for FPDS) for the customers ordering tickets recently. 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. 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 FPDS can succeed or not.This research was financially supported by National Science Fund for Distinguished Young Scholars(No.70625001), Natural Science Foundation of China (N090204001) and National Natural Science Fund for Young Scholars (No.61004121). FPDS is described as the Vehicle Scheduling for Air-passenger (short for VSAP) in this paper. From the modeling perspective, FPDS can be viewed as Vehicle Routing Problem with Time Windows (short for VRPTW). VRPTW is a typical optimization and decision-making problem for the commercial and service enterprise in operations management field. First, this paper analyzes the operations of FPDS in details, and reviews the theoretical foundation and research status of FPDS briefly. Next, according to the characteristic of FPDS, the customers’satisfaction is quantified by the pickup time. A mathematical model of minimum number of vehicles is given with circumvention constrain of vehicles in vehicle-rental mode, and a reversed-order-based time windows first clustering algorithm is proposed. The effectiveness of the model and algorithm is verified through the simulation experiment and results analysis. In addition, in term of VIPs’demand, the customers’satisfaction is quantified by the pickup time and the time of arriving at airport. A cost minimizing model considering maximum driver waiting time, customers’satisfaction and circumvention constrain for vehicle-rental companies is given to solve a Double Time Windows Problem. A random-cluster-based three-stage heuristic combining vehicle optimization is developed to solve this model. Computational results show that the proposed heuristic produces high quality results within a reasonable computing time.Based on the theoretical research, the business processes and functional requirements of the scheduling administrator are analyzed and designed, including demand analysis, function design, database design and pages design. Finally, the software module based on C/S structure is designed and completed for the model.