Academic literature on the topic 'Problema del agente viajero'

ACO (algoritmo de colonia de hormigas) es una metaheurística inspirada en el comportamiento de las colonias de hormigas para solucionar problemas de optimización combinatoria, por medio de la utilización de agentes computacionales simples que trabajan de manera cooperativa y se comunican mediante rastros de feromonas artificiales. En este trabajo se presenta un modelo para resolver el Problema clásico de optimización 'Problema del Agente viajero' (TSP Travelling Salesman Problem).

El presente artículo encuentra soluciones factibles para el Problema del Agente Viajero, mediante una nueva forma de agrupar al problema en clústeres con la intención de crear subproblemas del Agente Viajero, las cuales se resuelven por el metaheurístico algoritmos genéticos. Posteriormente las agrupaciones son unidas nuevamente utilizando las soluciones proporcionadas por el metaheurístico, obteniendo una solución final, además, la propuesta de agrupación de ciudades consiste en la utilización de la media aritmética sobre las coordenadas, para calcular iterativamente a los nodos representativos de cada familia. En la literatura se encuentra una tendencia para abordar este problema mediante la metodología propuesta. Los resultados demuestran que al utilizar esta metodología de agrupación se mejoran los resultados en comparación a las soluciones algoritmos genéticos sin utilizar clústeres.

<p>En este trabajo se explora la solución colectiva de problemas mediante la comparación del desempeño grupal humano y los algoritmos de inteligencia de enjambres. En el estudio participaron treinta estudiantes universitarios de distintos programas académicos, con edades entre dieciocho y treinta años que fueron asignados en grupos conformados por tres, cinco o siete integrantes. Se utilizó una versión espacial (campo abierto) del problema del agente viajero. El desempeño de los participantes se comparó con la ejecución de algoritmos de inteligencia colectiva de enjambres. Los resultados muestran algunas semejanzas entre la cognición de grupo y la cognición de enjambre en los mecanismos de procesamiento de información, las estrategias de organización colectiva y las pautas de elección o estrategias de consenso.</p><p> </p>

Las empresas de transporte vehicular terrestre, enfrentan un desafío cada día por controlar los costos de operación, con el surgimiento de la pandemia sanitaria se ha visto más afectado por la disminución de movimiento de carga y el incremento del costo de combustible, por lo que el presente artículo expone la forma de diseñar pre rutas para este medio de transporte, dando solución al problema del agente viajero a través de la técnica del vecino más cercano, con apoyo de google maps, para minimizar los costos de operación en cualquier empresa que tenga la necesidad de hacer recorridos con el transporte vehicular terrestre y no cuente con una plataforma digital para el diseño de sus recorridos por los costos de inversión que este representa.

La optimización combinatoria se utiliza para modelar un caso especial del problema del agente viajero — TSP relacionado a la actividad turística en la región de Ancash, zona de la cordillera negra. El destino turístico, Laguna de Wilcacocha tiene un conjunto de rutas existentes para su visita, los cuales deben ser recorridos a pie por los usuarios turísticos. La elección de una heurística permite diseñar o seleccionar las rutas de acceso que contribuyan al usuario en niveles de satisfacción, así como de reducción de distancias y de tiempos. Cada ruta se inicia y finaliza en la ciudad de Huaraz.

<p><span style="font-family: Arial;">Este trabajo presenta la solución mono-objetivo y multi-objetivo del problema de la distribución de planta en celdas de manufactura a través de dos nuevos algoritmos híbridos discretos basados en quimiotaxis de bacterias y en algoritmos genéticos. Los modelos propuestos resuelven simultáneamente los dos inconvenientes que constituyen el problema de la distribución de planta en celdas de manufactura: la formación de las celdas y la distribución de planta intra e inter celdas, considerando el agrupamiento de las celdas y el costo de transporte y manipulación de materiales. El desempeño de las propuestas se evaluó con problemas de prueba de distribución de planta de celdas de manufactura, agente viajero (TSP) y el caso multi-objetivo del problema de las mochilas. Los resultados mono-objetivo se compararon con AG, BFOA y <em>Bacterial</em>-GA, mientras que los resultados multi-objetivo se compararon con los reconocidos algoritmos NSGA2 y SPEA2 en los que se obtuvo un mejor desempeño en los dos casos.</span></p>

