Exact algorithms for the equitable traveling salesman problem

DOI10.1016/J.EJOR.2017.02.017MaRDI QIDQ1753595zbMATH OpenOpenAlexFDO

Authors J. Kinable, Bart Smeulders, Eline Delcour, Frits C. R. Spieksma

Publication date 29 May 2018

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://lirias.kuleuven.be/handle/123456789/538102

zbMATH Keywords

combinatorial optimizationexact algorithmstraveling salesman problembranch-and-boundbranch-and-price

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The balanced traveling salesman problem
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• The traveling salesman problem on a graph and some related integer polyhedra
• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• The Black and White Traveling Salesman Problem

Cites work

• scientific article; zbMATH DE number 1187159 (Why is no real title available?)
• (1,2)-Hamiltonian completion on a matching
• A classification of formulations for the (time-dependent) traveling salesman problem
• A method for solving traveling-salesman problems
• Balanced optimization problems
• Balanced paths in acyclic networks: Tractable cases and related approaches
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Efficient algorithms for minimum range cut problems
• Heuristic algorithms for the 2-period balanced travelling salesman problem in Euclidean graphs
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances
• Maximum matching and a polyhedron with 0,1-vertices
• Minimization of maximum absolute deviation in integers
• Mixed integer linear programming formulation techniques
• Most and least uniform spanning trees
• Natural and extended formulations for the time-dependent traveling salesman problem
• Reverse multistar inequalities and vehicle routing problems with a lower bound on the number of customers per route
• Solution of a Large-Scale Traveling-Salesman Problem
• The balanced traveling salesman problem
• The color-balanced spanning tree problem.

Cited in

(7)

• A note on equitable Hamiltonian cycles
• Balanced Optimization with Vector Costs
• The equity constrained shortest path problem
• A variable neighborhood search algorithm for cost-balanced travelling salesman problem
• Mixed integer programming formulations for the balanced traveling salesman problem with a lexicographic objective
• Robust balanced optimization
• A branch-and-cut algorithm for the balanced traveling salesman problem

Describes a project that uses

Uses Software

• JGraphT
• LEMON
• TSPLIB

This page was built for publication: Exact algorithms for the equitable traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1753595)