(Universitas Negeri Semarang, Indonesia)(2) Subiyanto Subiyanto
(Universitas Negeri Semarang, Indonesia)(3) Ulfah Mediaty Arief
(Universitas Negeri Semarang, Indonesia)*corresponding author
AbstractThis work aims to develop an enhanced Perturbation based Variable Neighborhood Search with Adaptive Selection Mechanism (PVNS ASM) to solve the capacitated vehicle routing problem (CVRP). This approach combined Perturbation based Variable Neighborhood Search (PVNS) with Adaptive Selection Mechanism (ASM) to control perturbation scheme. Instead of stochastic approach, selection of perturbation scheme used in the algorithm employed an empirical selection based on success rate of each perturbation scheme along the search. The ASM helped algorithm to get more diversification degree and jumping from local optimum condition using most successful perturbation scheme empirically in the search process. A comparative analysis with existing heuristics in the literature has been performed on 21 CVRP benchmarks. The computational results proof that the developed method is competitive and very efficient in achieving high quality solution within reasonable computation time.
KeywordsMeta-heuristics; Vehicle routing problem; Adaptive mechanism; Variable neighborhood search; Perturbation mechanism
|
DOIhttps://doi.org/10.26555/ijain.v4i3.244 |
Article metricsAbstract views : 3267 | PDF views : 477 |
Cite |
Full Text Download
|
References
[1] F. Alfredo Tang Montané, R. D. Galvão, A. T. Montané, and R. D. Galvão, “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service,” Comput. Oper. Res., vol. 33, no. 3, pp. 595–619, 2006, doi: https://doi.org/10.1016/j.cor.2004.07.009.
[2] J. Dethloff, “Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up,” OR Spektrum, vol. 23, no. 1, pp. 79–96, 2001, doi: https://doi.org/10.1007/PL00013346.
[3] G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Manage. Sci., vol. 6, no. 1, pp. 80–91, Oct. 1959, doi: https://doi.org/10.1287/mnsc.6.1.80.
[4] G. Nagy, N. A. Wassan, M. G. Speranza, and C. Archetti, “The vehicle routing problem with divisible deliveries and pickups,” Transp. Sci., vol. 49, no. 2, pp. 271–294, 2015, doi: https://doi.org/10.1287/trsc.2013.0501.
[5] R. Baldacci, P. Toth, and D. Vigo, “Exact algorithms for routing problems under vehicle capacity constraints,” Ann. Oper. Res., vol. 175, no. 1, pp. 213–245, Mar. 2010, doi: https://doi.org/10.1007/s10479-009-0650-0.
[6] P. Toth and D. Vigo, “The Granular Tabu Search and Its Application to the Vehicle-Routing Problem,” INFORMS J. Comput., vol. 15, no. 4, pp. 333–346, Nov. 2003, doi: https://doi.org/10.1287/ijoc.15.4.333.24890.
[7] C. Prodhon and C. Prins, “A survey of recent research on location-routing problems,” Eur. J. Oper. Res., vol. 238, no. 1, pp. 1–17, 2014, doi: https://doi.org/10.1016/j.ejor.2014.01.005.
[8] B. E. Gillett and L. R. Miller, “A Heuristic Algorithm for the Vehicle-Dispatch Problem,” Oper. Res., vol. 22, no. 2, pp. 340–349, Apr. 1974, doi: https://doi.org/10.1287/opre.22.2.340.
[9] M. L. Fisher and R. Jaikumar, “A generalized assignment heuristic for vehicle routing,” Networks, vol. 11, no. 2, pp. 109–124, 1981, doi: https://doi.org/10.1002/net.3230110205.
[10] Z. Fang, W. Tu, Q. Li, S.L. Saw, S. Chen, and B.Y. Chen, “A Voronoi neighborhood-based search heuristic for distance / capacity constrained very large vehicle routing problems,” Int. J. Geographic. Inf. Sci., vol. 27, no. 4, 2013, pp. 37–41, 2012, doi: https://doi.org/10.1080/13658816.2012.707319.
[11] F. Cakir, W. N. Street, and B. W. Thomas, “Revisiting Cluster First , Route Second for the Vehicle Routing Problem,” no. August, 2015, available at: https://pdfs.semanticscholar.org/2891/fc38fe7b52142701c63bbc85f0276501d6f3.pdf.
[12] M. C. Bouzid, A.H. Hacene, and S. Salhi, “An Integration of Lagrangian Split and VNS : The case of the Capacitated Vehicle Routing Problem,” Comput. Oper. Res., vol. 78, pp. 513-525, 2017, doi: https://doi.org/10.1016/j.cor.2016.02.009.
[13] S. E. Comert, H. R. Yazgan, S. Kır, and F. Yener, “A cluster first-route second approach for a capacitated vehicle routing problem: a case study,” Int. J. Procure. Manag., vol. 11, no. 4, p. 399, 2018, doi: https://doi.org/10.1504/IJPM.2018.092766.
[14] A. A. Khan, M. U. Khan, and M. Iqbal, “Multilevel Graph Partitioning Scheme to Solve Traveling Salesman Problem,” in 2012 Ninth International Conference on Information Technology - New Generations, Las Vegas, NV, 2012, pp. 458-463. doi: https://doi.org/10.1109/ITNG.2012.106.
[15] C. Walshaw, “A Multilevel Approach to the Travelling Salesman Problem,” Oper. Res., vol. 50, no. 5, pp. 751-922, 2002, doi: https://doi.org/10.1287/opre.50.5.862.373.
[16] C. Kloimüllner, P. Papazek, B. Hu, and G. R. Raidl, “A Cluster-First Route-Second Approach for Balancing Bicycle Sharing Systems,” 2015, pp. 439–446, doi: https://doi.org/10.1007/978-3-319-27340-2_55.
[17] D. Sariklis and S. Powell, “A heuristic method for the open vehicle routing problem,” J. Oper. Res. Soc., vol. 51, no. 5, pp. 564–573, May 2000, doi: https://doi.org/10.1057/palgrave.jors.2600924.
[18] P. Toth and D. Vigo, Vehicle routing: problems, methods, and applications. Philadelphia, PA, USA, PA: Society for Industrial and Applied Mathematics, 2014, available at: https://epubs.siam.org/doi/abs/10.1137/1.9781611973594.fm.
[19] G. Clarke and J. W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Oper. Res., vol. 12, no. 4, pp. 519-643, 1964, doi: https://doi.org/10.1287/opre.12.4.568.
[20] R. H. Mole and S. R. Jameson, “A Sequential Route-Building Algorithm Employing a Generalised Savings Criterion,” Oper. Res. Q., vol. 27, no. 2, p. 503, 1976, doi: https://doi.org/10.2307/3008819.
[21] N. Christofides and S. Eilon, “An Algorithm for the Vehicle- dispatching Problem,” Oper. Res., vol. 20, no. 3, pp. 309–318, 1969, doi: https://doi.org/10.1057/jors.1969.75.
[22] S. W. Lin, Z. J. Lee, K. C. Ying, and C. Y. Lee, “Applying hybrid meta-heuristics for capacitated vehicle routing problem,” Expert Syst. Appl., vol. 36, no. 2 PART 1, pp. 1505–1512, 2009, doi: https://doi.org/10.1016/j.eswa.2007.11.060.
[23] V. F. Yu, A. A. N. P. Redi, C. L. Yang, E. Ruskartina, and B. Santosa, “Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem,” Appl. Soft Comput. J., vol. 52, pp. 657–672, 2017, doi: https://doi.org/10.1016/j.asoc.2016.10.006.
[24] B. L. Golden, E. A. Wasil, J. P. Kelly, and I.-M. Chao, “The Impact of Metaheuristics on Solving the Vehicle Routing Problem: Algorithms, Problem Sets, and Computational Results,” in Fleet Management and Logistics, Boston, MA: Springer US, 1998, pp. 33–56, doi: https://doi.org/10.1007/978-1-4615-5755-5_2.
[25] F. Li, B. Golden, and E. Wasil, “Very large-scale vehicle routing: new test problems, algorithms, and results,” Comput. Oper. Res., vol. 32, no. 5, pp. 1165–1179, May 2005, doi: https://doi.org/10.1016/j.cor.2003.10.002.
[26] C. D. Tarantilis, C. T. Kiranoudis, and V. S. Vassiliadis, “A list based threshold accepting algorithm for the capacitated vehicle routing problem,” Int. J. Comput. Math., vol. 79, no. 5, pp. 537–553, 2002, doi: https://doi.org/10.1080/00207160210948.
[27] D. Mester and O. Bräysy, “Active guided evolution strategies for large-scale vehicle routing problems with time windows,” Comput. Oper. Res., vol. 32, no. 6, pp. 1593–1614, Jun. 2005, doi: https://doi.org/10.1016/j.cor.2003.11.017.
[28] M. Reed, A. Yiannakou, and R. Evering, “An ant colony algorithm for the multi-compartment vehicle routing problem,” Appl. Soft Comput. J., vol. 15, pp. 169–176, 2014, doi: https://doi.org/10.1016/j.asoc.2013.10.017.
[29] C. B. C. B. Kalayci and C. Kaya, “An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery,” Expert Syst. Appl., vol. 66, pp. 1–18, 2016, doi: https://doi.org/10.1016/j.eswa.2016.09.017.
[30] M. Polacek, R. F. Hartl, K. Doerner, and M. Reimann, “A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows,” J. Heuristics, vol. 10, no. 6, pp. 613–627, Dec. 2004, doi: https://doi.org/10.1007/s10732-005-5432-5.
[31] J. Kytöjoki, T. Nuortio, O. Bräysy, and M. Gendreau, “An efficient variable neighborhood search heuristic for very large scale vehicle routing problems,” Comput. Oper. Res., vol. 34, no. 9, pp. 2743–2757, Sep. 2007, doi: https://doi.org/10.1016/j.cor.2005.10.010.
[32] K. Fleszar, I. H. Osman, and K. S. Hindi, “A variable neighbourhood search algorithm for the open vehicle routing problem,” Eur. J. Oper. Res., vol. 195, no. 3, pp. 803–809, 2009, doi: https://doi.org/10.1016/j.ejor.2007.06.064.
[33] S. Akpinar, “Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem,” Expert Syst. Appl., vol. 61, pp. 28–38, 2016, doi: https://doi.org/10.1016/j.eswa.2016.05.023.
[34] J. F. Sze, S. Salhi, and N. Wassan, “A hybridisation of adaptive variable neighbourhood search and large neighbourhood search: Application to the vehicle routing problem,” Expert Syst. Appl., vol. 65, pp. 383–397, 2016, doi: https://doi.org/10.1016/j.eswa.2016.08.060.
[35] N. Mladenović and P.Hansen, “Variable neighborhood search,” Comput. Oper. Res., vol. 24, no. 11, pp. 1097–1100, 1997, doi: https://doi.org/10.1016/S0305-0548(97)00031-2.
[36] C. Blum, “Hybrid metaheuristics in combinatorial optimization: A tutorial,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 7505 LNCS, no. 6, pp. 1–10, 2012, doi: https://doi.org/10.1007/978-3-642-33860-1_1.
[37] O. Polat, C. B. Kalayci, O. Kulak, and H.-O. Günther, “A perturbation based variable neighborhood search heuristic for solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery with Time Limit,” Eur. J. Oper. Res., vol. 242, no. 2, pp. 369–382, 2015, doi: https://doi.org/10.1016/j.ejor.2014.10.010.
[38] J. Li, P. M. Pardalos, H. Sun, J. Pei, and Y. Zhang, “Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups,” Expert Syst. Appl., vol. 42, no. 7, pp. 3551–3561, 2015, doi: https://doi.org/10.1016/j.eswa.2014.12.004.
[39] B. Eksioglu, A. V. Vural, and A. Reisman, “The vehicle routing problem: A taxonomic review,” Comput. Ind. Eng., vol. 57, no. 4, pp. 1472–1483, Nov. 2009, doi: https://doi.org/10.1016/j.cie.2009.05.009.
[40] G. Laporte, R. Musmanno, and F. Vocaturo, “An Adaptive Large Neighbourhood Search Heuristic for the Capacitated Arc-Routing Problem with Stochastic Demands,” Transp. Sci., vol. 44, no. 1, pp. 125–135, Feb. 2010, doi: https://doi.org/10.1287/trsc.1090.0290.
[41] P. Toth and D. Vigo, Vehicle Routing Problem. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2014, doi: https://doi.org/10.1137/1.9781611973594.
[42] K. Braekers, K. Ramaekers, and I. Van Nieuwenhuyse, “The vehicle routing problem: State of the art classification and review,” Comput. Ind. Eng., vol. 99, pp. 300–313, Sep. 2016, doi: https://doi.org/10.1016/j.cie.2015.12.007.
[43] İ. K. Altınel and T. Öncan, “A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem,” J. Oper. Res. Soc., vol. 56, no. 8, pp. 954–961, 2005, doi: https://doi.org/10.1057/palgrave.jors.2601916.
[44] P. Hansen and N. Mladenovic, “Variable neighborhood search: Principles and applications,” Eur. J. Oper. Res., vol. 130, no. 3, pp. 449–467, 2001, doi: https://doi.org/10.1016/S0377-2217(00)00100-4.
[45] P. Hansen, N. Mladenović, and J. A. Moreno Pérez, “Variable neighbourhood search: Methods and applications,” Ann. Oper. Res., vol. 175, no. 1, pp. 367–407, 2010, doi: https://doi.org/10.1007/s10479-009-0657-6.
[46] T. Doyuran and B. Çatay, “A robust enhancement to the Clarke–Wright savings algorithm,” J. Oper. Res. Soc., vol. 62, no. 1, pp. 223–231, 2011, doi: https://doi.org/10.1057/jors.2009.176.
[47] V. C. Hemmelmayr, K. F. Doerner, and R. F. Hartl, “A variable neighborhood search heuristic for periodic routing problems,” Eur. J. Oper. Res., vol. 195, no. 3, pp. 791–802, 2009, doi: https://doi.org/10.1016/j.ejor.2007.08.048.
[48] F. Pan, C. Ye, K. Wang, and J. Cao, “Research on the Vehicle Routing Problem with Time Windows Using Firefly Algorithm,” J. Comput., vol. 8, no. 9, pp. 2256–2261, 2013, doi: https://doi.org/10.4304/jcp.8.9.2256-2261.
[49] F. P. Goksal, I. Karaoglan, and F. Altiparmak, “A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery,” Comput. Ind. Eng., vol. 65, no. 1, pp. 39–53, 2013, doi: https://doi.org/10.1016/j.cie.2012.01.005.
[50] M. Avci and S. Topaloglu, “An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries,” Comput. Ind. Eng., vol. 83, pp. 15–29, 2015, doi: https://doi.org/10.1016/j.cie.2015.02.002.
[51] J. Crispim and J. Brandão, “Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls,” J. Oper. Res. Soc., vol. 56, no. 11, pp. 1296–1302, 2005, doi: https://doi.org/10.1057/palgrave.jors.2601935.
[52] Y. Gajpal and P. Abad, “An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup,” Comput. Oper. Res., vol. 36, no. 12, pp. 3215–3223, 2009, doi: https://doi.org/10.1016/j.cor.2009.02.017.
[53] P. Shaw, “Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems,” in Principles and Practice of Constraint Programming --- CP98: 4th International Conference, CP98 Pisa, Italy, October 26--30, 1998 Proceedings, M. Maher and J.-F. Puget, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998, pp. 417–431, doi: https://doi.org/10.1007/3-540-49481-2_30.
[54] G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt, and G. Dueck, “Record Breaking Optimization Results Using the Ruin and Recreate Principle,” J. Comput. Phys., vol. 159, no. 2, pp. 139–171, Apr. 2000, doi: https://doi.org/10.1006/jcph.1999.6413.
[55] A. M. Campbell and M. Savelsbergh, “Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems,” Transp. Sci., vol. 38, no. 3, pp. 369–378, 2004, doi: https://doi.org/10.1287/trsc.1030.0046.
[56] P. Augerat, J. Belenguer, E. Benavent, A. Coberan, D. Naddef, and G. Rinaldi, “Computational results with a branch-and-cut code for the capacitated vehicle routing problem,” Rapp. Rech. - IMAG, vol. 95, no. 949–M, p. 30, 1998, available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.718.7812.
[57] M. A. Mohammed et al., “Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution,” J. Comput. Sci., vol. 21, pp. 232–240, 2017, doi: https://doi.org/10.1016/j.jocs.2017.04.012.
[58] M. Amous, S. Toumi, B. Jarboui, and M. Eddaly, “A variable neighborhood search algorithm for the capacitated vehicle routing problem,” Electron. Notes Discret. Math., vol. 58, pp. 231–238, 2017, doi: https://doi.org/10.1016/j.endm.2017.03.030.
[59] M. Stanojević, B. Stanojević, and M. Vujošević, “Enhanced savings calculation and its applications for solving capacitated vehicle routing problem,” Appl. Math. Comput., vol. 219, no. 20, pp. 10302–10312, 2013, doi: https://doi.org/10.1016/j.amc.2013.04.002.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
___________________________________________________________
International Journal of Advances in Intelligent Informatics
ISSN 2442-6571 (print) | 2548-3161 (online)
Organized by UAD and ASCEE Computer Society
Published by Universitas Ahmad Dahlan
W: http://ijain.org
E: info@ijain.org (paper handling issues)
andri.pranolo.id@ieee.org (publication issues)
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0