Track: Operations Research

Abstract

With the rapid growth in e-commerce and virtual markets due to the COVID-19 pandemic, customer satisfaction due to logistics activities has become more imperative than ever. The Traveling Repairman Problem (TRP), which is also known as the cumulative traveling salesman problem, the deliveryman problem and the minimum latency problem, is a special variant of the Traveling Salesman Problem (TSP). All these problems differ in their objective function criteria.  In TSP, the total cost (distance or time) of the salesman is minimized. In the case of the TRP, the total latency (waiting time or delay time) of all customers is minimized. Ultimately, with TRP, customer satisfaction is maximized through minimizing the total latency.

This paper focuses on a generalized version of TRP with multi depots and time windows, namely Multi Depot Traveling Repairman Problem with Time Windows (MDTRPTW). A group of homogeneous repairmen initiate and finish their visit tours at depots. Each customer must be visited exactly by one repairman within their provided earliest end latest times, defined as their time windows.  To the best of our knowledge, there is no study in the literature on this problem. In this paper, in addition to posing the problem, we propose a mixed integer programming model for MDTRPTW with O(n²) integer decision variables and O(n²) constraints. MDTRPTW is an NP-hard challenging combinatorial optimization problem. In order to find near optimal solutions within a reasonable computational time for realistic sized dimensions, we also propose a biogeography-based optimization algorithm as a metaheuristic approach. The performance of our formulation and metaheuristic are analyzed by solving instances with time windows from other problems in the literature that are adapted for MDTRPTW. We observe that our proposed formulation is able to solve small and moderate size problems in reasonable times. The efficacy of the metaheuristic solution approach is evaluated in terms of solution quality as well as computation time. The developed metaheuristic approach is able to solve problems with 300 customers within seconds. Moreover, when contrasted with the exact solution methodology, 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 paper is to define and to present a mathematical model for the multi depot Traveling Repairman Problem with time windows. In addition, to propose a metaheuristic approach for this problem.