برنامه ریزی سیستم های حمل ونقل یکپارچه با رویکرد الگوریتم جستجوی گرانشی توسعه یافته مبتنی برکنترلرفازی جهش
محورهای موضوعی : مدیریت(تحقیق در عملیات)علی رضا حسین زاده کاشانی 1 , سید احمد شایان نیا 2 , محمد مهدی موحدی 3 , سهیلا سردار 4
1 - دانشجوی دکتری گروه مدیریت صنعتی، واحد تهران شمال، دانشگاه آزاد اسلامی، تهران، ایران
2 - استادیار گروه مدیریت صنعتی، واحد فیروزکوه، دانشگاه آزاد اسلامی، فیزوکوه، ایران
3 - دانشیار گروه مدیریت صنعتی، واحد فیروزکوه، دانشگاه آزاد اسلامی، فیروزکوه، ایران
4 - استادیار گروه مدیریت صنعتی، واحد تهران شمال، دانشگاه آزاد اسلامی، تهران، ایران
کلید واژه: VRP, MTP, الگوریتم نیروی گرانشی,
چکیده مقاله :
الگوریتم جستجوی گرانشی یک الگوریتم فراابتکاری تازه ظهوری است در این الگوریتم به دو روش میتوان نیروی گرانشی میان پاسخ ها را محاسبه کرد. در روش اول یک پاسخ از فضای همسایگی محلی پاسخ جاری انتخاب شده و نیروی گرانشی بین این دو پاسخ محاسبه می شود. در روش دوم، نیروی گرانشی بین تمام پاسخ های همسایه در فضای همسایگی پاسخ جاری محاسبه می شود و به یک پاسخ همسایه محدود نمی شود. این الگوریتم در برخی از مسائل بهینه سازی دچار همگرایی زودرس شده و در بهینه محلی گیر می کند و پیشرفتی برای پیدا کردن جواب بهینه ندارد که این مشکل جزء معایب این الگوریتم محسوب میشود. در مقاله این مشکل را در مرحله اول با مقایسه دو روش نامبرده تحت آزمون قرار گرفت که نتیجه آن بدینگونه می باشد: روش اول برتری نسبی از نظر پارامتر سرعت رسیدن به جواب و جواب برتر دارد و سپس با تعریف یک تابع جهش ابتکاری، که از کنترلر فازی جهت کنترل کردن میزان جهش استفاده می کند، برطرف میکند. روش پیشنهاد شده بر روی توابع محک استاندارد که شامل توابع تک مدی و چند مدی است ارزیابی شده است و نتایج حاصل از ارزیابی این دو روش با الگوریتم جستجوی گرانشی استاندارد (GSA) و الگوریتم جمعیت ذرات گرانشی (GPS)، الگوریتم بهینه ساز جمعیت ذرات (PSO) و الگوریتم وراثتی حقیقی (RGA) مقایسه شده است.آزمایشات مشاهده شده، نشان دهنده این است که این روش ارائه شده نتایج بهتری نسبت به دیگر الگوریتم های مقایسه شده دارد.
Abstract:
Gravitational search algorithm is a newly emerging meta-heuristic algorithm. In this algorithm, the gravitational force between answers can be calculated in two ways. In the first method, a response is selected from the local neighborhood space of the current response and the gravitational force between these two responses is calculated. In the second method, the gravitational force is calculated among all the neighboring responses in the neighborhood space of the current response and is not limited to a neighboring response. This algorithm has premature convergence in some optimization problems and gets stuck in the local optimum and does not make progress to find the optimal solution, which is one of the disadvantages of this algorithm. In the article, this problem was tested in the first step by comparing the two mentioned methods, and it was found that the first method has relative superiority in terms of the speed of reaching the response, in particular, the optimal response, and then by defining a heuristic mutation function, it uses a Fuzzy controller to control the jump rate. The proposed method has been evaluated on standard benchmark functions, including single-mode and multi-mode functions, and the results of evaluating these two methods have been compared with the standard gravitational search algorithm (GSA) and the gravitational particle population algorithm (GPS), the particle population optimization algorithm (PSO) and real genetic algorithm (RGA). The observed tests show that the presented method has better results than other compared algorithms.
Key Words: gravitational force algorithm, integrated combined transport, routing, multimodal transport, vehicles, VRP, MTP
1.Introduction
The vehicle routing problem has long been a subject of extensive research. However, a review of the literature reveals that simultaneous constraints related to warehouse capacity, vehicle capacity, and route length have not been considered together. Considering these three constraints simultaneously brings the problem closer to reality.
In many logistics environments, the location routing problem helps managers to make decisions such as the location of facilities (distribution centers or warehouses), the allocation of customers to these facilities, and then the transportation plans to connect customers and facilities. In fact, the problems of location routing are defined in order to find the right place and number of facilities as well as distribution routes by means of vehicles. The main difference between routing positioning problem and traditional positioning problem is that in the first one, after determining the location of facilities, communication routes between customers and facilities are examined as a tour, but in the second one, it is assumed that there are direct routes between customers and facilities, which ultimately leads to an increase in distribution costs. So, unlike the traditional positioning method, in the routing positioning method, considering the tour, it simultaneously looks for the optimal places of facilities and also the optimal routes.
- Literature Review
By reviewing the literature in this field, it was seen that until now, the limitations related to warehouse capacity, vehicle capacity, and route length have not been considered simultaneously, while considering these three limitations together brings the problem closer to reality. Rabbani, Sepehri and Zagerdi, in a research entitled “the problem of vehicle routing connected to multimodal transportation: an integrated approach”, designed and modeled a network consisting of vehicle routes and multimodal transportation routes for the first time. In another study, entitled "Analysis of the Role of Financial Factors in the Whiplash Effect in a Two-tier Supply Chain”, Movahedi, Zulfaqari and Jolai, paid attention to the financial factors affecting the escalation of the whiplash effect and quantified this effect. Moreover, by entering the financial factors in the obtained model, they examined the result carefully examined in two ways: first, investigating the time value of money in estimating the financial value of the demand met during p period; second, investigating changes in the monetary value of orders due to the waiting time for order delivery (L). Dera Mirki also investigated the effectiveness of this proposed algorithm by solving 11 VRP problems in a research titled "New Innovative Algorithm for Solving Vehicle Routing Problems".
- Methodology
In this research, the goal of developing the gravitational force algorithm is to solve the problems of integrated and multi-purpose transportation systems, and in the real world, the effect of gravity on objects in a mutual way and the application of gravitational force to all objects in space is the main idea of this algorithm. Obviously, this force changes the speed of objects and pulls them towards larger objects, which in nature can be referred to the relationship between the earth, the moon, terrestrial objects and other celestial bodies. Gravitational force algorithm or GSA local search is a new algorithm which, as its name suggests, is a heuristic local search method. In addition, this algorithm belongs to the group of those methods that imitate some natural or physical processes (such as simulated cooling and genetic algorithm).
In the gravitational force algorithm, the search space is imagined as a galaxy, and the solutions in the search space are like the objects inside the galaxy. Each of these bodies creates a mutual force, which is obtained using Newton's law of gravity with a slight change for F=(m-n)/r^2 problems. Based on the formula, this force is equal to the difference between the value of the evaluation function of the candidate response and the current response divided by the radius of the neighborhood to the square of two. Since the high speed of the gravitational force algorithm is due to the local search, it is very important to create and select the neighborhood as well as to choose the correct conditions for the solutions to be neighbors in this algorithm. In addition to the high speed in reaching the optimal response, the algorithm avoids reaching and staying in a local optimum due to the inherent properties of gravity.
- Result
In this section, the results of the implementation of true genetic algorithm (RGA), particle population optimization algorithm (PSO), gravity particle population algorithm (GPS), standard gravity search algorithm(SGSA) and mutated gravity search algorithm(MUGSA) on 23 functions of the standard benchmark are presented in Tables 2,3 and 4.
Real Genetic Algorithm (RGA)
The true genetic algorithm is randomly generated with an initial population of 50 members in the search space. The dimensions of the problem are the number of genes that are continuously evaluated in the problem space. In each generation, based on the fitness of the chromosomes and using the roulette wheel, parents are selected and then randomly paired with each other. Children are generated by hemming and mutation operators. The rate of hembray operator is 0.3 and the mutation probability is 0.1.
The continuous symmetry operator is performed on each pair of X i and X j in the form of equation 1. In this relation, a is a random value with a uniform distribution in the interval [0,1].
Xi, new = Xi −a (Xi − X j), X j,new= X j −a (Xi − X j ) (1)
In the mutation operator on each child Xi, a gene X id is randomly selected and its value is replaced with a new random value according to relations 2 and 3 in the range of the search space.
Sigma = Scale× (1− Tt), Scale = X hi −5 X lo (2)
a Id, new = X id + rand ×Sigma (3)
In the relations above, Xhi and Xlo are the upper limit and lower limit of the search space, respectively. T is the total number of repetitions and rand is a random number with a normal distribution and zero mean.
Particle Population Optimization Algorithm (PSO)
The particle population optimizer algorithm is randomly generated with an initial population of 50 birds in the search space, and Vid, X id is calculated according to relations 4 and 5.
X id (t+1)=X id (t)+Vid(t+1) (4)
Vid (t +1) = w(t)Vid (t) + C1ri1(pbestid (t)) + C2ri2 (gbest d − xid (t) ) (5)
In these relations, ri1 and ri2 are two random variables in the interval [1,0], C 1 and C 2 are positive values, W is the inertial weight, X id and Vid indicate the position and speed of the particles in the d dimension, pbestid and gbestid respectively indicate the best previous position of the i-th particle and the best previous position among all the particles in the population. In these relationships, C = 2C1 = 2 and W decreases linearly from 0.9 to 0.2 during repetitions.
Gravitational Particle Population Algorithm (GPS)
Equation 6 has been used to update the speed of the gravitational particle population algorithm, in which the speed of the particle population optimizer algorithm Vid (t+1) PSO and the acceleration of the gravitational search algorithm Vid (t+1) GSA have been used, respectively, given in relation 7 and 8. In these relations, 3r is a uniform random variable in the interval [1,0], which is used to create the random property of the speed of the particle population optimization algorithm and the acceleration of the gravitational search algorithm in the gravitational particle population algorithm, and 3C and 4C are two constants to determine the degree of the speed of the particle population optimizer algorithm and the acceleration of the gravitational search algorithm in the gravitational particle population algorithm the values of which are considered 3C and 4C. Vid (t+1)GPS is also used to update the position of the agents in the particle population algorithm in equation 9.
Vid (t +1) GPS = C3ri3 ×Vid (t +1) PSO + C4 (li − ri3) ×Vid (t +1) GSA (6)
Vid (t +1)PSO=W (t)C3Vid (t)+C1ri1 (pbest id−X id (t)) + c2ri2 (gbest id−X id(t)) (7)
Vid (t +1) GSA = ravdi ×Vid (t) + aid (t) (8)
X id (t +1) = X id (t) +Vid (t +1) GPS (9)
Standard Gravitational Search Algorithm (GSA) and Standard Gravitational Search Algorithm with Mutation (MUGSA)
The two standard gravitational search algorithms and the standard gravitational search algorithm with mutation are also randomly generated with an initial population of 50 objects in the search space. Algorithms are performed according to the second chapter. In the relationships of the second chapter, the value of a equals 20 and G0 equals 100, and initially K0 = N, where N is the number of factors, and decreases linearly to 1.
- Discussion
In this research, the validation of the model, using the solution of the proposed model for different problems was estimated. Then, five collective optimizer algorithms, true inheritance algorithm, particle population optimization algorithm, gravity particle population algorithm, standard gravity search algorithm and mutated gravity search algorithm were provided. The search algorithm was used in solving 23 standard benchmark functions, including single mode and multi-mode functions.
The general conclusion is that the gravitational search algorithm and the mutated gravitational search algorithm have better answers on the 23 standard benchmark functions than the real genetic algorithms, the particle population algorithm and the gravitational particle population algorithm, except for the functions F2, F6, F12 to F15. In functions F1, F2, F15, the best results are observed in the gravitational particle population algorithm, while for functions F13, F14, the best results are observed in the particle population optimizer algorithm, and in F9, the real inheritance algorithm has better performance. The efficiency of the gravity search algorithm and the mutated gravity search algorithm is better in functions F4, F7, F11, F21. The diagram of the best solution is shown in Figure 1 and Figure 2 for the comparison between the gravity search algorithm and the mutated gravity search algorithm as an example, respectively for F3 and F11.
A. Haramlou, S. Abdullah, Z. (2011), Othman, Gravitational Search Algorithm with Heuristic Search for clustering problems,3rd Conference on data mining and Optimization,Malaysia,.doi.org:10.1109/dmo.2011. 5976526
A. Saffar, R. Hooshmand and A. Khodabakhshian. A new fuzzy optimal reconfiguration of distribution systems for loss reduction and load balancing using ant colony search-based algorithm, Applied Soft Computing, vol.11,pp. 4021-4028,2011. doi:10.1016/j.asoc.
A.P. Engelbrecht. Fundamentals of computational swarm intelligence, John wiley and sons, 1-640. 2005. doi: 10.1007/s10710-006-9020-8
A.P.F. Saeidi-Khabisi, and E. Rashedi. Fuzzy Gravitational Search Algorithm, 2nd International eConference on Computer and Knowledge Engineering (ICCKE), 2012. doi.org:10.1109/iccke
B. Sahu, D. Mishra. A Novel Feature Selection Algorithm using Particle Swarm Optimization for CancerMicroarray Data, Procedia Engineering, vol. 38, pp. 27-31, 2012. doi:10.1016/j.proeng
C, Li, J. Zhou. Parameter’s identification of hydraulic turbine gonverning and Management52(2011)374-381. doi.org:10.1109/appeec.2010.5448987
Ch. Guo, Zh. Jiang, H. Zhang, N. Li. Decomposition-based classified ant colony optimization algorithm forscheduling semiconductor wafer fabrication system, Computers & Industrial Engineering, vol. 62, pp. 141-151, 2012. doi:10.1016/j.cie
D. d. Serafino, S. Gomez, L. Milano, F. Riccio, G. Toraldo. A genetic algorithm for a global optimization problem arising in the detection of gravitational waves, Springer Science and Business Media, vol. 48, pp.41– 55, 2010. doi:10.1007/s10898-010-9525-9
D. Hu, A. Sarosh, Y. F. Dong. An improved particleswarm optimizer for parametric optimization of flexiblesatellite controller, Applied Mathematics and Computation, 217, 8512-8521, 2011. doi:10.1016/j.amc
D. Mishra. Discovery of Overlapping Pattern Biclustersfrom Gene Expression Data using Hash based PSO, Procedia Technology, vol. 4, pp. 390 – 394, 2012. doi:10.1016/j.protcy
D.Holliday, R. resnick and J. Walker. Fundamentals of physics, John wiley and sons, 1-1431. 1993. doi.org:10.2174/9789815049909123010003
E. Rashedi, H. Nezamabadi-pour, and S. Saryazdi. GSA: a gravitational search algorithm, Information sciences, vol. 179, no. 13, pp. 2232-2248, 2009. doi.org:10.1016/j.ins
E. Rashedi, H. Nezamabadi-pour, S. Saryazdi. Filter modeling using gravitational search algorithm, Engineering Application of Artificial Intelligence, vol. 24, no.1 pp. 117–122, 2011. doi:10.1016/j.engappai
E. Rasshedi, H. Nezamabadi-pour, and S. Saryazdi. BGSA: binary gravitational search algorithm, Natural computing, vol. 9, no. 3, pp. 727-745, 2010. doi.org: 10.1007/s11047
F. Musharavati, A. M. S. Hamouda. Simulated annealing with auxiliary knowledge for process planning optimization in reconfigurable manufacturing, Robotics and Computer-Integrated Manufacturing, vol. 28, pp. 113-131, 2012. doi:10.1016/j.rcim
H. Ding, L. Benyoucef and X. Xie. A simulation-based multi-objective genetic algorithm approach for networked enterprises optimization, Engineering Application of Artificial Intelligence, vol. 19, pp. 609-623, 2006. doi:10.1016/j.engappai
H. S. Kim and S. B. Cho. Application of interactive genetic algorithm to fashion design, Engineering Applications of Artificial Intelligence, vol. 13, pp. 635-644, 2000. doi.org:10.1016/s0952
Hossein. Nezamabadipour. Inheritance Algorithm, Basic and Advanced Concepts, First Edition, 1-230. 2010. [In Pershian]. doi:10.1109/iscisc
I. Aydogdu, A. Akin and M.P. Saka. Design Optimization of real-World steel space frames using artificial bee colony with Levy flight distribution, Advance in Engineering Software, vol. 92, pp. 1-14,2016. doi:10.1016/j.advengsoft
J. Kennedy, and R. C. Eberhart. particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, vol. 4, pp.1942-1948, 1995. doi.org:10.5772/6754
J. Xkao, F. Qi, Y. Li. Gravitational Choatic Search Algorithm for partners Selection with Due Date Constraint in Virtual Enterprise, Fourth International Workshio on Advanced Computatianal Intelligence, 2011. doi.org:10.1109/iwaci.2011.6159990
K. Ioannidis, G. Ch. Sirakoulis, I. Anreadis. Cellular ants: A method to create collision free trajectories for a cooperative robot team, Robotics and Autonomous System, vol. 59, pp. 113-127, 2011. doi:10.1016/j.robot
L.A.Zadeh. Fuzzy Sets, Information and Cotorol, vol.8, pp.338-353,1965. doi.org:10.1007/s12543
M. Doraghinejad, and H. Nezamabadi-pour. Black Hole: A New Operator For Gravitational Search Algorithm, International Journal Of Computational Intelligence Systems, 7(5), pp. 1-18, 2014. doi.org:10.1080/18756891
M. Dorigo, V. Maniezzo, A. Colorni. The ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics – Part B 26 (1) (1996) 29–41. doi.org:10.5772/13840
M. Shams, E. Rashedi and 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
M. Shams, E. Rashedi and 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.org:10.1016/j.amc
M. Soleimanpour Moghadam, H. Nezamabadi-pour, and M. Farsangi. A Quantom Behaved Gravitational Search Algorithm, Intelligent Information Management, pp. 390-395, 2012. doi.org:10.4236/iim.2012.46043
M.Y. Cheng, Doddy prayogo, Y.W. Wu and M. Marcellinus Lukito. A Hybrid Harmony Search algorithm for discrete sizing optimization of truss structure, Automation in Construction, vol. 69, no.,pp.21-33, 2016. doi:10.1016/j.autcon
N. KarasnogorandJ.Smith. A tutorial for competent memtic algprithm: model, taxonomyand degign issues, IEEE transaction on evolutionary computation, 9(5), 474 - 488.,2005. doi.org:10.1109/tevc.2005.850260
N. Mohd Sabri, M. Puteh, and M.R. Mahmood. A Review of Gravitational Search Algorithm, International Journal of Advances in soft computing and its applications, vol. 5, no. 3, 2013. doi.org:10.1103/physrevd.36.2901
P. C. Chang, J. J. Lin, C. H. Liu. An attribute weight assignment and particle swarm optimization algorithm for medical database classifications, Computer Methods and Programs in Biomedicine vol. 107, pp. 382-392, 2012. doi:10.1016/j.cmpb
P. Tarasewich, and P. R. McMullen. Swarm intelligence: Power in nimbers, Appears in communication of ACM, Agust 2002, 45(8), 62-67. doi.org:10.1049/pbce119h_ch21
Q. Zhua, J. Hu, L. Henschen. A new moving target interception algorithm for mobile robots based on subgoal forecasting and an improved scout and algorithm, Applied Soft Computing, vol. 13, pp. 539-549, 2013. doi:10.1016/j.asoc
R. Dinverno. IntroducinE nistien Relativity, Published in the United States by Oxford university Press lnc, New York, 1992. doi.org:10.1017/cbo9781139140355.020
R. Mansouri, F. Nasseri and M. Khorrami. Effective time variation of G in a model universe with variable space dimention, Physics Letters, vol. 259, pp. 194-200, 1999. doi.org:10.1016/s0375
R.L. Haupt and E. Haupt. Practical Genetic Algorithms, second ed., John Wiley & Sons, 1-288. 2004. doi.org:10.1201/9781420011326
S. Ebrahimi Mood, E. Rasshedi and M.M. Javidi. (2010), New Functions for Mass Caculation in Gravitational Search Algorithm. doi.org:10.24425/aoa
S. Mondal, A. Bhattacharya, S. H. N. Dey. Multi-Objective economic emission load dispatch solutionusing gravitational search algorithm and consideringwind power penetration, Electrical Power and Energy Systems, vol. 44, pp. 282, 292, 2013. doi:10.1016/j.ijepes
S. Sarafrazi, H. Neannhadi-pour, S, Sayazdi. Disruption: Anew operator in Gravitational search algorithm ScientiaIranica, pp.539-548, Feb2011. doi.org:10.1016/j.scient.2011.04.003
U. Guvenca, Y. Sonmezb, S. Dumank, N. Yorukerend. Combined economic and emission dispatch solution using gravitational search algorithm, Scientia Iranica, 19(6):1754–1762. 2012 in press. doi:10.1016/j.scient
W. Zhao. Adaptive Image Enhancement based on Gravitational Search Algorithm, Procedia Engineering, vol. 15, pp. 3288-3292, 2011. doi:10.1016/j.proeng
X. Han and X. Chang. Chaotic secure communication based on a gravitational search algorithm filter, Engineering Applications of Artificial Intelligence, vol. 24, pp.766-774, 2012. doi:10.1016/j.ins
X.Yao, Y. Liu and G. Lin. Evolutionary programming made faster, IEEE Transaction
