Track: Logistics Management

Abstract

Most of the operational problems arise in distribution and logistics management are based on the routing of persons and/or vehicles. The Traveling Salesman Problem (TSP) and its variants lie at the heart of routing problems. One of the main variant of the TSP is named as travelling repairman problem which is also known as deliveryman, and minimum latency problem. Those problems focus on the time passed until the costumer’ service completed.  In these problems, waiting time or latency of a customer is defined as the time passed from the beginning of the travel until this customer’s service completed. The objective is to find a Hamiltonian Tour or a Hamiltonian Path that minimizes the total waiting time of customers. The multiple traveling repairmen problem (kTRP) is a generalization of the traveling repairman problem where there are k repairmen (travelers), each customer is visited by one of the repairmen. kTRP may arise for the distribution of the perishable goods, humanitarian logistic, school bus routing and similar problems. As far as we know, there exist a few formulations for the kTRP.  Very recently two integer linear programming formulations appeared in the literature, in one of which we are the authors. Both formulation has O(n²) constraints and  O(n²) binary variables, so they may be used directly to solve suitable size  problems by an optimizer. In this paper, we focused on these two formulations and present a new integer programming formulation with the O(n² ) constraints and  O(n² ) binary variables. In order to see the performance of the formulations we conduct a detailed computational analysis.  Around 200 instances up to 80 nodes from the literature are solved to optimality via CPLEX 12.6. Up to now, those instances were solved only one single value of k, we solved all the instances with various values of k and obtained optimal or best values of the objective function. Linear programming relaxations, CPU and optimality gap are used for performance measures and the results are analyzed. Later, we discuss how these formulations can be adopted the  cases where additional restrictions, such as time windows, are imposed. We show that, our newly proposed formulation can be adapted to those cases very easily, while the existing formulations need to define new variables that cause to enlarge the size of the formulations. We also present our preliminary computational results for the kTRP with time windows