Metaheuristics for the bi-objective orienteering problem
Tóm tắt
In this paper, heuristic solution techniques for the multi-objective orienteering problem are developed. The motivation stems from the problem of planning individual tourist routes in a city. Each point of interest in a city provides different benefits for different categories (e.g., culture, shopping). Each tourist has different preferences for the different categories when selecting and visiting the points of interests (e.g., museums, churches). Hence, a multi-objective decision situation arises. To determine all the Pareto optimal solutions, two metaheuristic search techniques are developed and applied. We use the Pareto ant colony optimization algorithm and extend the design of the variable neighborhood search method to the multi-objective case. Both methods are hybridized with path relinking procedures. The performances of the two algorithms are tested on several benchmark instances as well as on real world instances from different Austrian regions and the cities of Vienna and Padua. The computational results show that both implemented methods are well performing algorithms to solve the multi-objective orienteering problem.
Tài liệu tham khảo
Archetti, C., Hertz, A., & Speranza, M. G. (2007). Metaheuristics for the team orienteering problem. Journal of Heuristics, 13(1), 49–76.
Chao, I.-M., Golden, B. L., & Wasil, E. A. (1996a). A fast and effective heuristic for the orienteering problem. European Journal of Operations Research, 88(3), 475–489.
Chao, I.-M., Golden, B. L., & Wasil, E. A. (1996b). The team orienteering problem. European Journal of Operational Research, 88(3), 464–474.
Coello Coello, C. A., Van Veldhuizen, D. A., & Lamont, G. B. (2007). Evolutionary algorithms for solving multi-objective problems (2nd ed.). Genetic algorithms and evolutionary computation (Vol. 5, pp. 88–113) New York: Springer. Chap. 2
Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations Research, 6(6), 791–812.
Czyzak, P., & Jaszkiewicz, A. (1996). A multiobjective metaheuristic approach to the localization of a chain of petrol stations by the capital budgeting model. Control and Cybernetics, 25(1), 177–187.
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197.
Doerner, K. F., Gutjahr, W. J., Hartl, R. F., Strauss, C., & Stummer, C. (2004). Pareto ant colony optimization: A metaheuristic approach to multiobjective portfolio selection. Annals of Operations Research, 131(1), 79–99.
Doerner, K. F., Gutjahr, W. J., Hartl, R. F., Strauss, C., & Stummer, C. (2006a). Nature-inspired metaheuristics for multiobjective activity crashing. Omega, 36(6), 1019–1037.
Doerner, K. F., Gutjahr, W. J., Hartl, R. F., Strauss, C., & Stummer, C. (2006b). Pareto ant colony optimization in multiobjective project portfolio selection with ilp preprocessing. European Journal of Operations Research, 171(3), 830–841.
Doerner, K. F., Focke, A., & Gutjahr, W. J. (2007). Multicriteria tour planning for mobile healthcare facilities in a developing country. European Journal of Operational Research, 179(3), 1078–1096.
Dorigo, M., & Di Caro, G. (1999). The ant colony optimization meta-heuristic. In D. Corne, M. Dorigo, & F. Glover (Eds.), New ideas in optimization (pp. 11–32). London: McGraw-Hill. Chap. 2.
Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the travelling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66.
Dorigo, M., & Stuetzle, T. (2004). Ant colony optimization. Cambridge: MIT Press.
Ehrgott, M., & Gandibleux, X. (2000). A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum, 22(4), 425–460.
Ehrgott, M., & Gandibleux, X. (2004). Approximative solution methods for multiobjective combinatorial optimization. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 12(1), 1–63.
Feillet, D., Dejax, P., & Gendreau, M. (2005). Travelling salesman problems with profits. Transportation Science, 39(2), 188–205.
Garcia-Martinez, C., Cordon, O., & Herrera, F. (2007). A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for bi-criteria TSP. European Journal of Operational Research, 180(1), 116–148.
Glover, F., & Laguna, M. (1997). Tabu search. Norwell: Kluwer Academic.
Glover, F., Laguna, M., & Martí, R. (2003). Scatter search and path relinking: Advances and applications. In F. Glover & G. A. Kochenberger (Eds.), International series in operations research and management science : Vol. 57. Handbook of Metaheuristics (pp. 1–35). New York: Springer.
Grunert da Fonseca, V., Fonseca, C. M., & Hall, A. O. (2001). Inferential performance assessment of stochastic optimisers and the attainment function. In E. Zitzler, K. Deb, L. Thiele, C. A. Coello, & D. Corne (Eds.), Lecture notes in computer science : Vol. 1993. First International Conference on Evolutionary Multi-Criterion Optimization (pp. 213–225). New York: Springer.
Hansen, M. P., & Jaszkiewicz, A. (1998). Evaluating the quality of approximations to the non-dominated set (Technical Report IMM-REP-1998-7). Technical University of Denmark, Kgs. Lyngby, Denmark.
Jozefowiez, N., Glover, F., & Laguna, M. (2008). Multi-objective meta-heuristics for the traveling salesman problem with profits. Journal of Mathematical Modelling and Algorithms, 7(2), 177–195.
Kindervater, G. A. P., & Savelsbergh, M. W. P. (1997). Vehicle routing: Handling edge exchanges. In E. Aarts & J. K. Lenstra (Eds.), Local search in combinatorial optimization (pp. 311–336). Chichester: Wiley.
Knowles, J. D., Thiele, L., & Zitzler, E. (2006). A tutorial on the performance assessment of stochastic multiobjective optimizers (Technical Report 214). Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Switzerland, February 2006.
Mladenović, N. (1995). A variable neighborhood algorithm: A new metaheuristic for combinatorial optimization. In Abstract of papers presented at Optimization Days, p. 112, Montréal, Canada, 1995.
Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers and Operations Research, 24(11), 1097–1100.
Pasia, J. M., Hartl, R. F., & Doerner, K. F. (2006). Solving a bi-objective flowshop scheduling problem by Pareto-ant colony optimization. In M. Dorigo, L. M. Gambardella, M. Birattari, A. Martinoli, R. Poli, & T. Stützle (Eds.), Lecture notes in computer science : Vol. 4150. Ant colony optimization and swarm intelligence (pp. 294–305). Berlin: Springer.
Pasia, J. M., Gandibleux, X., Hartl, R. F., & Doerner, K. F. (2007). Local search guided by path relinking and heuristic bounds. In S. Obayashi, K. Deb, C. Poloni, T. Hiroyasu, & T. Murata (Eds.), Lecture notes in computer science : Vol. 4403. Evolutionary multi-criterion optimization (pp. 501–515). Berlin: Springer.
Schott, J. R. (1995). Fault tolerant design using single and multicriteria genetic algorithm optimization. Master’s thesis, Department of Aeronautics and Astronautics, MIT, Cambridge, MA.
Souffriau, W., Vansteenwegen, P., Vanden Berghe, G., & Van Oudheusden, D. (2008). A greedy randomised adaptive search procedure for the team orienteering problem. In EU/MEeting 2008, Troyes, France, October 23–24, 2008.
Steuer, R. E., Gardiner, L. R., & Gray, J. (1996). A bibliographic survey of the activities and international nature of multiple criteria decision making. Journal of Multi-Criteria Decision Analysis, 5(3), 195–217.
Tsiligirides, T. (1984). Heuristic methods applied to orienteering. The Journal of the Operational Research Society, 35(9), 797–809.
Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., & Van Oudheusden, D. (2009). A guided local search metaheuristic for the team orienteering problem. European Journal of Operational Research, 196(1), 118–127.
Zitzler, E., & Thiele, L. (1999). Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, 3(4), 257–271.
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C. M., & Grunert da Fonseca, V. (2003). Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on Evolutionary Computation, 7(2), 117–132.