• صفحه اصلی
  • برنامه ریزی سیستم های حمل ونقل یکپارچه با رویکرد الگوریتم جستجوی گرانشی توسعه یافته مبتنی برکنترلرفازی جهش

اشتراک گذاری

آدرس مقاله


کد مقاله : QJOPM-2307-3566 (R1) بازدید : 104 صفحه: 151 - 180

10.71737/jpm.2025.3073566

نوع مقاله: پژوهشی

برنامه ریزی سیستم های حمل ونقل یکپارچه با رویکرد الگوریتم جستجوی گرانشی توسعه یافته مبتنی برکنترلرفازی جهش

محورهای موضوعی : مدیریت(تحقیق در عملیات)

علی رضا حسین زاده کاشانی 1 , سید احمد شایان نیا 2 * , محمد مهدی موحدی 3 , سهیلا سردار 4

1 - دانشجوی دکتری گروه مدیریت صنعتی، واحد تهران شمال، دانشگاه آزاد اسلامی، تهران، ایران
2 - استادیار گروه مدیریت صنعتی، واحد فیروزکوه، دانشگاه آزاد اسلامی، فیزوکوه، ایران
3 - دانشیار گروه مدیریت صنعتی، واحد فیروزکوه، دانشگاه آزاد اسلامی، فیروزکوه، ایران
4 - استادیار گروه مدیریت صنعتی، واحد تهران شمال، دانشگاه آزاد اسلامی، تهران، ایران

تاریخ دریافت : 1402/04/16 تاریخ پذیرش : 1402/07/19 تاریخ انتشار : 1403/12/28

کلید واژه: 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.

  1. 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".

  1. 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.

  1. 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.

  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
متن کامل:
سنجي فرهنگ دانايي: مطالعه موردي

Vol.19, No.72, Spring 2025                                                                Journal of Productivity Management 

 

 

 

 

 

 

 

 

Planning an Integrated Transportation System Using a Gravitational Search Algorithm Based on Fuzzy Mutant Controller

 

Alireza Hosseinzadeh Kashani1, Seyed Ahmad Shayannia2*, Mohammad Mehdi Movahedi3, Soheila Sardar4

 

(Received:2023.07.07 - Accepted:2023.10.11 )

 

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.

2. 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".

3. 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.

4. 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.

5. 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.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

برنامه ریزی سیستم های حمل ونقل یکپارچه با رویکرد الگوریتم جستجوی گرانشی توسعه یافته مبتنی برکنترلرفازی جهش

 

علی رضا حسین زاده کاشانی5، سید احمد شایان نیا*6، محمد مهدی موحدی7، سهیلا سردار8

 

