A dual local search framework for combinatorial optimization problems with TSP application. Issue 11 (1st November 2017)

• Record Type: Journal Article
• Authors: Ouenniche, Jamal; Ramaswamy, Prasanna K.; Gendreau, Michel
• Is Part Of: Journal of the Operational Research Society. Volume 68:Issue 11(2017)
• Page Start: 1377
• Page End: 1398
• Publication Date: 2017-11-01
• Subjects: dual local search -- relaxation -- optimization -- traveling salesman -- routing and scheduling; Operations research -- Periodicals; 658.4034
• DOI: 10.1057/s41274-016-0173-4
• Languages: English
• ISSNs: 0160-5682

Abstract

Abstract: 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.