En el presente artículo se analiza la problemática en la distribución de productos de consumo que realizan empresas del sector alimentario. La falta de eficiencia en el diseño de la red de distribución, con base en información confiable sobre ubicaciones y distancias de traslado hacia los clientes, son factores que afectan principalmente la planeación de la cadena de suministro. A través de un caso de estudio de un problema de distribución de productos alimenticios que deben ser entregados mediante un programa gubernamental de seguridad alimentaria, basado en desayunos escolares, cuya población objetivo son estudiantes matriculados en escuelas de nivel básico, en la zona sureste del estado de Hidalgo. Se propone el diseño de una red de distribución en dos escalones o niveles que identifica las rutas para el reparto de estos productos. Utilizando de manera conjunta herramientas tecnológicas como Google API para el cálculo de distancias de traslado, técnicas cluster y software para el análisis de datos, se desarrolla una propuesta de distribución, la cual se obtiene mediante un modelo, resuelto a través de un algoritmo genético, aplicado al problema del agente viajero (TSP, por sus siglas en ingles). Los resultados de esta propuesta muestran un panorama general de la localización de todos los clientes, las distancias reales entre estos, los consumos y las posibles rutas que deben ser consideradas en la planeación de la cadena de suministro. Esta propuesta resulta útil también para tomar decisiones sobre otros aspectos como: el correcto abastecimiento de los productos, la selección de posibles centros de distribución, el diseño de la logística basado en los costos de distribución y la distancia recorrida de los transportes. Generando como resultado un notable ahorro económico en la distribución que permita planear una futura expansión y cobertura en otras áreas geográficas.

En la primera parte se estudian el problema de asignación y el problema del agente viajero. Se revisan los modelamientos matemáticos de ambos problemas y se busca una relación entre ellos. Posteriormente se desarrollan nuevas metodologías de formulación del problema del agente viajero asimétrico. Se utiliza un software para comprobar las soluciones de los modelamientos propuestos y se comprueban con la solución exhaustiva. Se generan diferentes problemas como comprobación de los modelamientos matemáticos propuestos.
Tesis

En las últimas décadas, la globalización ha impulsado la adaptación del sector del Transporte y la Logística a las nuevas demandas sociales. Al mismo tiempo, el transporte ha sido la columna vertebral de la globalización. Esta necesidad social crea consumidores ambiciosos que necesitan sus productos de forma rápida y a un precio asequible muchas veces sin ser conscientes de su origen, el transporte o los aspectos medioambientales, entre otros factores. Sin embargo, para satisfacer las demandas del cliente, es necesario encontrar el modo de transporte más barato, que significa la mejora de la logística del transporte de estos productos. Por lo tanto, estas demandas requieren un servicio cada vez más flexible para satisfacer las necesidades del cliente, y, además, las empresas quieren un transporte eficiente y productivo. Traveling Salesman Problems (TSP) and Vehicle Routing Problems (VRP) proporcionan el marco teórico para tratar este tipo de problemas logísticos relacionados con la distribución física de mercancías desde un almacén central hasta los clientes. Son dos de los problemas más desafiantes e investigados debido a su complejidad y aplicabilidad. El objetivo principal de esta tesis doctoral es la introducción de metodologías híbridas que integran varias técnicas para resolver de manera eficiente rich VRPs con restricciones realistas. Esta tesis comienza con problemas teóricos y evoluciona hacia escenarios más realistas abordando un total de seis problemas combinatorios relacionados con el transporte por carretera. Una metaheurística llamada Tailored Lagrangian Metaheuristic (TLM) se ha desarrollado para abordar el TSP. Está basa en la relajación de Lagrange que se utiliza para explotar la estructura del problema que reduce considerablemente su complejidad moviendo restricciones difíciles de satisfacer a la función objetivo, asociando una penalización en caso de que no se cumplen. La metaheurística desarrollada para el TSP se ha integrado en dos metodologías híbridas combinadas con Constraint Programming para hacer frente a problemas más complejos. En primer lugar, el Capacitated Vehicle Routing Problem (CVRP), cuyos los vehículos tienen limitaciones de capacidad de carga de las mercancías que deben ser entregadas, es abordado. En segundo lugar, se ha abordado un problema real, Home Health Care (HHC), del servicio de Salud en el municipio de Ferrara, Italia. Este consiste en la asignación de los tratamientos de los pacientes a las enfermeras que viajan a las casas de los pacientes. Investigaciones teóricas suelen asumir la simetría de los costes basados en la distancia de viajar de un lugar a otro y la existencia de una flota homogénea de vehículos con una misma capacidad. Esta tesis estudia diferentes variantes centradas en el impacto que causa la asimetría de los costes y la heterogeneidad de la flota. Para estos estudios, se abordan la versión con costes asimétricos del TSP y del CVRP -el Asymmetric Traveling Salesman Problem (ATSP) y el Asymmetric Capacitated Vehicle Routing Problem (ACVRP)- y la versión con flota heterogénea del ACVRP –el Asymmetric and Heterogeneous Vehicle Routing Problem (AHVRP).
Over the last decades, globalization has driven the adaptation of the Transport and Logistics sector to new social demands. At the same time, transport has been the backbone of globalization. This social need creates ambitious consumers who need their products quickly and an affordable price often unaware of their origin, transport mode or environmental aspects, among other factors. Nevertheless, to satisfy customer demands, it is needed to find the cheapest transport mode, which in turn means the improvement of transport logistics of the products. Therefore, these demands require an increasingly flexible service to meet customer requirements, and in addition companies want an efficient and productive transport. The so called Traveling Salesman Problems (TSP) and Vehicle Routing Problems (VRP) provide the theoretical framework for approaching this class of logistic problems associated with the physical distribution of goods from a central depot to customers. They are two of the most challenging and researched problems because of their complexity and applicability. The main goal of this PhD thesis is to introduce hybrid methodologies that integrate several techniques to efficiently solve rich VRPs with realistic constraints. It starts with theoretical problems and evolves into more realistic scenarios tackling six combinatorial problems related to road transport. A metaheuristic named Tailored Lagrangian Metaheuristic (TLM) has been developed to tackle the TSP. It is based on the Lagrangian Relaxation which is used to exploit the structure of the problem reducing considerably its complexity by moving hard-to-satisfy constraints into the objective function, associating a penalty in case the constraints are not satisfied. The developed metaheuristic for the TSP has been integrated into two hybrid methodologies combined with Constraint Programming to tackle more complex problems. First of all, it is addressed the Capacitated Vehicle Routing Problem (CVRP), whose vehicles have limited loading capacity of the goods that must be delivered. Secondly, it has been addressed a real problem of the Home Health Care (HHC) service in the municipality of Ferrara, Italy. It consists on assigning patients' services to nurses which travel to each patient’s home. Theoretical researches typically assume the symmetry of the distance-based costs associated with traveling from one place to another as well as the existence of a homogeneous fleet of vehicles with limited capacity. This thesis studies different variants focusing on the impact that causes the asymmetry of the costs and the heterogeneity of the fleet. For these purpose, the Asymmetric Traveling Salesman Problem (ATSP), the Asymmetric Capacitated Vehicle Routing Problem (ACVRP) and the Asymmetric and Heterogeneous Vehicle Routing Problem (AHVRP) are addressed.

Magíster en Gestión de Operaciones
Dada una colección de ciudades y el costo de viajar entre cualquier par de ella, el problema del vendedor viajero, que denotaremos como TSP (traveling salesman problem en inglés), consiste en encontrar el tour menos costoso que visita todas las ciudades al menos una vez retornando al punto inicial. En su forma métrica este problema es NP-duro, y por lo tanto no existe un algoritmo en tiempo polinomial que lo resuelva, salvo que P=NP. Para el caso métrico, Christofides diseñó en el año 1976 un 3/2-algoritmo de aproximación, el cual despertó una gran curiosidad con respecto a la aproximabilidad del problema. Sin embargo, y pese a los grandes esfuerzos efectuados en investigación, el algoritmo de Christofides es el de mejor garantía hasta el día de hoy. Recientemente han habido varios mejoras importantes con respecto a la aproximabilidad en casos especiales de TSP métrico. En el año 2011 Oveis Gharan et al. diseñaron un (3/2-ε)-algoritmo de aproximación para el caso graph-TSP, donde la distancia métrica entre cada par de ciudades está dada por el menor número de arcos necesarios para conectarlas por un camino dentro de un grafo sin pesos. En el mismo año Mömke y Svensson mejoran el resultado a 1.461, mientras Mucha en el 2012 mejora la garantía del algoritmo a 13/9. En el caso de que el grafo es cúbico de n vértices y 2-conexo, el algoritmo de Mömke y Svensson entrega un tour de largo menor a (4/3)n, resultado obtenido también por Boyd et al. en el año 2011. En este trabajo estudiamos el problema graph-TSP en distintas variantes de grafos cúbicos. Primero estudiamos el caso en que el grafo es planar, cúbico, bipartito y 3-conexo, el cual es un caso interesante desde el punto de vista de teoría de grafos ya que, según la conjetura de Barnette de hace más de 40 años estos grafos serían Hamiltonianos. En esta clase de grafos, conocidos como grafos de Barnette, mostramos que en un grafo de n vértices existe un tour de largo a lo más (4/3-1/18)n. Luego relajamos las condiciones sobre el grafo, quitando la hipótesis de planaridad e imponiendo que sea cúbico, bipartito y 2-conexo, caso en el cual mostramos que existe un tour de largo a lo más (4/3-1/108)n. Finalmente, estudiamos el caso en que el grafo es solamente cúbico y 2-conexo. En este caso nos basamos en las técnicas de Boyd et al. para mostrar que existe un tour de largo a lo más (4/3-1/61236)n. En cada caso mostramos que el tour se puede encontrar en tiempo polinomial, y como n es naturalmente una cota inferior del valor de graph-TSP, cada uno de los resultados obtenidos se traduce en un algoritmo de aproximación. Además, como n es una cota inferior de la relajación de Held & Karp, que es una conocida formulación para TSP como programa lineal, obtenemos como consecuencia que el gap de integralidad de TSP con respecto a esta relajación es acotado superiormente por (4/3-1/18) para el caso de Barnette, (4/3-1/108) para el caso cúbico, bipartito y 2-conexo, y (4/3-1/61236) para el caso cúbico y 2-conexo.

