Experimental evaluation of a linear programming model for solving the vehicle routing problem (VRP)
DOI:
https://doi.org/10.26439/interfases2018.n011.2956Keywords:
linear programming, complexity, routing, vehicles, delivery pointsAbstract
This article aims to propose a quantitative criterion to evaluate the feasibility of implementing solutions based on linear programming for solving the vehicle routing problem (VRP). An experimental design was used to measure the relative solution time with a proposed linear programming model. The sample was randomized employing three dispersion scenarios of the delivery points: poorly scattered, scattered and very scattered. A linear programming solver was used to determine the time and iterations necessary for solving the model. As a result, the solution time was found in terms of the number of delivery points and the number of iterations for the proposed scenarios, and the time required to solve the problem was predicted using the proposed model. The research concludes with a proposal of the number of viable points to be solved by linear programming.
Downloads
References
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.
Downloads
Published
Issue
Section
License
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under an Attribution 4.0 International (CC BY 4.0) License. that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Last updated 03/05/21
