Una estrategia GRASP aplicada al Problema de Enrutamiento de Vehículos con Recogida y Entrega Simultánea

Autores/as

  • Alina Fernández Arias Departamento de Matemática, Universidad de La Habana, La Habana, Cuba
  • Sira Allende Alonso Departamento de Matemática Aplicada, Universidad de La Habana, La Habana, Cuba

Resumen

El Problema de Enrutamiento de Vehículos con Recogida y Entrega Simultánea es una extensión del Problema de Enrutamiento de Vehículos con Restricciones de Capacidad. El objetivo de este problema es diseñar rutas que satisfagan la demanda de recogida y entrega de los clientes en una única visita y se minimice el costo total de transportación. En este trabajo se presenta una estrategia de penalización basada en la metaheurística Greedy Randomized Adaptive Search Procedure. En la construcción de las soluciones iniciales se utilizó una simplificación del concepto de factibilidad y se empleó la Búsqueda por Entornos Variables Descendentes para realizar la búsqueda local en cada paso. En este trabajo se proponen diferentes variantes de GRASP. Los resultados computacionales muestran el comportamiento de los algoritmos desarrollados para el conjunto de prueba descrito por Salhi y Nagy.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

SP Anbuudayasankar and K Mohandas. Mixed-integer linear programming for vehicle routing problem with simultaneous delivery and pick-up with maximum routelength. The International Journal of Applied Management and Technnology, 6(1):31–52, 2007.

R Baldacci, M Batarra, and D Vigo. The vehicle routing problem: latest advances and new challenges, chapter Routing heterogeneous fleet of vehicles, pages 3–28. Springer, 2008.

J-F Chen and T-H Wu. Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society, 57(5):579–587, 2006.

M Dell’Amico, G Righini, and M Salani. A branchand-price approach to the vehicle routing problem with simultaneous distribution and collection. Transportation Science, 40(2):235–247, 2006.

J. Dethloff. Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR Spektrum, 23:79–96, 2001.

J Dréo, A Pétrowski, and E Taillard. Metaheuristics for Hard Optimization. Springer, 2006.

A Fernández-Arias. Problema de enrutamiento de vehículos con recogida y entrega simultánea considerando una flota heterogénea. Master’s thesis, Facultad de Matemática y Computación. Universidad de La Habana, 2010.

F.P Goksal, I Karaoglan, and F Altiparmk. A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers and Industrial Engineering, 65:39–53, 2013.

P Hansen and N Mladenovic. Variable neighborhood search: Principles and applications. European Journal of Operational Research, (130):449–467, 2001.

P Hansen, N Mladenovic, and JA Moreno-Pérez. Búsqueda de entorno variable. Revista Iberoamericana de Inteligencia Artificial, (19):72–92, 2003.

H Min. The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Reseach, 23A(5):377–386, 1989.

O Polat, Kalayci C-B, O Kulak, and H-O Gunther. A perturbation based variable neighborhood search heuristic for solving the vehicle routing problem with simultaneous pickup and delivery with time limit. European Journal of Operational Research, pages 369–382, 2015.

R Rosenthal. A GAMS Tutorial. www.gams.com.

S Salhi and G Nagy. A cluster insertion heuristic for the single and multiple depot vehicle routing problem with backhauling. The Journal of the Operational Research Society, 50(10):1034–1042, 1999.

A Subramanian and L Cabral. An ils based heuristic for the vehicle routing problem with simultaneous pickup and delivery and time limit. In J van Hemert and C Cotta, editors, EvoCOP, pages 135–146. Springer-Verlag, 2008.

F-A Tang-Montané and R-D Galvao. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers and Operations Reseach, 33:595–619, 2006.

A-S Tasan andMGen. A genetic based approach to vehicle routing problem with simultaneous pick-up and deliveries. Computers and Industrial Engieneering, 62:755–761, 2012.

P Toth and D Vigo. The vehicle routing problem. SIAM, Monograph on Discrete Mathematics and Applications, 9, 2002.

E Zachariadis, C Tarantilis, and C Kiranoudis. A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service. Expert System with Applications, 36:1070–1081, 2009.

E Zachariadis, C Tarantilis, and C Kiranoudis. An adaptive memory methodology for the vehicle routing problem with simultaneous delivery and pick-up service. Expert System with Applications, 36:1070–1081, 2010.

Descargas

Publicado

2017-06-01

Cómo citar

[1]
Fernández Arias, A. y Allende Alonso, S. 2017. Una estrategia GRASP aplicada al Problema de Enrutamiento de Vehículos con Recogida y Entrega Simultánea. Ciencias matemáticas. 31, 1 (jun. 2017), 1–8.

Número

Vol. 31 Núm. 1: Junio, 2017

Sección

Artículo Original

Licencia

Derechos de autor 2024 Ciencias Matemáticas

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Esta licencia permite copiar y redistribuir el material en cualquier medio o formato bajo los siguientes términos: se debe dar crédito de manera adecuada, no se puede hacer uso del material con propósitos comerciales, y si remezcla, transforma o crea a partir del material, no podrá distribuir el material modificado. Bajo la licencia mencionada, los autores mantienen los derechos de autor de su trabajo.