A Modified Camel Algorithm for Optimizing Green Vehicle Routing Problem with Time Windows

Authors

  • Dana Marsetiya Utama Department of Industrial Engineering, Universitas Muhammadiyah Malang
  • Wa Ode Nadhilah Safitri Department of Industrial Engineering, Universitas Muhammadiyah Malang
  • Annisa Kesy Garside Department of Industrial Engineering, Universitas Muhammadiyah Malang

DOI:

https://doi.org/10.9744/jti.24.1.23-36

Keywords:

Vehicle Routing Problem with Time Windows, Fuel consumption, Green Vehicle Routing Problem, Camel Algorithm

Abstract

In recent years, the issue of fuel depletion has become a significant problem in the world. The logistics sector is one of the sectors with an increase in fuel consumption. Therefore, route optimization is one of the attempts to solve the problem of minimization fuel consumption. In addition, this problem generally also has time windows. This study aimed to solve the Green Vehicle Routing Problem with Time Windows (GVRPTW) using the Camel Algorithm (CA). The objective function in this problem was to minimize the total cost of distribution, which involves the cost of fuel consumption and the cost of late delivery. The CA parameter experiment was conducted to determine the effect of the parameter on distribution cost and the computation time. In addition, this study also compared the CA algorithm's performance with the Local search algorithm, Particle Swarm Optimization, and Ant Colony Optimization. Results of this study indicated that the use of Camel population parameters and the total journey step affected the quality of the solution. Furthermore, the research results showed that the proposed algorithm had provided a better total distribution cost than the comparison algorithm.

References

Zhang, W., Yang, D., Zhang, G., and Gen, M., Hybrid Multiobjective Evolutionary Algorithm with Fast Sampling Strategy-based Global Search and Route Sequence Difference-Based Local Search for VRPTW, Expert Systems with Applications, 145, 2020, pp. 113-151.

Ibrahim, M.F., Putri, M.M., and Utama, D.M., A Literature Review on Reducing Carbon Emission from Supply Chain System: Drivers, Barriers, Performance Indicators, and Practices, IOP Conference Series: Materials Science and Engineering, 722, 2020, pp. 012034.

Corstjens, J., Depaire, B., Caris, A., and Sörensen, K., A Multilevel Evaluation Method for Heuristics with an Application to the VRPTW, International Transactions in Operational Research, 27(1), 2020, pp. 168-196.

Garside, A.K., Sulistyani, X., and Utama, D.M., Penentuan Rute Distribusi LPG dengan Pendekatan Model Matematis, in Prosiding SENTRA (Seminar Teknologi Dan Rekayasa), 2, 2016, pp. 12-18.

Utama, D.M., Dewi, S.K., Wahid, A., and Santoso, I., The Vehicle Routing Problem for Perishable Goods: A Systematic Review, Cogent Engineering, 7(1), 2020, pp. 1816148.

Niu, Y., Yang, Z., Chen, P., and Xiao, J., Optimizing the Green Open Vehicle Routing Problem with Time Windows by Minimizing Comprehensive Routing Cost, Journal of Cleaner Production, 171, 2018, pp. 962-971.

Dixit, A., Mishra, A., and Shukla, A., Vehicle Routing Problem with Time Windows using Meta-heuristic Algorithms: A Survey, in Harmony Search and Nature Inspired Optimization Algorithms, Springer, 2019.

Hallowell, R., The Relationships of Customer Satisfaction, Customer Loyalty, and Profitability: An Empirical Study, International Journal of Service Industry Management, 7(4), 1996, pp. 27-42.

Gocken, T. and Yaktubay, M., Comparison of Different Clustering Algorithms via Genetic Algorithm for VRPTW, International Journal of Simulation Modelling, 18, 2019, pp. 574-585.

Kummer N, A.F., Buriol, L.S., and de Araújo, O.C., A Biased Random Key Genetic Algorithm Applied to the VRPTW with Skill Requirements and Synchronization Constraints, in Proceedings of the 2020 Genetic and Evolutionary Computation Conference, 2020, pp. 717-724.

Desrochers, M., Desrosiers, J., and Solomon, M., A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows, Operations Research, 40(2), 1992, pp. 342-354.

Moghdani, R., Salimifard, K., Demir, E., and Benyettou, A., The Green Vehicle Routing Problem: A Systematic Literature Review, Journal of Cleaner Production, 279, 2021, pp. 123691.

Lin, C., Choy, K.L., Ho, G.T., Chung, S.H., and Lam, H., Survey of Green Vehicle Routing Problem: Past and Future Trends, Expert Systems with Applications, 41(4), 2014, pp. 1118-1138.

Xiao, Y., Zhao, Q., Kaku, I., and Xu, Y., Development of A Fuel Consumption Optimization Model for the Capacitated Vehicle Routing Problem, Computers & Operations Research, 39(7), 2012, pp. 1419-1431.

