PYME.Analysis.points.traveling_salesperson.sectioned_two_opt module

PYME.Analysis.points.traveling_salesperson.sectioned_two_opt.calculate_length_with_reversal(order, reversals, positions)
Parameters
order: ndarray

section order

reversals: ndarray

array of bool, forward (False) and reverse (True)

positions: ndarray

pivot positions, sorted such that [::2] yields the positions of one end of each section.

Returns
——-
length: float

cumulative length _between_ sections

Optimize section order and direction with a two-opt + reversal swap algorithm

Parameters
positions: 2darray

Positions array, size n x 2

cut_indices: 1darray

first and last index for each section

sections: 1darray

denotes section assignment for each point in positions

epsilon: float

relative improvement exit criteria for two-opt

PYME.Analysis.points.traveling_salesperson.sectioned_two_opt.reversal_swap(reversals, ind)

Flag a section as being reversed, returning a copy. Parameters ———- reversals: ndarray

array of boolean flags denoting whether a segment is reversed (True) or not

ind: int

index to swap

Returns
new_reversals: ndarray

copy of input reversals but with ind “not”-ed

PYME.Analysis.points.traveling_salesperson.sectioned_two_opt.reversal_two_opt(section_ids, pivot_positions, epsilon)
Parameters
pivot_indices: ndarray

sorted indices (into original position array) of start and end points for each section

section_ids: ndarray

same shape as pivot indices, encoding which section each pivot is in

epsilon: float

relative improvement exit criteria

Returns
——-
PYME.Analysis.points.traveling_salesperson.sectioned_two_opt.split_points_by_grid(positions, points_per_chunk)

Assuming uniform density, separate points using a grid

Parameters
positions: ndarray

Positions array, size n x 2

points_per_chunk: Int

Number of points desired to be in each chunk that a two-opt algorithm is run on. Larger chunks tend toward more ideal paths, but much larger computational complexity.

Returns
section: ndarray

array of int denoting grid assignment

n_sections: int

number of sections in the grid

PYME.Analysis.points.traveling_salesperson.sectioned_two_opt.split_points_kmeans(positions, points_per_chunk)
Parameters
positions: ndarray

Positions array, size n x 2

points_per_chunk: Int

Number of points desired to be in each chunk that a two-opt algorithm is run on. Larger chunks tend toward more ideal paths, but much larger computational complexity.

Returns
section: ndarray

array of int denoting section assignment

n_sections: int

number of sections

PYME.Analysis.points.traveling_salesperson.sectioned_two_opt.tsp_chunk_two_opt_multiproc(positions, epsilon, points_per_chunk, n_proc=1)
PYME.Analysis.points.traveling_salesperson.sectioned_two_opt.two_opt_section(positions, start_section, counts, n_tasks, epsilon, master_route)

Perform two-opt TSP on (potentially) multiple sections.

Parameters
positions: ndarray

positions, shape (n_points, 2), where n_points are just the positions for the tasks this call is responsible for

start_section: int

index denoting where the first position in the input positions belongs in the master_route array

counts: ndarray

array of counts corresponding to the number of positions in each sorting task

n_tasks: int

number of sorting tasks to execute in this function call. Each task will be sorted independently and shoved into the master_route array in the order the tasks are executed.

epsilon: float

relative improvement exit criteria for sorting

master_route: shmarray

output array for the sorted tasks