The classical Multiple Traveling Salesmen Problem is a well-studied optimization problem. Given a set of goals/targets and agents, the objective is to find round trips, such that each target is visited only once and by only one agent, and the total distance of these round trips is minimal. In this paper we describe the Multiagent Planning Problem, a variant of the classical Multiple Traveling Salesmen Problem: given a set of goals/targets and a team of agents, subtours (simple paths) are sought such that each target is visited only once and by only one agent. We optimize for minimum time rather than minimum total distance; therefore the objective is to find the Team Plan in which the longest subtour is as short as possible (a min–max problem). We propose an easy to implement Genetic Algorithm Inspired Descent (GAID) method which evolves a set of subtours using genetic operators. We benchmarked GAID against other evolutionary algorithms and heuristics. GAID outperformed the Ant Colony Optimization and the Modified Genetic Algorithm. Even though the heuristics specifically developed for Multiple Traveling Salesmen Problem (e.g., -split, bisection) outperformed GAID, these methods cannot solve the Multiagent Planning Problem. GAID proved to be much better than an open-source Matlab Multiple Traveling Salesmen Problem solver.
from #AlexandrosSfakianakis via Alexandros G.Sfakianakis on Inoreader http://ift.tt/2kCkK3j
via IFTTT
Εγγραφή σε:
Σχόλια ανάρτησης (Atom)
Δημοφιλείς αναρτήσεις
-
Publication date: Available online 4 January 2018 Source: European Journal of Radiology Author(s): Peiyao Zhang, Jing Wang, Qin Xu, Zhen...
-
Medicine by Alexandros G. Sfakianakis,Anapafseos 5 Agios Nikolaos 72100 Crete Greece,00302841026182, Butyric Acid from Probiotic Staphyloco...
-
Medicine by Alexandros G. Sfakianakis,Αλέξανδρος Γ. Σφακιανάκης A Novel Technique for Endoscopic Repair of Large Anterior Skull Base Defect...
-
2016-11-22T07-55-59Z Source: International Journal of Medical Science and Public Health Banothu Srinivas, Madhu Mohan Reddy B. Backgrou...
-
2016-10-15T06-30-01Z Source: The Southeast Asian Journal of Case Report and Review Sangita Deepak Kamath, Neeraj Jain, Saurabh Pathak, Ba...
-
BACKGROUND AND PURPOSE: Lesion load is a common biomarker in multiple sclerosis, yet it has historically shown modest association with cl...
-
Abstract The development of focused ion beam-scanning electron microscopy (FIB-SEM) techniques has allowed high-resolution 3D imaging of n...
-
Vol.48 No.2 from #AlexandrosSfakianakis via Alexandros G.Sfakianakis on Inoreader http://ift.tt/1S2Z7n2 via IFTTT
-
Does CBD Oil Lower Blood Pressure? This article was originally published at SundayScaries." Madeline Taylor POSTED ON January 13, 20...
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου