geoVeRoPy.tsp module

geoVeRoPy.tsp.solveTSP(nodes: dict, locFieldName: str = 'loc', depotID: int | str = 0, nodeIDs: list[int | str] | str = 'All', vehicles: dict = {0: {'speed': 1}}, vehicleID: int | str = 0, serviceTime: float = 0, edges: str = 'Euclidean', algo: str = 'IP', detailsFlag: bool = False, metaFlag: bool = False, **kwargs) → dict

Use MIP/Heuristic to find optimal/sub-optimal TSP solution

Parameters:

• nodes (dict, required) – The nodes dictionary, with coordinates of given nodes. See nodes

• locFieldName (str, optional, default as 'loc') – The key value in nodes indicating the location of each node.

• depotID (int|string, optional, default as 0) – The node ID of the depot.

• nodeIDs (string 'All' or a list of node IDs, optional, default as 'All') – The following are two options: 1) ‘All’, all nodes will be visited, 2) A list of node IDs to be visited.

• vehicles (dict, optional, default as {0: {'speed': 1}}) – The vehicle information, since the TSP optimizes route for one vehicle, only the first vehicle with vehicleID will be considered. The speed of vehicle needs to be specified.

• vehicleID (int|str, optional, default as 0) – The vehicle that takes the TSP route in vehicles.

• serviceTime (float, optional, default as 0) – The service time needed at each location. If serviceTime is provided in nodes, it will be ignored.

• edges (string, optional, default as 'Euclidean') – The methods for the calculation of distances between nodes. Options and required additional information are referred to matrixDist().

• algo (string, optional, default as 'IP') –

  Select the algorithm for calculating TSP. Options and required additional inputs are as follows:

  1. (default) ‘IP’, use (Mixed) Integer Programming to solve TSP. Needs commercial solver such as Gurobi and COPT.

     • solver: str, supports ‘Gurobi’ and ‘COPT’.

     • fml: str, choose formulation of TSP:

       • if use ‘Gurobi’ as solver, fml supports the following options: [‘DFJ_Lazy’, ‘DFJ_Plainloop’, ‘MTZ’, ‘ShortestPath’, ‘MultiCommodityFlow’, ‘QAP’]. In fact, ‘DFJ_Lazy’ will be faster than all other formulations, implementation of different formulation is for education purpose.

       • if use ‘COPT’ as solver, fml supports ‘DFJ_Lazy’.

     • timeLimit: int|float, additional stopping criteria

     • gapTolerance: int|float, additional stopping criteria

     • outputFlag: bool, True if turn on the log output from solver. Default to be False

  2. ’Heuristic’, use different 2-phase heuristic methods to solve TSP to sub-optimal.

     • cons: str, choose a construction heuristic to find a feasible TSP solution, options and addition inputs needed are as follows:

       • cons = ‘Initial’, use a given initial solution, requires the following information:

         • initSeq: a list of node IDs

       • cons = ‘Insertion’, in each iteration, insert a node into the existing route, which has the minimal cost.

       • cons = ‘RandomInsertion’, in each iteration, randomly insert a not that has not yet been inserted to the route.

       • cons = ‘NearestNeighbor’, in each iteration, find the (k-)nearest node to the end of existing route and add it to the route.

         • k: the k-th nearest neighbor, default to be 1

       • cons = ‘Sweep’, sweep all nodes clock-wise (or counter-clock-wise) and add the node to the route one by one.

       • cons = ‘Christofides’, use Christofides algorithm

       • cons = ‘CycleCover’, use CycleCover algorithm, particularly design for Asymmetric TSP

       • cons = ‘Random’, randomly create a feasible route

     • impv: str, choose the local improvement heuristic to improve the existing feasible route

       • impv = ‘2Opt’, use the 2-opt algorithm

  3. ’Metaheuristic’, use metaheuristic methods to solve TSP to sub-optimal, different metaheuristic methods requires different construction phase of heuristic

     • cons: str, construction heuristic for metaheuristic, options depends on meta

     • meta: str, choose a metaheuristic improvement method

       • meta = ‘SimulatedAnnealing’, use Simulated Annealing to improve a solution create by ‘cons’, choice of ‘cons’ are all construction heuristic available for ‘Heuristic’

       • meta = ‘GeneticAlgorithm’, use Genetic Algorithm to create solutions. Choice of ‘cons’ includes [‘Random’, ‘RandomInsertion’]

• detailsFlag (bool, optional, default as False) – If True, an additional field vehicle will be added into the solution, which can be used for animation. See aniRouting().

• **kwargs (optional) – Provide additional inputs for different edges options and algo options

Returns:

A TSP solution in the following format::

>>> solution = {
...     'ofv': ofv,
...     'seq': seq,
...     'gap': gap,
...     'solType': solType,
...     'lowerBound': lb,
...     'upperBound': ub,
...     'runtime': runtime
... }

Return type:

dict