Skip to Main content Skip to Navigation
Conference papers

Nash fairness solutions for balanced TSP

Abstract : In this paper, we consider a variant of the Traveling Salesman Problem (TSP), called Balanced Traveling Salesman Problem (BTSP) [7]. The BTSP seeks to find a tour which has the smallest maxmin distance : the difference between the maximum edge cost and the minimum one. We present a Mixed Integer Program (MIP) to find optimal solutions minimizing the max-min distance for BTSP. However, minimizing only the max-min distance may lead to a tour with an inefficient total cost in many situations. Hence, we propose a fair way based on Nash equilibrium [5], [11] to inject the total cost into the objective function of the BTSP. We consider a Nash equilibrium as it is defined in a context of fair competition based on proportional-fair scheduling. For BTSP, we are interested in solutions achieving a Nash equilibrium between two players: the first aims at minimizing the total cost and the second aims at minimizing the max-min distance. We call such solutions Nash Fairness (NF) solutions. We first show that NF solutions for BTSP exist and may be more than one. We show that NF solutions are Pareto-optimal [10] and can be found by optimizing a sequence of linear combinations of the two players objectives based on Weighted Sum Method [13]. We then focus on extreme NF solutions which are NF solutions having either the smallest value of total cost or the smallest max-min distance. Finally, we propose a Newton-based iterative algorithm which converges to extreme NF solutions in a polynomial number of iterations. Computational results on smallsize instances from TSPLIB will be presented and commented.
Document type :
Conference papers
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03654554
Contributor : Minh Hieu NGUYEN Connect in order to contact the contributor
Submitted on : Monday, June 6, 2022 - 4:54:31 PM
Last modification on : Thursday, June 9, 2022 - 3:37:29 AM

File

INOC2022.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03654554, version 2

Citation

Minh Hieu Nguyen, Mourad Baiou, Viet Hung Nguyen, Thi Quynh Trang Vo. Nash fairness solutions for balanced TSP. 10th International Network Optimization Conference (INOC), Jun 2022, Aachen, Germany. ⟨hal-03654554v2⟩

Share

Metrics

Record views

34

Files downloads

13