New mathematical models for the traveling repairman problem with time windows and its extensions

The Traveling Repairman Problem (TRP) is a variant of the Traveling Salesman Problem (TSP) which is the basis of the routing problems. TRP is based on customer satisfaction and aims to minimize total delay time of customers. TRP involves finding a Hamiltonian tour or path starting from an initial node, after visiting all customers, it ends at the starting or any given node in such a way that, total delay time is minimized. In this study, TRP with time windows (TRPTW), multiple traveler TRPTW (kTRPTW) and multi depot TRPTW (DTRPTW) are considered. Firstly, we observe that there exist only two mathematical models for TRPTW and four new mathematical models with polynomial number of constraints and decision variables are developed. Benchmark problems are solved by existing and new models for TRPTW and CPU times and deviation rates are analyzed. We conclude that two of the new mathematical models are superior to the others. Then, for kTRPTW, two mathematical models are found for homogeneous and heterogeneous case in the literature. Two new mathematical models which are node-based and arc-based with polynomial number of constraints and decision variables are developed for homogeneous and heterogeneous kTRPTW. The performances of the existing and new models for kTRPTW are compared by using benchmark problems in terms of CPU times and deviation rates with different number of repairmen. As a result of computational analysis, we observe that, the node-based models show superior performance for both cases. Lastly, it is focused on DTRPTW and we could not find any study for DTRPTW in the literature. Five mathematical models with polynomial number of constraints and decision variables are proposed for various types of the DTRPTW. The performances of new formulations are analyzed in terms of CPU times and deviation rates for solving problems. Since the optimal solutions cannot be reached with mathematical formulation by using small number of repairmen for some large-sized problems in a reasonable time, a metaheuristic algorithm named as Biogeography-Based Optimization (BBO) is developed to solve them approximately. The parameter values of BBO algorithm are estimated by experimental design. The efficiency of the algorithm is evaluated by using deviation rate from the optimal value, coefficient of variation and solution time. The proposed metaheuristic algorithm represents a high performance to find good quality solutions within acceptable CPU times for large-size problems. The main contribution of this study is to present new mathematical models for TRPTW, kTRPTW, DTRPTW and the metaheuristic algorithm for DTRPTW.