Evaluación experimental de un modelo de programación lineal para el problema de ruteo de vehículos (VRP)

  • Juan Manuel Machuca-de-Pina Universidad de Lima (Perú)
  • Michael Dorin University of St. Thomas (Estados Unidos)
  • Alicia-Isabel García-Yi Universidad de Lima (Perú)
Palabras clave: programación lineal, complejidad, ruteo, vehículos, puntos de entrega

Resumen

El presente articulo tiene como objetivo proponer un criterio cuantitativo para evaluar la viabilidad de implementar soluciones basadas en programacion lineal para resolver el problema de ruteo de vehiculos (VRP). Se utilizo un diseno experimental para medir el tiempo relativo de solucion con un modelo de programacion lineal propuesto. La muestra utilizada fue aleatoria utilizando tres escenarios de dispersion de puntos de entrega: poco dispersos, dispersos y muy dispersos. Se utilizo un solver de programacion lineal con el objetivo de determinar el tiempo y las iteraciones necesarias para encontrar la solucion del modelo. Como resultado se encontro el tiempo de solucion en funcion de la cantidad de puntos de entrega, la cantidad de iteraciones para los escenarios propuestos y se pronostica el tiempo necesario para resolver el problema utilizando el modelo propuesto. Se concluye con una propuesta de cantidad de puntos viables para ser resueltos por programacion lineal.

Descargas

La descarga de datos todavía no está disponible.

Biografía del autor/a

Juan Manuel Machuca-de-Pina, Universidad de Lima (Perú)

Ingeniero industrial por la Universidad de Lima, con estudios de maestría en docencia y gestión universitaria por la Universidad Marcelino Champagnat. Ha realizado diversas actividades de asesoría en temas logísticos y sistemas de información comercial. Actualmente se desempeña como docente en la Facultad de Ingeniería y Arquitectura, y en la Facultad de Ciencias Empresariales y Económicas de la Universidad de Lima.

Michael Dorin, University of St. Thomas (Estados Unidos)

Titulado en ciencias matemático-computacionales por la Universidad de Wisconsin y magíster en ciencias por la Universidad Estatal Metropolitana, Minneapolis, Minnesota. Cuenta con treinta años de experiencia en diseño y desarrollo de software profesional, especializado en cifrado y seguridad de datos. Conocedor de múltiples lenguajes de programación: C, C++, C#, Java, Perl, PHP, Python, TTCN-3, Assembly, Visual Basic, Pascal y FORTRAN. Actualmente es docente en la Universidad St. Thomas en Minnesota y anteriormente en la Universidad Estatal Metropolitana. Se desempeñó como ingeniero senior de diseño de software en Dell Inc., ingeniero senior en investigación y desarrollo de Software en Garmin International, ingeniero senior de Software en Honeywell, y como ingeniero de Software y presidente de EDI Enterprises Inc.

Alicia-Isabel García-Yi, Universidad de Lima (Perú)

Ingeniera industrial por la Universidad de Lima y magíster en marketing por la Universidad Peruana de Ciencias Aplicadas, con más de 25 años de experiencia laboral. Es docente de cursos de operaciones y marketing de la Facultad de Ciencias Empresariales y Económicas. Ha realizado investigaciones sobre biocomercio y preferencias del consumidor dentro de la gestión de la cadena de suministro, y ha publicado artículos en Latin American Journal of Business Management y en la Conferencia Anual de Investigación en Agricultura Tropical y Subtropical, gestión de recursos naturales y desarrollo rural (Tropentag) en la que participan universidades y otras instituciones europeas.

Citas

Alvarez, P., Lerga, I., Serrano, A. y Faulin, J. (2017). Considering Congestion Costs and Driver Behaviour into Route Optimisation Algorithms in Smart Cities (pp. 39-50). DOI:10.1007/978-3-319-59513-9_5.

Arboleda-Zúñiga, J., López, A. X. y Lozano, Y. L. (2016). El problema de ruteo de vehículos [VRP] y su aplicación en medianas empresas colombianas. Ingenium, 10(27), 29-36.

Azzara, C. V. (2010). Questionnaire Design for Business Research: Beyond Linear Thinking-an Interactive

Approach. Mustang: Tate Publishing & Enterprises.

Baldacci, R., Hadjiconstantinou, E. y Mingozzi, A. (2004). An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Operations Research, 52(5), 723-738. DOI:10.1287/opre.1040. 0111.

Cook, S. A. (1983). An overview of computational complexity. Communications of the ACM (Vol. 26).

Dantzig, G. B. (2002). Linear Programming. Operations Research, 50(1), 42-47. DOI:10.1287/opre.50.1.42.17798.

Daza, J. M., Montoya, J. R. y Narducci, F. (2009). Resolución de problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases. Eia, 1(12), 23-38.

Gattorna, J. (2009). Cadena de abastecimientos dinámicas: Cómo movilizar la empresa alrededor de

lo que los clientes quieren (1ª. ed.). Bogotá: Ecoe Ediciones.

Golden, B. L., Wasil, E. A., Kelly, J. P. y Chao, I.-M. (1998). The impact of metaheuristics on solving the vehicle routing problem: Algorithms, problem sets, and computational results. En Fleet Management and Logistics (pp. 33-56). Boston, MA: Springer US. DOI:10.1007/978-1-4615-5755-5_2.

Han, H. y Cueto, E. P. (2015). Waste Collection Vehicle Routing Problem: A Literature Review. PROMET - Traffic & Transportation, 27(4), 345-358. https://doi.org/10.7307/ptt.v27i4.1616.

Landero, R. y González, M. (2011). Estadística con SPSS y metodología de la investigación (1ª. ed.).México: Trillas.

Laporte, G. (2009). Fifty Years of Vehicle Routing. Transportation Science, 43(4), 408-416. DOI:10.1287/trsc.1090.0301

Limeños pierden el 25 % de sus ingresos por el tránsito vehicular. (2017). La República. Recuperado

de: http://larepublica.pe/economia/865633-limenos-pierden-el-25-de-sus-ingresos-porel-transito-vehicular

Lovelock, C. y Wirtz, J. (2009). Marketing de servicios (6ª. ed.). México: Pearson Educación.

Machuca, J. y Taquía, J. (2009). Balanza comercial de los combustibles líquidos derivados del petróleo mediante dinámica de sistemas y simulación. Ingeniería Industrial, 27, 61-79.

Onut, S., Kamber, M. R. y Altay, G. (2014). A heterogeneous fleet vehicle routing model for solving the LPG distribution problem: A case study. Journal of Physics: Conference Series, 490. DOI:10.1088/1742-6596/490/1/012043.

Ministerio de Transportes y Comunicaciones (2009). Decreto Supremo No. 017-2009-MTC.

Srivatsa Srinivas, S. y Gajanand, M. S. (2017). Vehicle routing problem and driver behaviour: a review and framework for analysis. Transport Reviews, 37(5), 590-611. DOI:10.1080/01441647.2016.1273276.

Tzeng, G.-H., Cheng, H.-J., y Huang, T. D. (2007). Multi-objective optimal planning for designing relief delivery systems. Transportation Research Part E: Logistics and Transportation Review, 43(6), 673-686. DOI:10.1016/j.tre.2006.10.012.

Publicado
2018-12-03
Cómo citar
Machuca-de-Pina, J. M., Dorin, M., & García-Yi, A.-I. (2018). Evaluación experimental de un modelo de programación lineal para el problema de ruteo de vehículos (VRP). Interfases, 11(011), 103-117. https://doi.org/10.26439/interfases2018.n011.2956
Sección
Artículos de investigación