Desempeño de las técnicas de agrupamiento para resolver el problema de ruteo con múltiples depósitos

  • Eliana M. Toro-Ocampo Universidad Tecnológica de Pereira, Pereira
  • Andrés H. Domínguez-Castaño Universidad Tecnológica de Pereira, Pereira
  • Antonio H. Escobar-Zuluaga Universidad Tecnológica de Pereira, Pereira
Palabras clave: Búsqueda local iterada, optimización combinatoria, ruteo con múltiples depósitos, red de distribución, técnicas de agrupamiento

Resumen

El problema de ruteo de vehículos considerando múltiples depósitos es clasificado como NP duro, cuya solución busca determinar simultáneamente las rutas de un conjunto de vehículos, atendiendo un conjunto de clientes con una demanda determinada. La función objetivo del problema consiste en minimizar el total de la distancia recorrida por las rutas, teniendo en cuenta que todos los clientes deben ser atendidos cumpliendo restricciones de capacidad de depósitos y vehículos. En este artículo se propone una metodología híbrida que combina las técnicas aglomerativas de clusterización para generar soluciones iniciales con un algoritmo de búsqueda local iterada, iterated location search (ILS) para resolver el problema. Aunque en trabajos previos se proponen los métodos de clusterización como estrategias para generar soluciones de inicio, en este trabajo se potencia la búsqueda sobre el sistema de información obtenido después de aplicar el método de clusterización. Además se realiza un extenso análisis sobre el desempeño de las técnicas de clusterización y su impacto en el valor de la función objetivo. El desempeño de la metodología propuesta es factible y efectivo para resolver el problema en cuanto a la calidad de las respuestas y los tiempos computacionales obtenidos, sobre las instancias de la literatura evaluadas.

Biografía del autor/a

Eliana M. Toro-Ocampo, Universidad Tecnológica de Pereira, Pereira
MSc. en Investigación de Operaciones y Estadística, Facultad de Ingeniería Industrial, Universidad Tecnológica de Pereira, Pereira
Andrés H. Domínguez-Castaño, Universidad Tecnológica de Pereira, Pereira
MSc. en Ingeniería Eléctrica, Universidad Tecnológica de Pereira, Pereira
Antonio H. Escobar-Zuluaga, Universidad Tecnológica de Pereira, Pereira
PhD. en Ingeniería Eléctrica, Escuela de Tecnología Eléctrica, Universidad Tecnológica de Pereira, Universidad Tecnológica de Pereira, Pereira

Referencias bibliográficas

K. F. Doerner and V. Schmid, “Survey: Matheuristics for rich vehicle routing problems,” in 7th International Workshop on Hybrid Metaheuristics, HM 2010, vol. 6373 LNCS, M. Blesa, C. Blum, G. Raidl, A. Roli, and M. Samples, Eds. Berlin: Springer, 2010, pp. 206–221.

J. R. Montoya-Torres, J. López Franco, S. Nieto Isaza, H. Felizzola Jiménez, and N. Herazo-Padilla, “A literature review on the vehicle routing problem with multiple depots,” Comput. Ind. Eng., vol. 79, pp. 115–129, Jan. 2015.

P. Cassidy and H. Bennett, “Vehicle System Scheduling,” OR Soc., vol. 23, no. 2, pp. 151–163, 2015.

M. Ball, B. Golden, and A. Assad, “Planning for Truck Fleet Size in the Presence of a Common-Carrier Option,” Decis. Sci., vol. 14, no. 1, pp. 103–120, 2007.

B. L. Golden and E. a. Wasil, “OR Practice--Computerized Vehicle Routing in the Soft Drink Industry,” Oper. Res., vol. 35, no. 1, pp. 6–17, 1987.

M. Fisher, R. Greenfield, R. Jaikumar, and J. Lester, “A computerized Vehicle Routing Application,” Interfaces (Providence)., vol. 4, pp. 42–52, 12AD.

W. J. Bell, L. M. Dalberto, M. L. Fisher, a. J. Greenfield, R. Jaikumar, P. Kedia, R. G. Mack, and P. J. Prutzman, “Improving the Distribution of Industrial Gases with an On-Line Computerized Routing and Scheduling Optimizer,” Interfaces (Providence)., vol. 13, no. 6, pp. 4–23, 1983.

A. G. G. Brown, C. J. Ellis, G. W. Graves, and D. Ronen, “of the dispatching are to minimize cost of delivered product, to balance the workload among the company trucks, and to load the maximum weight on a truck while adhering to all laws. The important,” vol. 17, no. 1, pp. 2–4, 1987.

J. Pooley, “Integrated Production and Distribution Facility Planning at Ault Foods,” Interfaces (Providence)., vol. 24, no. 4, pp. 113–121, 1994.

