FUW TRENDS IN SCIENCE & TECHNOLOGY JOURNAL
(A Peer Review Journal)
e–ISSN: 2408–5162; p–ISSN: 2048–5170
keywords: Cheapest shop seeker, COPs, metaheuristics, population-based algorithm, TSP
In this paper, a discrete version of the cheapest shop seekers algorithm is presented for solving the traveling salesman problem. The cheapest shop seeker, a recently proposed nature-inspired algorithm utilized to solve the global optimization function. It is a population-based metaheuristic inspired by mimicking a group of shoppers cooperatively seeking for the cheapest shop for shopping and proved to be effective when investigated in continuous domain. The performance of the discrete CSS algorithm is evaluated on some benchmark instances from TSPLIB. Experimental results show that the discrete version is found to be effective on small instances where it obtained optimum solution. Similarly, it had comparable performance on the large instance.
Benders JF 1962. Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1): 238-252. Blum C & Sampels M 2004. An ant colony optimization algorithm for shop scheduling problems.J. Mathematical Modelling & Algorithms, 3(3): 285-308. Bolaji AL, Khader AT, Al-Betar MA & Awadallah MA 2014. University course timetabling using hybridized artificial bee colony with hill climbing optimizer.J. Computational Sci., 5(5): 809-818. Bouly H, Dang DC & Moukrim A 2008. A memetic algorithm for the team orienteering problem.Applications of Evolutionary Computing, 649-658. Lecture Notes in Computer Science, Vol. 4974: 649-658. Brailsford SC, Potts CN & Smith BM 1999. Constraint satisfaction problems: Algorithms and applications. Eur. J. Operational Res., 119(3): 557-581. Burke E, Newall J & Weare R 1996. A memetic algorithm for university exam timetabling. In:E. Burke, P. Ross(eds) The Practice and Theory of Automated Timetabling,Lecture Notes in Computer Science, Vol. 1153: 241-250, Springer Verlag. Crauwels HAJ, Potts CN & Van Wassenhove LN 1998. Local search heuristics for the single machine total weighted tardiness scheduling problem. INFORMS Journal on Computing, 10(3): 341-350. Den Besten M, Stützle T & Dorigo M 2000. Ant colony optimization for the total weighted tardiness problem. In Parallel Problem Solving from Nature PPSN VI (pp. 611-620). Springer Berlin/Heidelberg. Divsalar A, Vansteenwegen P & Cattrysse D 2013. A variable neighborhood search method for orienteering problems with hotel selection. Int. J. Production Econ., 145(1): 150 – 160. Dorigo M 1997. Ant colony system: A cooperative learning approach to the travelling salesman problem. IEEE Transactions on Evolutionary Computation. IEEE, 1(1): 53-66. Fister Jr. I, Yang XS, Fister I, Brest J & Fister D 2013. A brief review of nature-inspired algorithms for optimization ELEKTROTEHNISKI VESTNIK 80(3) English edition. Gendreau M, Hertz A & Laporte G 1994. A tabu search heuristic for the vehicle routing problem.Management Science, 40(10): 1276-90. Gendreau M, Laporte G & Semet F 1998.A branch-and-cut algorithm for the undirected selective traveling salesman problem.Networks, 32(4): 263-273. Gendreau M, Lori M, Laporte G & Martello S 2006. A tabu search algorithm for a routing and container loading problem.Transportation Science, 40(3): 342-50. Glover F & Laguna M 1997. Tabu Search, Kluwer Academic Publishers, Boston. Gomory RE 1958. Outline of an algorithm for integer solution to linear programs. Bull. Amer. Math. Soc., 64: 275–278. Gomory RE 1960. Solving linear programming problems in integers.Combinatorial Analysis, 10: 211-215. Held M & Karp RM 1962.A dynamic programming approach to sequencing problems.J. Soc. Indus. & Appl. Maths., 10(1): 196-210. Ignall E & Schrage L 1965. Application of the branch and bound technique to some flow- shop scheduling problems. Operations Res., 13(3): 400-412. Kaya K & Uçar B 2009. Exact algorithms for a task assignment problem. Parallel Processing Letters, 19(03): 451-465. Kennedy J & Eberhart J 1995 Particle Swarm Optimization. In: Proc. IEEE International Conference Neural Networks, Piscataway NJ, Vol. 4: 1942-1948. Kennedy J & Eberhart R 1997. A discete binary version of the particle swarm optimization [A]. In Proceeding of the Conference on System, Man, and Cybernetics (Vol. 100). NJ, USA: IEEE Service Center. Kirkpatrick S, Gelatt CD & Vecchi MP 1983. Optimization by simulated annealing.Sciences, 220(4598): 671-680. Kwon YK & Moon BR 2003. Daily stock prediction using neuro-genetic hybrids. In Genetic and Evolutionary Computation–GECCO 2003 pp. 214-214. Springer Berlin/Heidelberg. Liao CJ, Tseng CT & Luarn P 2007. A discrete version of particle swarm optimization for flowshop scheduling problems. Computers & Operations Res., 34(10): 3099-3111. Lin SW, Lee ZJ, Ying KC & Lee CY 2009.Applying hybrid meta-heuristics for capacitated vehicle routing problem. Expert Systems with Applications, 36(2), 1505-1512. Manar H & Shameen F 2011.”Survey of genetic algorithms for university timetabling problem” International conference on future information technology IPCSIT vol 13 IACSIT Press Singapore. Matsuo H, Juck SC & Sullivan RS 1989. A controlled search simulated annealing method for the single machine weighted tardiness problem. Annals of Operations Res., 21(1): 85-108. Mezmaz M, Melab N & Talbi EG 2007. Combining metaheuristics and exact methods for solving exactly multi-objective problems on the grid. J. Math. Modelling & Algorithms in Operations Res., 6(3): 393-409. Muthuswamy S & Lam S 2011. Discrete particle swarm optimization for the orienteering problem.Int. J. Indus. Engr: Theory, Applic. & Practice, 18(2): 92-102. Pirkwieser S, Raidl GR & Puchinger J 2008. A Lagrangian decomposition/ evolutionary algorithm hybrid for the knapsack constrained maximum spanning tree problem. In: Recent Advances in Evolutionary Computation for Combinatorial Optimization pp. 69-85. Springer Berlin Heidelberg. Potts CN & Van Wassenhove LN 1985. A branch and bound algorithm for the total weighted tardiness problem. Operations Res., 33(2): 363-377. Reinelt G 1991. TSPLIB – A traveling salesman problem library.ORSA J. Computing, 3(4): 376-384. Ronconi DP 2005.A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking. Annals of Operations Res., 138(1): 53-65. Ropke S & Pisinger D 2006. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4): 455-472. Salman A, Ahmad I & Al-Madani S 2002. Particle swarm optimization for task assignment problem.Microprocessors and Microsystems, 26(8): 363-371. Shaw P 1998. Using constraint programming and local search methods to solve vehicle routing problems.In International Conference on Principles and Practice of Constraint Programming (pp. 417-431). Springer Berlin Heidelberg Shola PB, 2016. The Cheapest Shop Seeker: a new algorithm for optimization problem in a continuous space. IAES Inter. J. of Art. Intel. (IJ-AI), 4(3), 119 - 126. Sonawane MPA & Ragha L 2014. Hybrid genetic algorithm and TABU search algorithm to solve class time table scheduling Problem. Int.. J. Res. Studies in Comp. Sci. & Eng., 1(4): 19-26. Sousa T, Silva A &NevesA 2004. Particle swarm based data mining algorithms for classification tasks. Parallel Computing, 30(5): 767-783. Takeshi Y & Ryohei N 1995. A Genetic Algorithm with Multi-step crossover for Job-shop Scheduling problems. First IEE/IEEE International conference on Genetic Algorithms in Engineering systems: Innovations and Applications (GALESIA ’95), 12-14 September 1995, Sheffield, UK (pp. 146-151). Thompson PM 1988. Local search algorithms for vehicle routing and other combinatorial problems. PhD thesis, Operations Research Center, MIT.
