Efficient Multiobjective Genetic Algorithm for Solving Transportation, Assignment, and Transshipment Problems

Sayed A. Zaki, Abd Allah A. Mousa, Hamdy M. Geneedi, Adel Y. Elmekawy

.

DOI: 10.4236/am.2012.31015                

Abstract

This paper presents an efficient genetic algorithm for solving multiobjective transportation problem, assignment, and transshipment Problems. The proposed approach integrates the merits of both genetic algorithm (GA) and local search (LS) scheme. The algorithm maintains a finite-sized archive of non-dominated solutions which gets iteratively updated in the presence of new solutions based on clustering algorithm. The use clustering algorithm makes the algorithms practical by allowing a decision maker to control the resolution of the Pareto set approximation. To increase GAs’ problem solution power, local search technique is implemented as neighborhood search engine where it intends to explore the less-crowded area in the current archive to possibly obtain more nondominated solutions. The inclusion of local search and clustering algorithm speeds-up the search process and also helps in obtaining a fine-grained value for the objective functions. Finally, we report numerical results in order to establish the actual computational burden of the proposed algorithm and to assess its performances with respect to classical approaches for solving MOTP.

Keywords

Transportation Problem; Genetic Algorithms; Local Search; Cluster Algorithm

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	A. A. Mousa, “Using Genetic Algorithm and TOPSIS Technique for Multiobjective Transportation Problem: A Hybrid Approach,” International Journal of Computer Mathematics, Vol. 87, No. 13, 2010, pp. 3017-3029. doi:10.1080/00207160902875262
[2]	L. Yang and Y. Feng, “A Bicriteria Solid Transportation Problem with Fixed Charge under Stochastic Environment,” Applied Mathematical Modelling, Vol. 31, No. 12, 2007, pp. 2668-2683. doi:10.1016/j.apm.2006.10.011
[3]	W. F. Abd El-Wahed and S. M. Lee, “Interactive Fuzzy Goal Programming for Multiobjective Transportation Problems,” Omega, Vol. 34, No. 2, 2006, pp. 158-166. doi:10.1016/j.omega.2004.08.006
[4]	W. F. Abd El-Wahed, “A Multi-Objective Transportation Problem under Fuzziness,” Fuzzy Sets and Systems, Vol. 117, No. 1, 2001, pp. 27-33. doi:10.1016/S0165-0114(98)00155-9
[5]	Z. Michalewicz, G. A. Vignaux and M. Hobbs, “a Non-standard Genetic Algorithm for the Nonlinear Transportation Problem,” INFORSA Journal on Computing, Vol. 3, No. 4, 1991, pp. 307-316.
[6]	G. A. Vignaux and Z. Michalewicz, “a Genetic Algorithm for the Linear Transportation Problem,” IEEE Transactions on Systems, Man & Cybernetics, Vol. 21, No. 3, 1991, pp. 445-452. doi:10.1109/21.87092
[7]	M. Gen, K. Ida Kono and Y. Z. Li, “Solving Bi-Criteria Solid Transportation Problem by Genetic Algorithm,” Proceeding of the 16th International Conference on Computers & Industrial Engineering, San Antonio, 2-5 October 1994, pp. 572-575.
[8]	M. Gen, Y. Z. Li and Kenichi Ida, “Solving Multiobjective Transportation Problem by Spanning Tree-Based Genetic Algorithm,” IEICE Transactions on Fundamentals, Vol. E82-A, No. 2, 1999, pp. 2802-2810.
[9]	M. Laumanns, L. Thiele, K. Deb and E. Zitzler, “Archiving with Guaranteed Convergence and Diversity in Multi-Objective Optimization,” Proceedings of the Genetic and Evolutionary Computation Conference, New York, 9-13 July 2002, pp. 439-447.
[10]	M. S. Osman, M. A. Abo-Sinna and A. A. Mousa, “IT-CEMOP: An Iterative Co-evolutionary Algorithm for Multiobjective Optimization Problem with Nonlinear Constraints,” Journal of Applied Mathematics & Computation, Vol. 183, No. 1, 2006, pp. 373-389.
[11]	Z. Michalewicz, “Genetic Algorithms + Data Structures = Evolution Programs,” 3rd Edition, Springer-Verlag, Berlin, 1996.
[12]	M. Gen and R.Cheng, “Genetic Algorithms & Engineering Design,” John Wily & Sons, New York, 1997.
[13]	Y. Kilani, “Comparing the Performance of the Genetic and Local Search Algorithms for Solving the Satisfiability Problems,” Applied Soft Computing, Vol. 10, No. 1, 2010, pp. 198-207. doi:10.1016/j.asoc.2009.07.012
[14]	G. Whittaker, et al., “A Hybrid Genetic Algorithm for Multiobjective Problems with Activity analysis-Based Local Search,” European Journal of Operational Research, Vol. 193, No. 1, 2009, pp. 195-203. doi:10.1016/j.ejor.2007.10.050
[15]	C. Hamzacebi,” Improving Genetic Algorithms’ Performance by Local Search for Continuous Function Optimization”, Applied Mathematics and Computation, Vol. 196, No. 1, 2008, pp. 309-317. doi:10.1016/j.amc.2007.05.068
[16]	A. A. Mousa, R. M. Rizk-Allah and W. F. Abd El-Wahed, “A Hybrid Ant Colony Optimization Approach Based Local Search Scheme Formultiobjective Design Optimizations,” Electric Power Systems Research, Vol. 81, No. 4, 2011, pp. 1014-1023. doi:10.1016/j.epsr.2010.12.005
[17]	K. Miettinen, “Non-Linear Multiobjective Optimization,” Kluwer Academic Publisher, Dordrecht, 2002.
[18]	M. S. Osman, M. A. Abo-Sinna and A. A. Mousa, “Epsilon-Dominance Based Multiobjective Genetic Algorithm for Economic Emission Load Dispatch Optimization Problem,” Electric Power Systems Research, Vol. 79, No. 11, 2009, pp. 1561-1567.
[19]	C. M. Fonseca and P. J. Fleming, “An Overview of Evolutionary Algorithms in Multiobjective Optimization,” Evolutionary Computation, Vol. 3, No. 1, 1995, pp. 1-16. doi:10.1162/evco.1995.3.1.1
[20]	M. S. Osman, M. A. Abo-Sinna and A. A. Mousa, “An Effective Genetic Algorithm Approach to Multiobjective Routing Problems (MORPs),” Journal of Applied Mathematics & Computation, Vol. 163. No. 2, 2005, pp. 769-781.
[21]	S. S. Rao,” Engineering Optimization Theory and Practice,” 3rd Edition, John Wiley, New York, 1996, p. 903.
[22]	Y. P. Aneja and K. P. K. Nair, “Bicriteria Transportation Problems,” Management Science, Vol. 25, No. 1, 1979, pp. 73-80. doi:10.1287/mnsc.25.1.73
[23]	A. K. Bit, M. P. Biswal, S. S. Alam, “Fuzzy Programming Approach to Multicriteria Decision Making Transportation Problem,” Fuzzy Sets and Systems, Vol. 50, No. 2, 1992, pp. 35-41. doi:10.1016/0165-0114(92)90212-M
[24]	J. L. Ringuest and D. B. Rinks, “Interactive Solutions for the Linear Multiobjective Transportation Problems,” European Journal of Operational Research, Vol. 32, No. 1, 1987, pp. 96-106. doi:10.1016/0377-2217(87)90274-8