Psychas, I.-D., Marinaki, M., Marinakis, Y., and Migdalas, A., Minimizing the Fuel Consumption of a Multiobjective Vehicle Routing Problem using the Parallel Multi-Start NSGA II Algorithm, in Models, Algorithms and Technologies for Network Analysis, 2014, pp. 69-88.

Zhang, Z., Wei, L., and Lim, A., An Evolutionary Local Search for the Capacitated Vehicle Routing Problem Minimizing Fuel Consumption under Three-Dimensional Loading Constraints, Trans¬por¬tation Research Part B: Methodological, 82, 2015, pp. 20-35.

Niu, Y., Yang, Z., Chen, P., and Xiao, J., A Hybrid Tabu Search Algorithm for a Real-World Open Vehicle Routing Problem Involving Fuel Consumption Constraints, Complexity, 2018, 2018, pp. 5754908.

Rao, W., Liu, F., and Wang, S., An Efficient Two-Objective Hybrid Local Search Algorithm for Solving the Fuel Consumption Vehicle Routing Problem, Applied Computational Intelligence and Soft Computing, 2016, 2016, pp. 3713918.

Zulvia, F.E., Kuo, R., and Nugroho, D.Y., A Many-objective Gradient Evolution Algorithm for Solving a Green Vehicle Routing Problem with Time Windows and Time Dependency for Perishable Products, Journal of Cleaner Production, 242, 2020, pp. 118428.

Macrina, G., Pugliese, L.D.P., Guerriero, F., and Laporte, G., The Green Mixed Fleet Vehicle Routing Problem with Partial Battery Recharging and Time Windows, Computers & Operations Research, 101, 2019, pp. 183-199.

Yu, Y., Wang, S., Wang, J., and Huang, M., A Branch-and-price Algorithm for the Heterogeneous Fleet Green Vehicle Routing Problem with Time Windows, Transportation Research Part B: Methodological, 122, 2019, pp. 511-527.

Rabbani, M., Davoudkhani, M., and Farrokhi-Asl, H., A New Multi-objective Green Location Routing Problem with Heterogonous Fleet of Vehicles and Fuel Constraint, International Journal of Strategic Decision Sciences (IJSDS), 8(3), 2017, pp. 99-119.

Salehian, F., Tavakkoli-Moghaddam, R., and Norouzi, N., Solving a Vehicle Routing Problem Considering Customers’ Satisfaction and Energy Consumption by a Bee Algorithm, Quarterly Journal of Transportation Engineering, 11(2), 2019, pp. 299-311.

Utama, D.M., Fitria, T.A., and Garside, A.K., Artificial Bee Colony Algorithm for Solving Green Vehicle Routing Problems with Time Windows, Journal of Physics: Conference Series, 1933(1), 2021, pp. 012043.

Norouzi, N., Sadegh-Amalnick, M., and Tavakkoli-Moghaddam, R., Modified Particle Swarm Optimization in a Time-dependent Vehicle Routing Problem: Minimizing Fuel Consumption, Optimization Letters, 11(1), 2017, pp. 121-134.

Yao, E., Lang, Z., Yang, Y., and Zhang, Y., Vehicle Routing Problem Solution Considering Minimising Fuel Consumption, IET Intelligent Transport Systems, 9(5), 2015, pp. 523-529.

Kuo, Y., Using Simulated Annealing to Minimize Fuel Consumption for the Time-dependent Vehicle Routing Problem, Computers & Industrial Engineering, 59(1), 2010, pp. 157-165.

Jemai, J., Zekri, M., and Mellouli, K., An NSGA-II Algorithm for the Green Vehicle Routing Problem, in European Conference on Evolutionary Computation in Combinatorial Optimization, 2012, pp. 37-48.

Xu, X., Wang, C., and Zhou, P., GVRP considered Oil-gas Recovery in Refined Oil Distribution: From an Environmental Perspective, International Journal of Production Economics, 235, 2021, pp. 108078.

Cooray, P.L.N.U. and Rupasinghe, T.D., Machine Learning-based Parameter Tuned Genetic Algorithm for Energy Minimizing Vehicle Routing Problem, Journal of Industrial Engineering, 2017, 2017, pp. 3019523.

Dewi, S.K. and Utama, D.M., A New Hybrid Whale Optimization Algorithm for Green Vehicle Routing Problem, Systems Science & Control Engineering, 9(1), 2021, pp. 61-72.

Utama, D.M., Widodo, D.S., Ibrahim, M.F., and Dewi, S.K., A New Hybrid Butterfly Optimization Algorithm for Green Vehicle Routing Problem, Journal of Advanced Transportation, 2020, 2020, pp. 8834502.

