.This paper proposes a PSO-based optimization approach with a particular path relinking technique for moving particles. PSO is evaluated for two combinatorial problems. One under uncertainty, which represents a new application of PSO with path relinking in a stochastic scenario. PSO is considered first in a deterministic scenario for solving the Task Assignment Problem (TAP) and hereafter for a resource allocation problem in a petroleum terminal. This is considered for evaluating PSO in a problem subject to uncertainty whose performance can only be evaluated by simulation. In this case, a discrete event simulation is built for modeling a real-world facility whose typical operations of receiving and transferring oil from tankers to a refinery are made through intermediary storage tanks. The simulation incorporates uncertain data and operational details for optimization that are not considered in other mathematical optimization models. Experiments have been carried out considering issues that affect the choice of parameters for both optimization and simulation. The results show advantages of the proposed approach when compared with Genetic Algorithm and OptQuest (a commercial optimization package).
Particle Swarm Optimization (PSO) is a technique developed by Engelbrecht, 2007 and Kennedy and Eberhart, 1995. It is inspired on the behavior of birds in flocks where solutions to a given optimization problem, called particles, “fly” (like birds) through a multidimensional search space. Similarly to Genetic Algorithms (GAs), PSO can be classified as a bio-inspired paradigm. PSO was first developed for continuous optimization problems. However, research of PSO applications for combinatorial optimization problems can be found in the recent literature (Wang et al., 2011, Kennedy and Eberhart, 1997, Rosendo and Pozo, 2010, Souza et al., 2006 and Hu, 2011). In discrete spaces a technique named path relinking (Glover, Kelly, & Laguna, 1999) can be used to move a particle (solution) toward another one, generating a path between the two solutions.
This paper proposes a PSO-based optimization approach where a particular path relinking technique is adopted for moving particles. Additionally, the PSO algorithm is modified to deal with randomness. In this case, simulation is used whenever the fitness of a particle cannot be captured by a simple computation. PSO has been chosen mainly due the fact that it is easy to implement with few parameters to adjust, and interesting results have also been obtained with PSO for combinatorial optimization (literature has demonstrated it gets better results in a faster and cheaper way when compared with other methods (Poli, 2008)). Two applications are considered in this paper to emphasize these PSO properties. Results for both applications are compared with those obtained by a Genetic Algorithm-based approach. In the first part of experiments, PSO is considered in a simple scenario (the Task Assignment Problem – TAP) where simulation and randomness are not present. In the second part, PSO is applied in a more complex scenario involving simulation whose results are also compared with those obtained by OptQuest (Kleijnen & Wan, 2007) (a well-known and fully integrated optimization package of ARENA simulation framework (Kelton, Sadowski, & Sturrock, 2007)). Then, PSO should be adapted to solve a complex combinatorial problem subject to uncertain data. The proposed approach computes the fitness according to an average performance measure obtained over a set of simulation replications. In this case, PSO is used to optimize the utilization of piers and tanks in a complex petroleum terminal. Operational details and uncertain information are incorporated into optimization.
There are two main contributions of this paper. The first is that the PSO algorithm was modified to deal with combinatorial problems in scenarios of randomness whose results have only been recently reported in the literature (Mukhef et al., 2008 and Jiao et al., 2011). These modifications are related to: (i) introduction of the path relinking technique where a particle encodes sets of same type resources of the application (previous approaches adopt this technique in other application contexts (Rosendo and Pozo, 2010 and Souza et al., 2006)) and (ii) analysis of path relinking for PSO subject to uncertain information (path relinking has not been previously used in scenarios of randomness). The second contribution was in the modeling. This includes (i) formalizing the description of the purpose of the approach in a path relinking context, firstly by adapting the notation of combinatorial PSO approaches when they use particles with permutation-based encoding and secondly, by redefining the velocity equation, especially when the terms associated with inertial, cognitive and social components are presented and (ii) a real-world facility that incorporates uncertain data is modeled and operational details which are not considered in other mathematical optimization models are taken into account for optimization.
The paper is organized as follows. Section 2 presents details about PSO and its implementation. The addressed problems are described in Section 3. Section 4 presents our proposed simulation model and optimization approach. Results are shown in Section 5 followed by conclusions in Section 6.
This paper has proposed a PSO-based optimization approach with a particular path relinking technique adopted for moving particles. The PSO algorithm has been tested in a deterministic optimization problem and then modified to be applied in a scenario of randomness found in a petroleum terminal using simulation optimization. The proposed approach has shown good performance to be an attractive option for some particular resource allocation problems as those addressed in the paper. PSO has presented final solutions comparable with or better than GA with less computational burden. Moreover, they are comparable with those of OptQuest with a slight advantage to PSO. Our approach is also able to deal with randomness in the application as it has shown good performance with average values. It turns out that PSO is quite useful for simulation optimization approach where an application-independent algorithm is necessary and run time is a real concern for practical applications. However, further work should be done for comparing the optimization algorithms in terms of convergence properties.
