Class: ORTools::TSP

Inherits:
Object
  • Object
show all
Defined in:
lib/or_tools/tsp.rb

Constant Summary collapse

DISTANCE_SCALE = 
1000
DEGREES_TO_RADIANS = 
Math::PI / 180

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(locations) ⇒ TSP

Returns a new instance of TSP.

Raises:

  • (ArgumentError) 


8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/or_tools/tsp.rb', line 8

def initialize(locations)
  raise ArgumentError, "Locations must have latitude and longitude" unless locations.all? { |l| l[:latitude] && l[:longitude] }
  raise ArgumentError, "Latitude must be between -90 and 90" unless locations.all? { |l| l[:latitude] >= -90 && l[:latitude] <= 90 }
  raise ArgumentError, "Longitude must be between -180 and 180" unless locations.all? { |l| l[:longitude] >= -180 && l[:longitude] <= 180 }
  raise ArgumentError, "Must be at least two locations" unless locations.size >= 2

  distance_matrix =
    locations.map do |from|
      locations.map do |to|
        # must be integers
        (distance(from, to) * DISTANCE_SCALE).to_i
      end
    end

  manager = ORTools::RoutingIndexManager.new(locations.size, 1, 0)
  routing = ORTools::RoutingModel.new(manager)

  distance_callback = lambda do |from_index, to_index|
    from_node = manager.index_to_node(from_index)
    to_node = manager.index_to_node(to_index)
    distance_matrix[from_node][to_node]
  end

  transit_callback_index = routing.register_transit_callback(distance_callback)
  routing.set_arc_cost_evaluator_of_all_vehicles(transit_callback_index)
  assignment = routing.solve(first_solution_strategy: :path_cheapest_arc)

  @route_indexes = []
  @distances = []

  index = routing.start(0)
  while !routing.end?(index)
    @route_indexes << manager.index_to_node(index)
    previous_index = index
    index = assignment.value(routing.next_var(index))
    @distances << routing.arc_cost_for_vehicle(previous_index, index, 0) / DISTANCE_SCALE.to_f
  end
  @route_indexes << manager.index_to_node(index)
  @route = locations.values_at(*@route_indexes)
  @total_distance = @distances.sum
end

Instance Attribute Details

#distances ⇒ Object (readonly)

Returns the value of attribute distances.



3
4
5
 
# File 'lib/or_tools/tsp.rb', line 3

def distances
  @distances
end

#route ⇒ Object (readonly)

Returns the value of attribute route.



3
4
5
 
# File 'lib/or_tools/tsp.rb', line 3

def route
  @route
end

#route_indexes ⇒ Object (readonly)

Returns the value of attribute route_indexes.



3
4
5
 
# File 'lib/or_tools/tsp.rb', line 3

def route_indexes
  @route_indexes
end

#total_distance ⇒ Object (readonly)

Returns the value of attribute total_distance.



3
4
5
 
# File 'lib/or_tools/tsp.rb', line 3

def total_distance
  @total_distance
end