A Cluster-First Route-Second Heuristic Approach to Solve The Multi-Trip Periodic Vehicle Routing Problem
DOI:
https://doi.org/10.22219/JTIUMM.Vol20.No2.172-181Keywords:
vehicle routing, cluster first route second, multi trip, tabu search, periodicAbstract
This paper discusses periodic vehicle routing problems that allow vehicles to travel on multiple trips in a single day. It is known as the Multi-Trip Periodic Vehicles (MTPVRP) Problem Route. Cluster-first route-second (CFRS) heuristics to solve MTPVRP was proposed in this study. In phase 1, customers were divided into clusters using the formulation of integer programming. Phase 2 determined the route of the cluster and verified that the total journey time to visit the trips does not exceed the working hours of the vehicle. Implementing the heuristic CFRS to solve the real problem faced by the Liquefied petroleum gas (LPG) distributor shows that the procedure could provide a better routing solution.
Downloads
Author Biography
Annisa Kesy Garside, Industrial Engineering Department, Faculty of Engineering, University of Muhammadiyah Malang, Indonesia
PROFILE
- PROFILE SCOPUS : https://www.scopus.com/authid/detail.uri?authorId=57190378485
- PROFILE GOOGLE SCHOLAR : https://scholar.google.co.id/citations?user=XG2otqIAAAAJ&hl=en
References
[1] G. B. Dantzig and J. H. Ramser, "The truck dispatching problem," Management science, vol. 6, pp. 80-91, 1959. https://doi.org/10.1287/mnsc.6.1.80.
[2] B. Eksioglu, A. V. Vural, and A. Reisman, "The vehicle routing problem: A taxonomic review," Computers & Industrial Engineering, vol. 57, pp. 1472-1483, 2009. https://doi.org/10.1016/j.cie.2009.05.009.
[3] C. Lin, K. L. Choy, G. T. Ho, S. H. Chung, and H. Lam, "Survey of green vehicle routing problem: past and future trends," Expert systems with applications, vol. 41, pp. 1118-1138, 2014. https://doi.org/10.1016/j.eswa.2013.07.107.
[4] S. Srivatsa Srinivas and M. Gajanand, "Vehicle routing problem and driver behaviour: a review and framework for analysis," Transport reviews, vol. 37, pp. 590-611, 2017. https://doi.org/10.1080/01441647.2016.1273276.
[5] A. Imran and L. Okdinawati, "Adaptation Of The Variable Neighborhood Search Heuristic To Solve The Vehicle Routing Problem," Jurnal Teknik Industri, vol. 12, pp. 10-15, 2012. https://doi.org/10.22219/JTIUMM.Vol12.No1.10-15.
[6] B. E. Gillett and L. R. Miller, "A heuristic algorithm for the vehicle-dispatch problem," Operations research, vol. 22, pp. 340-349, 1974. https://doi.org/10.1287/opre.22.2.340.
[7] M. L. Fisher and R. Jaikumar, "A generalized assignment heuristic for vehicle routing," Networks, vol. 11, pp. 109-124, 1981. https://doi.org/abs/10.1002/net.3230110205.
[8] R. Dondo and J. Cerdá, "A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows," European Journal of Operational Research, vol. 176, pp. 1478-1507, 2007. https://doi.org/10.1016/j.ejor.2004.07.077.
[9] K. Shin and S. Han, "A centroid-based heuristic algorithm for the capacitated vehicle routing problem," Computing and Informatics, vol. 30, pp. 721-732, 2012. http://www.cai.sk/ojs/index.php/cai/article/viewArticle/192.
[10] F. Cakir, W. N. Street, and B. W. Thomas, "Revisiting Cluster First, Route Second for the Vehicle Routing Problem," no. August, 2015.
[11] S. E. CÖMERT, H. R. YAZGAN, I. Sertvuran, and H. ŞENGÜL, "A new approach for solution of vehicle routing problem with hard time window: an application in a supermarket chain," Sādhanā, vol. 42, pp. 2067-2080, 2017. https://doi.org/10.1007/s12046-017-0754-1.
[12] D. Hiquebran, A. Alfa, J. Shapiro, and D. Gittoes, "A revised simulated annealing and cluster-first route-second algorithm applied to the vehicle routing problem," Engineering Optimization, vol. 22, pp. 77-107, 1993. https://doi.org/10.1080/03052159308941327.
[13] D. A. P. Putri, "Vehicle Routing Problem Dengan Time Window Untuk Multiple Product Dan Multiple Route Menggunakan Algoritma Sequential Insertion," Jurnal Teknik Industri, vol. 17, pp. 22-30, 2016. https://doi.org/10.22219/JTIUMM.Vol17.No1.22-30.
[14] A. Mingozzi, R. Roberti, and P. Toth, "An exact algorithm for the multitrip vehicle routing problem," INFORMS Journal on Computing, vol. 25, pp. 193-207, 2013. https://doi.org/10.1287/ijoc.1110.0495.
[15] B. Fleischmann, "The vehicle routing problem with multiple use of vehicles," Fachbereich Wirtschaftswissenschaften, Universität Hamburg, 1990.
[16] É. D. Taillard, G. Laporte, and M. Gendreau, "Vehicle routeing with multiple use of vehicles," Journal of the Operational research society, vol. 47, pp. 1065-1070, 1996. https://doi.org/10.1057/jors.1996.133.
[17] R. J. Petch and S. Salhi, "A multi-phase constructive heuristic for the vehicle routing problem with multiple trips," Discrete Applied Mathematics, vol. 133, pp. 69-92, 2003. https://doi.org/10.1016/S0166-218X(03)00434-7.
[18] D. Cattaruzza, N. Absi, and D. Feillet, "Vehicle routing problems with multiple trips," 4OR, vol. 14, pp. 223-259, 2016. https://doi.org/10.1007/s10288-016-0306-2.
[19] A. M. Campbell and J. H. Wilson, "Forty years of periodic vehicle routing," Networks, vol. 63, pp. 2-15, 2014. https://doi.org/10.1002/net.21527.
[20] E. J. Beltrami and L. D. Bodin, "Networks and vehicle routing for municipal waste collection," Networks, vol. 4, pp. 65-94, 1974. https://doi.org/10.1002/net.3230040106.
[21] R. Russell and W. Igo, "An assignment routing problem," Networks, vol. 9, pp. 1-17, 1979. https://doi.org/abs/10.1002/net.3230090102.
[22] G. Clarke and J. W. Wright, "Scheduling of vehicles from a central depot to a number of delivery points," Operations research, vol. 12, pp. 568-581, 1964. https://doi.org/10.1287/opre.12.4.568.
[23] N. Christofides and J. E. Beasley, "The period routing problem," Networks, vol. 14, pp. 237-256, 1984. https://doi.org/10.1002/net.3230140205.
[24] J.-F. Cordeau, G. Laporte, and A. Mercier, "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational research society, vol. 52, pp. 928-936, 2001. https://doi.org/10.1057/palgrave.jors.2601163.
[25] J. F. Cordeau, M. Gendreau, and G. Laporte, "A tabu search heuristic for periodic and multi‐depot vehicle routing problems," Networks: An International Journal, vol. 30, pp. 105-119, 1997. https://doi.org/10.1002/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO;2-G.
[26] P. Parthanadee and R. Logendran, "Periodic product distribution from multi-depots under limited supplies," Iie Transactions, vol. 38, pp. 1009-1026, 2006. https://doi.org/10.1080/07408170600575454.
[27] E. Angelelli and M. G. Speranza, "The periodic vehicle routing problem with intermediate facilities," European journal of Operational research, vol. 137, pp. 233-247, 2002. https://doi.org/10.1016/S0377-2217(01)00206-5.
[28] F. Alonso, M. J. Alvarez, and J. E. Beasley, "A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions," Journal of the Operational Research Society, vol. 59, pp. 963-976, 2008. https://doi.org/10.1057/palgrave.jors.2602405.
[29] A. Rusdiansyah and D.-b. Tsao, "An integrated model of the periodic delivery problems for vending-machine supply chains," Journal of Food Engineering, vol. 70, pp. 421-434, 2005. https://doi.org/10.1016/j.jfoodeng.2004.05.073.
[30] T. E. Saputro and A. Prihatina, "Perencanaan Jadwal dan Rute Distribusi Rokok untuk Menekan Total Biaya Transportasi," Jurnal Teknik Industri, vol. 13, pp. 151-157, 2012. https://doi.org/10.22219/JTIUMM.Vol13.No2.151-157.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2019 Annisa Kesy Garside, Nabila Rohmatul Laili
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
