Download PDFOpen PDF in browser

CNF Encodings for the Min-Max Multiple Traveling Salesmen Problem

EasyChair Preprint 3290, version 2

Versions: 12history
8 pagesDate: November 11, 2020

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, Multiple traveling salesmen problem, min-max optimization

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@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}}
Download PDFOpen PDF in browser