Buscar

Borrar filtros
Filtrado por: Fecha de creacion 2013-01 Eliminar la restricciónFecha de creacion: 2013-01 Departamento Aerospace Engineering and Engineering Mechanics Eliminar la restricciónDepartamento: Aerospace Engineering and Engineering Mechanics

Resultados de la búsqueda

  • A Market-based Solution to the Multiple Traveling Salesmen Problem

    Article thumbnail: A Market-based Solution to the Multiple Traveling Salesmen Problem
    Type:
    Article
    Descripción/Resumen:
    This paper describes a market-based solution to the problem of assigning mobile agents to tasks. The problem is formulated as the multiple depots, multiple traveling salesmen problem (MTSP), where agents and tasks operate in a market to achieve near-optimal solutions. We consider both the classical MTSP, in which the sum of all tour lengths is minimized, and the Min-Max MTSP, in which the longest tour is minimized. We compare the market-based solution with direct enumeration in small scenarios, and show that the results are nearly optimal. For the classical MTSP, we compare our results to linear programming, and show that the results are within 1 % of the best cost found by linear programming in more than 90 % of the runs, with a significant reduction in runtime. For the Min-Max case, we compare our method with Carlsson's algorithm and show an improvement of 5 % to 40 % in cost, albeit at an increase in runtime. Finally, we demonstrate the ability of the market-based solution to deal with changes in the scenario, e.g., agents leaving and entering the market. We show that the market paradigm is ideal for dealing with these changes during runtime, without the need to restart the algorithm, and that the solution reacts to the new scenarios in a quick and near-optimal way.
    Creador/Autor:
    Cohen, Kelly; Kumar, Manish, and Kivelevitch, Elad
    Peticionario:
    Kelly Cohen
    Fecha modificada:
    02/13/2017
    Fecha modificada:
    04/05/2017
    Fecha de creacion:
    2013-01
    Licencia:
    All rights reserved