Academic literature on the topic 'Problema del vendedor viajero'

Se describe y se analiza un espacio literario relevante sobre el Problema del Vendedor Viajero (TSP) en términos de contenido, clases de TSP, métodos y campos de inspiración. Los datos empleados provinieron de los trabajos más citados en Scopus sobre el TSP, tanto a través de la historia como en el período 2006-2010. Se encontró que el TSP prevalece en las investigaciones, con enfoques tanto en el problema original como en sus variantes, entre las cuales se identificaron el TSP Múltiple y el TSP Probabilístico. Entre los principales campos de inspiración para resolver el TSP están la evolución biológica y su base genético-molecular, el comportamiento de hormigas reales, la termodinámica, las estrategias sistemáticas para combinar reglas de decisión y la búsqueda de vecindades. Hoy día se tiende a desarrollar métodos híbridos, especialmente integrando enfoques globales con búsquedas locales, y se identifica la necesidad de introducir nuevos campos de inspiración.

En este trabajo se presenta una propuesta para aplicar la meta-heurística Optimización Basada en Mallas Variables (VMO) al problema discreto del Viajero Vendedor (TSP); este modelo explora el espacio de búsqueda a Objetivo partir de una población de soluciones llamada malla que se expande y contrae con la finalidad de encontrar soluciones de buena calidad. En este contexto se modifica el operador de expansión de manera tal que sea aplicable en un dominio discreto, realizando combinaciones entre las soluciones a fin de obtener nuevos nodos. Otro de los elementos que se modifica es el operador de clearing, el cual se encarga de mantener la diversidad de la malla en cada interacción. Metodología. Se resume en este trabajo un estudio de parámetros del modelo VMO utilizando un conjunto de instancias de TSP con diferentes características; además, se puede observar que la propuesta de este trabajo obtiene Resultados competitivos al compararlos con otros algoritmos de referencia internacional mencionado en el estado del arte. El trabajo está estructurado de la siguiente manera: En el apartado 1 se describe los aspectos fundamentales de problema de estudio TSP. Seguidamente en el segundo se explica el funcionamiento general de VMO, en el tercero se define cada uno de los operadores de expansión y contracción para el problema de estudio. Posteriormente en el apartado cuarto se realiza un estudio de parámetros de la propuesta y un análisis comparativo experimental con los resultados obtenidos con otros algoritmos mencionado en el estado del arte. Conclusiones Se aplicaron otros operadores de generación de nuevos nodos en el proceso de expansión, donde se realiza una combinación de soluciones de manera que cumpla con las restricciones impuestas por el problema.

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.

Sergio Chejfec y Martín Caparrós, autores hispanoamericanos, residentes fuera de su país de origen y que han tratado poéticas del movimiento, sirven como punto de partida para analizar las estrategias narrativas del viajero contemporáneo. Cómo se cuentan los viajes, qué elementos reúnen o separan estos dos autores, qué nos dice su escritura que permite identificar su condición con la de viajeros y sus libros con la escritura de viajes –ese género fronterizo, híbrido, mestizo–. Entre los elementos analizados está la búsqueda, la hipertextualidad, el problema del tiempo y el espacio, la condición de testigo y traductor del viajero y la premisa informativa que forma parte del relato de viaje más allá de las estrategias narrativas.

<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>

En este escrito se aborda el problema de la fenomenología como filosofía y como método. Asimismo, se destacan los elementos metodológicos que Husserl ofrece en sus obras. Este proceso metodológico es posible encontrarlo en la forma de exponer el ejercicio propio del filosofar: como geógrafo. Para ello tomaremos como referencia el método fenomenológico expuesto por el propio Husserl. En primer término, esbozaremos los fundamentos de la fenomenología husserliana, luego estudiaremos los elementos que conforman el método fenomenológico.

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.

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.