R. Baldacci and A. Mingozzi, “A unified exact method for solving different classes of vehicle routing problems,” Math. Program., vol. 120, no. 2, pp. 347–380, Sep. 2009.

N. Christofides, A. Mingozzi, and P. Toth, “Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations,” Math. Program., vol. 20, no. 1, pp. 255–282, Dec. 1981.

R. Baldacci, E. Bartolini, a. Mingozzi, and a. Valletta, “An Exact Algorithm for the Period Routing Problem,” Oper. Res., vol. 59, no. 1, pp. 228–241, 2011.

C. Contardo and R. Martinelli, “A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints,” Discret. Optim., vol. 12, pp. 129–146, May 2014.

S. Salhi and M. Sari, “A multi-level composite heuristic for the multi-depot vehicle fleet mix problem,” Eur. J. Oper. Res., vol. 103, no. 1, pp. 95–112, Nov. 1997.

E. M. Toro O., A. H. Escobar Z., and M. Granada E., “Literature Review On The Vehicle Routing Problem In The Green Transportation Context,” Luna Azul, vol. 42, no. 42, pp. 362–387, Dec. 2015.

I. D. Giosa, I. L. Tansini, and I. O. Viera, “New assignment algorithms for the multi-depot vehicle routing problem,” J. Oper. Res. Soc., vol. 53, no. 9, pp. 977–984, Sep. 2002.

G. Nagy and S. Salhi, “Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries,” Eur. J. Oper. Res., vol. 162, no. 1, pp. 126–141, Apr. 2005.

C.-G. Lee, M. a. Epelman, C. C. White, and Y. a. Bozer, “A shortest path approach to the multiple-vehicle routing problem with split pick-ups,” Transp. Res. Part B Methodol., vol. 40, no. 4, pp. 265–284, May 2006.

B. Crevier, J.-F. Cordeau, and G. Laporte, “The multi-depot vehicle routing problem with inter-depot routes,” Eur. J. Oper. Res., vol. 176, no. 2, pp. 756–773, Jan. 2007.

G. Jeon, H. R. Leep, and J. Y. Shim, “A vehicle routing problem solved by using a hybrid genetic algorithm,” Comput. Ind. Eng., vol. 53, no. 4, pp. 680–692, Nov. 2007.

W. Ho, G. T. S. Ho, P. Ji, and H. C. W. Lau, “A hybrid genetic algorithm for the multi-depot vehicle routing problem,” Eng. Appl. Artif. Intell., vol. 21, no. 4, pp. 548–557, Jun. 2008.

G. Clarke and J. W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Oper. Res., vol. 12, no. 4, pp. 568–581, Aug. 1964.

P. Surekha and S. Sumathi, “Solution To Multi-Depot Vehicle Routing Problem Using Genetic Algorithms,” World Appl. Program., vol. 1, no. 3, pp. 118–131, 2011.

J.-F. Cordeau and M. Maischberger, “A parallel iterated tabu search heuristic for vehicle routing problems,” Comput. Oper. Res., vol. 39, no. 9, pp. 2033–2050, Sep. 2012.

T. Vidal and T. G. G. Crainic, “A hybrid genetic algorithm for multidepot and periodic vehicle routing problems,” Oper. …, vol. 60, no. 3, pp. 611–624, 2012.

A. Subramanian, E. Uchoa, and L. S. Ochi, “A hybrid algorithm for a class of vehicle routing problems,” Comput. Oper. Res., vol. 40, no. 10, pp. 2519–2531, Oct. 2013.

J. W. Escobar, R. Linfati, P. Toth, and M. G. Baldoquin, “A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem,” J. Heuristics, vol. 20, no. 5, pp. 483–509, Oct. 2014.

A. C. Rencher, A Review Of “Methods of Multivariate Analysis, ,” vol. 37, no. 11. 2005.

S. Barreto, C. Ferreira, J. Paixão, and B. S. Santos, “Using clustering analysis in a capacitated location-routing problem,” Eur. J. Oper. Res., vol. 179, no. 3, pp. 968–977, Jun. 2007.

A. Subramanian, “Heuristic, Exact and Hybrid Approaches for Vehicle Routing Problems.” Universidade Federal Fluminense, Niteroi, Sao Pablo, pp. 60–69, 2012.

Cómo citar
[1]
E. M. Toro-Ocampo, A. H. Domínguez-Castaño, y A. H. Escobar-Zuluaga, «Desempeño de las técnicas de agrupamiento para resolver el problema de ruteo con múltiples depósitos», TecnoL., vol. 19, n.º 36, pp. 49–62, ene. 2016.

Descargas

Los datos de descargas todavía no están disponibles.
Publicado
2016-01-30
Sección
Artículos de investigación

Métricas