(دریافت: 16/04/1402-پذیرش نهایی: 19/07/1402(

 

 

چکیده

الگوریتم جستجوي گرانشی یک الگوریتم فرا‌‌ابتکاري تازه‌ظهوري است؛ در این الگوریتم به دو روش می‌توان نیروی گرانشی میان پاسخ‌ها را محاسبه کرد. در روش اول یک پاسخ از فضای همسایگی محلی پاسخ جاری انتخاب شده و نیروی گرانشی بین این دو پاسخ محاسبه می‌شود. در روش دوم، نیروی گرانشی بین تمام پاسخ‌های همسایه در فضای همسایگی پاسخ جاری محاسبه می‌شود و به یک پاسخ همسایه محدود نمی‌شود. این الگوریتم در برخی از مسائل بهینه سازي دچار همگرایی زودرس شده و در بهینه محلی گیر می‌کند و پیشرفتی براي پیدا کردن جواب بهینه ندارد که این مشکل از معایب این الگوریتم محسوب می‌شود. برای حل  این مشکل، ضمن تنظیم پارامترهای الگوریتم و توابع انتقال به سمت تعادل بهتر بین اکتشاف و بهره برداری، این الگوریتم را گسترش دادیم. در مرحله اول با مقایسه دو روش نامبرده تحت آزمون قرار گرفت که نتیجه آن بدین‌گونه می‌باشد: روش اول برتری نسبی از نظر پارامتر سرعت رسیدن به جواب و جواب برتر دارد و سپس با تعریف یک تابع جهش ابتکاری، که از کنترلر فازي جهت کنترل کردن میزان جهش استفاده می‌کند، برطرف می‌کند. روش پیشنهاد شده بر روي توابع محک استاندارد که شامل توابع تک مدي و چند مدي است ارزیابی شده است و نتایج حاصل از ارزیابی این دو روش با الگوریتم جستجوي گرانشی استاندارد (GSA) و الگوریتم جمعیت ذرات گرانشی (GPS)، الگوریتم بهینه‌ساز جمعیت ذرات (PSO) و الگوریتم وراثتی حقیقی (RGA) مقایسه شده است. آزمایش‌های مشاهده شده، نشان دهنده این است که این روش ارائه شده نتایج بهتري نسبت به دیگر الگوریتم‌هاي مقایسه شده دارد.

واژه­های کلیدی: الگوریتم نیروی گرانشی، حمل و نقل یکپارچه ترکیبی، مسیریابی، حمل ونقل چند وجهی، وسایل نقلیه،VRP، MTP

 

 

مقدمه

مسأله‌ي مسیریابی وسایل نقلیه به عنوان یک زمینۀ گسترده مطالعاتی همواره مورد توجه محققان بوده است. با مروري بر ادبیات این حوزه دیده شد که تا به حال محدودیت‌هاي مربوط به ظرفیت انبار، ظرفیت وسایل نقلیه و طول مسیر به‌طور هم‌زمان در نظر گرفته نشده است درحالی که در نظر گرفتن هم‌زمان این سه محدودیت با یکدیگر مسأله را به واقعیت نزدیک‌تر می‌کند (جعفری و همکاران، 1390).

مسأله مكان‌يابي مسيريابي، در بسياري از محيط‌هاي لجستيك به مديران براي اخذ تصميماتي مثل محل استقرار تسهيلات (مراكز توزيع يا انبارها)، تخصيص مشتريان به اين تسهيلات، سپس برنامه‌هاي حمل ونقل براي ارتباطات مشتريان به اين تسهيلات كمك مي‌كند. در واقع مسائل مكان‌يابي مسيريابي، به منظور پيدا كردن مكان و تعداد مناسب تسهيلات و نيز مسيرهاي توزيع توسط وسايل نقليه تعريف شده است. تفاوت اساسي بين مسأله مكان يابي مسيريابي با مسأله مكان‌يابي سنتي اين است كه در اولي پس از تعيين مكان تسهيلات، مسيرهاي ارتباطي بين مشتريان و تسهيلات به صورت يك تور بررسي مي‌شود ولي در دومي فرض بر اين است كه مسيرهاي مستقيم بين مشتري و تسهيلات وجود دارد و اين در نهايت به افزايش هزينه‌هاي توزيع منجر مي‌شود. پس برخلاف روش مكان يابي سنتي، در روش مسأله مكان‌يابي مسيريابي با در نظر گرفتن تور، به طور هم‌زمان به دنبال مكان‌هاي بهينه تسهيلات و همچنين مسيرهاي بهينه است (رضوی، 1399).

ترانزیت و حمل و نقل از جمله عوامل مهمی است که در چرخه اقتصاد یک کشور، تمامی ارکان اقتصادي از ابتداي امر تولید تا رساندن کالا به بازارهاي مصرف نهائی را تحت تأثیر قرار می‌دهد. اگر حمل و نقل را در ابعاد کلان آن در نظر بگیریم هیچ فعلی در اقتصاد جامعه وجود ندارد که بدون استفاده از این صنعت انجام پذیرد. از این رو داشتن یک صنعت حمل و نقل کارا تأثیر بسزایی در اقتصاد یک جامعه دارد. کشورهایی که دارای موقعیت جغرافیایی مناسب هستند و از موقعیت ترانزیتی خوبی برخوردارند، درآمدهای حاصل از ترانزیت آن‌ها سهم مهمی در تولید ناخالص ملی آن کشور دارد. کشور ایران نیز با توجه به موقعیت استراتژیک و حساس خود می‌تواند در زمره کشورهاي موفق در زمینه ترانزیت باشد. متأسفانه این صنعت در ایران یکی از بخش‌هایی به شمار می‌رود که با بی‌توجهی مسئولان روبه‌رو بوده است. بخش حمل و نقل و ترانزیت با توجه به گستره‌اي که تحت پوشش دارد سهم عمده‌ای در زمینه‌سازي براي افزایش حجم مبادلات تجاري دارد و هم‌چنین رشد چشمگیر حجم مبادلات تجاري در قرن اخیر، متأثر از افزایش مازاد تولید در برخی کشورها و به دنبال آن گسترش فعالیت هاي بازاریابی بین المللی است. بنابراین بازاریابی در بخش حمل و نقل و تبیین مشکلات موجود از اهمیت ویژه‌اي برخوردار است (نصرآزادانی و همکاران، 1392).

حمل و نقل یکی از زیرساخت‌های هر کشور است که مبنا و لازمه سطوح مختلف دسترسی و انتقال مردم و كالا از یک مکان به مکان‌های دیگر است. سامانه حمل و نقل یکی از عوامل مهم بیان کننده میزان توسعه یافتگی یک کشور است. سامانه‌هاي اطلاعات مکانی در زمینه مدیریت بهینه تسهیلاتی چون حمل و نقل، دارای قابلیت‌های فراوانی هستند. تجزیه و تحلیل شبکه مکانی همانند محاسبه کوتاه‌ترین مسیر، جابه‌جایی و تخصیص منابع، محاسبه سطح دسترسی و غیره از مهم‌ترین این قابلیت‌ها هستند (صابریان، 1395).

در مسأله حاضر، شبکه بین دپو تا بنادر بزرگ به شکل یک شبکه از مسیرهای وسایل نقلیه (VRP) و شبکه ارتباطی بین بنادر بزرگ و مراکز مصرف، به صورت یک شبکه حمل و نقل چند وجهی(MTP) مدل شده است و در این شبکه، امکان تبدیل روش‌های حمل کالا به یکدیگر با صرف هزینه در بعضی از مراکز مصرف و واسط وجود دارد بدین صورت که از بنادر بزرگ واقع در منطقه به عنوان مراکز واسط برای دریافت کالا از کشتی‌های بزرگ و ارسال کالا توسط کشتی‌های کوچک‌تر و سایر وسایل نقلیه به مشتریان استفاده می‌شود. مسأله مورد بررسی يک مسیریابی بهینه دو مرحله‌ای خواهد بود که مرحله اول شامل حمل ونقل کالاها از دپو به مراکز واسط و مرحله دوم شامل حمل ونقل کالاها از مراکز واسط به مشتریان است. ناوگان حمل ونقل شامل انواع مختلف وسيله نقليه اعم از کشتی های سوخت‌بر، فله‌بر، کانتینر‌بر، واگن‌های بقل‌دار، کمپرسی، تانکر، کپسولی برای حمل گاز، کامیون‌های چادری، کفی، کمرشکن، بوژی و غیره می‌باشد که داراي ظرفيت‌هاي متفاوتی براي حمل کالاها هستند. هدف این مسأله، ارسال كالاها به مشتریان به نحوي است كه كالاها با کمترین هزینه حمل و نقل و هزینه انتقال به مشتریان تحویل گردد.

ایده قابل بررسی در این خصوص این است که از بنادر بزرگ موجود در منطقه، به عنوان مراکز واسط برای تغذیه شبکه حمل و نقل دریایی (شامل کشتی‌ها و بنادر کوچک‌تر) استفاده می‌شود. به این ترتیب فرض بر این است که کشتی‌های بزرگ از یک مرکز (دپو) واقع در خارج از منطقه خلیج فارس واقع در منطقه جبل علی می باشد، روانه منطقه می‌شوند و کالاهای خود را در چند بندر بزرگ واسط در ایران شامل بندر عباس، بندر امام، چابهار و خرمشهر تخلیه کرده و سپس به دپو بر می‌گردند. کالاها سپس توسط یک شبکه حمل و نقل چندوجهی (با وجوه حمل دریایی توسط کشتی‌های کوچک‌تر؛ حمل ریلی؛ و حمل زمینی) به مراکز مصرف مورد نظر (مراکز مصرف استانی در ایران، و مقاصد ترانزیتی کالا از ایران مانند ترکمنستان، عراق، ترکیه، روسیه، ایتالیا و...) ارسال می‌شوند. این وضعیت فرصت مناسبی را برای رونق کشتیرانی خصوصی و نیز بنادر کوچک‌تر و کمتر توسعه یافته ایران فراهم می‌کند. به علاوه، همسایگان ایران مانند امارات و پاکستان با سرمایه گذاری زیاد بنادر بزرگی را به وجود آورده‌اند که از ظرفیت آن‌ها  می‌توان برای این منظور و رونق‌دهی به کشتیرانی و بنادر ایران در خلیج فارس و نیز برای افزایش ظرفیت حمل ونقل و ترانزیت ناوگان کشور بهره گرفت. به این ترتیب امکان بهره‌گیری از سرمایه دیگران در جهت فعال کردن بیش از پیش بنادر و ناوگان خصوصی ایران به وجود می‌آید. البته استفاده از این فرصت، نیازمند مطالعات امکان پذیری و اقتصادی و دیگر جنبه های سیاسی و اجتماعی است.

در این بخش به توصیف الگوریتم نیروی گرانشی و چرایی ایده استفاده از این الگوریتم در حل این قبیل مسائل می‌پردازیم. الگوریتم نیروی گرانشی یا جستجوی محلی GSA یک الگوریتم جدید است؛ همانطور که از نام آن پیداست یک روش جستجوی محلی اکتشافی است. علاوه بر این، این الگوریتم در گروه آن دسته از روش‌هایی که از برخی فرآیندهای طبیعی یا فیزیکی تقلید می‌کنند (مثل سرد کردن شبیه سازی شده و الگوریتم ژنتیک)، قرار دارد.

در این طرح هدف توسعه الگوریتم نیروی گرانشی در راستای حل مسائل سیستم‌های حمل و نقل یکپارچه ترکیبی و چند هدفه می‌باشد و در دنیای واقعی تأثیر جاذبه بر اجسام به صورت متقابل و اعمال نیروی گرانشی به تمامی اجسام موجود در فضا ایده اصلی این الگوریتم می‌باشد. بدیهی است این نیرو باعث تغییر سرعت اجسام و کشیده شدن آنها به سمت اجسام بزرگتر می‌شود که در طبیعت می‌توان به رابطه زمین، ماه، اشیای زمینی و دیگر اجسام و اجرام آسمانی موجود اشاره نمود.

تحقيق حاضر به استفاده از الگوریتم گرانش براي حل مسائل حمل و نقل یکپارچه ترکیبی مي‌پردازد. نوآوری پژوهش هم در توسعه مدل حمل و نقل ترکیبی و همچنین در توسعه الگوریتم نیروی گرانشی است به این صورت که در حالت توسعه یافته الگوريتم تنها k جرم مناسب‌تر جمعيت امكان وارد آوردن نيرو به ساير اجرام را دارند. يعني در هر تكرار الگوريتم نيروي وارد بر هر جرم، برابر برآيند نيروي وارد از سوي k جرم برتر جمعيت است. در اين رابطه kbest، بيانگر مجموعه k جرم برتر جمعيت است. در تكرارهاي اوليه الگوريتم، هنوز مساله احتياج به كاوش بالا دارد اما با جلو رفتن زمان، جمعيت به نتايج بهتري مي‌رسد بنابراين مقدار k به صورت متغير با زمان تعريف مي‌شود. به اين صورت كه در زمان شروع تمام اجرام روي يكديگر تاثير مي‌گذارند و با گذشت زمان از تعداد اعضا تاثير گذار بر جمعيت، به صورت يك نسبت خطي كم مي‌شود تا اينكه در انتها، تنها 2 درصد جمعيت بر ساير اعضا نيرو وارد مي‌كنند.

 

 

خلاصه پژوهش‌های انجام شده در این زمینه به قرار ذیل می‌باشد:

 

جدول 1: خلاصه پژوهش های انجام شده

Table 1- Summary of the conducted researches

نویسنده

عنوان

نشریه و سال انتشار

نتیجه

یوسف ربانی، محمدمهدی سپهری، سیدحسام الدین ذگردی

مسأله مسیریابی وسیله نقلیه متصل به حمل ونقل چندوجهی رویکردیکپارچه

پژوهشنامه حمل ونقل، سال پنجم، شماره چهارم، زمستان 1387

در این مقاله يك شبكه متشکل ازمسيرهاي وسايل نقليه ومسيرهاي حمل ونقل چند وجهي براي اولين بار طرح و مدل شده است و با استفاده از روش ابتكاري به نام  RAB  SB- براساس روش سيمپلكس با ورود محدود متغيرها توسعه داده شده است.

یاسرموحدي،روح ا... ذوالفقاری، فریبرزجولاي

تحلیل نقش عوامل مالی در "اثرشلاقی" درزنجیره تأمین دو رده اي

نشریه تخصصی مهندسی صنایع، دوره 45، شماره 2، مهر1390

عوامل مالی تأثیرگذار برتشدید اثرشلاقی مورد توجه قرارگرفته است و به کمی سازی این اثر پرداخته و با واردکردن عوامل مالی در مدل حاصله در دو حالت مورد بررسی دقیق قرار می گیرد :

·       بررسی ارزش زمانی پول درتخمین ارزش مالی تقاضاي برآورد شده درطول p دوره

·       بررسی تغییرات ارزش پولی سفارشات دراثرمدت انتظاربراي تحویل سفارش (L)

مجید دره میرکی

الگوریتم ابتکاری جدید برای حل مسأله مسیریابی وسایل نقلیه

مجله تحقیق در عملیات وکاربرد های آن، سال نهم، شماره چهارم،زمستان 91

الگوریتمی ابتکاری که تلفیقی از کلونی مورچگان و عمل جهش می باشد برای حل مسئله مسیریابی وسیله نقلیه ارائه و با حل 11 مسئله VRP کارایی این الگوریتم پیشنهادی آشکار شده است.

رضاتوکلی مقدم، مسعودربانی، محمدعلی شریعت، نیماصفایی

حل مسئله مسیریابی وسایل نقلیه با پنجره های زمانی نرم با استفاده از یک الگوریتم فرا ابتکاری تلفیقی

نشریه دانشکده فنی، جلد40، شماره4، مهرماه 1385

یک مدل سه معیاره مسیریابی وسایل حمل ونقل بافرض پنجره های زمانی نرم وسخت؛ جهت کمینه سازی هزینه ناوگان؛ هزینه مسافت طی شده وجریمه نقض محدودیتهای پنجره زمانی نرم ارائه شده که برای حل ازروش فرا ابتکاری تلفیقی ازآنیلینگ شبیه سازی شده (SA) با اپراتورهای ژنتیک استفاده شده است.

محمد تقی تقوی فرد، کیوان شیخ، آرین شهسواری

ارائه روش اصلاح شده کلونی مورچگان جهت حل مسئله مسیریابی وسایل نقلیه به همراه پنجره های زمانی

نشریه بین المللی مهندسی صنایع و مدیریت تولید، شماره2، جلد20، تابستان1388

الگوریتم اصلاح شده کلونی مورچگان بر روی تعدادی از نمونه مسائل Solomon  برای مسئله مسیریابی وسائل نقلیه به همراه پنجره های زمانی و ناوگانی ناهمگن ازوسایل نقلیه بکار گرفته شد.

علی ظفری، سید مهدی تشکری هاشمی، مجید یوسفی خوشبخت

الگوریتم ترکیبی موثر ژنتیک برای حل مساله مسیریابی وسیله نقلیه

نشریه بین المللی مهندسی صنایع و مدیریت تولید ، شماره2، جلد21، تابستان1389

نوعی روش فرا ابتکاری ترکیبی شامل  روش اصلاحی ژنتیک که در آن روش جدید تقاطع برای ترکیب کروموزوم ها ارائه شده والگوریتم بهبود دهنده سه گانه می باشد برای حل مساله کلاسیک مسیریابی وسایل نقلیه پیشنهاد می شود.

رضاتوکلی مقدم،  مهدی علینقیان، علیرضا سلامت بخش

ارائه وحل مدل برنامه ریزی ریاضی جدید برای مسیریابی وسائط نقلیه در حالت رقابتی: یک مطالعه موردی

پژوهشنامه حمل ونقل، سال ششم، شماره چهارم، زمستان 1388

در این مقاله، برمبنای مشاهدات دنیای واقعی، رویکرد جدیدی از مسائل مسیریابی وسائط نقلیه به نام مسیریابی رقابتی توسعه یافته است و علاوه بر مدلسازی درجهت اعتبارسنجی به مدل،  برای حل مسائل با ابعاد بزرگ ازالگوریتم فراابتکاری تلفیقی مبتنی برشبیه سازی تبرید با اپراتورهای ژنتیک استفاده شده است.

 

ایرج مهدوی، رضا توکلی مقدم، سید مصطفی قاضی زاده هاشمی

مسیریابی وسایط نقلیه وتعیین تعداد ماشین های جمع آوری زباله بااستفاده ازیک روش فراابتکاری – یک مطالعه موردی

پژوهشنامه حمل ونقل، سال هفتم، شماره اول، بهار 1389

دراین مقاله، یک مدل برنامه ریزی خطی- عددصحیح ازمسأله مسیریابی وسایط نقلیه حمل برگشتی با پنجره زمانی وظرفیت (CVRPBTW) ارائه شده، همچنین یک الگوریتم فراابتکاری مبتنی بربازپخت شبیه سازی شده (HSA) پیشنهادگردیده که جواب های خوبی درمدت زمان مناسب ایجاد می‌کند.

رضاتوكلي مقدم،  نرگس نوروزي،  عليرضا سلامت بخش ورجوي، مهدي علينقيان

مسئله مسيريابي وسائط نقليه با درنظرگرفتن ايجاد توازن درتوزيع كالاها با استفاده ازالگوريتم بهبود يافته بهينه سازي انبوه ذرات

پژوهشنامه حمل ونقل، سال هشتم، شماره چهارم، زمستان 1390

هدف اين مقاله ارائه مدلي بیان شده كه با ايجاد توازن درمقداركالاي توزيع شده نسبت به ظرفيت وسائط نقليه دريك ناوگان ناهمگن، حداكثررضايت براي رانندگان ايجاد گردد وازسويي ديگر با كاهش هزينه هاي حمل ونقل، سود ناشي ازتوزيع افزايش يابد. براي حل این مدل يك الگوريتم بهبود يافته بهينه سازي انبوه ذرات (IPSO) ارائه گرديده است.

محمد یوسفی خوشبخت، فرزاد دیده ور، فرهاد رحمتی، محمد صدیق پور

الگوریتم مؤثر رقابتی فراگیر برای حل مسئله مسیریابی وسیله نقلیه باز

پژوهشنامه حمل و نقل، سال نهم، شماره اول، بهار 1391

الگوریتم فراابتکاری جستجوی رقابتی فراگیر(ICA) به منظورکمینه سازی هزینه‌های مسیریابی وسایل نقلیه که مجبور نیستند به انبار بازگردند (OVRP) ارائه شده است و بر روی 22 مثال مورد آزمایش قرار گرفته است.

رضا توکلی مقدم، مهدی علینقیان، نرگس نوروزی، علیرضا سلامت بخش

حل یک مدل جدید برای مسأله مسیریابی وسائط نقلیه با در نظر گرفتن ایمنی در حمل و نقل مواد خطرناک

مهندسی حمل ونقل، سال دوم ، شماره سوم، بهار1390

دراين مقاله، يک مدل مسيريابي وسائط نقليه چند هدفه شامل کمينه سازي هزينه حمل ونقل وريسک وقوع حوادث درحمل ونقل موادخطرناك ارائه شد. روشفر اابتکاري NSGA-II پيشنهاد و براي نشان دادن کارآيي الگوريتم پيشنهادي، جواب هاي به دست آمده درابعاد کوچک باجوابهاي به دست آمده ازروش محدوديت اپسيلون مقايسه شد.

 

 

از جمله اهداف این مقاله عبارتند از:

1- توسعه الگوریتم نیروی گرانشی برای برنامه ریزی سیستم های حمل و نقل یکپارچه ترکیبی شامل مسیریابی وسایل نقلیه (VRP) و مسیریابی حمل و نقل چندوجهی(MTP)

2- توسعه مدل حمل و نقل ترکیبی از حالت یک دپو به چند دپو

3- مقایسه الگوریتم نیروی گرانشی توسعه یافته با الگوریتم نیروی گرانشی از لحاظ کیفیت روند رسیدن به جواب

 

بنابراین این پژوهش به دنبال پاسخگویی به سوال اساسی زیر می‌باشد:

آیا اجرای نیروی گرانشی، برای حل یک مشکل واقعی در دنیای بیرون قادر به تولید راه حل های معتبر می‌شود؟

 

ابزار و روش

در این پژوهش هدف توسعه الگوریتم نیروی گرانشی در راستای حل مسائل سیستم‌های حمل و نقل یکپارچه ترکیبی و چند هدفه می‌باشد و در دنیای واقعی تأثیر جاذبه بر اجسام به صورت متقابل و اعمال نیروی گرانشی به تمامی اجسام موجود در فضا ایده اصلی این الگوریتم می‌باشد. بدیهی است این نیرو باعث تغییر سرعت اجسام و کشیده شدن آنها به سمت اجسام بزرگتر می‌شود که در طبیعت می‌توان به رابطه زمین، ماه، اشیای زمینی و دیگر اجسام و اجرام آسمانی موجود اشاره نمود.

الگوریتم نیروی گرانشی یا جستجوی محلیGSA یک الگوریتم جدید است و همانطور که از نام آن پیداست یک روش جستجوی محلی اکتشافی است. علاوه بر این، این الگوریتم در گروه آن دسته از روش‌هایی که از برخی فرآیندهای طبیعی یا فیزیکی تقلید می‌کنند (مثل سرد کردن شبیه سازی شده و الگوریتم ژنتیک)، قرار دارد.

در الگوریتم نیروی گرانشی فضای جستجو به عنوان کهکشان تصور می‌شود و راه حل های موجود در فضای جستجو به مانند اجسام داخل کهکشان هستند. هر یک از این اجسام نیروی متقابلی برهم وارد می‌سازند که برای به دست آوردن این نیرو از قانون جاذبه نیوتن به همراه اندکی تغییر برای مسائل img0 استفاده می‌شود. این نیرو بر اساس فرمول برابر است با تفاضل مقدار تابع ارزیابی پاسخ نامزد و پاسخ جاری تقسیم بر شعاع همسایگی به نمای دو. از آنجا که سرعت بالای الگوریتم نیروی گرانشی به سبب جستجوی محلی می‌باشد، ایجاد و انتخاب همسایگی و همچنین انتخاب شروط صحیح برای همسایه بودن راه حل‌ها در این الگوریتم از اهمیت بالایی برخوردار است. علاوه بر سرعت بالا در رسیدن به پاسخ بهینه، الگوریتم با توجه به خواص ذاتی جاذبه از رسیدن و ماندن در یک بهینه محلی اجتناب می‌کند.

درالگوريتم GSA بهينه‌يابي به كمك طرح قوانين گرانشي وحركت، دريك سيستم مصنوعي بازمان گسسته انجام مي‌شود. محيط سيستم همان محدوده تعريف مساله مي‌باشد طبق قانون گرانش هرجرم محل و وضعيت سايراجرام را ازطريق نيروي جاذبه گرانشي درك مي‌كند .بنابراين مي‌توان ازاين نيرو به عنوان ابزاري براي تبادل اطلاعات استفاده كرد. ازبهينه‌ياب طراحي شده، مي‌توان براي حل هرمساله بهينه‌سازي كه درآن هرجواب مساله به صورت يك موقعيت درفضا قابل تعريف است وميزان شباهت آن با سايرجواب‌هاي مساله به صورت يك فاصله قابل بيان باشد، استفاده نمود. ميزان اجرام باتوجه به تابع هدف تعيين مي‌شوند.

درقدم اول فضاي سيستم مشخص مي شود. محيط شامل يك دستگاه مختصات چند بعدي درفضاي تعريف مساله است هرنقطه ازفضا، يك جواب مساله است. عامل‌هاي جستجوكننده، مجموعه‌اي ازاجرام مي‌باشند. هرجرم سه مشخصه دارد:

الف:  موقعيت جرم

ب: جرم گرانشي

ج: جرم اينرسي.

 

اجرام فوق برگرفته از مفاهيم جرم گرانشي اكتيو و جرم اينرسي درفيزيك مي‌باشند. درفيزيك جرم گرانشي اكتيو معياري ازميزان شدت نيروي گرانشي حول يك جسم و جرم اينرسي معياري ازمقاومت جسم درمقابل حركت است.  اين دو مشخصه برخلاف واقعيت مي‌توانند بايكديگر برابر نباشند و مقدار آنها باتوجه به برازندگي هرجرم تعيين مي‌شود موقعيت جرم، نقطه اي درفضا است كه جوابي از مساله است.

 

VRP

مسأله مسیریابی وسایل نقلیه به مجموعه‌ای از مسائل اطلاق می‌گردد که در آن تعدادی خودرو متمرکز در یک یا چند قرارگاه باید به مجموعه‌ای از مشتریان مراجعه نموده و خدمتی را ارائه دهند که هر یک دارای تقاضای معینی می‌باشند. 

 

MTP

برنامه‌ریزی چندوجهی به شیوه سنتی شامل چهار مرحله: تولید جریان، توزیع جریان، شکستن جریان بین وسایل و تخصیص جریان به وسایل می‌شود که همگی به صورت بخش‌های مجزا دیده می‌شوند. مشکل این روش، در نظر نگرفتن هم‌زمان جریان کالا و نوع وسیله حمل و نقل است که باعث افزایش هزینه‌ها می‌شود.

 

یافته ها

مدل ریاضی حمل و نقل یکپارچه VRP وMTP        

 

جدول2: پارامتر های مسأله

Table 2: Problem parameters

تعریف پارامتر

پارامتر

تعداد گره ها در زیر شبکهVRP

N

تعداد گره ها در زیر شبکهMTP

img0 

هزینه حمل ونقل برای طی کردن یال (i, j) E img0 است که غیرمنفی است.

img0 

هزینه انتقال واحد کالا از وسیله نوع k به نوع q در گره j به صورت یک عدد غیرمنفی است.

img0 

تقاضا (مصرف) گره j که یک مقدار عدد صحیح است V-{1} jimg0

img0 

تعداد وسیله نقلیه در زیر شبکه VRP است.

M

ظرفیت هر وسیله در زیر شبکه VRP است img0

 

img0 

تعداد انواع وسیله نقلیه در زیر شبکه MTP است که روی گره های V-{1} فعال هستند.

Kv

 

در این صورت مدل مسیریابی را می‌توان توسط روابط زیر بیان کرد :

MIN Z = img0

img0 (1)

img0(2)

 

img0 

(3)


img0(4)

img0(5)

img0(6)

img0(7)

img0(8)

img0(9)

img0(10)

img0(11)

 

img0(12)

رابطه (1) از چهار قسمت تشکیل شده است: بخش اول مربوط به هزینه‌های حمل از دپو تا مراکز واسط می‌باشد، بخش دوم مربوط به هزینه‌های حمل از مراکز واسط تا مقصد نهایی می‌باشد، بخش سوم شامل هزینه‌های انتقال بین مراکز واسط می‌باشد و بخش چهارم مربوط به هزینه های انتقال بین مراکز مصرف می‌باشد. توجه داشته باشید که در این مدل تابع هدف حاصل جمع هزینه‌های حمل و نقل کالا و انتقال کالا بین وسایل نقلیه است. رابطه (4) - (2) معادلات تعادل برای هر نوع وسیله در هر گره هستنند. رابطه (5) معادلات تعادل برای تعداد وسایل نقلیه فعال در زیر شبکه VRPرا بیان می کند. رابطه (7) – (6) ارضای تقاضاهای موجود در گره‌ها را تضمین می‌کنند. رابطه (8) ظرفیت وسایل موجود در زیر شبکه را در نظر می‌گیرد.رابطه (10) – (9) تواماٌ تضمین کننده آنند که فقط در صورتی که یالی بین دو گره انتخاب شده باشد، جریان مواد در داخل آن جاری شود. رابطه (12) – (11) دو  محـدودیت کلی هستند.

مراحل پیاده سازی الگوریتم به قرار زیر می‌باشد:

 

 

 

 

 

 

 

 

 

نه

 

 

 

 

 

 

 

 

دیاگرام بلوکی الگوریتم جستجوی گرانشی

نتیجه 

در این بخش نتایج پیاده سازي الگوریتم وراثتی حقیقی (RGA)، الگوریتم بهینه‌ساز جمعیت ذرات (PSO)، الگوریتم جمعیت ذرات گرانشی(GPS)، الگوریتم جستجوي گرانشی استاندارد (SGSA) و الگوریتم جستجوي گرانشی جهش یافته (MUGSA) بر روي 23 تابع محک استانداردکه درجدول 2 جدول 3 و جدول4 آورده شده است ارایه می‌شود:  

 

الگوریتم وراثتی حقیقی (RGA)

الگوریتم وراثتی حقیقی با جمعیت اولیه 50 عضو در فضاي جستجو به صورت تصادفی تولید می‌شود. ابعاد مسئله همان تعداد ژن ها است که به صورت پیوسته در فضاي مسئله مقداردهی می‌شود. در هر نسل براساس برازندگی کروموزوم‌ها و با استفاده از چرخ رولت، والدین انتخاب می‌شوند و پس از آن به صورت تصادفی با یکدیگر جفت می شوند. فرزندان با عملگر همبري و جهش تولید می‌شوند. نرخ عملگر همبري 0.3 است و احتمال جهش 0.1 در نظر گرفته شده است.

عملگر همبري پیوسته روي هر جفت X i و X j به صورت رابطه (1) انجام می‌شود. در این رابطه a یک مقدار تصادفی با توزیع یکنواخت در بازه [0,1] است.

 

Xi, new = Xi −a (Xi − X j), X j,new= X j −a (Xi − X j )     (1)

در عملگر جهش روي هر فرزند Xi ، یک ژن X id به صورت تصادفی انتخاب کرده و مقدار آن با یک مقدار جدید تصادفی مطابق روابط 2 و 3 در محدوده فضاي جستجو جایگزین می شود.

 

Sigma = Scale× (1− Tt), Scale = X hi −5 X lo          (2)

a Id, new = X id + rand ×Sigma (3)

 

در روابط بالاXhi  وXlo  به ترتیب حد بالا و حد پایین محدوده فضاي جستجومی‌باشند.T تعداد کل تکرارها و rand یک عدد تصادفی با توزیع نرمال و میانگین صفر می‌باشد.

 

الگوریتم بهینه‌ساز جمعیت ذرات (PSO)

الگوریتم بهینه‌ساز جمعیت ذرات با جمعیت اولیه 50 پرنده در فضاي جستجو به صورت تصادفی تولید می‌شود که Vid , X id مطابق روابط 4 و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)

 

که ri1 و ri2 دو متغیر تصادفی در بازه [1,0] است، C 1وC 2 مقادیر مثبت هستند، W وزن اینرسی است، X id و Vid نشان دهنده موقعیت و سرعت ذرات در بعد d است pbestid و gbestid به ترتیب نشان دهنده بهترین موقعیت قبلی ذرات iام و بهترین موقعیت قبلی در میان تمام ذرات جمعیت است.

در این روابط 2 = 2C1 =C و W در طول تکرارها به صورت خطی از 9/0 تا 2/0 کاهش می‌یابد.

 

الگوریتم جمعیت ذرات گرانشی (GPS)

براي بروزرسانی سرعت الگوریتم جمعیت ذرات گرانشی از رابطه 6 استفاده شده است که در این رابطه، از سرعت الگوریتم بهینه‌ساز جمعیت ذرات Vid (t +1) PSO و شتاب الگوریتم جستجوي گرانشی Vid (t+1) GSA استفاده شده است که به ترتیب در رابطه7 و 8 آورده شده است. که در این روابط 3r یک متغیر تصادفی یکنواخت در بازه [1,0] است که براي ایجاد خاصیت تصادفی سرعت الگوریتم بهینه‌ساز جمعیت ذرات و شتاب الگوریتم جستجوي گرانشی در الگوریتم جمعیت ذرات گرانشی استفاده شده است و 3C و 4C دو ثابت براي تعیین درجه سرعت الگوریتم بهینه‌ساز جمعیت ذرات و شتاب الگوریتم جستجوي گرانشی در الگوریتم جمعیت ذرات گرانشی است که مقدار 3C و 4C، در نظر گرفته شده است.Vid (t+1) GPS براي بروزرسانی موقعیت عامل‌ها در الگوریتم جمعیت ذرات نیز از رابطه 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)

 