El-Sherbeny, N.A., Vehicle Routing with Time Windows: An Overview of Exact, Heuristic and Metaheuristic Methods, Journal of King Saud University-Science, 22(3), 2010, pp. 123-131.

Bräysy, O. and Gendreau, M., Vehicle Routing Problem with Time Windows, Part II: Metaheuristics, Transportation Science, 39(1), 2005, pp. 119-139.

Ibrahim, M.F., Nurhakiki, F.R., Utama, D.M., and Rizaki, A.A., Optimised Genetic Algorithm Crossover and Mutation Stage for Vehicle Routing Problem Pick-Up and Delivery with Time Windows, IOP Conference Series: Materials Science and Engineering, 1071(1), 2021, pp. 012025.

Ibrahim, M.F., Putri, M., Farista, D., and Utama, D.M., An Improved Genetic Algorithm for Vehicle Routing Problem Pick-up and Delivery with Time Windows, Jurnal Teknik Industri, 22(1), 2021, pp. 1-17.

Hu, W., Liang, H., Peng, C., Du, B., and Hu, Q., A hybrid Chaos-particle Swarm Optimization Algorithm for the Vehicle Routing Problem with Time Window, Entropy, 15(4), 2013, pp. 1247-1270.

Qi, C. and Sun, Y., An Improved Ant Colony Algo-rithm for VRPTW, in 2008 International Conference on Computer Science and Software Engineering, 1, 2008, pp. 455-458.

Nalepa, J. and Blocho, M., Adaptive Memetic Algo-rithm for Minimizing Distance in the Vehicle Routing Problem with Time Windows, Soft Computing, 20(6), 2016, pp. 2309-2327.

Zhang, J., Yang, F., and Weng, X., An Evolutionary Scatter Search Particle Swarm Optimization Algorithm for the Vehicle Routing Problem with Time Windows, IEEE Access, 6, 2018, pp. 63468-63485.

Ali, R.S., Alnahwi, F.M., and Abdullah, A.S., A Modified Camel Travelling Behaviour Algorithm for Engineering Applications, Australian Journal of Electrical and Electronics Engineering, 16(3), 2019, pp. 176-186.

Hassan, K.H., Rashid, A.T., and Jasim, B.H., Parameters Estimation of Solar Photovoltaic Module using Camel Behavior Search Algorithm, International Journal of Electrical and Computer Engineering, 11(1), 2021, pp. 788.

Omran, K.M., Jasim, B.H., and Hassan, K.H., Optimum Speed Controller Structure Utilizing the MCA Approach, Bulletin of Electrical Engineering and Informatics, 10(2), 2021, pp. 640-649.

Tavakkoli-Moghaddam, R., Gazanfari, M., Alinaghian, M., Salamatbakhsh, A., and Norouzi, N., A New Mathematical Model for a Competitive Vehicle Routing Problem with Time Windows solved by Simulated Annealing, Journal of Manufacturing Systems, 30(2), 2011, pp. 83-92.

Utama, D.M. and Widodo, D.S., An Energy-Efficient Flow Shop Scheduling using Hybrid Harris Hawks Optimization, Bulletin of Electrical Engineering and Informatics, 10(3), 2021, pp. 1154-1163.

Utama, D.M., Widodo, D.S., Ibrahim, M.F., and Dewi, S.K., An Effective Hybrid Ant Lion Algorithm to Minimize Mean Tardiness on Permutation Flow Shop Scheduling Problem, International Journal of Advances in Intelligent Informatics, 6(1), 2020, pp. 23-35.

Utama, D.M., Widodo, D.S., Ibrahim, M.F., Hidayat, K., Baroto, T., and Yurifah, A., The Hybrid Whale Optimization Algorithm: A New Meta¬heuristic Algorithm for Energy-Efficient on Flow Shop with Dependent Sequence Setup, Journal of Physics: Conference Series, 1569, 2020, pp. 022094.

Widodo, D.S. and Utama, D.M., The Hybrid Ant Lion Optimization Flow Shop Scheduling Problem for Minimizing Completion Time, in Journal of Physics: Conference Series, 1569(2), 2020, pp. 022097.

Ali, I.M., Essam, D., and Kasmarik, K., A Novel Differential Evolution Mapping Technique for Generic Combinatorial Optimization Problems, Applied Soft Computing, 80, 2019, pp. 297-309.

Utama, D.M., Farida, B.N.I., Fitriani, U., Ibrahim, M.F., and Widodo, D.S., Hybrid Henry Gas Solubility Optimization: An Effective Algorithm for Fuel Consumption Vehicle Routing Problem, Jurnal Ilmiah Teknik Industri, 20(2), 2021, pp. 141-152.

Downloads

Published

2022-06-02

Issue

Section

Articles