Caso aplicativo del Mercader Viajero

DETERMINACIÓN DE UNA RUTA DE RECOJO Y ENTREGA DE ROPA PARA UNA LAVANDERÍA INDUSTRIAL USANDO EL ALGORITMO DE LIN Y KERNIGHAN

(Horario 0832, Profesor: Eduardo Carbajal)

MAURICIO ALEJANDRO ALCA PALOMINO

Pontificia Universidad Católica del Perú, Lima, Perú, a20111076@pucp.pe

HAROLD ZEGARRA TORRES

Pontificia Universidad Católica del Perú, Lima, Perú, harold.zegarra@pucp.edu.pe

ALFREDO ALEJANDRO UCAÑAN RAMIREZ

Pontificia Universidad Católica del Perú, Lima, Perú, alfredo.ucanan@pucp.pe

DIEGO ALONSO ARIZMENDI MIRANDA

Pontificia Universidad Católica del Perú, Lima, Perú, daarizmendi@pucp.pe

Abstract

In view of the need for SAC Industrial Laundry Antarctica S.A.C., with location in the city of Lurigancho, Lima, Peru, from having to collect clothes from different parts of the city and then return them to these points with clothes and washed. This research seeks to minimize the total cost of the fuel and the time used for transport to go and reach each collection point, by minimizing the distance to cover to get back to the laundry. The method used can be generalized to any other case in which a transport network where they seek to minimize the distances traveled through a defined number of points required before returning to the starting point is taken.

Keywords: transportation route, delivery routes, resource optimization, optimal routing distance, demanding points.

Resumen

En vista de la necesidad de la Lavandería Industrial Antártida S.A.C., con ubicación en la ciudad de Lurigancho, Lima, Perú, de tener que recoger prendas de distintos puntos de la ciudad y retornarlas posteriormente lavadas a dichas localizaciones. Esta investigación busca minimizar el costo total del combustible, además del uso del tiempo empleado por el transporte al recorrer y llegar hasta cada punto de acopio, por medio de la optimización de la distancia a recorrer hasta llegar de regreso a la lavandería. El método a usar se podrá generalizar en cualquier otro caso en el cual se tenga una red de transporte en donde se busque minimizar las distancias recorridas, pasando por un número definido de puntos obligatorios para luego regresar al punto inicial de partida.

Palabras claves: ruta de transporte, rutas de entrega, optimización de recursos, distancia óptima de ruteo, puntos de demandas.

Introducción:

En el distrito de Lurigancho se encuentra ubicada la Lavandería Antártida S.A. la cual se encarga de procesar prendas de manera industrial. Se dedica a los retoques sobre textiles, principalmente en Jeans. Los procesos son en su mayoría húmedos como los de tintura en prenda, lavado en prenda y acabados en prenda o como se les llama en el rubro industrial: tratamientos de lavandería. La empresa dirige sus servicios exclusivamente a las entidades dedicadas al rubro textil las cuales están situadas principalmente dentro del emporio comercial de Gamarra, sin embargo debido a su gran exigencia de calidad, puntualidad y competitividad la empresa cuenta con clientes en los distritos de La Victoria, El Agustino, San Luis, Lurigancho, Santa Anita y Ate Vitarte.

Dentro del ámbito textil, la Lavandería Antártida S.A.C cuenta en la actualidad con 5 años de experiencia y es gracias a su apuesta e inversión por la innovación tecnológica, preparación y capacitación del personal, que en su largo recorrido ha podido competir con otras empresas del mismo rubro, en precio, calidad y servicio.

La empresa posee un camión marca Volkswagen del año 2002 el cual trabaja diariamente recogiendo las prendas de todos sus clientes. Tiene además un compromiso con el medio ambiente ya que desde su fundación se ha preocupado por cumplir e implementar las normas vigentes. Es por esta razón sumado al alto costo de transporte (en el mes de Julio tuvo un gasto de más de S/. 5300 en combustible) que la empresa desea optimizar sus rutas de acopio de prendas de los trece clientes que posee.

La distribución de todos los clientes se muestran en el siguiente gráfico realizado en Google Maps, la tachuela indica la ubicación de la Lavandería Antártida S.A.C. y los círculos la de los clientes. Como se observa, las fábricas textiles se encuentran dispersas en puntos alejados donde en muchos casos no existen vías directas entre ellas por lo que se tienen que tomar rutas que hacen regresar un y otra vez a varios puntos de manera desorganizada.

Lo que se busca finalmente con esta investigación es encontrar un único camino que empiece y termine en la  lavandería pasando por todos los puntos de recojo de la manera más eficiente posible.

[pic 1]^[a]

Figura 1

Fuente:

Marco teórico:

Investigación de Operaciones según Winston (2008), puede ser interpretado como aquel método científico interdisciplinario para la solución de problemas que presentan una interacción compleja, dinámica y subjetiva de hombres, métodos y sistemas.

En primer lugar, es necesario definir  el concepto de programación lineal. Se entiende por PL a la técnica matemática que consiste en seguir una serie de métodos y procedimientos que permiten resolver problemas de optimización. Debido a la complejidad para problemas de varias variables, se suele enfocar en los problemas de PL bidimensionales, los de 2 variables, debido a que presentan un desarrollo más sencillo en comparación a las demás.

Para una adecuada resolución del problema previamente se debe definir factores que vayan a respaldar el análisis a desarrollar como por ejemplo la reducción de costos, variaciones en la producción, etc.; aunque previamente se debe de definir si la problemática a resolver es un problema de optimización o un problema de decisión. Además, el problema en si debe permitir elaborar algún modelo matemático que describa al problema tal cual.

Los problemas de redes surgen en varios y muy distintos contextos tales como, el transporte, redes eléctricas, de sistemas y de comunicaciones. De los distintos ámbitos mencionados se puede encontrar similitudes, como el hecho de que cada red está compuesta por estaciones unidas por líneas entre punto y punto.

Un caso particular del problema de redes es el “problema del viajante de comercio” trata de un viajero de comercio que ha de visitar n ciudades una y sólo una vez cada una, comenzando y finalizando en su propia ciudad. Conociendo el coste de ir de cada una de las ciudades a otra, se ha de determinar el recorrido de coste mínimo.

Para la resolución de un problema del tipo TPS existen varios algoritmos, entre los cuales están:

        ALGORITMO CODISIOSO

        El algoritmo codicioso realiza los siguientes pasos para construir un tour:

...