Differential evolution algorithms with local search for the multi-products capacitated vehicle routing problem with time windows: A case study of the ice industry
Article Sidebar
Published:
Dec 19, 2018
Keywords:
Ice transportation Capacitated vehicle routing problem Time windows Differential evolution algorithm Local search
Main Article Content
Abstract
This research aims to offer a solution to the capacitated vehicle routing problem for multiple products, time windows and a heterogeneous fleet for ice transport. The problem structure is that the capacitated vehicle routing problem is one-to-many with multiple products, where each customer has a variety of product types and demands. Also, limited delivery time is considered for each customer. We used a mixed integer linear programming model to give an optimal solution, and propose a differential evolution method with a local search that we have developed. The objective is to sequence the delivery procedures for ice transport to minimize total costs, comprised of traveling costs, driver wages and a penalty costs. We obtained various solutions by a comparison of our proposed solution and the optimal solution of the ice transport case study and differential evolution with local search (DELS) to validate the proposed metaheuristic. The relative improvement between the current practice of the ice transport in the case study and the differential evolution with a local search was 3.70-25.75%. The differential evolution with a local search outperformed current practices by an average by 2.29%.
Article Details
How to Cite
Kamphukaew, R., Sethanan, K., Jamrus, T., & Wang, H.- kai. (2018). Differential evolution algorithms with local search for the multi-products capacitated vehicle routing problem with time windows: A case study of the ice industry. Engineering and Applied Science Research, 45(4), 273–281. Retrieved from https://ph01.tci-thaijo.org/index.php/easr/article/view/127413
Issue
Section
ORIGINAL RESEARCH
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
[1] Hartl RF, Hasle G, Janssens GK. Special issue on rich vehicle routing problems. Cent Eur J Oper Res. 2006;14(2):103-4.
[2] Dantzig GB, Ramser JH. The truck dispatching problem. Manag Sci. 1959;6(1):80-91.
[3] Worasan K, Sethanan K, Chaikanha N. Dairy transportation problem with no mixing of raw milk and time windows constraints. Proceedings of the Asia Pacific Industrial Engineering and Management Systems Conference (APIEMS); 2014 Oct 12-15; Jeju Island, Korea; 2014.
[4] Akpinar S. Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem. Expert Syst Appl. 2016;61:28-38.
[5] Abdulkader MS, Gajpal Y, Elmekkawy TY. Hybridized ant colony algorithm for the multi compartment vehicle routing problem. Appl Soft Comput. 2015;37:196-203.
[6] Zhang Y, Chen XD. An optimization model for the vehicle routing problem in multi-product frozen food delivery. J Appl Res Tech. 2014;12(2):239-50.
[7] Hsu CI, Hung SF, Li HC. Vehicle routing problem with time-windows for perishable food delivery. J Food Eng. 2007;80(2):465-75.
[8] Osvald A, Stirn LZ. A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food. J Food Eng. 2008;85(2):285-95.
[9] Jiang J, Ng KM, Poh KL, Teo, KM. Vehicle routing problem with a heterogeneous fleet and time windows. Expert Syst Appl. 2014;41(8):3748-60.
[10] Chamnanlor C, Sethanan K. Bi-objective optimization for reentrant shop scheduling problem. CMU J Nat Sci. 2015;14:447-60.
[11] Jamrus T, Chien CF, Gen M, Sethanan K. Hybrid particle swarm optimization combined with genetic operators for flexible job-shop scheduling under uncertain processing time for semiconductor manufacturing. IEEE Trans Semicond Manuf. 2018;31(1):32-41.
[12] Sethanan K, Pitakaso R. Improved differential evolution algorithms for solving generalized assignment problem. Expert Systems With Applications 2016;45:450-9.
[13] Kachitvichyanukul V. Comparison of three evolutionary algorithms: GA, PSO, and DE. Ind Eng Manag Syst. 2012;11(3): 215-23.
[14] Nearchou AC. Meta-heuristics from nature for the loop
layout design problem. Int J Prod Econ. 2006;101(2):312-28.
[15] Wisittipanich W, Hengmeechai P. A multi-objective differential evolution for just-in-time door assignment and truck scheduling in multi-door cross docking problems. Ind Eng Manag Syst. 2015;14(3):299-311.
[16] Xu H, Wen J. Differential evolution algorithm for the optimization of the vehicle routing problem in logistics. The 8th International Conference on Computational Intelligence and Security (CIS 2012); 2012 Nov 17-18; Guangzhou, China. USA: IEEE; 2012. p. 48-51.
[17] Lingjuan HOU, Zhijiang HOU. A novel discrete differential evolution algorithm. Indonesian J Electr Eng Comput Sci. 2013;11(4):1883-8.
[18] Dechampai D, Tanwanichkul L, Sethanan K, Pitakaso R. A differential evolution algorithm for the capacitated VRP with flexibility of mixing pickup and delivery services and the maximum duration of a route in poultry industry. J Intell Manuf. 2017;28(6):1357-76.
[19] Alinaghian M, Kaviani Z, Khaledan S. A novel heuristic algorithm based on clark and wright algorithm for green vehicle routing problem. Int J Supply Oper Manag. 2015;2(2):784-97.
[20] Ponnambalam SG, Ganesan K. Differential evolution algorithm with local search for capacitated vehicle routing problem. Int J of Bio-Inspired Computation. 2015;7(5):321-42.
[21] Price K, Strom R. Differential evolution a simple evolution strategy for fast optimization. Dobb’s J. 1997;22(4):18-24.
[22] Laguna M, Luis J, Velarde G. A search heuristic for just-in-time scheduling in parallel machines. J Intell Manuf. 1991;2(4):253-60.
[23] Laguna M, Barnes JW, Glover F. Intelligent scheduling with tabu search: an application to jobs with linear delay penalties and sequence dependent setup costs and times. Appl Intell. 1993;3(2): 159-72.
[24] De la Cruz JJ, Paternina-Arboleda CD, Cantillo V, Montoya-Torres JR. A two-pheromone trail ant colony system-tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products. J Heuristics. 2013;19(2):1-20.
[25] Meesuptaweekoon K, Chaovalitwongse P. Dynamic vehicle routing problem with multiple depots. Eng J. 2014;18(4):135-49.
[26] Joshi S, Kaur S. Nearest neighbor insertion algorithm for solving capacitated vehicle routing problem. In: Hoda MN, editor. 2015 2nd International Conference on Computing for Sustainable Global Development (INDIACom); 2015 Mar 11-13; New Delhi, India. New Delhi: IEEE; 2015. p. 86-8.
[2] Dantzig GB, Ramser JH. The truck dispatching problem. Manag Sci. 1959;6(1):80-91.
[3] Worasan K, Sethanan K, Chaikanha N. Dairy transportation problem with no mixing of raw milk and time windows constraints. Proceedings of the Asia Pacific Industrial Engineering and Management Systems Conference (APIEMS); 2014 Oct 12-15; Jeju Island, Korea; 2014.
[4] Akpinar S. Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem. Expert Syst Appl. 2016;61:28-38.
[5] Abdulkader MS, Gajpal Y, Elmekkawy TY. Hybridized ant colony algorithm for the multi compartment vehicle routing problem. Appl Soft Comput. 2015;37:196-203.
[6] Zhang Y, Chen XD. An optimization model for the vehicle routing problem in multi-product frozen food delivery. J Appl Res Tech. 2014;12(2):239-50.
[7] Hsu CI, Hung SF, Li HC. Vehicle routing problem with time-windows for perishable food delivery. J Food Eng. 2007;80(2):465-75.
[8] Osvald A, Stirn LZ. A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food. J Food Eng. 2008;85(2):285-95.
[9] Jiang J, Ng KM, Poh KL, Teo, KM. Vehicle routing problem with a heterogeneous fleet and time windows. Expert Syst Appl. 2014;41(8):3748-60.
[10] Chamnanlor C, Sethanan K. Bi-objective optimization for reentrant shop scheduling problem. CMU J Nat Sci. 2015;14:447-60.
[11] Jamrus T, Chien CF, Gen M, Sethanan K. Hybrid particle swarm optimization combined with genetic operators for flexible job-shop scheduling under uncertain processing time for semiconductor manufacturing. IEEE Trans Semicond Manuf. 2018;31(1):32-41.
[12] Sethanan K, Pitakaso R. Improved differential evolution algorithms for solving generalized assignment problem. Expert Systems With Applications 2016;45:450-9.
[13] Kachitvichyanukul V. Comparison of three evolutionary algorithms: GA, PSO, and DE. Ind Eng Manag Syst. 2012;11(3): 215-23.
[14] Nearchou AC. Meta-heuristics from nature for the loop
layout design problem. Int J Prod Econ. 2006;101(2):312-28.
[15] Wisittipanich W, Hengmeechai P. A multi-objective differential evolution for just-in-time door assignment and truck scheduling in multi-door cross docking problems. Ind Eng Manag Syst. 2015;14(3):299-311.
[16] Xu H, Wen J. Differential evolution algorithm for the optimization of the vehicle routing problem in logistics. The 8th International Conference on Computational Intelligence and Security (CIS 2012); 2012 Nov 17-18; Guangzhou, China. USA: IEEE; 2012. p. 48-51.
[17] Lingjuan HOU, Zhijiang HOU. A novel discrete differential evolution algorithm. Indonesian J Electr Eng Comput Sci. 2013;11(4):1883-8.
[18] Dechampai D, Tanwanichkul L, Sethanan K, Pitakaso R. A differential evolution algorithm for the capacitated VRP with flexibility of mixing pickup and delivery services and the maximum duration of a route in poultry industry. J Intell Manuf. 2017;28(6):1357-76.
[19] Alinaghian M, Kaviani Z, Khaledan S. A novel heuristic algorithm based on clark and wright algorithm for green vehicle routing problem. Int J Supply Oper Manag. 2015;2(2):784-97.
[20] Ponnambalam SG, Ganesan K. Differential evolution algorithm with local search for capacitated vehicle routing problem. Int J of Bio-Inspired Computation. 2015;7(5):321-42.
[21] Price K, Strom R. Differential evolution a simple evolution strategy for fast optimization. Dobb’s J. 1997;22(4):18-24.
[22] Laguna M, Luis J, Velarde G. A search heuristic for just-in-time scheduling in parallel machines. J Intell Manuf. 1991;2(4):253-60.
[23] Laguna M, Barnes JW, Glover F. Intelligent scheduling with tabu search: an application to jobs with linear delay penalties and sequence dependent setup costs and times. Appl Intell. 1993;3(2): 159-72.
[24] De la Cruz JJ, Paternina-Arboleda CD, Cantillo V, Montoya-Torres JR. A two-pheromone trail ant colony system-tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products. J Heuristics. 2013;19(2):1-20.
[25] Meesuptaweekoon K, Chaovalitwongse P. Dynamic vehicle routing problem with multiple depots. Eng J. 2014;18(4):135-49.
[26] Joshi S, Kaur S. Nearest neighbor insertion algorithm for solving capacitated vehicle routing problem. In: Hoda MN, editor. 2015 2nd International Conference on Computing for Sustainable Global Development (INDIACom); 2015 Mar 11-13; New Delhi, India. New Delhi: IEEE; 2015. p. 86-8.