The Research On Vehicle Routing Problem With Time Windows And Staff Resource Assignment

This dissertation extracts four vehicle routing problems with staff resource assignment which arise from real-life applications: team orienteering problem with time windows and multiple deliverymen(TOPTWMD),team orienteering problem with time windows and multiple deliverymen considering vehicle distance(TOPTWMDD),vehicle routing problem with time windows and manpower allocation(MAVRPTW)and vehicle routing problem with time windows and manpower allocation considering limited number of staffs(MAVRPLTW).In TOPTWMD,each vehicle can be equipped with multiple deliverymen,and the entire service process must be completed within the time window.The service time is not only related to the demand,but also associated with the number of deliverymen.The aim of TOPTWMD is to maximize the total profit obtained.TOPTWMDD takes the total distance traveled into consideration based on the TOPTWMD.The primary objective is to maximize the total profit obtained,and the second objective is to minimize the total distance traveled.The MAVRPTW arises from hospital providing non-emergency ambulance transportation service for elderly or disabled patients.Each patient makes requests in advance in terms of two aspects: one is seat reservation,and the other is staff demand.The transportation service must begin within the time window.The objective is to minimize the financial expenditure,which consists of outsourcing costs,manpower costs and total traveling costs.MAVRPLTW takes the limited number of staffs into account on the basis of the MAVRPTW,and its objective is to minimize the summation of the outsourcing costs and the total traveling costs.According to the characteristics of each problem,this dissertation establishes mathematical models and designs heuristic algorithms or exact algorithms.The main research contributions are as follows:(i)TOPTWMD: To solve this problem,this dissertation proposes a tabu search algorithm which allows searching the infeasible solution space.It first generates the initial solution by a randomized greedy construction method.Then it searches the solution space by seven neighborhood search operators and enlarges the search space by using a shaking operator.Compared with CPLEX,the tabu search algorithm is demonstrated to be effective and efficient.(ii)TOPTWMDD: To solve this problem,this dissertation adopts an iterative threecomponent heuristic which is characterized by a hybridization of the local search(LS)algorithm,the simulated annealing(SA)algorithm and the route recombination.This algorithm starts with a greedy algorithm to generate initial solutions.These solutions are firstly decomposed into a route library in unit of route,then neighborhood solutions are generated by LS and SA to update the global optimal solution and the route library.After that,the produced routes are recombined to construct a new solution.Computational results indicate the proposed algorithm is more effective than CPLEX and the tabu search algorithm.Moreover,this dissertation also designs an enhanced iterative three-component heuristic which uses an iterated local search method in feasible region and a tabu search method in infeasible region to replace the original LS and SA,respectively.Computational experiments show that the enhanced algorithm outperforms the original method.(iii)MAVRPTW: This dissertation proposes a branch-and-price-and-cut algorithm to obtain its optimal solution.The algorithm firstly decomposes the original problem into a Set-Packing model and a subproblem model according to the Dantzig-Wolfe decomposition.Then the algorithm employs the column generation method and the label setting algorithm to calculate between the main problems and the subproblems iteratively.Moreover,during this process subset-row cuts are generated to adjust the feasible region.Obtaining the optimal solution to the linear relaxation of the main problem,the algorithm finally adopts the branching strategies for the feasible solutions.Compared with CPLEX,the algorithm is proved to have good performances in stability and efficiency.By carrying out extensive computational experiments,this dissertation not only analyzes the influence of the number of patients and the number of vehicles on the results,but also finds that the cutting plane method is capable of improving efficiency of the algorithm.(iv)MAVRPLTW: A branch-and-price-and-cut algorithm is designed to solve this problem,and two accelerating strategies are added to the method.Compared with CPLEX,the proposed algorithm is demonstrated to be effective and efficient.Moreover,the influence of the number of vehicles and staffs to the performance of algorithm is also analyzed.