Ejercicios Optimizacion

UN ALGORITMO PARA LA OPTIMIZACIÓN DE RUTAS DE TRANSPORTE
A. Garrido
E. Onaindía
Dpto. Sistemas Informáticos y Computación
Universidad Politécnica de Valencia
Camino de Vera s/n 46071
Valencia, Spain.
{agarridot, onaindia}@dsic.upv.es
Palabras clave: optimización, algoritmo, logística, transporte.
Keywords: optimisation, algorithm, logistics, transport.
RESUMEN. Este artículo presenta unalgoritmo para la resolución de un problema de asignación de rutas y destinos en una flota de vehículos. El objetivo es minimizar los costes asociados
al transporte satisfaciendo una serie de restricciones. Para la resolución de dicho problema se
han empleado técnicas de búsqueda inteligente por profundización iterativa que permiten ir
refinando progresivamente la calidad de una solucióninicial dada. Así, cuanto mayor sea el
tiempo de optimización, mejor será el resultado obtenido. Por lo tanto, si el algoritmo se ejecuta durante el tiempo necesario devolverá la solución óptima. Gracias al refinamiento progresivo de la solución, si en un instante determinado se dispone de una solución que satisface
las necesidades previstas, aun a pesar de no ser la óptima, se puede interrumpir elproceso de
búsqueda. Adicionalmente, los resultados de las pruebas realizadas proporcionan una idea
acerca del ahorro económico alcanzado.
ABSTRACT. This paper presents an algorithm to solve a route allocation problem in a fleet of
vehicles. The objective is to minimise the transport costs while guaranteeing the problem
constraints satisfaction. The problem has been tackled by usingiterative-deepening search
techniques, which allow to progressively refine the quality of a given initial solution. In this
way, the longer optimization process is executed, the better the obtained result will be.
Eventually, the algorithm will return the optimal solution. This approach allows the user to
interrupt the process when a solution satisfies the company requirements even though it isnonoptimal solution. Moreover, the results obtained in the experiments show the important
economic savings achieved.
1.- INTRODUCCIÓN.
Tradicionalmente, el estudio de problemas sobre distribución física ha sido tratado mediante
técnicas de Programación Dinámica (Bellman 62, Cormen 90) y de Investigación Operativa
(Winston 94). Los problemas clásicos (Ford 74), como el problema del viajante decomercio,
obtención de la ruta más corta, etc., utilizan, en su mayoría, la teoría de grafos y la
programación lineal. Sin embargo, a medida que la complejidad y número de restricciones
implicadas en el problema aumenta, se hace más difícil su resolución mediante este tipo de
técnicas. Por tanto, resulta necesario utilizar técnicas alternativas (Gottinger 90) para los problemas en los que, como éste,la complejidad y la cantidad de combinaciones posibles hacen
complicado su tratamiento mediante técnicas de Investigación Operativa. Por otra parte, un
estudio detallado del problema reveló la imposibilidad de aplicar técnicas de programación
dinámica. Aunque el coste global de realizar el transporte puede ser mínimo, no ocurre lo

mismo con los costes parciales; esto es, la formulación delproblema no cumple el principio de
optimalidad. Por todo esto, y dada la complejidad del problema, se optó por la aplicación de
técnicas de búsqueda por profundización iterativa para lograr, no sólo una exploración
inteligente del árbol de búsqueda sino, además, la obtención de soluciones subóptimas
incrementales al problema. El método empleado es una variación de la técnica de ramificación ypoda (Brassard 90), donde se consideran todas las alternativas posibles pero sólo se expanden
aquéllas que puedan conducir a la solución óptima.
Debido a la complejidad y al elevado número de posibilidades en la obtención de las rutas, el
tiempo necesario para encontrar la solución óptima del problema puede resultar excesivo para
las necesidades de la empresa. En consecuencia surge la...