CNF Encodings for the Min-Max Multiple Traveling Salesmen Problem

EasyChair Preprint 3290, version 1

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 the proposed extended 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. Compared to the IP method, one of the proposals is more effective on relatively large-scale problems, and it also has an obvious advantage over the IP method in solving instances with a small ratio of the number of cities to the number of salesmen.

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

@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 3290},
  year      = {EasyChair, 2020}}