AUTHORS: Supaporn Suwannarongsri, Deacha Puangdownreong

Download as PDF

ABSTRACT: The traveling transportation problem (TTP) is one of the classic algorithmic problems like the traveling salesman problem (TSP) in the field of computer science, operations research and logistics engineering. It has been classified as the NP-complete problems which can be effectively solved by metaheuristic searching techniques based on modern optimization context. Recently, the flower pollination algorithm (FPA) was developed and proposed as one of the most efficient population-based metaheuristic optimization searching techniques to solve continuous and combinatorial optimization problems. Moreover, the FPA’s algorithm is not complex. In this paper, the FPA is applied to solve the large scale traveling transportation problems (LsTTP) consisting of more than 500 destinations. The FPA is tested against six standard LsTTP problems from literatures. Results obtained by the FPA will be compared with those obtained by the genetic algorithm (GA) and the particle swarm optimization (PSO). As results, the FPA can provide optimal solutions for all selected LsTTP problems superior to GA and PSO within shorter computational time.

KEYWORDS: Large Scale Traveling Transportation Problem, Flower Pollination Algorithm, Metaheuristics

REFERENCES:

[1] M. Bellmore and G. L. Nemhauser, The Traveling Salesman Problem: A Survey, Operation Research, Vol. 16, 1986, pp. 538- 558.

[2] S. Kikuchi and P. Chakroborty, Place of Possibility Theory in Transportation Analysis, Transportation Research, Part B, Vol. 40, 2006, pp. 595-615.

[3] G. Reinelt, The Traveling Salesman: Computational Solutions for TSP Applications, Springer-Verlag, 1994.

[4] J. Little, K. Murty, D. Sweeney and C. Karel, An Algorithm for the Traveling Salesman Problem, Operation Research, Vol. 12, 1963, pp. 972-989.

[5] G. B. Dantzig, D. R. Fulkerson and S. M. Johnson, Solution of a Large Scale Traveling Salesman Problem, Operation Research, Vol. 2, 1954, pp. 393-410.

[6] E. H. L. Aarts, J. H. M. Korst and P. J. M. Laarhoven, A Quantitative Analysis of the Simulated Annealing Algorithm: A Case Study for the Traveling Salesman Problem, J. of Stats Phys, Vol. 50, 1988, pp. 189-206.

[7] C. N. Fiechter, A Parallel Tabu Search Algorithm for Large Scale Traveling Salesman Problems, Discrete Applied Mathematics, Vol. 51, No. 3, 1994, pp. 243-267.

[8] J. V. Potvin, Genetic Algorithms for the Traveling Salesman Problem, Annuals of Operation Research, Vol. 63, 1996, pp. 339- 370.

[9] X. C. Shi, Y. C. Liang, H. P. Lee, C. Lu and Q. X. Wang, Particle Swarm Optimization-Based Algorithms for TSP and Generalized TSP, Information Processing Letters, Vol. 103, 2007, pp. 169-176.

[10] S. Suwannarongsri and D. Puangdownreong, Solving Traveling Transportation Problems in Thailand by Cuckoo Search, The 9th International Conference on Sciences, Technology and Innovation for Sustainable Well-Being (STIWB), 2017, pp. 32-36.

[11] X. S. Yang, Flower Pollination Algorithm for Global Optimization, Unconventional Computation and Natural Computation, Lecture Notes in Computer Science, Vol. 7445, 2012, pp. 240- 249.

[12] X. S. Yang, M. Karamanoglua and X. He, Multi-Objective Flower Algorithm for Optimization, Procedia Computer Science, Vol. 18, 2013, pp. 861-868. Y-distance (km.) Y-distance (km.)

[13] D. Puangdownreong, Optimal State-Feedback Design for Inverted Pendulum System by Flower Pollination Algorithm, International Review of Automatic Control (IREACO), Vol. 9, No. 5, 2016, pp. 289-297.

[14] S. Hlungnamtip, C. Thammarat and D. Puangdownreong, Obtaining Optimal PID Controller for DC Motor Speed Control System via Flower Pollination Algorithm, The 9th International Conference on Sciences, Technology and Innovation for Sustainable Well-Being (STIWB), 2017, pp. 52-56.

[15] C. Thammarat, A. Nawikavatan and D. Puangdownreong, Application of Flower Pollination Algorithm to PID Controller Design for Three-Tank Liquid-Level Control System, The 9th International Conference on Sciences, Technology and Innovation for Sustainable Well-Being (STIWB), 2017, pp. 42-46.

[16] S. Hlungnamthip, N. Pringsakul, A. Nawikavatan and D. Puangdownreong, FPABased PID Controller Design for Temperature Control of Electric Furnace System, The 2018 International Conference on Engineering and Natural Science (ICENS 2018), 2018, pp. 60- 68.

[17] D. Puangdownreong, C. Thammarat, S. Hlungnamtip and A. Nawikavatan, Application of Flower Pollination Algorithm to Parameter Identification of DC Motor Model, The 2017 International Electrical Engineering Congress (iEECON–2017), Vol. 2, 2017, pp. 711-714.

[18] TSPLIB95, Symmetric traveling salesman problem, http://comopt.ifi.uniheidelberg.de/ software/ TSPLIB95/, 2011.

[19] M. Held and R. Karp, A Dynamic Programming Approach to Sequencing Problems, SIAM Journal, Vol. 1, 1962, pp. 196-210.

[20] B. J. Glover, Understanding Flowers and Flowering: An Integrated Approach, Oxford University Press, 2007.

[21] P. Willmer, Pollination and Floral Ecology, Princeton University Press, 2011.

[22] K. Balasubramani and K. Marcus, A Study on Flower Pollination Algorithm and Its Applications, International Journal of Application or Innovation in Engineering & Management (IJAIEM), Vol. 3, 2014, pp. 320- 325.