الگوریتم جستجوي گرانشی استاندارد (GSA) و الگوریتم جستجوي گرانشی استاندارد همراه با جهش (MUGSA)

دو الگوریتم جستجوي گرانشی استاندارد و الگوریتم جستجوي گرانشی استاندارد همراه با جهش نیز با جمعیت اولیه 50 جرم در فضاي جستجو به صورت تصادفی تولید می شوند. الگوریتم ها مطابق فصل دوم انجام  می‌شوند. در روابط فصل دوم مقدار a برابر 20 و G0 برابر 100 و در ابتدا K0 = N که N تعداد عامل ها است به صورت خطی به 1 کاهش می‌یابد.

نتایج پیاده­­­­­­­­­سازي توابع جدول 5، جدول 6 و جدول 7 که نتایج از میانگین بهترین جواب و میانه بهترین جواب به دست آمده حاصل 30بار اجرا است وتعداد تکرارها برابر 1000 در نظرگرفته شده است.

 

جدول3: نتایج پیاده سازي الگوریتم وراثتی حقیقی، الگوریتم بهینه سازجمعیت ذرات، الگوریتم جمعیت ذرات گرانشی، الگورتم جستجوي گرانشی و الگوریتم جستجوي گرانشی جهش یافته روي توابع محک

Table 3: The results of the implementation of the real inheritance algorithm, the particle population optimization algorithm, the gravitational particle population algorithm, the gravitational search algorithm and the mutated gravitational search algorithm on the benchmark functions.

 

 

