ml4co_kit.task.routing.tsp.tsp

Traveling Salesman Problem (TSP).

TSP requires finding the shortest tour that visits each vertex of the graph exactly once and returns to the starting node.

Classes

TSPTask(distance_type, round_type, precision)

class ml4co_kit.task.routing.tsp.tsp.TSPTask(distance_type: ~ml4co_kit.task.routing.base.DISTANCE_TYPE = DISTANCE_TYPE.EUC_2D, round_type: ~ml4co_kit.task.routing.base.ROUND_TYPE = ROUND_TYPE.NO, precision: ~numpy.float32 | ~numpy.float64 = <class 'numpy.float32'>)

Bases: RoutingTaskBase

check_constraints(sol: ndarray) → bool

Check if the solution is valid.

static edges_to_node_pairs(edge_target: ndarray)

Helper function to convert edge matrix into pairs of adjacent nodes.

evaluate(sol: ndarray, check_constr: bool = True) → floating

Evaluate the total distance of the TSP solution.

from_data(points: ndarray | None = None, sol: ndarray | None = None, ref: bool = False, normalize: bool = False, name: str | None = None)

Create a problem instance from raw data. To be implemented by subclasses.

from_tsplib(tsp_file_path: Path | None = None, tour_file_path: Path | None = None, ref: bool = False, normalize: bool = False)

Load TSP data from a TSPLIB file.

render(save_path: Path, with_sol: bool = True, figsize: tuple = (5, 5), node_color: str = 'darkblue', edge_color: str = 'darkblue', node_size: int = 50)

Render the TSP problem instance with or without solution.

to_tsplib(tsp_file_path: Path | None = None, tour_file_path: Path | None = None)

Save TSP data to a TSPLIB file.