Development of Traveling Salesman Problem in Returned Products and Solving with Bat Algorithm

Subject Areas : Industrial Management

Meisam Jafari Eskandari ¹ , Ali Amouzad Khalili ²

1 - Payame Noor University, Department of Industrial Engineering, Tehran, Iran
2 - M.A student, Payame Noor, Department of Industrial Engineering, Asalouyeh, Iran

Received: 2016-01-13 Accepted : 2016-07-18 Published : 2016-08-25

Keywords:

Abstract :

The Travelling Salesman Problem (often called TSP) is a classic algorithmic problem in the field of computer science. TSP is a special case of the traveling purchaser problem and the vehicle routing problem. It is focused on optimization. In this context better solution often means a solution that is cheaper. In this paper, TSP models to returned products to manufacturers seeking to minimize transport costs. Since the model is NP-Hard, to solve it we use bat algorithm.

References:

1. pplegate, D. L.; Bixby, R. M.; Chvátal, V.; Cook, W. J. (2006), the Traveling Salesman Problem, ISBN 0-691-12993-2.


2. Bektas, T. (2006). The multiple traveling salesman problem: An overview of formulations and solution procedures. Omega, 34(3), 209–219.


3. Chan, D. and Mercier, D. (1989). IC insertion: An application of the traveling salesman Problem, International Journal of Production Research, 27, 1837–1841.


4. Cordeau,J.F.,Ghiani,G.,& Guerriero, E. (2014). Analysis and branch and-cut algorithm for the time dependent travelling salesman problem. Transportation Science, 48(1), 46–58.


5. Gromicho J., Paixao J. and Branco I. (1992). Exact solution of multiple traveling salesman problems, In: MustafaAkgül, et al., editors. Combinatorial optimization. NATO ASI Series, Berlin: Springer, F82, 291–292.


6. Hougardy Stefan, Mirko Wilde. (2014). On the nearest neighbor rule for the metric traveling salesman problem, Discrete Applied Mathematics.


7.  Li. D, and H.X. Sun. (2009) “An Application Research of TSP Based on Genetic Algorithm,” Science Technology of Heilongjiang Province, (13), 27.


8. Nemati, K., Shamsuddin, S.M. and Saberi Kamarposhti, M. (2011). Using Imperial Competitive Algorithm for Solving Traveling Salesman Problem and Comparing the Efficiency of the Proposed Algorithm with Methods in Use, Australian Journal of Basic and Applied Sciences, 5(10), 540-543.


9. Peng. D.P, Z.Y. Lin, and J.Q. Wang. (2002).An Improved Genetic Algorithm for TSP      Problem, Computer Engineering and Applications, (13), 91-93.


10. Roberti, R., & Toth, P. (2012). Models and algorithms for the asymmetric traveling sales man problem: an experimental comparison. EURO Journal on Transportation and Logistics,1,113–133.


11. Salari M., Z. Naji Azimi. (2012). An integer programming-based local search for the covering salesman problem, Comput. Oper. Res. 39 (11), 2594–2602.


12. Salari Majid, Mohammad H. Shaelaiea, Zahra Naji-Azimib. (2014). The generalized covering traveling salesman problem, Applied Soft Computing.


13. Soylu Banu. (2015). A general variable neighborhood search heuristic for multiple traveling salesmen problem, Computers & Industrial Engineering.


14. Tas Duygu, Michel Gendreaub, Ola Jabali, Gilbert Laporte. (2015). The traveling salesman problem with time-dependent service times, European Journal of Operational Research2.


15. Venkatesh, P., & Singh, A. (2015). Two metaheuristic approaches for the multiple traveling salesperson problem. Applied Soft Computing, 26, 74–89.


16. Wong, L.P., Low, M.Y.H. and Chong, C.S. (2008). A bee colony optimization algorithm for traveling salesman problem, Modeling & Simulation, AICMS 08. Second Asia International Conference on, 818– 823.


17.  Yang, X.S. (2008). Nature-inspired metaheuristic algorithms, 1stEdition, Luniver Press.


18.  Yang, X.S. (2010). a new metaheuristic bat-inspiredalgorithm, in: Nature Inspired Cooperative Strategiesfor Optimization, NISCO 2010, Studies in Computational Intelligence, Springer Berlin. Available from: http://arxiv.org/


