Solving the Uncapacitated Traveling Purchaser Problem with the MAX–MIN Ant System
| Autor: | Rafał Skinderowicz |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Traveling purchaser problem
Mathematical optimization 021103 operations research Heuristic (computer science) Computer science Generalization Ant colony optimization algorithms 0211 other engineering and technologies 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 02 engineering and technology Travelling salesman problem |
| Zdroj: | Computational Collective Intelligence ISBN: 9783319984452 ICCCI (2) |
| DOI: | 10.1007/978-3-319-98446-9_24 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|