Revue: | Dyna (Medellín) |
Base de datos: | PERIÓDICA |
Número de sistema: | 000415498 |
ISSN: | 0012-7353 |
Autores: | Kawashima, Makswell Seyiti1 Rangel, Socorro1 Litvinchev, Igor2 Infante, Luis2 |
Instituciones: | 1Universidade Estadual Paulista "Julio de Mesquita Filho", Sao Jose do Rio Preto, Sao Paulo. Brasil 2Universidad Autónoma de Nuevo León, San Nicolás de los Garza, Nuevo León. México |
Año: | 2015 |
Periodo: | Jun |
Volumen: | 82 |
Número: | 191 |
Paginación: | 42-50 |
País: | Colombia |
Idioma: | Inglés |
Tipo de documento: | Artículo |
Enfoque: | Aplicado, descriptivo |
Resumen en español | En este artículo nosotros exploramos una formulación de flujo multiproductos para el Problema del Agente Viajero Asimétrico (ATSP) en la obtención de cotas duales de este problema. El procedimiento empleado es una variante del método relax and cut propuesto en la literatura que computa los multiplicadores lagrangianos asociados a las restricciones de eliminación de subrutas preservando la optimalidad de los multiplicadores asociados a las restricciones de asignación. Los resultados obtenidos con la experimentación computacional son alentadores y muestran que el algoritmo propuesto genera buenas cotas duales con un tiempo de ejecución bajo |
Resumen en inglés | In this paper we explore the multi-commodity flow formulation for the Asymmetric Traveling Salesman Problem (ATSP) to obtain dual bounds. The procedure employed is a variant of a relax and cut procedure proposed in the literature that computes the Lagrangean multipliers associated to the subtour elimination constraints preserving the optimality of the multipliers associated to the assignment constraints. The results obtained by the computational study are encouraging and show that the proposed algorithm generated good dual bounds for the ATSP with a low execution time |
Disciplinas: | Ingeniería |
Palabras clave: | Ingeniería industrial, Distribución de mercancías, Modelos numéricos, Relajación lagrangiana |
Keyword: | Engineering, Industrial engineering, Commodities distribution, Numerical models, Lagrangian relaxation |
Texte intégral: | Texto completo (Ver HTML) |