Advertisement
Published in:
2018 | OriginalPaper | Chapter
Solving the Uncapacitated Traveling Purchaser Problem with the MAX–MIN Ant System
Author : Rafał Skinderowicz
Published in: Computational Collective Intelligence
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
The Traveling Purchaser Problem (TPP) is a generalization of the Traveling Salesman Problem that can be used to model various real-world applications. Several exact and heuristic approaches were proposed to solving the TPP (and its variants) in recent decades, including an Ant Colony Optimization–based one. We propose an alternative implementation based on the MAX–MIN Ant System and show that it is very competitive when solving the Uncapacitated TPP (U-TPP). When considering the U-TPP instances from a well-known repository by Laporte the proposed algorithm was able to find the optimum to all of the 89 closed instances in an average time of fewer than 3 s. Similarly, it was able to reach the best-known solutions for the 49 out of 51 open instances, while finding a new best solution for one instance.