A dual local search framework for combinatorial optimization problems with TSP application
| Autor: | Jamal Ouenniche, Michel Gendreau, Prasanna Kumar Ramaswamy |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization dual local search Heuristic (computer science) Strategy and Management 02 engineering and technology Management Science and Operations Research Travelling salesman problem routing and scheduling Management Information Systems 020901 industrial engineering & automation relaxation 0202 electrical engineering electronic engineering information engineering Combinatorial search Local search (optimization) Mathematics Marketing business.industry Dual (category theory) traveling salesman Combinatorial optimization 020201 artificial intelligence & image processing Relaxation (approximation) Heuristics business optimization |
| Zdroj: | Ouenniche, J, Ramaswamy, P K & Gendreau, M 2017, ' A dual local search framework for combinatorial optimization problems with TSP application ', Journal of the Operational Research Society, vol. 68, no. 11, pp. 1377-1398 . https://doi.org/10.1057/s41274-016-0173-4 |
| ISSN: | 1476-9360 0160-5682 |
| DOI: | 10.1057/s41274-016-0173-4 |
| Popis: | In practice, solving realistically sized combinatorial optimization problems to optimality is often too time-consuming to be affordable; therefore, heuristics are typically implemented within most applications software. A specific category of heuristics has attracted considerable attention, namely local search methods. Most local search methods are primal in nature; that is, they start the search with a feasible solution and explore the feasible space for better feasible solutions. In this research, we propose a dual local search method and customize it to solve the traveling salesman problem (TSP); that is, a search method that starts with an infeasible solution, explores the dual space—each time reducing infeasibility, and lands in the primal space to deliver a feasible solution. The proposed design aims to replicate the designs of optimal solution methodologies in a heuristic way. To be more specific, we solve a combinatorial relaxation of a TSP formulation, design a neighborhood structure to repair such an infeasible starting solution, and improve components of intermediate dual solutions locally. Sample-based evidence along with statistically significant t-tests support the superiority of this dual design compared to its primal design counterpart. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink