Proposal for an open vehicle routing model in a health-care institution
DOI:
https://doi.org/10.18041/1900-3803/entramado.2.4761Keywords:
Heuristics, vehicle routing, algorithm, COVRPAbstract
This research article presents an optimization model based on the application of two heuristics for a real situation of routing a fleet of vehicles of an Institution Provider of Health Services (IPS) to transport their patients. A quantitative study was carried out by applying the heuristics of the nearest neighbor and that of the modified nearest neighbor as this type of routing is of the COVRP type, for its initials in English: capacitated open vehicle routing problem. The cost table, the distance matrix construction algorithm and the heuristic algorithms are presented. The results indicate that the nearest neighbor heuristic offers a solution with a lower cost than that of the modified nearest neighbor since the savings would be 7.34% and 6.05% with respect to the current cost.
Downloads
References
AKSEN, Deniz; ÖZYURT, Zeynet; ARAS, Necati. Open vehicle routing problem with driver nodes and time deadlines. In: Journal of the Operational Research Society. 2007, vol. 58, no.9, p. 1223-1234. https://doi.org/10.1057/palgrave.jors.2602249
ASHOURI, Maryam; YOUSEFIKHOSHBAKHT, Majid. A combination of meta-heuristic and heuristic algorithms for the VRP, OVRP and VRP with simultaneous pickup and delivery. In: BRAIN. Broad Research in Artificial Intelligence and Neuroscience, 2017, vol. 8, no.2, p.81–95. Disponible en http://www.edusoft.ro/brain/index.php/brain/article/view/691
ATEFI, Reza; SALARI, Majid; COELHO, Leandro, RENAUD, Jacques. The open vehicle routing problem with decoupling points. In: European Journal of Operational Research, 2018, vol. 265, no.1, p. 316-327. https://doi.org/10.1016/j.ejor.2017.07.033
BAUER, Joanna; LYSGAARD, Jens. The offshore wind farm array cable layout problem: a planar open vehicle routing problem. In: Journal of the Operational Research Society, 2015, vol. 66, no. 3, p. 360-368. https://doi.org/10.1057/jors.2013.188
BEKTAS, Tolga; ELMASTAS, Seda. Solving school bus routing problems through integer programming. In: Journal of the Operational Research Society, 2007, vol. 58, no.12, p.1599-1604. https://doi.org/10.1057/palgrave.jors.2602305
BEN ATKINSON, J. A vehicle-scheduling system for delivering school meals. In: Journal of the Operational Research Society, 1990, vol. 41, no 8, p. 703–711. Disponible en https://link.springer.com/article/10.1057/jors.1990.99
CAO, Erbao; LAI, Mingyong. The open vehicle routing problem with fuzzy demands. In: Expert Systems with Applications, 2010, vol. 37, no. 3, p.2405–2411. https://doi.org/10.1016/j.eswa.2009.07.021
CAO, Erbao; LAI, Mingyong, YANG, Hongming. Open vehicle routing problem with demand uncertainty and its robust strategies. In: Expert Systems with Applications, 2014, vol. 41, no. 7, p. 3569–3575. https://doi.org/10.1016/j.eswa.2013.11.004
CHEN, Ping; DONG, Xingye, XIAO, Jianhua. Study on split delivery open vehicle routing problem within two splits. In: Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD), 2016 12th International Conference on, IEEE, 2016, p.724–728. https://doi:10.1109/FSKD.2016.7603264
CLARKE, Geoff, WRIGHT, J.W. Scheduling of vehicles from a central depot to a number of delivery points. In: Operations research, 1964, vol. 12, no. 4, p. 568–581. https://doi.org/10.1287/opre.12.4.568
DANTZIG, George; FULKERSON, Delbert; JOHNSON, Selmer. Solution of a large-scale traveling salesman problem. In: Journal of the operations research society of America, 1954, vol. 2, no. 4, p.393–410. https://doi.org/10.1287/opre.2.4.393
DANTZIG, George; RAMSER, John. The truck-dispatching problem. In: Management Science, 1959, vol. 6, no. 1, p. 80–91. https://doi.org/10.1287/mnsc.6.1.80
DERIGS, Ulrich; REUTER, K. A simple and efficient tabu search heuristic for solving the open vehicle routing problem. In: Journal of the Operational Research Society. 2009, vol. 60, no.12, p.1658–1669.
https://doi.org/10.1057/jors.2008.107
EPPEN, Gary D. Investigación de operaciones en la ciencia administrativa: construcción de modelos para la toma de decisiones con hojas de cálculo electrónicas. Pearson Educación, 2000.
FENGHUA, Duan; XIAONIAN, He. On open vehicle routing problem with soft time windows and tabu search. In: Logistics Research and Practice in China-Proceedings of 2008. Disponible en https://pdfs.semanticscholar.org/0b6a/d9937b37c64c8fd6ebad49d1bb90d1b82961.pdf
FU, Zhuo; WRIGHT, Mike. Train plan model for British rail freight services through the channel tunnel. In: Journal of the Operational Research Society. 1994, vol. 45, no.4, p.384–391. Disponible en https://link.springer.com/article/10.1057/jors.1994.57
FU, Zhuo. The capacitated open vehicle routing problem and its tabu search algorithm. In: Systems Engineering-theory & Practice. 2004, vol. 3, p.123–128. Disponible en http://en.cnki.com.cn/Article_en/CJFDTOTAL-XTLL200403021.htm
GE, Bin; HAN, Yue; BIAN, Chen. Hybrid ant colony optimization algorithm for solving the open vehicle routing problem. In: Journal of Computers. 2016, vol.27, no.4, p. 41–54. https://doi:10.3966/199115592016122704004
GE, Hongyi, ZHEN, Tong, JIANG, Yuying, CHE, Yi. An intelligent solution for open vehicle routing problem in grain logistics. In: Advances in Wireless Networks and Information Systems. 2010, vol.72 p.389–396. Disponible en https://link.springer.com/chapter/10.1007/978-3-642-14350-2_49
GUO, Jinling, YU, Shiwey. A hybrid algorithm for open vehicle routing optimization of coal mines material. In: Applied Mechanics and Materials. 2012, vol.197, p. 455–461. Disponible en https://www.scientific.net/AMM.197.455
GURPREETSINGH, Er; DHIR, Vijay. Open vehicle routing problem by ant colony optimization. In: International Journal of Advanced Computer Science and Applications. 2014, vol. 5, p. 63-68. Disponible en https://pdfs.semanticscholar.org/9e57/ac344b3d2f42e6c02b27536d23cbf40a02e5.pdf
HEDAR, Abdel; ABDALLAH, Mohammed. Applying tabu search in finding an efficient solution for the OVRP. In: International Journal of Open Problems in Computer Science and Mathematics (IJOPCM) 2014, vol.7, no.4, p.36–51. Disponible en http://www.i-csrs.org/Volumes/ijopcm/vol.7/7.4.4.pdf
HOSSEINABADI, Ali; KARDGAR, Maryam; SHOJAFAR, Mohammad; SHAMSHIRBAND, Shahab; ABRAHAM, Ajith. Gravitational search algorithm to solve open vehicle routing problem. In: Innovations in Bio-Inspired Computing and Applications. 2016, p. 93–103. https://doi.org/10.1007/978-3-319-28031-8_8
HOSSEINABADI, Ali; VAHIDI, Javad; BALAS, Valentina; MIRKAMALI, Seyed. OVRP_GELS: solving open vehicle routing problem using the gravitational emulation local search algorithm. In: Neural Computing and Applications. 2016, p.1–14. https:// doi:10.1007/s00521-016-2608-x
HU, Fengjun; WU, Fan. Diploid hybrid particle swarm optimization with differential evolution for open vehicle routing problem. In: Intelligent Control and Automation 2010. p. 2692–2697. https://doi:10.1109/WCICA.2010.5554989
JINHUI, Ge; YING, Xiong; HONGZHEN, Wang. An improved TS for the open vehicle routing problem with soft time windows. In: Computational Intelligence and Design, 2012. p.382–385. https://doi:10.1109/ISCID.2012.102
KRITZINGER, Stefanie; DOERNER, Karl; TRICOIRE, Fabien; HARTL, Richard. Adaptive search techniques for problems in vehicle routing, Part II: A numerical comparison. In: Yugoslav Journal of Operations Research. 2016, vol. 25.no.2, p. 3-31. Disponible en http://yujor.fon.bg.ac.rs/index.php/yujor/article/view/453
LABADIE, Nacima; PRINS, Christian; PRODHON, Caroline. Metaheuristics for Vehicle Routing Problems. John Wiley & Sons. 2016.
LALLA-RUIZ, Eduardo, et al. An improved formulation for the multi-depot open vehicle routing problem. In: OR spectrum. 2016, vol.38, no.1, p.175–187. https://doi.org/10.1007/s00291-015-0408-9
LALLA-RUIZ, Eduardo; VOß, Stefan. A note on a hybrid genetic algorithm for the multi-depot open vehicle routing problem. 2016. Disponible en https://www.bwl.uni-hamburg.de/iwi/forschung/projekte/papernote.pdf
LETCHFORD, Adam, LYSGAARD, Jens, EGLESE, Richard. A branch-and-cut algorithm for the capacitated open vehicle routing problem. In: Journal of the Operational Research Society. 2007, vol. 58, no.12, p.1642–1651. https://doi.org/10.1057/palgrave.jors.2602345
LI, Leon; FU, Zhuo. The school bus routing problem: a case study. In: Journal of the Operational Research Society. 2002, vol. 53, no.5, p. 552–558. https://doi.org/10.1057/palgrave.jors.2601341
LI, Feiyue; GOLDEN, Bruce; WASIL, Edward. The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. In: Computers & operations research. 2007, vol. 34, no.10, p.2918–2930. https://doi.org/10.1016/j.cor.2005.11.018
LI, Xiang; LEUNG, Stephen; TIAN, Peng. A multistart adaptive memory-based tabu search algorithm for the heterogeneous fixed fleet open vehicle routing problem. In: Expert Systems with Applications. 2012, vol.39, no.1, p.365–374. https://doi.org/10.1016/j.eswa.2011.07.025
LIU, Ran; JIANG, Zhibin; GENG, Na. Erratum to: A hybrid genetic algorithm for the multi-depot open vehicle routing problem. In: OR Spectrum. 2014, vol. 36, no.2, p. 423–424. http://dx.doi.org/10.1007/s00291-012-0289-0.
LIU, Ran; JIANG, Zhibin; GENG, Na. A hybrid genetic algorithm for the multi-depot open vehicle routing problem. In: OR spectrum. 2014, vol.36, no.2, p.401–421. http://dx.doi.org/10.1007/s00291-013-0346-3.
LÓPEZ-SÁNCHEZ, Ana, et al. A multi-start algorithm for a balanced real-world open vehicle routing problem. In: European Journal of Operational Research. 2014, vol. 238, no.1, p.104–113. https://doi.org/10.1016/j.ejor.2014.04.008
MARINAKIS, Yannis; MARINAKI, Magdalene. Bumble bees mating optimization algorithm for the vehicle routing problem. In: Handbook of Swarm Intelligence. 2011, p. 347–369. https://doi.org/10.1007/978-3-642-17390-5_15
MARINAKIS, Yannis; MARINAKI, Magdalene. A honey bees mating optimization algorithm for the open vehicle routing problem. In: Proceedings of the 13th annual conference on Genetic and evolutionary computation. 2011, p. 101–108. https://doi.org/10.1145/2001576.2001591
MIRHASSANI, S.A; ABOLGHASEMI, N. A particle swarm optimization algorithm for open vehicle routing problem. In: Expert Systems with Applications. 2011, vol.38, no.9, p. 11547–11551. https://doi.org/10.1016/j.eswa.2011.03.032
NADERIPOUR, Mansoureh; ALINAGHIAN, Mahdi. Measurement, evaluation and minimization of CO2, NOx, and CO emissions in the open time dependent vehicle routing problem. In: Measurement. 2016, vol.90, p. 443–452. https://doi.org/10.1016/j.measurement.2016.04.043
NOROUZI, Narges, et al. A new multi-objective competitive open vehicle routing problem solved by particle swarm optimization. In: Networks and Spatial Economics. 2012, vol.12, no.4, p.609–633. https://doi.org/10.1007/s11067-011-9169-4
ÖZYURT, Zeynep; AKSEN, Deniz; ARAS, Necati. Open vehicle routing problem with time deadlines: Solution methods and an application. In: Operations Research Proceedings 2005. 2006, p. 73–78. https://doi.org/10.1007/3-540-32539-5_12
PAN, Lijum, FU, Z. A clone selection algorithm for the open vehicle routing problem. In: Genetic and Evolutionary Computing, 2009. p. 786–790. https://doi.org/10.1109/WGEC.2009.174
PENNA, Puca; SUBRAMANIAN, Anand; OCHI, Luiz. An iterated local search heuristic for open vehicle routing problems. In: Congreso Latino-Iberoamericano de Investigacion operativa y Simposio Brasileiro de Pesquisa Operacional. 2012, p. 4504-4514. Disponible en http://www.din.uem.br/sbpo/sbpo2012 pdf/arq0141.pdf
PESSOA, Artur; DE ARAGÃO, Marcus; UCHOA, Eduardo. Robust branch-cut-and-price algorithms for vehicle routing problems. In: The vehicle routing problem: Latest advances and new challenges. 2008, vol. 43, p.297–325. https://doi.org/10.1007/978-0-387-77778-8_14
PICHPIBUL, Tantikorn; KAWTUMMACHAI, Ruengsak. A heuristic approach based on clarke-wright algorithm for open vehicle routing problem. In: The Scientific World Journal 2013. http://dx.doi.org/10.1155/2013/874349
PISINGER, David, ROPKE, Stefan. A general heuristic for vehicle routing problems. In: Computers & operations research. 2007, vol.34, no.8, p.2403–2435. https://doi.org/10.1016/j.cor.2005.09.012
RAFF, Samuel. Routing and scheduling of vehicles and crews: The state of the art. In: Computers & Operations Research. 1983, vol.10, no.2, p.195–211. https://doi.org/10.1016/0305-0548(83)90030-8
REDI, A.P.; MAGHFIROH, Meilinda; VINCENT, Yu. An improved variable neighborhood search for the open vehicle routing problem with time windows. In: Industrial Engineering and Engineering Management (IEEM), 2013. p. 1641-1645. https://doi.org/ 10.1109/IEEM.2013.6962688
REINHOLZ, Andreas; SCHNEIDER, Holger. A hybrid (1+1)-evolutionary strategy for the open vehicle routing problem. In: Advances in Metaheuristics. Springer. 2013, p. 127–141. https://doi.org/10.1007/978-1-4614-6322-1_8
REN, Chunyu. Research on single and mixed fleet strategy for open vehicle routing problem. In: Journal of Software. 2011, vol. 6, no.10, p. 2076–2081. https://doi.org/10.4304/jsw.6.10.2076-2081
REPOUSSIS, Panagiotis, et al. A web-based decision support system for waste lube oils collection and recycling. In: European Journal of Operational Research. 2009b, vol. 195, no.3, p.676–700. https://doi.org/10.1016/j.ejor.2007.11.004
REPOUSSIS, Panagiotis, et al. A hybrid evolution strategy for the open vehicle routing problem. In: Computers & Operations Research. 2010, vol. 37, no.3, p.443–455. https://doi.org/10.1016/j.cor.2008.11.003
REPOUSSIS, Panagiotis; TARANTILIS, Christos; IOANNOU, George. The open vehicle routing problem with time windows. In: Journal of the Operational Research Society. 2007, vol. 58, no.3, p.355–367. https://doi.org/10.1057/palgrave.jors.2602143
RUIZ, Hector; RUIZ, M.; ALCARAZ, M.V. Manuel. Problemas de rutas abiertas de vehículos con restricciones de capacidad heterogéneas. En: Revista de Difusión Técnico Científica de Instituto Tecnológico de Nogales.2016, p. 5-7 Disponible en http://depiitn.edu.mx/wp-content/uploads/2016/02/Tema-2-Problemas-de-Rutas-Abiertas-de-Vehiculos.pdf
RUSSELL, Robert; CHIANG, Wenchyuan; ZEPEDA, David. Integrating multi-product production and distribution in newspaper logistics. In: Computers&Operations Research. 2008, vol. 35, no.5, p.1576–1588. https://doi.org/10.1016/j.cor.2006.09.002
RUSSELL, Robert. A constraint programming approach to designing a newspaper distribution system. In: International Journal of Production Economics. 2013, vol. 145, no.1, p.132–138. https://doi.org/10.1016/j.ijpe.2013.01.018
SALARI, Mahid; TOTH, Paolo; TRAMONTANI, Andrea. An ILP improvement procedure for the open vehicle routing problem. In: Computers & Operations Research. 2010, vol. 37, no.12, p.2106–2120. https://doi.org/10.1016/j.cor.2010.02.010
SARIKLIS, Dimitrios; POWELL, Susan. A heuristic method for the open vehicle routing problem. In: Journal of the Operational Research Society. 2000, vol. 51, no.5, p. 564–573. https://doi.org/10.1057/palgrave.jors.2600924
SCÁRDUA, Rayane, et al. Planejamento do transporte de empregados por uma frota de ônibus fretada por meio de um modelo matemático baseado no open vehicle routing problem (OVRP). En: TRANSPORTES. 2016, vol. 24, no.3, p. 20–28. https://doi.org/10.14295/transportes.v24i3.1089
SCHOPKA, Kristian; KOPFER, Herbert. An adaptive large neighborhood search for the reverse open vehicle routing problem with time windows. In: Logistics Management. 2016, p. 243–257. https://doi.org/10.1007/978-3-319-20863-3_18
SCHRAGE, Linus. Formulation and structure of more complex/realistic routing and scheduling problems. In: Networks. 1981, vol. 11, no.2, p.229–232. https://doi.org/10.1002/net.3230110212
SEDIGHPOUR, Mohammad, et al. Solving the open vehicle routing problem by a hybrid ant colony optimization. In: Kuwait Journal of Science. 2014, vol. 41, no.3, p.139-162. Disponible en: https://journalskuwait.org/kjs/index.php/KJS/article/view/42/49
SEVKLI, Aise; GÜLER, Bekir. A multi-phase oscillated variable neighbourhood search algorithm for a real-world open vehicle routing problem. In: Applied Soft Computing. 2017, vol. 58, p.128–144. https://doi.org/10.1016/j.asoc.2017.04.045
SHAMSHIRBAND, Shabad, et al. OVRP_ICA: An imperialist-based optimization algorithm for the open vehicle routing problem. In: International Conference on Hybrid Artificial Intelligence Systems, Springer.2015, p. 221–233. https://doi.org/10.1007/978-3-319-19644-2_19
SIAMAC, Universidad Nacional de Colombia Sede Amazonía, 2010. Tips y trucos de GIS. Disponible en: www.unal.edu.co/siamac/sig/tips.html.
SOTO, Maria; SEVAUX, Marc; ROSSI, André; REINHOLZ, Andreas. Multiple neighborhood search, tabu search and ejection chains for the multi-depot open vehicle routing problem. In: Computers & Industrial Engineering. 2017, vol. 107, p.211–222. https://doi.org/10.1016/j.cie.2017.03.022
SUBRAMANIAN, Anand; UCHOA, Eduardo; OCHI, Luiz. A hybrid algorithm for a class of vehicle routing problems. In: Computers & Operations Research. 2013, vol. 40, no.10, p. 2519–2531. https://doi.org/10.1016/j.cor.2013.01.013
SYSLO, Marciej M.; DEO, N.; KOWALIK, J. S. Discrete optimization with pascal programs. Prentice-Hall, Englewood Cliffs, NJ. 1983
TAMBUNAN, Hardi; MAWENGKANG, Herman. Mixed Integer Programming Model for open Vehicle Routing Problem with Fleet and driver Scheduling Considering Delivery and Pick-Up Simultaneously. In: International Journal on Recent and Innovation Trends in Computing and Communication. 2015, vol. 3, no.9, p.5508–5513. Disponible en https://pdfs.semanticscholar.org/78a4/743d839cb21d3777256b92dd0a95d162d830.pdf
TARANTILIS, Christos, et al. Solving the open vehicle routeing problem via a single parameter metaheuristic algorithm. In: Journal of the Operational Research Society. 2005, vol. 56, no.5, p. 588–596. https://doi.org/10.1057/palgrave.jors.2601848
TYASNURITA, Raras; ÖZCAN, Ender; JOHN, Robert. Learning heuristic selection using a time delay neural network for open vehicle routing. In: Evolutionary Computation (CEC). 2017, p.1474–1481. https://doi.org/10.1109/CEC.2017.7969477
VINCENT, F. Yu; JEWPANYA, Parida; REDI, AAN Perwira. Open vehicle routing problem with cross-docking. In: Computers & Industrial Engineering. 2016, vol. 94, p. 6-17. https://doi.org/10.1016/j.cie.2016.01.018
WANG, Shuxia; XIONG, Ying; WANG, Zengqiang. A Study on the Taboo Search Algorithm for the Open Vehicle Routing Problem with Hard Time Windows. In: Proceedings of the 2012 International Conference on Computer Application and System Modeling. 2012. Disponible en https://www.atlantis-press.com/proceedings/iccasm-12/2568
WANG, Xuping; ZHAN, Hongxin; ZHANG, Jun. Research of Oil Product Secondary Distribution Optimization Based on Collaborative Distribution. In: Procedia Computer Science. 2015, vol. 60, p. 1367-1376. Disponible en https://www.sciencedirect.com/journal/procedia-computer-science/vol/60/suppl/C?page-size=100&page=2
YANG, Jiao-ping; ZHAO, Hong-xia. Research on multi-enterprise allied open vehicle routing problem and its genetic algorithm. In: Multimedia Technology (ICMT). 2010, p.1-4. https://doi.org/ 10.1109/ICMULT.2010.5629841
YILMAZ, Duygu, et al. Introducing the MCHF/OVRP/SDMP: Multicapacitated/Heterogeneous Fleet/Open Vehicle Routing Problems with Split Deliveries and Multiproducts. In: The Scientific World Journal. 2014, vol. 2014. http://dx.doi.org/10.1155/2014/515402
YOUSEFIKHOSHBAKHT, Majid; DIDEHVAR, Farzad; RAHMATI, Farhad; SEDIGHPOUR, M. An effective imperialist competitive algorithm for solving the open vehicle routing problem. In: Journal of Transportation Research. 2012, vol. 9, p. 83–95. Disponible en http://www.sid.ir/En/Journal/ViewPaper.aspx?ID=245327
YOUSEFIKHOSHBAKHT, Majid; DIDEHVAR, Farzad; RAHMATI, Farhad. A mixed integer programming formulation for the heterogeneous fixed fleet open vehicle routing problem. In: Journal of Optimization in Industrial Engineering. 2015, vol. 8, no.18, p.37–46. Disponible en http://www.qjie.ir/article_219_ebb2cd520ac0626659d9b38e3b93b4d1.pdf
YOUSEFIKHOSHBAKHT, Majid; DOLATNEJAD, Azam. A column generation for the heterogeneous fixed fleet open vehicle routing problem. In: International Journal of Production Management and Engineering. 2017, vol.5, p.55–71. http://dx.doi.org/10.4995/ijpme.2017.5916
YOUSEFIKHOSHBAKHT, Majid, et al. A modified column generation to solve the heterogeneous fixed Fleet open vehicle routing problem. In: Journal of Engineering 2016. http://dx.doi.org/10.1155/2016/5692792
YU, Shiwei.; DING, Chang.; ZHU, Ding. A hybrid GA–TS algorithm for open vehicle routing optimization of coal mines material. In: Expert Systems with Applications. 2011, vol. 38, no.8, p. 10568–10573. https://doi.org/10.1016/j.eswa.2011.02.108
ZACHARIADIS, Emmanouil; KIRANOUDIS, Chris. An open vehicle routing problem metaheuristic for examining wide solution neighborhoods. In: Computers & Operations Research. 2010, vol. 37, no.4, p.712–723. https://doi.org/10.1016/j.cor.2009.06.021
ZHANG, Jingling; ZHAO, Yanwey; PENG, Dianjun; WANG, Wanliang. A hybrid quantum-inspired evolutionary algorithm for open vehicle routing problem. In: Advanced Intelligent Mechatronics. 2009, p.839–844. https://doi.org/ 10.1109/AIM.2009.5229905
ZHAO, Yan; ZHANG, J.L; PENG, D.J. Open vehicle routing problem using quantum evolutionary algorithm. In: Advanced Materials Research. 2010, vol. 102-104, p. 807–812. https://doi.org/10.4028/www.scientific.net/AMR.102-104.807
