Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

(1.75MB)
This is an Open Access publication published under CSC-OpenAccess Policy.
Simulation-based Optimization of a Real-world Travelling Salesman Problem Using an Evolutionary Algorithm with a Repair Function
Anna Syberfeldt, Joel Rogstrom, Andre Geertsen
Pages - 27 - 39     |    Revised - 30-09-2015     |    Published - 31-10-2015
Volume - 6   Issue - 3    |    Publication Date - October 2015  Table of Contents
MORE INFORMATION
KEYWORDS
Evolutionary Algorithm, Simulation-based Optimization, Travelling Salesman Problem, Waste Collection, Real-world Case Study.
ABSTRACT
This paper presents a real-world case study of optimizing waste collection in Sweden. The problem, involving approximately 17,000 garbage bins served by three bin lorries, is approached as a travelling salesman problem and solved using simulation-based optimization and an evolutionary algorithm. To improve the performance of the evolutionary algorithm, it is enhanced with a repair function that adjusts its genome values so that shorter routes are found more quickly. The algorithm is tested using two crossover operators, i.e., the order crossover and heuristic crossover, combined with different mutation rates. The results indicate that the order crossover is superior to the heuristics crossover, but that the driving force of the search process is the mutation operator combined with the repair function.
CITED BY (0)  
1 Google Scholar
2 CiteSeerX
3 refSeek
4 Scribd
5 SlideShare
6 PdfSR
1 R. Johnson and M. G. Pilcher. “The traveling salesman problem”, in Networks. E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B Shmoys, eds. 18(3), 1988. 253–254.
2 N. Jozefowiez, F. Semet, and E. G. Talbi. “Mulit-objective vehicle routing problems”, European Journal of Operational Research, vol. 189, pp. 293–309, 2008.
3 M. Gendreau, J.-Y. Potvin, O. Bräysy, G. Hasle, and A. Lokketangen. “Metaheuristics for the vehicle routing problem and its extensions: a categorized bibliography”, in The Vehicle Routing Problem: Latest Advances.
4 B. L. Golden, S. Raghavan, and E. A. Wasil, eds. New Challenges Operations Research/Computer Science Interfaces Series, vol. 43. New York: Springer, 2008, pp. 143– 169.
5 O. Bräysy, W. Dullaert, and M. Gendreau. “Evolutionary algorithms for the vehicle routing problem with time windows”, Journal of Heuristics, vol. 10(6), 587–611, 2004.
6 K. Deb. Multi-Objective Optimization using Evolutionary Algorithms. Chichester, UK: John Wiley & Sons, 2008.
7 J. April, M. Better, F. Glover, and J. Kelly. “New advances for marrying simulation and optimization”, in Proc. 2004 Winter Simulation Conference, 2004, pp. 80–86.
8 Swedish Standards Institute. Geografisk information: Väg- och järnvägsnät – Applikationsschema [Geographical information: Road and railroad network – Application scheme], 2nd ed. Stockholm: Swedish Standards Institute, 2009.
9 J. Grefenstette, R. Gopal, B. J. Rosmaita, and D. Van Gucht. “Genetic algorithms for the traveling salesman problem”, in Proc. 1st International Conference on Genetic Algorithms, 1985, pp. 160–168.
10 D. E. Goldberg and K. Deb. “A comparative analysis of selection schemes used in genetic algorithms”, In Foundations of Genetic Algorithms. G. J. Rawlins, ed. San Mateo, CA: Morgan Kaufmann, 1991, pp. 69–93.
11 D. Knuth. The Art of Computer Programming 2, 3rd ed. Boston, MA: Addison-Wesley, 1998.
12 I. Oliver, D. Smith, and J. Holland. “A study of permutation crossover operators on the traveling salesman problem”, in Proc. Second International Conference on Genetic Algorithms and their Application, 1987, pp. 224–230.
13 P. Larrañaga. “Genetic algorithms for the travelling salesman problem: a review of representations and operators”, Artificial Intelligence Review, vol. 13(2), 129–170, 1999.
14 J.T. Richardson, M. Palmer, G.E. Liepins, and M. Hilliard. “Some Guidelines for Genetic Algorithms with Penalty Functions”, in Proc. Third International Conference on Genetic Algorithms, 1989, pp. 191-197.
15 T. G. Bui and B. R. Moon, “A New Genetic Approach for the Traveling Salesman Problem,” in Proc. First IEEE Conference on Evolutionary Computation, 1994.
16 T. Walters, “Repair and Brood Selection in the Traveling Salesman Problem”, in Proc. Fifth International Conference on Parallel Problem Solving from Nature—PPSN V. A.-E. Eiben, T. Back, M. Schoenauer, and H.-P. Schwefel, Ed. Springer, 1998.
17 M.K. Kundu and N.R. Pal, “Self-crossover and its application to the traveling salesman problem”, in Proc. 12th international conference on Industrial and engineering applications of artificial intelligence and expert systems: multiple approaches to intelligent systems, 1999, pp. 326-332.
18 S. Salcedo-Sanz, “A survey of repair methods used as constraint handling techniques in evolutionary algorithms”, Computer Science Review, vol 3(3), pp. 175-192, Aug 2009.
19 M. Andersson, S. Bandaru, A. Ng, and A. Syberfeldt. “Parameter tuning of MOEAs using a nested optimization approach”, in Proc. 8th International Conference on Evolutionary Multicriterion Optimization, 2015.
20 S. Wessing, N. Beume, G. Rudolph, and B. Naujoks. “Parameter tuning boosts performance of variation operators in multiobjective optimization”, Parallel Problem Solving from Nature, PPSN XI, Lecture Notes in Computer Science, vol. 6238, 728–737, 2010.
21 M. P. W. Savelsbergh and M. Sol. “The general pickup and delivery problem”, Transportation Science, vol. 29(1), 17–29, 1995.
Mr. Anna Syberfeldt
Engineering Science University of Skövde Skövde, SE-54148 - Sweden
anna.syberfeldt@his.se
Dr. Joel Rogstrom
Engineering Science University of Skövde Skövde, SE-54148 - Sweden
Dr. Andre Geertsen
Engineering Science University of Skövde Skövde, SE-54148 - Sweden