Optimization Algorithms&Suitability Analyses Based On Constraints Of Time&District For Vehicle Scheduling In Pick-up And Delivery Service To Airport

In the past few years, many flight tickets sales companies carry out the service of free pick-up and delivery of customers to airport, with the vigorous development of service industry and the increasingly fierce competition of market. These companies usually rely on the experiences of their dispatchers to arrange the pick-up vehicles and utilization ratio of vehicles are not high enough. In the process of servicing customers, the service would make some customers dissatisfied for the reason of failing to service customers on time.Under such background, this paper studied the Vehicle Scheduling Problem for Air-passenger (VSAP). According to the different service time of customers, VSAP was classified into three types, such as VSAP considering time window of arrival airport, VSAP considering appointment time window of customer point and VSAP considering double time windows. The instances of the three VSAP were well designed and classified in this paper, which would provide public test instances for the comparative of algorithms. On the basis of designing of instances, VSAP considering appointment time window of customer point was mainly studied with the way of establishing mathematical model and then designing two heuristics algorithms and one exact algorithm to solve the VSAP.Firstly, for VSAP considering appointment time window of customer point, a sweep-heuristic algorithm combined with partition of time and district (SPTD) was proposed to solve the model of minimizing costs. Through the comparative with permutation-based cluster priority heuristic (PBCPH) and Sweep algorithms proposed before, it was indicated that SPTD was better than the algorithms before when solving instances larger than medium scale and had better effect on solving large-scale instances. Meanwhile, this algorithm had extensive applicability for kinds of instances with different distribution of district.Secondly, on account of the defects of SPTD and dissatisfaction of solving medium-scale instances with SPTD, two-way sweep algorithm of nearest-point priority (TSNP) was proposed. Through the comparative with SPTD algorithm, it was indicated that TSNP was better than SPTD algorithm when solving medium-scale and large-scale instances. In addition, through comparative with the results of solving minimizing-vehicle model with TSNP, it was found that TSNP was suitable for solving minimizing-vehicle model when the number of people had significant differences between customer points and had extensive applicability for kinds of instances with different distribution of district.Thirdly, exact algorithm based on set-partitioning model (EBSM) was proposed to compensate for the defect that could not ensure the optimal solution when solving small-scale instances using the first two algorithms. Through the comparative with the computational results, EBSM could exactly solve small-scale even some medium-scale instances. Within the acceptable computing time of it, it was true to solve all medium-scale and small-scale instances with EBSM.Finally, the algorithm module was designed and developed to integrate the instances designed and algorithms proposed, which would be helpful for the computational tests and subsequent research of algorithms.