CNF Encodings for the Min-Max Multiple Traveling Salesmen Problem

EasyChair Preprint no. 3290, version 2

Abstract

In this study, we consider the multiple traveling salesmen problem (mTSP) with the min-max objective of minimizing the longest tour length. We begin by reviewing an existing integer programming (IP) formulation of this problem. Then, we present several novel conjunctive normal form (CNF) encodings and an approach based on modifying a maximum satisfiability (MaxSAT) algorithm for the min-max mTSP. The correctness and the space complexity of each encoding are analyzed. In our experiments, we compare the performance of solving the TSP benchmark instances using an existing encoding and our new encodings comparing the results achieved using an implemented group MaxSAT solver to those achieved using the IP method. The results show that for the same problem, the new encodings significantly reduce the number of generated clauses over the existing CNF encoding. Although the proposals are still not competitive compared to the IP method, one of them may be more effective on relatively large-scale problems, and it has an advantage over the IP method in solving an instance with a small ratio of the number of cities to the number of salesmen.

Keyphrases: Boolean satisfiability, min-max optimization, Multiple traveling salesmen problem

@Booklet{EasyChair:3290,
  author = {Aolong Zha and Rongxuan Gao and Qiong Chang and Miyuki Koshimura and Itsuki Noda},
  title = {CNF Encodings for the Min-Max Multiple Traveling Salesmen Problem},
  howpublished = {EasyChair Preprint no. 3290},

  year = {EasyChair, 2020}}