Volume 18, Issue 4 (3-2022)
JSDP 2022, 18(4): 23-36 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Ebrahimi Mood S, Javidi M M, Khosravi M R. Proposing a Constrained-GSA for the Vehicle Routing Problem. JSDP 2022; 18 (4) : 2
URL: http://jsdp.rcisp.ac.ir/article-1-1012-en.html
URL: http://jsdp.rcisp.ac.ir/article-1-1012-en.html
Shahid Bahonar University of Kerman
Abstract: (1954 Views)
In the past decades, vehicle routing problem (VRP) has gained considerable attention for its applications in industry, military, and transportation applications. Vehicle routing problem with simultaneous pickup and delivery is an extension of the VRP. This problem is an NP-hard problem; hence finding the best solution for this problem which is using exact method, take inappropriate time, and these methods are not useful in real-world applications. Using meta-heuristic algorithms for calculating and computing the solutions for NP-hard problems is a common method to contrast this challenge.
The objective function defined for this problem, is a constrained objective function. In previous algorithms, the penalty method was used as constraint handling technique to define the objective function. Determining the value of parameters and penalty coefficient is not easy in these methods. Moreover, the optimal number of vehicles was not considered in the previous algorithms. So, the user should guess number of vehicles and compare the result with other values for this variable.
In this paper, a novel objective function is defined to solve the vehicle routing problem with simultaneous pickup and delivery. This method can find the vehicle routes such that increases the performance of the vehicles and decreases the processes’ costs of transportation. in addition, the optimal number of vehicle in this problem can be calculated using this objective function. Finding the best solution for this optimization problems is an NP-hard and meta-heuristic methods can be used to estimate good solutions for this problem.
Then, a constrained version of gravitational search algorithm is proposed. In this method, a fuzzy logic controller is used to calculate the value of the parameters and control the abilities of the algorithm, automatically. Using this controller can balance the exploration and exploitation abilities in the gravitational search algorithm and improve the performance of the algorithm. This new version of gravitational search algorithm is used to find a good solution for the predefined objective function. The proposed method is evaluated on some standard benchmark test functions and problems. The experimental results show that the proposed method outperforms the state-of-the-art methods, despite the simplicity of implementation.
The objective function defined for this problem, is a constrained objective function. In previous algorithms, the penalty method was used as constraint handling technique to define the objective function. Determining the value of parameters and penalty coefficient is not easy in these methods. Moreover, the optimal number of vehicles was not considered in the previous algorithms. So, the user should guess number of vehicles and compare the result with other values for this variable.
In this paper, a novel objective function is defined to solve the vehicle routing problem with simultaneous pickup and delivery. This method can find the vehicle routes such that increases the performance of the vehicles and decreases the processes’ costs of transportation. in addition, the optimal number of vehicle in this problem can be calculated using this objective function. Finding the best solution for this optimization problems is an NP-hard and meta-heuristic methods can be used to estimate good solutions for this problem.
Then, a constrained version of gravitational search algorithm is proposed. In this method, a fuzzy logic controller is used to calculate the value of the parameters and control the abilities of the algorithm, automatically. Using this controller can balance the exploration and exploitation abilities in the gravitational search algorithm and improve the performance of the algorithm. This new version of gravitational search algorithm is used to find a good solution for the predefined objective function. The proposed method is evaluated on some standard benchmark test functions and problems. The experimental results show that the proposed method outperforms the state-of-the-art methods, despite the simplicity of implementation.
Article number: 2
Keywords: Vehicle Routing Problem, Meta-heuristic algorithms, Constrained Gravitational Search Algorithm
Type of Study: Research |
Subject:
Paper
Received: 2019/05/4 | Accepted: 2020/08/18 | Published: 2022/03/21 | ePublished: 2022/03/21
Received: 2019/05/4 | Accepted: 2020/08/18 | Published: 2022/03/21 | ePublished: 2022/03/21
References
1. [1] N. Christofides, ''The vehicle routing problem'', Revue française d'automatique, informatique, recherche opérationnelle,vol. 10(V1), pp. 55-70, 1976. [DOI:10.1051/ro/197610V100551]
2. [2] P. Toth, D. Vigo, The vehicle routing problem, SIAM, 2002. [DOI:10.1137/1.9780898718515]
3. [3] T.J. Ai, V. Kachitvichyanukul, ''A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery'', Computers & Operations Research, vol. 36(5), pp. 1693-1702, 2009. [DOI:10.1016/j.cor.2008.04.003]
4. [4] E. Rashedi, H. Nezamabadi-Pour, S. Saryazdi, ''GSA: a gravitational search algorithm'', Information sciences, vol.179(13), pp. 2232-2248, 2009. [DOI:10.1016/j.ins.2009.03.004]
5. [5] E. Rashedi, H. Nezamabadi-Pour, S. Saryazdi, ''BGSA: binary gravitational search algorithm'', Natural Computing, vol.9(3), pp. 727-74, 2010. [DOI:10.1007/s11047-009-9175-3]
6. [6] S.E. Mood, M.M. Javidi, ''Energy-efficient clustering method for wireless sensor networks using modified gravitational search algorithm,'' Evolving Systems, pp. 1-13, 2019.
7. [7] B. González, P. Melin, F. Valdez, G. Prado-Arechiga, ''Ensemble Neural Network Optimization Using a Gravitational Search Algorithm with Interval Type-1 and Type-2 Fuzzy Parameter Adaptation in Pattern Recognition Applications, in: Fuzzy Logic Augmentation of Neural and Optimization Algorithms: Theoretical Aspects and Real Applications, Springer, 2018, pp. 17-27. [DOI:10.1007/978-3-319-71008-2_2]
8. [8] A. Karimi , L.S. Hoseini , ''An Optimal Algorithm for Dividing Microscopic Images of Blood for the Diagnosis of Acute Pulmonary Lymphoblastic Cell Using the FCM Algorithm and Genetic Optimization'', JSDP, vol.15 (2),pp. 45-54, 2018. URL: http://jsdp.rcisp.ac.ir/article-1-567-fa.html [DOI:10.29252/jsdp.15.2.45]
9. [9] M. Vaghefi, F. Jamshidi , ''Features selection for cardiac arrhythmia diagnosis using multiple objective binary particle swarm optimization'', JSDP, vol. 18 (2), pp.163-176, 2021. URL: http://jsdp.rcisp.ac.ir/article-1-972-fa.html
10. [10] A. Karimi, L.S. Hoseini , ''An Optimal Algorithm for Dividing Microscopic Images of Blood for the Diagnosis of Acute Pulmonary Lymphoblastic Cell Using the FCM Algorithm and Genetic Optimization'', JSDP, vol. 15 (2), pp. 45-54, 2018.
URL: http://jsdp.rcisp.ac.ir/article-1-567-fa.html [DOI:10.29252/jsdp.15.2.45]
11. [11] S. Mood, E. Rasshedi, M. Javidi, ''New functions for mass caculation in gravitational search algorithm,'' Journal of Computing and Security, 2(3), 2016.
12. [12] H.A. Kherabadi, S.E. Mood, M.M. Javidi, ''Mutation: a new operator in gravitational search algorithm using fuzzy controller'', Cybernetics and Information Technologies, vol. 17(1), pp. 72-86, 2017. [DOI:10.1515/cait-2017-0006]
13. [13] M. Soleimanpour-Moghadam, H. Nezamabadi-Pour, M.M. Farsangi, ''A quantum inspired gravitational search algorithm for numerical function optimization,'' Information Sciences, pp. 83-100, 2014. [DOI:10.1016/j.ins.2013.09.006]
14. [14] A. Hatamlou, ''Black hole: A new heuristic optimization approach for data clustering'', Information sciences, vol. 222, pp. 175-184, 2013. [DOI:10.1016/j.ins.2012.08.023]
15. [15] M. Shams, E. Rashedi, A. Hakimi, ''Clustered-gravitational search algorithm and its application in parameter optimization of a low noise amplifier,'' Applied Mathematics and Computation, vol.258, pp. 436-453, 2015. [DOI:10.1016/j.amc.2015.02.020]
16. [16] E. Rashedi, E. Rashedi, H. Nezamabadi-pour, ''A comprehensive survey on gravitational search algorithm'', Swarm and evolutionary computation, vol. 41, pp.141-158, 2018. [DOI:10.1016/j.swevo.2018.02.018]
17. [17] J.T. Zhang, L.X. Qiao, ''Optimization Mechanism Control Strategy of Vehicle Routing Problem Based on Improved PSO'', Advanced Materials Research, Trans Tech Publ, pp. 130-136, 2013. [DOI:10.4028/www.scientific.net/AMR.681.130]
18. [18] B. Yao, B. Yu, P. Hu, J. Gao, M. Zhang, ''An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot'', Annals of Operations Research, vol.242(2), pp.303-320, 2016. [DOI:10.1007/s10479-015-1792-x]
19. [19] M. Avci, S. Topaloglu, ''A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery'', Expert Systems with Applications, vol.53, pp. 160-17,12016. [DOI:10.1016/j.eswa.2016.01.038]
20. [20] A. Gupta, S. Saini, ''On Solutions to Vehicle Routing Problems Using Swarm Optimization Techniques: A Review, '' in: Advances in Computer and Computational Sciences, Springer, pp. 345-354, 2017. [DOI:10.1007/978-981-10-3770-2_32]
21. [21] E. Mezura-Montes, ''C.A.C. Coello, Constraint-handling in nature-inspired numerical optimization: past, present and future,'' Swarm and Evolutionary Computation, vol.1(4), pp. 173-194, 2011. [DOI:10.1016/j.swevo.2011.10.001]
22. [22] D. Orvosh, L. Davis, ''Using a genetic algorithm to optimize problems with feasibility constraints,'' in: Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, IEEE, pp. 548-553, 1994.
23. [23] R. de Paula Garcia, B.S.L.P. de Lima, A.C. de Castro Lemonge, B.P. Jacob, ''A rank-based constraint handling technique for engineering design optimization problems solved by genetic algorithms,'' Computers & Structures, vol. 187, pp. 77-87, 2017. [DOI:10.1016/j.compstruc.2017.03.023]
24. [24] M. Dell'Amico, G. Righini, M. Salani, ''A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection,'' Transportation science, vol. 40(2), pp. 235-247, 2006. [DOI:10.1287/trsc.1050.0118]
25. [25] J. Dethloff, ''Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up,'' OR-Spektrum, vol.23(1), pp. 79-96, 2001. [DOI:10.1007/PL00013346]
26. [26] F.A.T. Montané, R.D. Galvao, ''A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service'', Computers & Operations Research, vol.33(3), pp.595-619, 2006. [DOI:10.1016/j.cor.2004.07.009]
27. [27] N. Bianchessi, G. Righini, ''Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery'', Computers & Operations Research, vol.34(2) pp.578-594, 2007. [DOI:10.1016/j.cor.2005.03.014]
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
