Agent-Based Solution Approaches for Dynamic Traveling Salesman Problem: Resolving or Adapting Existing Solutions to New Conditions?
Adil Baykasoğlu and Zeynep D.U. Durmuşoğlu
Dynamic Travelling Salesman Problem (DTSP) is a novel type of TSP where the number of cities in the problem domain changes unpredictably. The approaches to handling dynamism in those DTSPs, has been solving the problems as they were static and recreating the models after each change. In this respect, multi-agent based strategies along with intelligent approaches provide an opportunity to deal with those difficulties. The proposed approach in this paper is based on the modification of existing solutions according to changes in the city domain. Thereby problem is not resolved while local city agents deliver their novel bids (solution proposals) for these new conditions. Finally, general manager agent makes a decision about the new solution. This study presents two different agent-based solution strategies for providing promising solutions to DTSP. One of these strategies is based on the competition of city agents in a greedy way and thereby city agents just search for randomly selected alternatives which are feasible for the new conditions. The second strategy covers competition of city agents by the use of great deluge algorithm as the search mechanism. Finally, both of those proposed strategies are compared against the solutions of reinvented models. Agent-based strategies start to produce better results as the problem size increases.
Keywords: Dynamic traveling salesman problem, Multi-agent modeling, Simulation, Agent-based competition, Great deluge algorithm