1. Zaman pencereli çok ekipli gecikme problemi için yeni matematiksel modeller.
- Author
-
Uzun, Gözde Önder and Kara, İmdat
- Subjects
- *
TRAVELING salesman problem , *LINEAR programming , *CUSTOMER services , *QUEUING theory , *POLYNOMIALS , *TOURS , *VEHICLE routing problem - Abstract
One of the important variants of the Traveling Salesman Problem (TSP) is the Minimum Latency Problem (LP). In the LP, the purpose is to find a Hamiltonian path or tour starting from the origin while minimizing the total latency (waiting time or delay time) of all customers. The latency of a customer is defined as the time passed from the beginning of the tour (or path) until the completing the service for that customer. Multiple LP with time windows (kLPTW) finds k tours or paths, each starting at the depot and visiting the nodes within their earliest and latest time (time windows) while minimizing total latency. If travel times between nodes do not depend on the traveler, it is named as homogeneous kLPTW, if travel times between nodes depend on the traveler, it is named as heterogeneous kLPTW. As far as we are aware, there is only one formulation for homogeneous and one formulation for heterogeneous case. In this paper, we proposed a new formulation for homogeneous and a new formulation for heterogeneous case with polynomial number of decision variables and constraints. Then, we solved benchmark instances with our formulations and existing formulations with different number of travelers. We compared the formulations in terms of CPU times and percentage deviation of linear programming relaxation values from the best values. We observed that, our formulations are superior than the existing formulations for all the problems for both kLPTW types with respect to each performance criteria. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF