A Branch-and-Bound Algorithm for the Multi-Objective Traveling Salesman Problem
Boumesbah Asma, Chergui Mohamed El-Amine · 2024
The goal of this study is to provide an exact method which is able to generate the efficient set of the MultiObjective Traveling Salesman Problem (MTSP) by using a based branch-and-bound principle. This approach allows only efficient Hamiltonian cycles to be constructed for TSP problems with more than two criteria. The branching process is conducted based on edges that are common to a minimum of two non-Hamiltonian cycles within the given graph. Inducing a process where linear constraints are systematically constructed to iteratively break cycles while ensuring the connectivity of the resulting graph. This leads to the partitioning of the initial graph into sub-graphs, each associated with a distinct multi-objective linear program aimed at identifying the non-dominated set of Hamiltonian cycles.