The Research on Vehicle Routing Problem with Time Windows and Staff Resource Assignment

帶時間窗和人力資源分配的車輛路徑的研究

Student thesis: Doctoral Thesis

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date16 Aug 2021

Abstract

The theme of this thesis is the vehicle routing problem with staff resource assignment. Based on the actual demand in real life, we study three variants, namely, team orienteering problem with time windows and multiple deliverymen (TOPTWMD), team orienteering problem with time windows and multiple deliverymen considering vehicle distance (TOPTWMDD), and manpower allocation and vehicle routing problem with limited staffs and time windows (MAVRPTW). In theTOPTWMD, each vehicle can be equipped with multiple deliverymen, and the entire service process must be completed within the predefined time window. The service time is not only dependent with the demand, but also related to the number of deliverymen. The aim of the TOPTWMD is to maximize the total profit obtained. Extended from the TOPTWMD, the TOPTWMDD takes the total distance traveled by vehicles into consideration, with the primary objective of maximizing the total profit obtained and the second objective of minimizing the total distance traveled by vehicles. The MAVRPTW arises from hospitals who provide non-emergency ambulance transportation services 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 summation of the outsourcing costs and the total traveling costs. This thesis builds mathematical model, and designs heuristic algorithm or exact algorithm for each of these problems according to their characteristics. Computational experiments are conducted based on a large number of instances, and the results demonstrate the effectiveness and efficiency of the proposed algorithms.

The main research contributions are summarized as follows. (i) TOPTWMD. We formulate this problem into an integer programming model, and then propose a tabu search algorithm to solve it. The proposed tabu search algorithm utilizes seven neighborhood search operators and a shaking operator, and employ a randomized greedy construction method to generate an initial solution. Particularly, we relax the capacity constraint of each vehicle and the time window constraint of each customer, and add the corresponding penalty costs in the objective function. We evaluate the performance of proposed algorithm based on modified Solomon's benchmark instances, and compare it with CPLEX. Computational results demonstrate the effectiveness and efficiency of our algorithm.

(ii) TOPTWMDD. To solve this problem, we devise an enhanced iterative three-component heuristic, which is characterized by a hybridization of an iterated local search method, a tabu search method, and a route recombination. This algorithm starts with a greedy algorithm to generate initial solutions, and these solutions are decomposed into a route library (in unit of route). Then, neighborhood solutions are generated by iterated local search method and tabu search method, and we update the global optimal solution and the route library on the fly. In particular, we enforce that iterated local search method searches the neighborhood solution in feasible search space, while allow the tabu search method to search in the infeasible solution space. After that, the produced routes are recombined to construct a new solution. Computational results substantiate the proposed algorithm is more effective than CPLEX. Moreover, we conducted additional experiments to highlight the contributions of the three components and the alteration between feasible and infeasible regions to the performance of the proposed algorithm.

(iii) MAVRPTW. According to the Dantzig-Wolfe decomposition, we decompose this problem into a set-packing model based on routes and a pricing submodel (corresponding to the shortest path problem to identify route with negative reduced cost). Based on them, we propose a branch-and-price-and-cut algorithm to solve this problem exactly. The algorithm is built upon a branch-and-bound framework. Each branch-and-bound tree node represent a linear programming (LP) relaxation of the set-packing model, and a column generation method is proposed to solve it. Notably, a tailored label-setting algorithm is deigned to solve the pricing submodel. To tighten the LP relaxation gap, subset-row cuts are generated and added into the LP relaxed model on the fly. To further improve the efficiency of the algorithm, we use two accelerating strategies, namely, a bidirectional label search and a decremental state-space relaxation. We run comparative experiment with CPLEX on three classes of 168 instances, and the proposed algorithm is demonstrated to be effective and efficient. Moreover, the impacts of the number of vehicles and staffs to the performance of algorithm is also analyzed.