El QAP-Arbol es un caso especial del problema de asignación cuadrática en que los flujos distintos de cero forman un árbol. No se requiere ninguna condición para la matriz de distancias. En este artículo presentamos una formulación del QAP-Arbol como un problema de programación lineal entera. Basándonos en esta formulación hemos construido cuatro relajaciones lagrangianas distintas que nos permiten obtener una serie de cotas inferiores para este problema. Para resolver una de estas relajaciones,...
En este artículo se estudia el comportamiento en el peor de los casos de dos algoritmos heurísticos propuestos para el Problema del Cartero Rural definido sobre un grafo no dirigido (RPP) y sobre un grafo dirigido (DRPP). En ambos problemas se determina el radio del peor caso de los heurísticos estudiados, que para el RPP es 3/2, mientras que para el DRPP no está acotado. Para conseguir cotas que sean más significativas, se ha determinado también este radio en función de ciertos parámetros que se...
In this paper we consider the Capacitated Arc Routing Problem, in which a fleet of K vehicles, all of them based on a specific vertex (the depot) and with a known capacity Q, must service a subset of the edges of the graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity.
A heuristic algorithm for this problem is proposed consisting of: the selection of K centers, the construction of K connected graphs with associated loads not exceeding...
El objetivo de este artículo es ofrecer una visión general de la situación actual de la investigación en Problemas de Rutas por Arcos, que consisten, básicamente, en encontrar rutas óptimas que atraviesen las aristas o/y arcos de un grafo dado. Se analizan, entre otros, el Problema del Cartero Chino (definido sobre grafos dirigidos, no dirigidos o mixtos), el Problema del Cartero Rural (dirigido y no dirigido), así como el problema de los m-Carteros con alguna de sus variantes. En todos los casos...
Download Results (CSV)