Genetic Algorithm with Cluster-first Route-second to Solve the Capacitated Vehicle Routing Problem with Time Windows
A Case Study
:
https://doi.org/10.9744/jti.23.1.75-82
Keywords:
Cluster-first Route-second. P-Median Clustering, Genetic Algorithm, CVRPTWAbstract
In a distribution problem, designing the right distribution route can minimize the total transportation costs. Therefore, this research aims to design a distribution route that produces a minimal distribution distance by clustering the demand points first. We generated the clustering method to cluster the demand points by considering the proximity among the demand points and the total vehicle capacity. In solving this problem, we are using p-median to determine the cluster and a genetic algorithm to determine the distribution route with the characteristics of the CVRPTW problem. CVRPTW or capacitated vehicle routing problem with time windows is a type of VRP problem where there is a limitation of the vehicle capacity and service time range of its demand point. This research concludes that clustering the demand points provides a better result in terms of total distribution costs by up to 16.26% compared to the existing delivery schedule. The performance of the genetic algorithm shows an average difference of 1.73%, compared to the exact or optimal method. The genetic algorithm is 89.68% faster than the exact method in the computational time.
References
Tseng, Y. Y., Taylor, M. A. P., and Yue, W. L., The Role of Transportation in Logistics Chain, in Proceeding of the Eastern Asia Society for Trans-port Studies, Adelaide, 2005.
Tlili, T., Harzi, M., and Krichen, S., Swarm-based Approach for Solving the Ambulance Routing Problem, in International Conference on Knowledge Based and Intelligent Information and Engineering Systems, KES2017, Marseille, France, 2017.
Wang, Y., Assogba, K., Liu, Y., Ma, X., Xu, M., and Wang, Y., Two-echelon Location-routing Optimization with Time Windows Based on Customemr Clustering, Expert Systems With Applications, 104, 2018.
Rabbani, M., Farrokhi-Asl, H., and Asgarian, B., Solving a Bi-objective Location Routing Problem by a NSGA-II Combined with Clustering Approach: Application in Waste Collection Problem, Journal of Industrial Engineering International, 13, 2016, pp. 13-27.
Fomin, F. V., Golovach, P. A.. and Simonov, K., Parameterized k-Clustering: Tractability Island, Journal of Computer and System Sciences, 117, 2021, 50-74.
Mai, F., Fry, M. J., and Ohlmann, J. W., Model-Based Capacitated Clustering with Posterior Regularization, European Journal of Operational Research, 271(2), 2018, pp. 594-605.
Garcia, S., Labbe, M., and Marin, A., Solving Large p-median Problems with a Radius Formulation, INFORMS Journal on Computing, 23(4), 2011, 546-556.
Elloumi, S., A Tighter Formulation of the p-Median Problem, Journal Combinatorial Opti-mi¬zation, 19, 2010, 69-83.
Puerto, J., Ramos, A., and Rodriguez-Chia, A., Single-allocation Ordered Median Hub Location Problems, Computers & Operations Research, 38, 2011, 559-570.
Hungerlander, P., Maier, K., Pocher, J., and Truden, C., Solning an On-Line Capacitated Vehicle Routing Problem with Structures Time Windows, in Operations Research Proceedings, 2016.
Giovanni, L. D., Gastaldon, N., Lauriola, I., and Sottovia, F., A Heuristic for Multi-attribute Vehicle Routing Problems in Express Freight Transportation, in International Conference on Optimization and Decision Science, 2017.
Bai, R., Wallace, S. W., Li, J., and Chong, A. Y.-L., Stochastic Service Network Design with Rerouting, Transportation Research Part B: Methodological, 60, 2014, 50-65.
da Costa, P. R. d. O., Mauceri, S., Caroll, P., and Pallonetto, F., A Genetic Algorithm for a Green Vehicle Routing Problem, Electronic Notes in Discrete Mathematics, 64, 2018, pp. 65-74.
Tasan, A. S., and Gen, M., A Genetic Algorithm based Approach to Vehicle Routing Problem with Simultaneous Pick-up and Deliveries, Computers & Industrial Engineering, 62, 2012, pp. 755-761.
Suprayogi and D. B. Pailin, Algoritma Genetika untuk Pemecahan Masalah Rute Kendaraan dengan Ukuran dan Campuran Armada, Trip Majemuk, Pengiriman Terbagi, Produk Majemuk dan Kendaraan dengan Kompartemen Maje¬muk, Jurnal Teknik Industri, 19(2), 2017, pp. 115-124.
Ghoseiri, K., and Ghannadpour, S. F., A Hybrid Genetic Algorithm for Multi-depot Homogenous Locomotive Assignment with Time Windows, Applied Soft Computing, 10, 2010, pp. 53-65.
Mostafa, N. and Eltawil, A., Solving the Heterogenous Capacitated Vehicle Routing Problem using K-Means Clustering and Valid Inequalities, in Industrial Engineering and Operations Management, Rabat, 2017.
Alfiyatin, A. N., Mahmudy, W. F., and Anggodo, Y. P., K-Means Clustering and Genetic Algorithm to Solve Vehicle Routing Problem with Time Windows Problem, Electrical Engineering and Computer Science, 11(2), 2018, pp. 462-468.
Jackson, L. E., Rouskas, G. N., and Stallmann, M. F. M., The Directional p-Median Problem: Definition, Complexity, and Algorithms, Euro-pean Journal of Operational Research, 179, 2007, pp. 1097-1108.
Kohn, H. F., and Steinley, D., The p-Median Model as a Tool for Clustering Psychological Data, American Psychological Association, 15, 2010, pp. 87-95.
Molina, J. C., Salmeron, J. L., Eguia, I. and Racero, J., The Heterogeneous Vehicle Routing Problem with Time Windows and Limited Number of Resources, Enginerring Applications of Artificial Intelligence, 94, 2020, 1-15.
Ferreira, H. S., Bogue, E. T., Noronha, T. F., Belhaiza, S., and Prins, C., Variable Neigh¬bor-hood Search for Vehicle Routing Problem with Multiple Time Windows, Electronic Notes in Discrete Mathematics, 66, 2018, pp. 207-214.
Tohidifard, M. , Moghaddam, T. R., Navazi, F., and Partovi, M., A Multi-Depot Home Care Routing Problem with Time Windows and Fuzzy Demands Solving by Particle Swarm Optimi-zation and Genetic Algorithm," Interna¬tional Federation of Automatic Control, 51(11), 2018, pp. 358-363.
Kulkarni, R. V., and Bhave, P. R., Integer Programming Formulation for Vehicle Routing Problem, European Journal of Operational Research, 20,1985, pp. 57-68.
Goldberg, D. E., Genetic Algorithm in Search, Optimization, and Machine Learning, Addison-Wesley Professional, Massachusetts,1989.
Downloads
Published
How to Cite
Issue
Section
License
Articles published in the Jurnal Teknik Industri: Jurnal Keilmuan dan Aplikasi Teknik Industri will be Open-Access articles distributed under the terms and conditions of the Creative Commons Attribution License (CC BY).
This work is licensed under a Creative Commons Attribution License (CC BY).
