New formulations for multiple traveler minimum latency problem

The Minimum Latency Problem (MLP) is a kind of Traveling Salesman Problem (TSP) which is the basis of the routing problems. MLP investigates the Hamilton tour or path, which starts from an initial node, after visiting all nodes, it ends at the starting or any given node. While TSP aims to make the smallest total time required to visit all customers, MLP aims to minimize total delay time of customers. When we review the literatüre, MLP with multiple traveler which is regarded as the most important exception of MLP, is modeled in two different ways: one with polynomial and the other with exponential number of constraints. However, both models are not efficient in terms of reaching a solution in a short time. Therefore the need for a new decision model is obvious. In this study, firstly MLP models are subjected to several quantitative analysis using available benchmarking problems in the literature. The purpose of this analysis is to create an infrastructure for the multiple traveling MLP. The best performing model is determined in terms of processing time (CPU) and linear programming (LP) relaxation values. Four models, one from literature and three new ones, are solved for benchmark problems with different number of nodes and different number of travelers and the best performing model is selected accordingly. As a result of this comparative analysis, we observe the relationship between problem size and CPU time and also the relationship between the number of travelers and CPU time. The most important result of this study is presented as a contribution to science, a new model for multiple traveling MLP.