Il sempre crescente numero di applicazioni di reti di sensori, robot cooperanti e formazioni di veicoli, ha fatto sì che le problematiche legate al coordinamento di sistemi multi-agente (MAS) diventassero tra le più studiate nell’ambito della teoria dei controlli. Esistono numerosi approcci per affrontare il problema, spesso profondamente diversi tra loro. La strategia studiata in questa tesi è basata sulla Teoria del Consenso, che ha una natura distribuita e completamente leader-less; inoltre il contenuto informativo scambiato tra gli agenti è ridotto al minimo. I primi 3 capitoli introducono ed analizzano le leggi di interazione (Protocolli di Consenso) che permettono di coordinare un Network di sistemi dinamici. Nel capitolo 4 si pensa all'applicazione della teoria al problema del "loitering" circolare di più robot volanti attorno ad un obiettivo in movimento. Si sviluppa a tale scopo una simulazione in ambiente Matlab/Simulink, che genera le traiettorie di riferimento di raggio e centro impostabili, a partire da qualunque posizione iniziale degli agenti. Tale simulazione è stata utilizzata presso il “Center for Research on Complex Automated Systems” (CASY-DEI Università di Bologna) per implementare il loitering di una rete di quadrirotori "CrazyFlie". I risultati ed il setup di laboratorio sono riportati nel capitolo 5. Sviluppi futuri si concentreranno su algoritmi locali che permettano agli agenti di evitare collisioni durante i transitori: il controllo di collision-avoidance dovrà essere completamente indipendente da quello di consenso, per non snaturare il protocollo di Consenso stesso.

Doctor en Ciencias de la Ingeniería, Mención Modelación Matemática En Cotutela con la Universidad Paris-Dauphine
En esta tésis se estudian aspectos teóricos del modelo de Agente-Principal y se presentan algunas aplicaciones en economía. En la primera parte de la tésis se presentan dos aplicaciones del modelo. En la primera, un proveedor de electricidad determina la tarifa óptima para cobrar a los clientes por su consumo. La población es heterogénea y el proveedor observa perfectamente el consumo de cada cliente. Esto conlleva a una situación de selección adversa sin riesgo moral. El problema del Principal se escribe como un problema variacional no estándar que se resuelve para formas particulares de la utilidad de reserva de la población. El contrato óptimo resulta ser o bien lineal o polinomial con respecto al consumo y el proveedor contrata solo a aquellos consumidores que presentan una alta o una baja necesidad de electricidad. En la segunda aplicación, un banco monitorea un conjunto de préstamos idénticos sujetos a contagio Markoviano. El banco obtiene fondos de un inversor, que no puede observar las acciones del banco y tampoco conoce su competencia para el trabajo. Este trabajo es una extensión del modelo de Pagès and Possamaï [84] al caso de incluye tanto riesgo moral como selección adversa. Siguiendo el enfoque de Cvitanić, Wan and Yang [31] para este tipo de problemas, el conjunto creíble dinámico es calculado explícitamente y la función valor del inversor se obtiene a través de un sistema recursivo de inecuaciones variacionales. Las propiedades del contrato óptimo se discuten en detalle. En la segunda parte de la tesis se estudia el problema de un Agente que controla el retorno esperado de un proceso de difusión bajo incerteza de la volatilidad. Se asume que tanto el Principal como el Agente tiene un enfoque pesimista al problema y actúan como si un tercer jugador, la Naturaleza, escogiera la peor volatilidad posible. Este trabajo es una extensión de Mastrolia y Possamaï [64] y de Sung [125] a un marco más general. Se demuestra que la función valor del Agente puede ser representada como la solución de una Ecuación Diferencial Estocástica Retrógrada de segundo orden, y también que la función valor del Principal corresponde a la única solución viscosa de la ecuación de Hamilton-Jacobi-Bellman- Isaacs asociada, asumiendo que esta última satisface un principio de comparación.
Este trabajo ha sido parcialmente financiado por CONICYT-Beca Doctorado Nacional 2013