An Exact Algorithm For Multi-Trip Vehicle Routing And Scheduling Problem Of Pickup And Delivery Of Customers To The Airport Service

Recently, service industry becomes more and more important. In order to increase income and more market-share in a long-term, Pickup and Delivery of Customers to the Airport (PDCA) was provided in Many Flight Ticket Sales Agencies (FTSAs) in China. However, the service may bring about some additional operations costs in transportation and vehicle-rent. Thus, the effort on seeking for a method to diminish operation costs and enhance service quality has never stopped. So far, all researches on PDCA focused on the single-trip mode. Comparing with the single-trip mode, the Multi-trip Mode PDCA (MTM-PDCA) can reduce distance and vehicles.To help the decision makers reduce the cost by making a scientific schedule, MTM-PDCA was proposed. The research of MTM-PDCA is more significant in theory and practice. The major work of this paper includes two parts.(1) MTM-PDCA was considered for the first time. A mathematical insight into the advantage of multi-trip mode was addressed. A novel trip oriented set-partitioning (TO-SP) model was built. An exact algorithm based on TO-SP model trips was proposed. In addition, the proof of exactness was given. To help decision-maker of PDCA evaluate which situations multi-trip should be used to replace the single-trip, many simulated instances with the different values of the factors were tested, i.e., the fixed cost in the objective of MTM-PDCA, average number of customers in each customer point, time windows distribution of customer points and geographical location distribution of customer points. By investigating the experimental results, several managerial insights into when multi-trip should be operated to diminish the costs of PDCA were summarized.(2) Considering the factors of traffic safety and driver health, duration of vehicles was taken into consideration and DCMTM-PDCA was addressed. According to the characteristics of DCMTM-PDCA, a novel trip-chain oriented set-partitioning (TCO-SP) model was built. Several mathematical insights into the number and characteristic of trip chains were proposed. To obtain the exact solution of DCMTM-PDCA, a novel exact algorithm based on Improved Label Algorithm (ILA) and TCO-SP model was proposed. In addition, the proof of exactness was given. In the exact algorithm, ILA can rapidly remove unfeasible trip chains and to save computation time. Even though the instance scale was large, it also can be solved quickly. To investigate the number and characteristic of trip chains in MTM-PDCA, many experiments on different instances and constraints were made. To compare total operational costs of single-trip and multi-trip mode, some experiments were made under different instances and satisfaction degree. To find out the influence on operational cost of overtime cost and maximum of vehicle duration, experiments on different values of overtime cost and maximum vehicle duration were made.In this paper, MTM-PDCA was proposed for the first time. The novel model and exact algorithm were proposed. In reality, the support of MTM-PDCA was provided for FTSA. The operation cost was reduced without reducing customer satisfaction. The market competitiveness of FTSA was improved.