tspgrasp

The operators listed here are intended to be easily available for the user, so they can be imported directy from tspgrap.

Grasp

class tspgrasp.grasp.Grasp(constructive=None, local_search=None, seed=None)

Greedy Randomized Adaptive Search Procedure for the TSP.

Parameters:
constructiveAny, optional

Constructive heuristic. Current options available are CheapestArc, SemiGreedyArc, CheapestInsertion, RandomInsertion, and SemiGreedyInsertion, which should be instantiated beforehand. By default None, which instantiates a CheapestArc operator.

local_searchAny, optional

Local search heuristic. Current options available are LocalSearch and SimulatedAnnealing, which should be instantiated beforehand. By default None, which uses LocalSearch, a VNS with first improvement

seedint, optional

Random generator seed (differs behavior from cython to python), by default None

Methods

__call__(D[, max_iter, max_moves, ...])

Solves a TSP based on a generic 2-dimensional distance matrix
__call__(D: ndarray, max_iter: int = 10000, max_moves: int = 100000, time_limit: float = inf, target: float = -inf, verbose: bool = False) → Solution

Solves a TSP based on a generic 2-dimensional distance matrix

Parameters:
Dnp.ndarray

2-dimensional distance matrix

max_iterint

Maximum number of complete iterations, by default 10000

max_movesint

Maximum number of local search moves, by default 100000

time_limitfloat, optional

Time limit (s) to interrupt the solution, by default float(“inf”)

targetfloat, optional

Taget value for objective which interrupts optimization process, by default -float(“inf”)

verbosebool, optional

Either or not to print messages during solution

Returns:
Solution

Attributes: - tour : List[int] - cost : float

costs: List[float]

List of costs generated throughout iterations

class tspgrasp.grasp.Solution(tour: Tour)

TSP Solution

cost: float

Cost of solution

tour: List[int]

List of node indexes in solution. Depot is repeated at the end.

Constructive Heuristics

class tspgrasp.environ.CheapestArc(seed: int = None)

Greedy adaptive construction for the TSP inserting the next node at the end of the partial tour. Depot nodes are randomly chosen.

Parameters:
seedint, optional

Random generator seed (differs behavior from cython to python), by default None

Methods

__call__(D)

Solves a TSP based on a pairwise distance matrix.
__call__(D: ndarray) → Solution

Solves a TSP based on a pairwise distance matrix.

Parameters:
Dnp.ndarray

2-dimensional distance matrix

Returns:
Solution

Attributes: - tour : List[int] - cost : float

class tspgrasp.environ.SemiGreedyArc(alpha=(0.0, 1.0), seed=None)

Greedy-randomized constructive heuristic for the TSP. It inserts the next node at the end of the partial tour. Depot nodes are randomly chosen.

Parameters:
alphatuple, optional

Alpha parameter - randomly generated at each iteration between range or fixed scalar. Use values closer to one for a more greedy approach. By default (0.0, 1.0).

seedint, optional

Random generator seed (differs behavior from cython to python), by default None

Attributes:
nodes

nodes: object

problem

problem: tspgrasp.cython.problem.Problem

queue

queue: ‘vector[int]’

rng

rng: tspgrasp.cython.random.RandomGen

tour

tour: tspgrasp.cython.tour.Tour

Methods

__call__(D)

Solves a TSP based on a pairwise distance matrix.

do(self, Problem problem)

class tspgrasp.environ.CheapestInsertion(seed=None)

Greedy adaptive construction for the TSP inserting the next node at the best position between two existing nodes of the partial tour. Depot nodes are randomly chosen.

Parameters:
seedint, optional

Random generator seed (differs behavior from cython to python), by default None

Attributes:
nodes

nodes: object

problem

problem: tspgrasp.cython.problem.Problem

queue

queue: ‘vector[int]’

rng

rng: tspgrasp.cython.random.RandomGen

tour

tour: tspgrasp.cython.tour.Tour

Methods

__call__(D)

Solves a TSP based on a pairwise distance matrix.

do(self, Problem problem)

class tspgrasp.environ.RandomInsertion(seed=None)

Constructive heuristic for the TSP inserting a random next node at the best position between two existing nodes of the partial tour. Depot nodes are randomly chosen.

Parameters:
seedint, optional

Random generator seed (differs behavior from cython to python), by default None

Attributes:
nodes

nodes: object

problem

problem: tspgrasp.cython.problem.Problem

queue

queue: ‘vector[int]’

rng

rng: tspgrasp.cython.random.RandomGen

tour

tour: tspgrasp.cython.tour.Tour

Methods

__call__(D)

Solves a TSP based on a pairwise distance matrix.

do(self, Problem problem)

class tspgrasp.environ.SemiGreedyInsertion(alpha=(0.0, 1.0), seed=None)

Greedy-randomized constructive heuristic for the TSP based on inserting the next node between two existing nodes of the partial tour.

Parameters:
alphatuple, optional

Alpha parameter - randomly generated at each iteration between range or fixed scalar. Use values closer to one for a more greedy approach. By default (0.0, 1.0).

seedint, optional

Random generator seed (differs behavior from cython to python), by default None

Attributes:
nodes

nodes: object

problem

problem: tspgrasp.cython.problem.Problem

queue

queue: ‘vector[int]’

rng

rng: tspgrasp.cython.random.RandomGen

tour

tour: tspgrasp.cython.tour.Tour

Methods

__call__(D)

Solves a TSP based on a pairwise distance matrix.

do(self, Problem problem)