Differential Evolution Optimization Applied to the Vehicle Routing with Time Windows and Multiple Demands
Article Sidebar
Main Article Content
Abstract
Vehicle Routing Problem with Time Window (VRPTW) is classified as a non-polynomial hard problem (NP-Hard Problem), that is difficult to be solved and according to real-world regularities on the various industries. The objective of this research is to minimize the total cost, where the total cost includes fuel costs and idle utilization costs of a vehicle under the hard time windows and multiple demands of customer conditions. The process of solving the case study is as following: firstly, to formulate the mathematical model to represent the case study and then using the LINGO optimization software. After that comparing obtained result to the Differential Evolution (DE), which is metaheuristic algorithms can effectively solve problems and can using with a large number of parameters. From the results, the DE algorithm given higher total cost than that of the mathematical model, however computational time speedy with the solutions that are nearly optimal solutions. The computational result showed that the DE can find 0.8 % higher total cost than that of LINGO but use 12 % less computational time.
Article Details
References
Sethanan, K. (2015). Metaheuristics and Applications for Industry. Khon Kaen, Thailand: Klangnanawittaya Publishers. (in Thai)
Office of the National Economic and Social Development Board. (2018). International Logistics Performance Index (LPI) 2018. Access (2 June 2019). Available (https://www.nesdb.go.th/ewt_dl_link.php?nid=8143&filename=index) (in Thai)
López-Sánchez, A. D., Hernández-Díaz, A. G., Vigo, D., Caballero, R., and Molina, J. (2014). A Multi-Start Algorithm for a Balanced Real-World Open Vehicle Routing Problem. European Journal of Operational Research. Vol. 238, Issue 1, pp. 104-113. DOI: 10.1016/J.EJOR.2014.04.008
Wen, L. and Eglese, R. (2015). Minimum Cost VRP with Time-Dependent Speed Data and Congestion Charge. Computers & Operations Research. Vol. 56, pp. 41-50. DOI: 10.1016/j.cor.2014.10.007
Boonmee, A., Sethanan, K., Arnonkijpanich, B., and Theerakulpisut, S. (2015). Minimizing the Total Cost of Hen Allocation to Poultry Farms using Hybrid Growing Neural Gas Approach. Computers and Electronics in Agriculture. Vol. 110, pp. 27-35. DOI: 10.1016/J.COMPAG.2014.10.006
Sommut, N. and Sintusoaw, S. (2009). GRASP Heuristic for Vehicle Routing Problem. RMUTI Journal. Vol. 2, No. 1, pp. 3-13
Sethanan, K. and Neungmatcha, W. (2016). Multi-Objective Particle Swarm Optimization for Mechanical Harvester Route Planning of Sugarcane Field Operations. European Journal of Operational Research. Vol. 252, Issue 3, pp. 969-984. DOI: 10.1016/J.EJOR.2016.01.043
Pichpibul, T. (2015). Improving Vehicle Routing Decision for Travel Agency in Chonburi, Thailand. pp. 251-258. In: Gen, M., Kim, K., Huang, X., Hiroshi, Y. (eds) Industrial Engineering, Management Science and Applications 2015. Lecture Notes in Electrical Engineering, Vol. 349, Springer, Berlin, Heidelberg
Lopes Silva, M. A., de Souza, S. R., Freitas Souza, M. J., and Bazzan, A. L. C. (2019). A Reinforcement Learning-Based Multi-Agent Framework Applied for Solving Routing and Scheduling Problems. Expert Systems with Applications. Vol. 131, pp. 148-171. DOI: 10.1016/j.eswa.2019.04.056
Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. European Journal of Operational Research. Vol. 35, Issue 2, pp. 254-265. DOI: 10.1287/opre.35.2.254
Figliozzi, M. A. (2010). The Impacts of Congestion on Commercial Vehicle Tour Characteristics and Costs. Transportation Research Part E: Logistics and Transportation Review. Vol. 46, Issue4, pp. 496-506. DOI: 10.1016/j.tre.2009.04.005
Karoonsoontawong, A. (2015). Effcient Insertion Heuristics for Multitrip Vehicle Routing Problem with Time Windows and Shift Time Limits. Transportation Research Record: Journal of the Transportation Research Board. Vol. 2477, Issue 1, pp. 27-39. DOI: 10.3141/2477-04
Prasetyo, H., Alfatsani, M. A., and Fauza, G. (2018). Solving Capacitated Closed Vehicle Routing Problem with Time Windows (CCVRPTW) using BRKGA with local search. IOP Conference Series: Materials Science and Engineering. Vol. 352, DOI: 10.1088/1757-899x/352/1/012014
Wang, B., Liang, Y., Yuan, Meng, Zhang, H., and Liao, Qi. (2019). A Metaheuristic Method for the Multireturn-to-Depot Petrol Truck Routing Problem with Time Windows. Petroleum Science. Vol. 16, pp. 701-712. DOI: 10.1007/s12182-019-0316-8
Storn, R. and Price, K. (1997). Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization. Vol. 11, pp. 341-359. DOI: 10.1023/A:1008202821328
Sethanan, K. and Pitakaso, R. (2016). Differential Evolution Algorithms for Scheduling Raw Milk Transportation. Computers and Electronics in Agriculture. Vol. 121, pp. 245-259. DOI: 1016/j.compag.2015.12.021
Dechampai, D., Tanwanichkul, L., Sethanan, K., and Pitakaso, R. (2017). 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. Journal of Intelligent Manufacturing. Vol. 28, pp. 1357-1376. DOI: 10.1007/s10845-015-1055-3
Wang, B., Liang, Y., Yuan, M., Zhang, H., and Liao, Q. (2019). A Metaheuristic Method for the Multi return-to-Depot Petrol Truck Routing Problem with Time Windows. Petroleum Science. Vol. 16, pp. 701-712. DOI: 10.1007/s12182-019-0316-8
Dhoruri, A., Sari, E. R. and Lestari, D. (2013). Solving Capacitated Vehicle Routing Problems with Time Windows by Goal Programming Approach. In Proceeding of IndoMS International Conference on Mathemathics and Its Applications. pp. 155-162