RGA[27]

PSO[27]

GPS[27]

GSA

MUGSA

F1

Average

best so far

23.13

1.8×10-3

5.43×10-19

2.26×10-17

3.3032×10-17

Median

best so far

21.87

1.2×10-3

5.65×10-19

2.09×10-17

3.3858×10-17

F2

Average

best so far

1.07

2.0

2.33×10-9

2.34×10-8

2.3330×10-8

Average

best so far

1.07

2.0

2.33×10-9

2.34×10-8

2.3330×10-8

F3

Average

best so far

5.6×10+3

4.1×10+3

1.83×103

240.33

14.6302

Median

best so far

5.6×10+3

2.2×10+3

1.62×103

240.50

13.0726

F4

Average

best so far

11.78

8.1

16.88

3.63×10-9

4.1430×10-9

Median

best so far

11.94

7.4

16.08

3.53×10-9

4.2047×10-9

F5

Average

best so far

1.1×10+3

3.6×10+4

40.70

32.75

29.6085

Median

best so far

1.0×10+3

1.7×10+3

26.70

26.14

26.1217

F6

Average

best so far

24.01

1.0×10-3

357.93

0

0

Median

best so far

24.55

6.6×10-3

311

0

0

F7

Average

best so far

0.06

0.04

0.0099

0.06

0.0178

Median

best so far

0.06

0.04

0.0086

0.06

0.0155

 

 

جدول4: نتایج پیاده سازي الگوریتم وراثتی حقیقی، الگوریتم بهینه سازجمعیت ذرات، الگوریتم جمعیت ذرات گرانشی، الگورتم جستجوي گرانشی و الگوریتم جستجوي گرانشی جهش یافته روي توابع محک کمینه شونده چند مد و با بعد متغییر

Table 4: The results of implementing the real inheritance algorithm, the particle population optimization algorithm, the gravity particle population algorithm, the gravity search algorithm and the mutated gravity search algorithm on multi-mode minimization benchmark functions with variable dimension.

 

 

RGA [27]

PSO [27]

GPS [27]

GSA

MUGSA

F8

Average

best so far

-1.2×10+4

-9.8×10+3

-5.78×10+3

-1.10×103

-3.4920×103

 

Median

best so far

-1.2×10+4

-9.8×10+3

-5.73×10+3

-1.10 ×103

-3.5776×103

F9

Average

best so far

5.90

55.1

17.01

15.69

14.6259

 

Median

best so far

5.71

56.6

15.42

14.92

13.9294

F10

Average

best so far

2.13

9.0×10-3

1.02

3.66×10-9

3.6336×10-9

 

Median

best so far

2.16

6.0×10-3

1.25

3.57 ×10-9

3.4925×10-9

F11

Average

best so far

1.16

0.01

31.24

4.25

0.0087

Median

best so far

1.14

0.0081

29.92

3.92

0.0086

F12

Average

best so far

0.051

0.29

8.12

0.0372

0.0051

Median

best so far

0.039

0.11

6.58

1.57 ×10-19

1.6007×10-19

F13

Average

best so far

0.081

3.1×10-18

27.14

7.32×10-4

3.6625×10-4

Median

best so far

0.032

2.2×10-23

27.82

2.02 ×10-18

2.0831×10-18

 

 

 

 

 

 

 

 

 

جدول5: نتایج پیاده سازي الگوریتم وراثتی حقیقی، الگوریتم بهینه سازجمعیت ذرات، الگوریتم جمعیت ذرات گرانشی، الگورتم جستجوي گرانشی و الگورتم جستجوي گرانشی جهش یافته روي توابع محک کمینه شونده چند مد و با بعد متغیر

Table 5: The results of implementing the real inheritance algorithm, the particle population optimization algorithm, the gravity particle population algorithm, the gravity search algorithm and the mutated gravity search algorithm on multi-mode minimization benchmark functions with variable dimension.

 

 

RGA[27]

PSO[27]

GPS[27]

GSA

MUGSA

F14 n=2

Average best so far

0.998

0.998

7.13

12.74

1.1022

Median

best so far

0.998

0.998

6.90

12.67

1.0022

F15 n=4

Average best so far

4.0×10-3

2.8×10-3

6.80 ×10-4

2.93 ×10-3

9.2500 ×10-4

Median

best so far

1.7×10-3

7.1×10-4

6.27 ×10-4

2.15 ×10-3

7.7164 ×10-4

F16   n=2

Average best so far

-1.0313

-1.0316

-1.0316

-1.0316

-1.0305

Median

best so far

-1.0315

-1.0316

-1.0316

-1.0316

-1.0310

F17   n=2

Average best so far

0.3996

0.3979

0.3979

0.3979

0.3979

Median

best so far

0.3980

0.3979

0.3979

0.3979

0.3979

F18   n=2

Average best so far

5.70

3.00

3.00

3.00

3.0000

Median

best so far

3.0

3.00

3.00

3.00

3.0000

F19   n=3

Average best so far

-3.8627

-3.8628

-3.8628

-3.8628

-3.8698

Median

best so far

-3.8628

-3.8628

-3.8628

-3.8628

-3.8698

F20   n=6

Average best so far

-3.3099

-3.2369

-3.2621

-3.3220

-3.1298

Median

best so far

-3.3217

-3.2031

-3.2625

-3.3220

-3.1243

F21   n=4

Average best so far

-5.6605

-6.6290

-6.8232

-5.9200

-4.3915

Median

best so far

-2.6824

-5.1008

-10.1532

-2.6829

-3.7784

F22   n=4

Average best so far

-7.3421

-9.1118

-9.3842

-10.403

-4.6502

Median

best so far

-10.3932

-10.402

-10.4029

-10.403

-4.1366

F23   n=4

Average best so far

-6.2541

-9.7634

-10.0575

-10.5364

-5.1276

Median

best so far

-4.5054

-10.536

-10.5364

-10.5364

-4.7831

 

بحث

در این پژوهش اعتبارسنجی مدل با استفاده از حل مدل پیشنهادی، برای مسائل مختلف برآورد شده است سپس پنج الگوریتم بهینه‌ساز جمعی، الگوریتم وارثتی حقیقی، الگوریتم بهینه‌ساز جمعیت ذرات، الگوریتم جمعیت ذرات گرانشی، الگوریتم جستجوي گرانشی استاندارد و الگوریتم جستجوي گرانشی جهش یافته در حل 23 تابع محک استاندارد که شامل توابع تک مدو چند مد بودند به کار گرفته شده است.

نتیجه گیري کلی این است که الگوریتم جستجوي گرانشی و الگوریتم جستجوي گرانشی جهش‌یافته بر روي 23 تابع محک استاندارد جواب‌هاي بهتري نسبت به الگوریتم‌هاي وراثتی حقیقی، الگوریتم جمعیت ذرات و الگوریتم جمعیت ذرات گرانشی دارند به جز در توابع F2, F6، F12 الیF15  در توابع F1, F2, F15 بهترین نتایج در الگوریتم جمعیت ذرات گرانشی مشاهده می‌شود در حالی که براي توابع F13, F14 بهترین نتایج در الگوریتم بهینه‌ساز جمعیت ذرات مشاهده شده است و در F9 الگوریتم وراثتی حقیقی کارایی بهتري دارد. کارایی الگوریتم جستجوي گرانشی و الگوریتم جستجوي گرانشی جهش‌یافته در توابع F4, F7, F11, F21 بهتر است و نمودار بهترین جواب دیده در شکل 1 و شکل 2 براي مقایسه بین الگوریتم جستجوي گرانشی والگوریتم جستجوي گرانشی جهش‌یافته به عنوان نمونه، به ترتیب براي F3, F11 است.

img0 

 

 

 

 

 

 

شکل1: نمودارمقایسه بهترین جواب براي الگوریتم جستجوي گرانشی ­­(GSA) و الگوریتم جستجوي گرانشی جهش یافته (MUGSA) در تابعF3

Figure 1: Comparison diagram of the best solution for the gravitational search algorithm (GSA) and the mutated gravitational search algorithm (MUGSA) in the F3 function.

img0 

 

 

 

 

 

شکل2: نمودارمقایسه بهترین جواب براي الگوریتم جستجوي گرانشی(GSA) و الگوریتم جستجوي گرانشی جهش یافته (MUGSA) در تابعF11

Figure 2: Comparison diagram of the best answer for the gravity search algorithm (GSA) and the mutated gravity search algorithm (MUGSA) in function F11

 

نتیجه گیری

نوآوری این پژوهش علاوه برآنکه در توسعه مدل حمل و نقل ترکیبی و در توسعه الگوریتم نیروی گرانشی کاربرد دارد در حفظ حداکثری به رهگیری و اکتشاف با تعریف یک تابع جهش جدید که به وسیله یک کنترلر فازی کار می‌کند این مشکل را نیز برطرف می‌کند و کارایی روش پیشنهادی با پیاده سازی روی توابع محک استاندارد و مقایسه این روش با چند الگوریتم ابتکاری بررسی شده است. در این پژوهش با تعریف یک تابع جهش جدید براي الگوریتم جستجوي گرانشی که به وسیله کنترلر فازي کار می‌کند و با الگوبرداری از فیزیک کوانتوم مطرح گردیده و این مشکل رفع شده است و باعث بهبود عملکرد این الگوریتم شده است، همچنین پارامترهای مورد استفاده در این پژوهش به‌صورت شهودی مورد استفاده قرار گرفته است. عامل‌های جستجوکننده مجموعه‌ای از اجرام در فضای کوانتومی می‌باشند. منطقه‌های بهینه چاه‌های پتانسیلی هستند که اجرام به خودشان جذب می‌کنند. اطلاعات مربوط به برازندگی هر جرم، در قالب جرم گرانشی ذخیره می‌شوند. مقادیر فوق با توجه به برازندگی هر جرم، در قالب جرم گرانشی ذخیره می‌شوند. مقادیر فوق با توجه به برازندگی نسبی هر عامل نسبت به سایر عامل ها در هر تکرار بروزرسانی می‌شود. تبادل اطلاعات و اثرگذاری اجرام روی یکدیگر تحت نیروی جاذبه حاکم بر فضای کوانتومی با وجود چندین چاه پتانسیل انجام می‌شود. با شبیه‌سازی فضای کوانتومی و قوانین حاکم بر آن، موقعیت عامل‌های جستجوکننده با گذشت زمان بهبود پیدا می‌کند. در هر تکرار، اجرامی که تابع برازش بهتری دارند، جرم گرانشی بیشتری نسبت داده می‌شود. در نتیجه تأثیر آن‌ها روی سایر عامل‌ها بیشتر می‌شود. به عبارت دیگر، هر جرم به اندازه شایستگی خود، سایر اجرام به سمت موقعیت‌های مناسب‌تر که همان مراکز چاه‌های پتانسیل می‌باشند، حرکت می‌کنند. همچنین با توجه به اینکه مراکز چاه‌های پتانسیل اجرام برتر هستند، بنابراین جرم بیشتری دارند و در مراحل تکرار الگوریتم نسبت به دیگر اجرام جا به جایی کمتری دارند. این رویکرد سبب می‌شود تا نقاط مناسب یافت شده در طول الگوریتم، حفظ شوند. این ایده پیشنهاد شده بر روي 23 تابع محک استاندارد که شامل توابع تک مد و چند مد است ارزیابی شده است و نتایج به دست آمده نیز با الگوریتم‌های بهینه‌سازي معروفی از قبیل الگوریتم وراثتی حقیقی، الگوریتم بهینه‌ساز جمعیت ذرات، الگوریتم جمعیت ذرات گرانشی و الگوریتم جستجوي گرانش استاندارد مقایسه شده است. نتایج آزمایش‌ها نشان می‌دهد که این ایده پیشنهاد شده در مقایسه با روش‌هاي دیگر یک روش قابل توجهی براي بهبود نتایج است و در آینده این روش جدید پیشنهاد شده، می‌تواند در مسایل بهینه‌سازي مختلفی استفاده شود. آزمایش‌های انجام شده (شامل دوگروه تابع محک استاندارد (کلاسیک و جدید)، با فضای جستجوی پیوسته کارایی الگوریتم را اثبات می‌کند. الگوریتم QIGSA پیشنهادی از سرعت و دقت خوبی برای توابع تک مدی برخوردار می‌باشد. این الگوریتم برای اغلب توابع تک مدی با سرعت بالایی به نقطه بهینه دست می‌یابد. پس از آن الگوریتم QIGSA معرفی شد. QIGSA توانایی بسیار خوبی برای حل انواع مسائل تک مدی و چند مدی دارد. به منظور بررسی الگوریتم QIGSA، این الگوریتم با 9 الگوریتم دیگر در سه بعد مقایسه شد. نتایج حاصل، برتری الگوریتم QIGSA را نسبت به دیگر الگوریتم ها نشان می‌دهد. الگوریتم QIGSA پیشنهادی، برای توابع پیچیده و چند مدی مطرح شده، دقیقا به نقطه بهینه دست می‌یابد که این یکی از ویژگی‌های این الگوریتم می‌باشد. پس از آن نسخه گسسته الگوریتم نیروی گرانشی مطرح شد در نهایت بهینه‌سازی مسایلی در حوزه حمل و نقل یکپارچه ترکیبی VRP/MTP، تقریب سیستم‌های خطی در فضای جستجوی پیوسته و گسسته آورده شد که نشان دهنده کارایی الگوریتم پیشنهادی می‌باشد. در تمامی این مسایل الگوریتم‌های پیشنهادی به نتایج مناسبی دست پیدا کردند.

نتایج حاصل ازمقایسه این پژوهش با نتایج پژوهش (سیزیمون و دومینیک،2013) و (دو و هی، 2017) حاکی از آنست که روش به‌کارگرفته شده کارایی لازم را داشته و می‌تواند در حل مسائل نتایج بهینه‌تری ارائه دهد.

از آنجایی که ایده پیشنهاد شده در این مقاله یک ایده نسبتا تازه و مهمی است، جاي کار زیادي دارد؛ ازجمله می‌توان در ادامه کار، روي این الگوریتم به تأثیر مقادیر مختلف پارامترها ونیز تنظیم وقفی پارامترها تحقیق کرد. همچنین می‌توان کارایی آن را در زمینه کاربرد‌هاي دیگري از زمینه‌هاي مختلف بهینه سازي وسایر موارد بررسی کرد.

 

تضاد منافع:

نویسندگان هیچگونه تضاد منافعی با یکدیگر ندارند.


References 

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

(151)

 

 

[1] .Ph.D. candidate in Industrial Management, Department of Industrial Management, Tehran North Branch, Islamic Azad University, Tehran, Iran

[2] .Assistant Professor, Department of Industrial Management, Firoozkooh branch, Islamic Azad university, Firoozkooh, Iran

*. Corresponding author: SA.shayannia@iau.ac.ir

[3] .Associate Professor, Department of Industrial Management, Firoozkooh branch, Islamic Azad university, Firoozkooh, Iran

[4] .Assistant Professor, Department of Industrial Management, Tehran North Branch, Islamic Azad University, Tehran, Iran

[5] .دانشجوی دکتری گروه مدیریت صنعتی، واحد تهران شمال، دانشگاه آزاد اسلامی، تهران، ایران  andishesaaz@gmail.com

[6] .استادیار گروه مدیریت صنعتی، واحد فیروزکوه، دانشگاه آزاد اسلامی، فیزوکوه، ایران(نویسنده مسؤول) SA.shayannia@iau.ac.ir

[7] .دانشیار گروه مدیریت صنعتی، واحد فیروزکوه، دانشگاه آزاد اسلامی، فیروزکوه، ایران m_m_movahedi@iaufb.ac.ir

[8] .استادیار گروه مدیریت صنعتی، واحد تهران شمال، دانشگاه آزاد اسلامی، تهران، ایران s_sardar@iau-tnb.ac.ir


مقالات مرتبط

حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات دانشگاه آزاد اسلامی است.
حق نشر © 1404-1400

صفحه اصلی| عضویت/ ورود| درباره سند| تماس با ما|
[English] [العربية] [en] [ar]