19.  Yang, X.S. (2011). Bat algorithm for multi-objectiveoptimization, International Journal Bio-Inspired Computation. Available from: http://arxiv.org/


20. Zhang, X. and Tang, L. (2009). A new hybrid ant colony optimization algorithm for the vehicle routing problem, Pattern Recognition Letters, 30, 848–855.

1. Applegate, D. L.; Bixby, R. M.; Chvátal, V.; Cook, W. J. (2006), the Traveling Salesman Problem, ISBN 0-691-12993-2.


2. Bektas, T. (2006). The multiple traveling salesman problem: An overview of formulations and solution procedures. Omega, 34(3), 209–219.


3. Chan, D. and Mercier, D. (1989). IC insertion: An application of the traveling salesman Problem, International Journal of Production Research, 27, 1837–1841.


4. Cordeau,J.F.,Ghiani,G.,& Guerriero, E. (2014). Analysis and branch and-cut algorithm for the time dependent travelling salesman problem. Transportation Science, 48(1), 46–58.


5. Gromicho J., Paixao J. and Branco I. (1992). Exact solution of multiple traveling salesman problems, In: MustafaAkgül, et al., editors. Combinatorial optimization. NATO ASI Series, Berlin: Springer, F82, 291–292.


6. Hougardy Stefan, Mirko Wilde. (2014). On the nearest neighbor rule for the metric traveling salesman problem, Discrete Applied Mathematics.


7.  Li. D, and H.X. Sun. (2009) “An Application Research of TSP Based on Genetic Algorithm,” Science Technology of Heilongjiang Province, (13), 27.


8. Nemati, K., Shamsuddin, S.M. and Saberi Kamarposhti, M. (2011). Using Imperial Competitive Algorithm for Solving Traveling Salesman Problem and Comparing the Efficiency of the Proposed Algorithm with Methods in Use, Australian Journal of Basic and Applied Sciences, 5(10), 540-543.


9. Peng. D.P, Z.Y. Lin, and J.Q. Wang. (2002).An Improved Genetic Algorithm for TSP      Problem, Computer Engineering and Applications, (13), 91-93.


10. Roberti, R., & Toth, P. (2012). Models and algorithms for the asymmetric traveling sales man problem: an experimental comparison. EURO Journal on Transportation and Logistics,1,113–133.


11. Salari M., Z. Naji Azimi. (2012). An integer programming-based local search for the covering salesman problem, Comput. Oper. Res. 39 (11), 2594–2602.


12. Salari Majid, Mohammad H. Shaelaiea, Zahra Naji-Azimib. (2014). The generalized covering traveling salesman problem, Applied Soft Computing.


13. Soylu Banu. (2015). A general variable neighborhood search heuristic for multiple traveling salesmen problem, Computers & Industrial Engineering.


14. Tas Duygu, Michel Gendreaub, Ola Jabali, Gilbert Laporte. (2015). The traveling salesman problem with time-dependent service times, European Journal of Operational Research2.


15. Venkatesh, P., & Singh, A. (2015). Two metaheuristic approaches for the multiple traveling salesperson problem. Applied Soft Computing, 26, 74–89.


16. Wong, L.P., Low, M.Y.H. and Chong, C.S. (2008). A bee colony optimization algorithm for traveling salesman problem, Modeling & Simulation, AICMS 08. Second Asia International Conference on, 818– 823.


17.  Yang, X.S. (2008). Nature-inspired metaheuristic algorithms, 1stEdition, Luniver Press.


18.  Yang, X.S. (2010). a new metaheuristic bat-inspiredalgorithm, in: Nature Inspired Cooperative Strategiesfor Optimization, NISCO 2010, Studies in Computational Intelligence, Springer Berlin. Available from: http://arxiv.org/


19.  Yang, X.S. (2011). Bat algorithm for multi-objectiveoptimization, International Journal Bio-Inspired Computation. Available from: http://arxiv.org/


20. Zhang, X. and Tang, L. (2009). A new hybrid ant colony optimization algorithm for the vehicle routing problem, Pattern Recognition Letters, 30, 848–855.