Local search effects in bi-objective orienteering

ABSTRACT

We analyze the effects of including local search techniques into a multi-objective evolutionary algorithm for solving a bi-objective orienteering problem with a single vehicle while the two conflicting objectives are minimization of travel time and maximization of the number of visited customer locations. Experiments are based on a large set of specifically designed problem instances with different characteristics and it is shown that local search techniques focusing on one of the objectives only improve the performance of the evolutionary algorithm in terms of both objectives. The analysis also shows that local search techniques are capable of sending locally optimal solutions to foremost fronts of the multi-objective optimization process, and that these solutions then become the leading factors of the evolutionary process.

References

1. J.-F. Beruhe, M. Gendreau, and J.-Y. Potvin. 2009. An exact {epsilon}-constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits. European Journal of Operational Research 194, 1 (2009), 39--50.
2. Jakob Bossek. 2015. netgen: Network Generator for Combinatorial Graph Problems. https://github.com/jakobbossek/netgen R package version 1.0.
3. K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (2002), 182--197.
4. Dominique Feillet, Pierre Dejax, and Michel Gendreau. 2005. Traveling Salesman Problems with Profits. Transportation Science 39, 2 (2005), 188--205.
5. Carlo Filippi and Elisa Stevanato. 2013. Approximation schemes for bi-objective combinatorial optimization and their application to the TSP with profits. Computers & Operations Research 40, 10 (2013), 2418--2428.
6. Birger Funke, Tore Grünert, and Stefan Irnich. 2005. Local Search for Vehicle Routing and Scheduling Problems: Review and Conceptual Integration. Journal of Heuristics 11, 4 (2005), 267--306.
7. Bruce L. Golden, Larry Levy, and Rakesh Vohra. 1987. The orienteering problem. Naval Research Logistics 34, 3 (1987), 307--318.
8. Christian Grimme, Stephan Meisel, Heike Trautmann, Günter Rudolph, and Martin Wölck. 2015. Multi-Objective Analysis of Approaches to Dynamic Routing of a Vehicle. In ECIS 2015 Completed Research Papers. Paper 62. AIS Electronic Library.
9. Chris Groër, Bruce Golden, and Edward Wasil. 2010. A library of local search heuristics for the vehicle routing problem. Mathematical Programming Computation 2, 2 (2010), 79--101.
10. Keld Helsgaun. 2009. General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation 1, 2-3 (2009), 119--163.
11. Roy Jonker and Ton Volgenant. 1983. Transforming asymmetric into symmetric traveling salesman problems. Operations Research Letters 2, 4 (1983), 161 -- 163.
12. Nicolas Jozefowiez, Fred Glover, and Manuel Laguna. 2008. Multi-objective Meta-heuristics for the Traveling Salesman Problem with profits. Journal of Mathematical Modelling and Algorithms 7, 2 (2008), 177--195.
13. C. P. Keller and M. Goodchild. 1988. The multiobjective vending problem: A generalization of the traveling salesman problem. Environ. Planning B: Planning Design 15, 2 (1988), 447--460.
14. L Kotthoff, P Kerschke, H Hoos, and H Trautmann. 2015. Improving the State of the Art in Inexact TSP Solving using Per-Instance Algorithm Selection. In LION 9, C. Dhaenens et al. (Eds.). Cham, 202--217.
15. Stephan Meisel. 2011. Anticipatory Optimization for Dynamic Decision Making. Operations Research/Computer Science Interfaces Series, Vol. 51. Springer New York.
16. Stephan Meisel, Christian Grimme, Jakob Bossek, Martin Wölck, Günter Rudolph, and Heike Trautmann. 2015. Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle. In GECCO '15. ACM, New York, NY, USA, 425--432.
17. Olaf Mersmann, Bernd Bischl, Jakob Bossek, Heike Trautmann, Markus Wagner, and Frank Neumann. 2012. Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness. In LION 6, Paris (LNCS), Y Hamadi and M Schoenauer (Eds.), Vol. 7219. Springer, 115--129.
18. Olaf Mersmann, Bernd Bischl, Heike Trautmann, Markus Wagner, and Frank Neumann. 2012. A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem. Annals of Mathematics and Artificial Intelligence 69 (2012), 151--182.
19. Zbigeniew Michalewicz. 1999. Genetic Algorithms + Data Structures = Evolution Programs (3 ed.). Springer, Berlin.
20. Yuichi Nagata and Shigenobu Kobayashi. 2013. A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem. INFORMS Journal on Computing 25, 2 (2013), 346--363.
21. M Solomon. 1987. Algorithms for the vehicle routing and scheduling problem with time windows. Operations Research 35, 2 (1987), 254--265.
22. Pieter Vansteenwegen, Wouter Souffriau, and Dirk Van Oudheusden. 2011. The orienteering problem: A survey. European Journal of Operational Research 209, 1 (2011), 1--10.
23. Eckart Zitzler, Lothar Thiele, Marco Laumanns, Carlos M. Fonseca, and Viviane Grunert da Fonseca. 2003. Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on Evolutionary Computation 7, 2 (2003), 117--132.

Index Terms

• Applied computing

  • Operations research

    • Decision analysis

      • Multi-criterion optimization and decision-making

    • Transportation