Exact Algorithms For Best Balance Model In Vehicle Scheduling Problem Of Free Pickup And Delivery Service To Airport

With the rapid development of economy, people’s living standard has been steadily improved and higher quality of service is expected. Flight tickets sales companies (short for FTSC) are a new kind of service companies. They earn their profit mainly through selling flight tickets. In order to meet the requirement of customers while dealing with increasingly fierce 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. Meanwhile, it also leads to an unpleasant outcome-higher operations cost. Obviously, this service can not earn profit for FTSCs directly. So how to improve customer satisfaction while reducing operating costs may be considered as decisive factors in the implementation of the business.FPDS is described as the Vehicle Allocation and Scheduling Problem (short for VASP) 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 problem in operations management field.Firstly, this paper analyzed the operations of FPDS in details, and reviewed the theoretical foundation and research status of FPDS. Next, according to the characteristic of FPDS, this paper analyzed the relationship between customer satisfaction and transportation costs in the service, and quantified the customer satisfaction and enterprise satisfaction through building the satisfaction functions. On this basis, the best balance model between vehicle number and customer satisfaction was proposed for the companies based on leasing vehicles. And then according to the characteristics of the problem, an exact algorithem based on set partition was exposed. The validity and effectiveness of this algorithm was demonstrated by testing different types of instances. Secondly, in order to overcome the limitations of EABSP, this paper proposed another exact algorithem which is based on labels and set partition (EABLSP) to solve the best balance problem. This algorithm can also be used to solve the model of minimizing costs and the model of maximizing customer satisfaction. This algorithm was proved to have great practical value after analyzing its validity and effectiveness through testing a lot of instances.At last, a best balance model was established for heterogeneous vehicle allocation and scheduling problem and an improved EABLSP was proposed to solve the problem. The practical significance of heterogeneous vehicle allocation and scheduling problem (HVASP) in the free pickup and delivery service was illustrated by camparing the results of homogeneous and heterogeneous vehicle scheduling. By computing and analyzing a lot of instances, it has been proved that the improved EABLSP can be used to solve the heterogeneous vehicle allocation and scheduling problem efficiently.