OR-Tools - operations research tools - for Ruby
Add this line to your application’s Gemfile:
gem "or-tools"Installation can take a few minutes as OR-Tools downloads and builds.
Higher Level Interfaces
Linear Optimization
Integer Optimization
Constraint Optimization
Assignment
Routing
- Traveling Salesperson Problem (TSP)
- Vehicle Routing Problem (VRP)
- Capacity Constraints
- Pickups and Deliveries
- Time Window Constraints
- Resource Constraints
- Penalties and Dropping Visits
- Routing Options
Bin Packing
Network Flows
Scheduling
Other Examples
Specify people and their availabililty
people = [
{
availability: [
{starts_at: Time.parse("2020-01-01 08:00:00"), ends_at: Time.parse("2020-01-01 16:00:00")},
{starts_at: Time.parse("2020-01-02 08:00:00"), ends_at: Time.parse("2020-01-02 16:00:00")}
],
max_hours: 40 # optional, applies to entire scheduling period
},
{
availability: [
{starts_at: Time.parse("2020-01-01 08:00:00"), ends_at: Time.parse("2020-01-01 16:00:00")},
{starts_at: Time.parse("2020-01-03 08:00:00"), ends_at: Time.parse("2020-01-03 16:00:00")}
],
max_hours: 20
}
]Specify shifts
shifts = [
{starts_at: Time.parse("2020-01-01 08:00:00"), ends_at: Time.parse("2020-01-01 16:00:00")},
{starts_at: Time.parse("2020-01-02 08:00:00"), ends_at: Time.parse("2020-01-02 16:00:00")},
{starts_at: Time.parse("2020-01-03 08:00:00"), ends_at: Time.parse("2020-01-03 16:00:00")}
]Run the scheduler
scheduler = ORTools::BasicScheduler.new(people: people, shifts: shifts)The scheduler maximizes the number of assigned hours. A person must be available for the entire shift to be considered for it.
Get assignments (returns indexes of people and shifts)
scheduler.assignments
# [
# {person: 2, shift: 0},
# {person: 0, shift: 1},
# {person: 1, shift: 2}
# ]Get assigned hours and total hours
scheduler.assigned_hours
scheduler.total_hoursFeel free to create an issue if you have a scheduling use case that’s not covered.
Create a seating chart based on personal connections. Uses this approach.
Specify connections
connections = [
{people: ["A", "B", "C"], weight: 2},
{people: ["C", "D", "E", "F"], weight: 1}
]Use different weights to prioritize seating. For a wedding, it may look like:
connections = [
{people: knows_partner1, weight: 1},
{people: knows_partner2, weight: 1},
{people: relationship1, weight: 100},
{people: relationship2, weight: 100},
{people: relationship3, weight: 100},
{people: friend_group1, weight: 10},
{people: friend_group2, weight: 10},
# ...
]If two people have multiple connections, weights are added.
Specify tables and their capacity
tables = [3, 3]Assign seats
seating = ORTools::Seating.new(connections: connections, tables: tables)Each person will have a connection with at least one other person at their table.
Get tables
seating.assigned_tablesGet assignments by person
seating.assignmentsGet all connections for a person
seating.connections_for(person)Get connections for a person at their table
seating.connections_for(person, same_table: true)Create locations - the first location will be the starting and ending point
locations = [
{name: "Tokyo", latitude: 35.6762, longitude: 139.6503},
{name: "Delhi", latitude: 28.7041, longitude: 77.1025},
{name: "Shanghai", latitude: 31.2304, longitude: 121.4737},
{name: "São Paulo", latitude: -23.5505, longitude: -46.6333},
{name: "Mexico City", latitude: 19.4326, longitude: -99.1332},
{name: "Cairo", latitude: 30.0444, longitude: 31.2357},
{name: "Mumbai", latitude: 19.0760, longitude: 72.8777},
{name: "Beijing", latitude: 39.9042, longitude: 116.4074},
{name: "Dhaka", latitude: 23.8103, longitude: 90.4125},
{name: "Osaka", latitude: 34.6937, longitude: 135.5023},
{name: "New York City", latitude: 40.7128, longitude: -74.0060},
{name: "Karachi", latitude: 24.8607, longitude: 67.0011},
{name: "Buenos Aires", latitude: -34.6037, longitude: -58.3816}
]Locations can have any fields - only latitude and longitude are required
Get route
tsp = ORTools::TSP.new(locations)
tsp.route # [{name: "Tokyo", ...}, {name: "Osaka", ...}, ...]Get distances between locations on route
tsp.distances # [392.441, 1362.926, 1067.31, ...]Distances are in kilometers - multiply by 0.6214 for miles
Get total distance
tsp.total_distanceCreate a puzzle with zeros in empty cells
grid = [
[0, 6, 0, 0, 5, 0, 0, 2, 0],
[0, 0, 0, 3, 0, 0, 0, 9, 0],
[7, 0, 0, 6, 0, 0, 0, 1, 0],
[0, 0, 6, 0, 3, 0, 4, 0, 0],
[0, 0, 4, 0, 7, 0, 1, 0, 0],
[0, 0, 5, 0, 9, 0, 8, 0, 0],
[0, 4, 0, 0, 0, 1, 0, 0, 6],
[0, 3, 0, 0, 0, 8, 0, 0, 0],
[0, 2, 0, 0, 4, 0, 0, 5, 0]
]
sudoku = ORTools::Sudoku.new(grid)
sudoku.solutionIt can also solve more advanced puzzles like The Miracle
grid = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]
]
sudoku = ORTools::Sudoku.new(grid, anti_knight: true, anti_king: true, non_consecutive: true)
sudoku.solutiongrid = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[3, 8, 4, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 2]
]
sudoku = ORTools::Sudoku.new(grid, x: true, anti_knight: true, magic_square: true)
sudoku.solution# declare the solver
solver = ORTools::Solver.new("GLOP")
# create the variables
x = solver.num_var(0, solver.infinity, "x")
y = solver.num_var(0, solver.infinity, "y")
puts "Number of variables = #{solver.num_variables}"
# define the constraints
solver.add(x + 2 * y <= 14)
solver.add(3 * x - y >= 0)
solver.add(x - y <= 2)
puts "Number of constraints = #{solver.num_constraints}"
# define the objective function
solver.maximize(3 * x + 4 * y)
# invoke the solver
status = solver.solve
# display the solution
if status == :optimal
puts "Solution:"
puts "Objective value = #{solver.objective.value}"
puts "x = #{x.solution_value}"
puts "y = #{y.solution_value}"
else
puts "The problem does not have an optimal solution."
end# declare the MIP solver
solver = ORTools::Solver.new("CBC")
# define the variables
infinity = solver.infinity
x = solver.int_var(0, infinity, "x")
y = solver.int_var(0, infinity, "y")
puts "Number of variables = #{solver.num_variables}"
# define the constraints
solver.add(x + 7 * y <= 17.5)
solver.add(x <= 3.5)
puts "Number of constraints = #{solver.num_constraints}"
# define the objective
solver.maximize(x + 10 * y)
# call the solver
status = solver.solve
# display the solution
if status == :optimal
puts "Solution:"
puts "Objective value = #{solver.objective.value}"
puts "x = #{x.solution_value}"
puts "y = #{y.solution_value}"
else
puts "The problem does not have an optimal solution."
end# declare the model
model = ORTools::CpModel.new
# create the variables
num_vals = 3
x = model.new_int_var(0, num_vals - 1, "x")
y = model.new_int_var(0, num_vals - 1, "y")
z = model.new_int_var(0, num_vals - 1, "z")
# create the constraint
model.add(x != y)
# call the solver
solver = ORTools::CpSolver.new
status = solver.solve(model)
# display the first solution
if status == :optimal || status == :feasible
puts "x = #{solver.value(x)}"
puts "y = #{solver.value(y)}"
puts "z = #{solver.value(z)}"
else
puts "No solution found."
end# declare the model
model = ORTools::CpModel.new
# create the variables
var_upper_bound = [50, 45, 37].max
x = model.new_int_var(0, var_upper_bound, "x")
y = model.new_int_var(0, var_upper_bound, "y")
z = model.new_int_var(0, var_upper_bound, "z")
# define the constraints
model.add(x*2 + y*7 + z*3 <= 50)
model.add(x*3 - y*5 + z*7 <= 45)
model.add(x*5 + y*2 - z*6 <= 37)
# define the objective function
model.maximize(x*2 + y*2 + z*3)
# call the solver
solver = ORTools::CpSolver.new
status = solver.solve(model)
# display the solution
if status == :optimal || status == :feasible
puts "Maximum of objective function: #{solver.objective_value}"
puts "x = #{solver.value(x)}"
puts "y = #{solver.value(y)}"
puts "z = #{solver.value(z)}"
else
puts "No solution found."
end# define the variables
model = ORTools::CpModel.new
base = 10
c = model.new_int_var(1, base - 1, "C")
p = model.new_int_var(0, base - 1, "P")
i = model.new_int_var(1, base - 1, "I")
s = model.new_int_var(0, base - 1, "S")
f = model.new_int_var(1, base - 1, "F")
u = model.new_int_var(0, base - 1, "U")
n = model.new_int_var(0, base - 1, "N")
t = model.new_int_var(1, base - 1, "T")
r = model.new_int_var(0, base - 1, "R")
e = model.new_int_var(0, base - 1, "E")
letters = [c, p, i, s, f, u, n, t, r, e]
# define the constraints
model.add_all_different(letters)
model.add(c * base + p + i * base + s + f * base * base + u * base +
n == t * base * base * base + r * base * base + u * base + e)
# define the solution printer
class VarArraySolutionPrinter < ORTools::CpSolverSolutionCallback
attr_reader :solution_count
def initialize(variables)
super()
@variables = variables
@solution_count = 0
end
def on_solution_callback
@solution_count += 1
@variables.each do |v|
print "%s=%i " % [v.name, value(v)]
end
puts
end
end
# invoke the solver
solver = ORTools::CpSolver.new
solution_printer = VarArraySolutionPrinter.new(letters)
status = solver.search_for_all_solutions(model, solution_printer)
puts
puts "Statistics"
puts " - status : %s" % status
puts " - conflicts : %i" % solver.num_conflicts
puts " - branches : %i" % solver.num_branches
puts " - wall time : %f s" % solver.wall_time
puts " - solutions found : %i" % solution_printer.solution_count# declare the model
board_size = 8
model = ORTools::CpModel.new
# create the variables
queens = board_size.times.map { |i| model.new_int_var(0, board_size - 1, "x%i" % i) }
# create the constraints
board_size.times do |i|
diag1 = []
diag2 = []
board_size.times do |j|
q1 = model.new_int_var(0, 2 * board_size, "diag1_%i" % i)
diag1 << q1
model.add(q1 == queens[j] + j)
q2 = model.new_int_var(-board_size, board_size, "diag2_%i" % i)
diag2 << q2
model.add(q2 == queens[j] - j)
end
model.add_all_different(diag1)
model.add_all_different(diag2)
end
# create a solution printer
class SolutionPrinter < ORTools::CpSolverSolutionCallback
attr_reader :solution_count
def initialize(variables)
super()
@variables = variables
@solution_count = 0
end
def on_solution_callback
@solution_count += 1
@variables.each do |v|
print "%s = %i " % [v.name, value(v)]
end
puts
end
end
# call the solver and display the results
solver = ORTools::CpSolver.new
solution_printer = SolutionPrinter.new(queens)
status = solver.search_for_all_solutions(model, solution_printer)
puts
puts "Solutions found : %i" % solution_printer.solution_count# create the model
model = ORTools::CpModel.new
# create the variables
num_vals = 3
x = model.new_int_var(0, num_vals - 1, "x")
y = model.new_int_var(0, num_vals - 1, "y")
z = model.new_int_var(0, num_vals - 1, "z")
# add an all-different constraint
model.add(x != y)
# create the solver
solver = ORTools::CpSolver.new
# set a time limit of 10 seconds.
solver.parameters.max_time_in_seconds = 10
# solve the model
status = solver.solve(model)
# display the first solution
if status == :optimal
puts "x = #{solver.value(x)}"
puts "y = #{solver.value(y)}"
puts "z = #{solver.value(z)}"
end# create the data
costs = [
[90, 80, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 95],
[45, 110, 95, 115],
[50, 100, 90, 100]
]
num_workers = costs.length
num_tasks = costs[0].length
# create the solver
solver = ORTools::Solver.new("CBC")
# create the variables
x = {}
num_workers.times do |i|
num_tasks.times do |j|
x[[i, j]] = solver.int_var(0, 1, "")
end
end
# create the constraints
# each worker is assigned to at most 1 task
num_workers.times do |i|
solver.add(num_tasks.times.sum { |j| x[[i, j]] } <= 1)
end
# each task is assigned to exactly one worker
num_tasks.times do |j|
solver.add(num_workers.times.sum { |i| x[[i, j]] } == 1)
end
# create the objective function
objective_terms = []
num_workers.times do |i|
num_tasks.times do |j|
objective_terms << (costs[i][j] * x[[i, j]])
end
end
solver.minimize(objective_terms.sum)
# invoke the solver
status = solver.solve
# print the solution
if status == :optimal || status == :feasible
puts "Total cost = #{solver.objective.value}"
num_workers.times do |i|
num_tasks.times do |j|
# test if x[i,j] is 1 (with tolerance for floating point arithmetic)
if x[[i, j]].solution_value > 0.5
puts "Worker #{i} assigned to task #{j}. Cost = #{costs[i][j]}"
end
end
end
else
puts "No solution found."
end# create the data
costs = [
[90, 76, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 105],
[45, 110, 95, 115],
[60, 105, 80, 75],
[45, 65, 110, 95]
]
num_workers = costs.length
num_tasks = costs[1].length
team1 = [0, 2, 4]
team2 = [1, 3, 5]
team_max = 2
# create the solver
solver = ORTools::Solver.new("CBC")
# create the variables
x = {}
num_workers.times do |i|
num_tasks.times do |j|
x[[i, j]] = solver.bool_var("x[#{i},#{j}]")
end
end
# add the constraints
# each worker is assigned at most 1 task
num_workers.times do |i|
solver.add(num_tasks.times.sum { |j| x[[i, j]] } <= 1)
end
# each task is assigned to exactly one worker
num_tasks.times do |j|
solver.add(num_workers.times.sum { |i| x[[i, j]] } == 1)
end
# each team takes at most two tasks
solver.add(team1.flat_map { |i| num_tasks.times.map { |j| x[[i, j]] } }.sum <= team_max)
solver.add(team2.flat_map { |i| num_tasks.times.map { |j| x[[i, j]] } }.sum <= team_max)
# create the objective
solver.minimize(
num_workers.times.flat_map { |i| num_tasks.times.map { |j| x[[i, j]] * costs[i][j] } }.sum
)
# invoke the solver
status = solver.solve
# display the results
if status == :optimal || status == :feasible
puts "Total cost = #{solver.objective.value}"
num_workers.times do |worker|
num_tasks.times do |task|
if x[[worker, task]].solution_value > 0.5
puts "Worker #{worker} assigned to task #{task}. Cost = #{costs[worker][task]}"
end
end
end
else
puts "No solution found."
end# create the data
costs = [
[90, 76, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 105],
[45, 110, 95, 115],
]
num_workers = costs.length
num_tasks = costs[0].length
# create the solver
assignment = ORTools::LinearSumAssignment.new
# add the constraints
num_workers.times do |worker|
num_tasks.times do |task|
if costs[worker][task]
assignment.add_arc_with_cost(worker, task, costs[worker][task])
end
end
end
# invoke the solver
status = assignment.solve
# display the results
case status
when :optimal
puts "Total cost = #{assignment.optimal_cost}"
assignment.num_nodes.times do |i|
puts "Worker #{i} assigned to task #{assignment.right_mate(i)}. Cost = #{assignment.assignment_cost(i)}"
end
when :infeasible
puts "No assignment is possible."
when :possible_overflow
puts "Some input costs are too large and may cause an integer overflow."
end# create the data
data = {}
data[:distance_matrix] = [
[0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972],
[2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579],
[713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260],
[1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987],
[1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371],
[1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999],
[2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701],
[213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099],
[2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600],
[875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162],
[1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200],
[2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504],
[1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0]
]
data[:num_vehicles] = 1
data[:depot] = 0
# create the distance callback
manager = ORTools::RoutingIndexManager.new(data[:distance_matrix].length, data[:num_vehicles], data[:depot])
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)
data[: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)
# run the solver
assignment = routing.solve(first_solution_strategy: :path_cheapest_arc)
# print the solution
puts "Objective: #{assignment.objective_value} miles"
index = routing.start(0)
plan_output = String.new("Route for vehicle 0:\n")
route_distance = 0
while !routing.end?(index)
plan_output += " #{manager.index_to_node(index)} ->"
previous_index = index
index = assignment.value(routing.next_var(index))
route_distance += routing.arc_cost_for_vehicle(previous_index, index, 0)
end
plan_output += " #{manager.index_to_node(index)}\n"
puts plan_output# create the data
data = {}
data[:distance_matrix] = [
[0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
[548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
[776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
[696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
[582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
[274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
[502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
[194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
[308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
[194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
[536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
[502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
[388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
[354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
[468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
[776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
[662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0]
]
data[:num_vehicles] = 4
data[:depot] = 0
# define the distance callback
manager = ORTools::RoutingIndexManager.new(data[:distance_matrix].length, data[:num_vehicles], data[:depot])
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)
data[: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)
# add a distance dimension
dimension_name = "Distance"
routing.add_dimension(transit_callback_index, 0, 3000, true, dimension_name)
distance_dimension = routing.mutable_dimension(dimension_name)
distance_dimension.global_span_cost_coefficient = 100
# run the solver
solution = routing.solve(first_solution_strategy: :path_cheapest_arc)
# print the solution
max_route_distance = 0
data[:num_vehicles].times do |vehicle_id|
index = routing.start(vehicle_id)
plan_output = String.new("Route for vehicle #{vehicle_id}:\n")
route_distance = 0
while !routing.end?(index)
plan_output += " #{manager.index_to_node(index)} -> "
previous_index = index
index = solution.value(routing.next_var(index))
route_distance += routing.arc_cost_for_vehicle(previous_index, index, vehicle_id)
end
plan_output += "#{manager.index_to_node(index)}\n"
plan_output += "Distance of the route: #{route_distance}m\n\n"
puts plan_output
max_route_distance = [route_distance, max_route_distance].max
end
puts "Maximum of the route distances: #{max_route_distance}m"data = {}
data[:distance_matrix] = [
[0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
[548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
[776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
[696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
[582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
[274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
[502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
[194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
[308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
[194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
[536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
[502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
[388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
[354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
[468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
[776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
[662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0]
]
data[:demands] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8]
data[:vehicle_capacities] = [15, 15, 15, 15]
data[:num_vehicles] = 4
data[:depot] = 0
manager = ORTools::RoutingIndexManager.new(data[:distance_matrix].size, data[:num_vehicles], data[:depot])
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)
data[: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)
demand_callback = lambda do |from_index|
from_node = manager.index_to_node(from_index)
data[:demands][from_node]
end
demand_callback_index = routing.register_unary_transit_callback(demand_callback)
routing.add_dimension_with_vehicle_capacity(
demand_callback_index,
0, # null capacity slack
data[:vehicle_capacities], # vehicle maximum capacities
true, # start cumul to zero
"Capacity"
)
solution = routing.solve(first_solution_strategy: :path_cheapest_arc)
total_distance = 0
total_load = 0
data[:num_vehicles].times do |vehicle_id|
index = routing.start(vehicle_id)
plan_output = String.new("Route for vehicle #{vehicle_id}:\n")
route_distance = 0
route_load = 0
while !routing.end?(index)
node_index = manager.index_to_node(index)
route_load += data[:demands][node_index]
plan_output += " #{node_index} Load(#{route_load}) -> "
previous_index = index
index = solution.value(routing.next_var(index))
route_distance += routing.arc_cost_for_vehicle(previous_index, index, vehicle_id)
end
plan_output += " #{manager.index_to_node(index)} Load(#{route_load})\n"
plan_output += "Distance of the route: #{route_distance}m\n"
plan_output += "Load of the route: #{route_load}\n\n"
puts plan_output
total_distance += route_distance
total_load += route_load
end
puts "Total distance of all routes: #{total_distance}m"
puts "Total load of all routes: #{total_load}"data = {}
data[:distance_matrix] = [
[0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
[548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
[776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
[696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
[582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
[274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
[502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
[194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
[308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
[194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
[536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
[502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
[388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
[354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
[468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
[776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
[662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0]
]
data[:pickups_deliveries] = [
[1, 6],
[2, 10],
[4, 3],
[5, 9],
[7, 8],
[15, 11],
[13, 12],
[16, 14],
]
data[:num_vehicles] = 4
data[:depot] = 0
manager = ORTools::RoutingIndexManager.new(data[:distance_matrix].size, data[:num_vehicles], data[:depot])
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)
data[: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)
dimension_name = "Distance"
routing.add_dimension(
transit_callback_index,
0, # no slack
3000, # vehicle maximum travel distance
true, # start cumul to zero
dimension_name
)
distance_dimension = routing.mutable_dimension(dimension_name)
distance_dimension.global_span_cost_coefficient = 100
data[:pickups_deliveries].each do |request|
pickup_index = manager.node_to_index(request[0])
delivery_index = manager.node_to_index(request[1])
routing.add_pickup_and_delivery(pickup_index, delivery_index)
routing.solver.add(routing.vehicle_var(pickup_index) == routing.vehicle_var(delivery_index))
routing.solver.add(distance_dimension.cumul_var(pickup_index) <= distance_dimension.cumul_var(delivery_index))
end
solution = routing.solve(first_solution_strategy: :parallel_cheapest_insertion)
total_distance = 0
data[:num_vehicles].times do |vehicle_id|
index = routing.start(vehicle_id)
plan_output = String.new("Route for vehicle #{vehicle_id}:\n")
route_distance = 0
while !routing.end?(index)
plan_output += " #{manager.index_to_node(index)} -> "
previous_index = index
index = solution.value(routing.next_var(index))
route_distance += routing.arc_cost_for_vehicle(previous_index, index, vehicle_id)
end
plan_output += "#{manager.index_to_node(index)}\n"
plan_output += "Distance of the route: #{route_distance}m\n\n"
puts plan_output
total_distance += route_distance
end
puts "Total Distance of all routes: #{total_distance}m"data = {}
data[:time_matrix] = [
[0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7],
[6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14],
[9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9],
[8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16],
[7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14],
[3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8],
[6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5],
[2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10],
[3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6],
[2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5],
[6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4],
[6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10],
[4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8],
[4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6],
[5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2],
[9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9],
[7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0],
]
data[:time_windows] = [
[0, 5], # depot
[7, 12], # 1
[10, 15], # 2
[16, 18], # 3
[10, 13], # 4
[0, 5], # 5
[5, 10], # 6
[0, 4], # 7
[5, 10], # 8
[0, 3], # 9
[10, 16], # 10
[10, 15], # 11
[0, 5], # 12
[5, 10], # 13
[7, 8], # 14
[10, 15], # 15
[11, 15], # 16
]
data[:num_vehicles] = 4
data[:depot] = 0
manager = ORTools::RoutingIndexManager.new(data[:time_matrix].size, data[:num_vehicles], data[:depot])
routing = ORTools::RoutingModel.new(manager)
time_callback = lambda do |from_index, to_index|
from_node = manager.index_to_node(from_index)
to_node = manager.index_to_node(to_index)
data[:time_matrix][from_node][to_node]
end
transit_callback_index = routing.register_transit_callback(time_callback)
routing.set_arc_cost_evaluator_of_all_vehicles(transit_callback_index)
time = "Time"
routing.add_dimension(
transit_callback_index,
30, # allow waiting time
30, # maximum time per vehicle
false, # don't force start cumul to zero
time
)
time_dimension = routing.mutable_dimension(time)
data[:time_windows].each_with_index do |time_window, location_idx|
next if location_idx == 0
index = manager.node_to_index(location_idx)
time_dimension.cumul_var(index).set_range(time_window[0], time_window[1])
end
data[:num_vehicles].times do |vehicle_id|
index = routing.start(vehicle_id)
time_dimension.cumul_var(index).set_range(data[:time_windows][0][0], data[:time_windows][0][1])
end
data[:num_vehicles].times do |i|
routing.add_variable_minimized_by_finalizer(time_dimension.cumul_var(routing.start(i)))
routing.add_variable_minimized_by_finalizer(time_dimension.cumul_var(routing.end(i)))
end
solution = routing.solve(first_solution_strategy: :path_cheapest_arc)
time_dimension = routing.mutable_dimension("Time")
total_time = 0
data[:num_vehicles].times do |vehicle_id|
index = routing.start(vehicle_id)
plan_output = String.new("Route for vehicle #{vehicle_id}:\n")
while !routing.end?(index)
time_var = time_dimension.cumul_var(index)
plan_output += "#{manager.index_to_node(index)} Time(#{solution.min(time_var)},#{solution.max(time_var)}) -> "
index = solution.value(routing.next_var(index))
end
time_var = time_dimension.cumul_var(index)
plan_output += "#{manager.index_to_node(index)} Time(#{solution.min(time_var)},#{solution.max(time_var)})\n"
plan_output += "Time of the route: #{solution.min(time_var)}min\n\n"
puts plan_output
total_time += solution.min(time_var)
end
puts "Total time of all routes: #{total_time}min"data = {}
data[:time_matrix] = [
[0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7],
[6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14],
[9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9],
[8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16],
[7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14],
[3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8],
[6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5],
[2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10],
[3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6],
[2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5],
[6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4],
[6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10],
[4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8],
[4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6],
[5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2],
[9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9],
[7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0]
]
data[:time_windows] = [
[0, 5], # depot
[7, 12], # 1
[10, 15], # 2
[5, 14], # 3
[5, 13], # 4
[0, 5], # 5
[5, 10], # 6
[0, 10], # 7
[5, 10], # 8
[0, 5], # 9
[10, 16], # 10
[10, 15], # 11
[0, 5], # 12
[5, 10], # 13
[7, 12], # 14
[10, 15], # 15
[5, 15], # 16
]
data[:num_vehicles] = 4
data[:vehicle_load_time] = 5
data[:vehicle_unload_time] = 5
data[:depot_capacity] = 2
data[:depot] = 0
manager = ORTools::RoutingIndexManager.new(data[:time_matrix].size, data[:num_vehicles], data[:depot])
routing = ORTools::RoutingModel.new(manager)
time_callback = lambda do |from_index, to_index|
from_node = manager.index_to_node(from_index)
to_node = manager.index_to_node(to_index)
data[:time_matrix][from_node][to_node]
end
transit_callback_index = routing.register_transit_callback(time_callback)
routing.set_arc_cost_evaluator_of_all_vehicles(transit_callback_index)
time = "Time"
routing.add_dimension(
transit_callback_index,
60, # allow waiting time
60, # maximum time per vehicle
false, # don't force start cumul to zero
time
)
time_dimension = routing.mutable_dimension(time)
data[:time_windows].each_with_index do |time_window, location_idx|
next if location_idx == 0
index = manager.node_to_index(location_idx)
time_dimension.cumul_var(index).set_range(time_window[0], time_window[1])
end
data[:num_vehicles].times do |vehicle_id|
index = routing.start(vehicle_id)
time_dimension.cumul_var(index).set_range(data[:time_windows][0][0], data[:time_windows][0][1])
end
solver = routing.solver
intervals = []
data[:num_vehicles].times do |i|
intervals << solver.fixed_duration_interval_var(
time_dimension.cumul_var(routing.start(i)),
data[:vehicle_load_time],
"depot_interval"
)
intervals << solver.fixed_duration_interval_var(
time_dimension.cumul_var(routing.end(i)),
data[:vehicle_unload_time],
"depot_interval"
)
end
depot_usage = [1] * intervals.size
solver.add(solver.cumulative(intervals, depot_usage, data[:depot_capacity], "depot"))
data[:num_vehicles].times do |i|
routing.add_variable_minimized_by_finalizer(time_dimension.cumul_var(routing.start(i)))
routing.add_variable_minimized_by_finalizer(time_dimension.cumul_var(routing.end(i)))
end
solution = routing.solve(first_solution_strategy: :path_cheapest_arc)
time_dimension = routing.mutable_dimension("Time")
total_time = 0
data[:num_vehicles].times do |vehicle_id|
index = routing.start(vehicle_id)
plan_output = String.new("Route for vehicle #{vehicle_id}:\n")
while !routing.end?(index)
time_var = time_dimension.cumul_var(index)
plan_output += "#{manager.index_to_node(index)} Time(#{solution.min(time_var)},#{solution.max(time_var)}) -> "
index = solution.value(routing.next_var(index))
end
time_var = time_dimension.cumul_var(index)
plan_output += "#{manager.index_to_node(index)} Time(#{solution.min(time_var)},#{solution.max(time_var)})\n"
plan_output += "Time of the route: #{solution.min(time_var)}min\n\n"
puts plan_output
total_time += solution.min(time_var)
end
puts "Total time of all routes: #{total_time}min"data = {}
data[:distance_matrix] = [
[0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
[548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
[776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
[696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
[582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
[274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
[502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
[194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
[308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
[194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
[536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
[502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
[388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
[354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
[468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
[776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
[662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0]
]
data[:demands] = [0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8]
data[:vehicle_capacities] = [15, 15, 15, 15]
data[:num_vehicles] = 4
data[:depot] = 0
manager = ORTools::RoutingIndexManager.new(data[:distance_matrix].size, data[:num_vehicles], data[:depot])
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)
data[: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)
demand_callback = lambda do |from_index|
from_node = manager.index_to_node(from_index)
data[:demands][from_node]
end
demand_callback_index = routing.register_unary_transit_callback(demand_callback)
routing.add_dimension_with_vehicle_capacity(
demand_callback_index,
0, # null capacity slack
data[:vehicle_capacities], # vehicle maximum capacities
true, # start cumul to zero
"Capacity"
)
penalty = 1000
1.upto(data[:distance_matrix].size - 1) do |node|
routing.add_disjunction([manager.node_to_index(node)], penalty)
end
assignment = routing.solve(first_solution_strategy: :path_cheapest_arc)
dropped_nodes = String.new("Dropped nodes:")
routing.size.times do |node|
next if routing.start?(node) || routing.end?(node)
if assignment.value(routing.next_var(node)) == node
dropped_nodes += " #{manager.index_to_node(node)}"
end
end
puts dropped_nodes
total_distance = 0
total_load = 0
data[:num_vehicles].times do |vehicle_id|
index = routing.start(vehicle_id)
plan_output = "Route for vehicle #{vehicle_id}:\n"
route_distance = 0
route_load = 0
while !routing.end?(index)
node_index = manager.index_to_node(index)
route_load += data[:demands][node_index]
plan_output += " #{node_index} Load(#{route_load}) -> "
previous_index = index
index = assignment.value(routing.next_var(index))
route_distance += routing.arc_cost_for_vehicle(previous_index, index, vehicle_id)
end
plan_output += " #{manager.index_to_node(index)} Load(#{route_load})\n"
plan_output += "Distance of the route: #{route_distance}m\n"
plan_output += "Load of the route: #{route_load}\n\n"
puts plan_output
total_distance += route_distance
total_load += route_load
end
puts "Total Distance of all routes: #{total_distance}m"
puts "Total Load of all routes: #{total_load}"routing.solve(
solution_limit: 10,
time_limit: 10, # seconds,
lns_time_limit: 10, # seconds
first_solution_strategy: :path_cheapest_arc,
local_search_metaheuristic: :guided_local_search,
log_search: true
)# create the data
values = [
360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,
78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28,
87, 73, 78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276,
312
]
weights = [[
7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9, 0,
42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71,
3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13
]]
capacities = [850]
# declare the solver
solver = ORTools::KnapsackSolver.new(:branch_and_bound, "KnapsackExample")
# call the solver
solver.init(values, weights, capacities)
computed_value = solver.solve
packed_items = []
packed_weights = []
total_weight = 0
puts "Total value = #{computed_value}"
values.length.times do |i|
if solver.best_solution_contains?(i)
packed_items << i
packed_weights << weights[0][i]
total_weight += weights[0][i]
end
end
puts "Total weight: #{total_weight}"
puts "Packed items: #{packed_items}"
puts "Packed weights: #{packed_weights}"# create the data
data = {}
data[:weights] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
data[:values] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
data[:num_items] = data[:weights].length
data[:all_items] = data[:num_items].times.to_a
data[:bin_capacities] = [100, 100, 100, 100, 100]
data[:num_bins] = data[:bin_capacities].length
data[:all_bins] = data[:num_bins].times.to_a
# declare the solver
solver = ORTools::Solver.new("CBC")
# create the variables
x = {}
data[:all_items].each do |i|
data[:all_bins].each do |b|
x[[i, b]] = solver.bool_var("x_#{i}_#{b}")
end
end
# each item is assigned to at most one bin
data[:all_items].each do |i|
solver.add(data[:all_bins].sum { |b| x[[i, b]] } <= 1)
end
# the amount packed in each bin cannot exceed its capacity
data[:all_bins].each do |b|
solver.add(data[:all_items].sum { |i| x[[i, b]] * data[:weights][i] } <= data[:bin_capacities][b])
end
# maximize total value of packed items
objective = solver.objective
data[:all_items].each do |i|
data[:all_bins].each do |b|
objective.set_coefficient(x[[i, b]], data[:values][i])
end
end
objective.set_maximization
# call the solver and print the solution
status = solver.solve
if status == :optimal
puts "Total packed value: #{objective.value}"
total_weight = 0
data[:all_bins].each do |b|
bin_weight = 0
bin_value = 0
puts "Bin #{b}\n\n"
data[:all_items].each do |i|
if x[[i, b]].solution_value > 0
puts "Item #{i} - weight: #{data[:weights][i]} value: #{data[:values][i]}"
bin_weight += data[:weights][i]
bin_value += data[:values][i]
end
end
puts "Packed bin weight: #{bin_weight}"
puts "Packed bin value: #{bin_value}"
puts
total_weight += bin_weight
end
puts "Total packed weight: #{total_weight}"
else
puts "The problem does not have an optimal solution."
end# create the data
data = {}
weights = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
data[:weights] = weights
data[:items] = (0...weights.length).to_a
data[:bins] = data[:items]
data[:bin_capacity] = 100
# create the mip solver with the CBC backend
solver = ORTools::Solver.new("CBC")
# variables
# x[i, j] = 1 if item i is packed in bin j
x = {}
data[:items].each do |i|
data[:bins].each do |j|
x[[i, j]] = solver.int_var(0, 1, "x_%i_%i" % [i, j])
end
end
# y[j] = 1 if bin j is used
y = {}
data[:bins].each do |j|
y[j] = solver.int_var(0, 1, "y[%i]" % j)
end
# constraints
# each item must be in exactly one bin
data[:items].each do |i|
solver.add(data[:bins].sum { |j| x[[i, j]] } == 1)
end
# the amount packed in each bin cannot exceed its capacity
data[:bins].each do |j|
sum = data[:items].sum { |i| x[[i, j]] * data[:weights][i] }
solver.add(sum <= y[j] * data[:bin_capacity])
end
# objective: minimize the number of bins used
solver.minimize(data[:bins].sum { |j| y[j] })
# call the solver and print the solution
status = solver.solve
if status == :optimal
num_bins = 0
data[:bins].each do |j|
if y[j].solution_value == 1
bin_items = []
bin_weight = 0
data[:items].each do |i|
if x[[i, j]].solution_value > 0
bin_items << i
bin_weight += data[:weights][i]
end
end
if bin_weight > 0
num_bins += 1
puts "Bin number #{j}"
puts " Items packed: #{bin_items}"
puts " Total weight: #{bin_weight}"
puts
end
end
end
puts
puts "Number of bins used: #{num_bins}"
puts "Time = #{solver.wall_time} milliseconds"
else
puts "The problem does not have an optimal solution."
end# define the data
start_nodes = [0, 0, 0, 1, 1, 2, 2, 3, 3]
end_nodes = [1, 2, 3, 2, 4, 3, 4, 2, 4]
capacities = [20, 30, 10, 40, 30, 10, 20, 5, 20]
# declare the solver and add the arcs
max_flow = ORTools::SimpleMaxFlow.new
start_nodes.length.times do |i|
max_flow.add_arc_with_capacity(start_nodes[i], end_nodes[i], capacities[i])
end
# invoke the solver and display the results
if max_flow.solve(0, 4) == :optimal
puts "Max flow: #{max_flow.optimal_flow}"
puts
puts " Arc Flow / Capacity"
max_flow.num_arcs.times do |i|
puts "%1s -> %1s %3s / %3s" % [
max_flow.tail(i),
max_flow.head(i),
max_flow.flow(i),
max_flow.capacity(i)
]
end
puts "Source side min-cut: #{max_flow.source_side_min_cut}"
puts "Sink side min-cut: #{max_flow.sink_side_min_cut}"
else
puts "There was an issue with the max flow input."
end# define the data
start_nodes = [ 0, 0, 1, 1, 1, 2, 2, 3, 4]
end_nodes = [ 1, 2, 2, 3, 4, 3, 4, 4, 2]
capacities = [15, 8, 20, 4, 10, 15, 4, 20, 5]
unit_costs = [ 4, 4, 2, 2, 6, 1, 3, 2, 3]
supplies = [20, 0, 0, -5, -15]
# declare the solver and add the arcs
min_cost_flow = ORTools::SimpleMinCostFlow.new
start_nodes.length.times do |i|
min_cost_flow.add_arc_with_capacity_and_unit_cost(
start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]
)
end
supplies.length.times do |i|
min_cost_flow.set_node_supply(i, supplies[i])
end
# invoke the solver and display the results
if min_cost_flow.solve == :optimal
puts "Minimum cost #{min_cost_flow.optimal_cost}"
puts
puts " Arc Flow / Capacity Cost"
min_cost_flow.num_arcs.times do |i|
cost = min_cost_flow.flow(i) * min_cost_flow.unit_cost(i)
puts "%1s -> %1s %3s / %3s %3s" % [
min_cost_flow.tail(i),
min_cost_flow.head(i),
min_cost_flow.flow(i),
min_cost_flow.capacity(i),
cost
]
end
else
puts "There was an issue with the min cost flow input."
end# create the solver
min_cost_flow = ORTools::SimpleMinCostFlow.new
# create the data
start_nodes = [0, 0, 0, 0] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4] + [5, 6, 7, 8]
end_nodes = [1, 2, 3, 4] + [5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8] + [9, 9, 9, 9]
capacities = [1, 1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1]
costs = [0, 0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115] + [0, 0, 0, 0]
supplies = [4, 0, 0, 0, 0, 0, 0, 0, 0, -4]
source = 0
sink = 9
tasks = 4
# create the graph and constraints
start_nodes.length.times do |i|
min_cost_flow.add_arc_with_capacity_and_unit_cost(
start_nodes[i], end_nodes[i], capacities[i], costs[i]
)
end
supplies.length.times do |i|
min_cost_flow.set_node_supply(i, supplies[i])
end
# invoke the solver
if min_cost_flow.solve == :optimal
puts "Total cost = #{min_cost_flow.optimal_cost}"
puts
min_cost_flow.num_arcs.times do |arc|
if min_cost_flow.tail(arc) != source && min_cost_flow.head(arc) != sink
if min_cost_flow.flow(arc) > 0
puts "Worker %d assigned to task %d. Cost = %d" % [
min_cost_flow.tail(arc),
min_cost_flow.head(arc),
min_cost_flow.unit_cost(arc)
]
end
end
end
else
puts "There was an issue with the min cost flow input."
end# define the data
num_nurses = 4
num_shifts = 3
num_days = 3
all_nurses = num_nurses.times.to_a
all_shifts = num_shifts.times.to_a
all_days = num_days.times.to_a
# create the variables
model = ORTools::CpModel.new
shifts = {}
all_nurses.each do |n|
all_days.each do |d|
all_shifts.each do |s|
shifts[[n, d, s]] = model.new_bool_var("shift_n%id%is%i" % [n, d, s])
end
end
end
# assign nurses to shifts
all_days.each do |d|
all_shifts.each do |s|
model.add(model.sum(all_nurses.map { |n| shifts[[n, d, s]] }) == 1)
end
end
all_nurses.each do |n|
all_days.each do |d|
model.add(model.sum(all_shifts.map { |s| shifts[[n, d, s]] }) <= 1)
end
end
# assign shifts evenly
min_shifts_per_nurse = (num_shifts * num_days) / num_nurses
max_shifts_per_nurse = min_shifts_per_nurse + 1
all_nurses.each do |n|
num_shifts_worked = model.sum(all_days.flat_map { |d| all_shifts.map { |s| shifts[[n, d, s]] } })
model.add(num_shifts_worked >= min_shifts_per_nurse)
model.add(num_shifts_worked <= max_shifts_per_nurse)
end
# create a printer
class NursesPartialSolutionPrinter < ORTools::CpSolverSolutionCallback
attr_reader :solution_count
def initialize(shifts, num_nurses, num_days, num_shifts, sols)
super()
@shifts = shifts
@num_nurses = num_nurses
@num_days = num_days
@num_shifts = num_shifts
@solutions = sols
@solution_count = 0
end
def on_solution_callback
if @solutions.include?(@solution_count)
puts "Solution #{@solution_count}"
@num_days.times do |d|
puts "Day #{d}"
@num_nurses.times do |n|
working = false
@num_shifts.times do |s|
if value(@shifts[[n, d, s]])
working = true
puts " Nurse %i works shift %i" % [n, s]
end
end
unless working
puts " Nurse #{n} does not work"
end
end
end
puts
end
@solution_count += 1
end
end
# call the solver and display the results
solver = ORTools::CpSolver.new
a_few_solutions = 5.times.to_a
solution_printer = NursesPartialSolutionPrinter.new(
shifts, num_nurses, num_days, num_shifts, a_few_solutions
)
solver.search_for_all_solutions(model, solution_printer)
puts
puts "Statistics"
puts " - conflicts : %i" % solver.num_conflicts
puts " - branches : %i" % solver.num_branches
puts " - wall time : %f s" % solver.wall_time
puts " - solutions found : %i" % solution_printer.solution_count# create the model
model = ORTools::CpModel.new
jobs_data = [
[[0, 3], [1, 2], [2, 2]],
[[0, 2], [2, 1], [1, 4]],
[[1, 4], [2, 3]]
]
machines_count = 1 + jobs_data.flat_map { |job| job.map { |task| task[0] } }.max
all_machines = machines_count.times.to_a
# computes horizon dynamically as the sum of all durations
horizon = jobs_data.flat_map { |job| job.map { |task| task[1] } }.sum
# creates job intervals and add to the corresponding machine lists
all_tasks = {}
machine_to_intervals = Hash.new { |hash, key| hash[key] = [] }
jobs_data.each_with_index do |job, job_id|
job.each_with_index do |task, task_id|
machine = task[0]
duration = task[1]
suffix = "_%i_%i" % [job_id, task_id]
start_var = model.new_int_var(0, horizon, "start" + suffix)
duration_var = model.new_int_var(duration, duration, "duration" + suffix)
end_var = model.new_int_var(0, horizon, "end" + suffix)
interval_var = model.new_interval_var(start_var, duration_var, end_var, "interval" + suffix)
all_tasks[[job_id, task_id]] = {start: start_var, end: end_var, interval: interval_var}
machine_to_intervals[machine] << interval_var
end
end
# create and add disjunctive constraints
all_machines.each do |machine|
model.add_no_overlap(machine_to_intervals[machine])
end
# precedences inside a job
jobs_data.each_with_index do |job, job_id|
(job.size - 1).times do |task_id|
model.add(all_tasks[[job_id, task_id + 1]][:start] >= all_tasks[[job_id, task_id]][:end])
end
end
# makespan objective
obj_var = model.new_int_var(0, horizon, "makespan")
model.add_max_equality(obj_var, jobs_data.map.with_index { |job, job_id| all_tasks[[job_id, job.size - 1]][:end] })
model.minimize(obj_var)
# solve model
solver = ORTools::CpSolver.new
status = solver.solve(model)
# create one list of assigned tasks per machine
assigned_jobs = Hash.new { |hash, key| hash[key] = [] }
jobs_data.each_with_index do |job, job_id|
job.each_with_index do |task, task_id|
machine = task[0]
assigned_jobs[machine] << {
start: solver.value(all_tasks[[job_id, task_id]][:start]),
job: job_id,
index: task_id,
duration: task[1]
}
end
end
# create per machine output lines
output = String.new("")
all_machines.each do |machine|
# sort by starting time
assigned_jobs[machine].sort_by! { |v| v[:start] }
sol_line_tasks = "Machine #{machine}: "
sol_line = " "
assigned_jobs[machine].each do |assigned_task|
name = "job_%i_%i" % [assigned_task[:job], assigned_task[:index]]
# add spaces to output to align columns
sol_line_tasks += "%-10s" % name
start = assigned_task[:start]
duration = assigned_task[:duration]
sol_tmp = "[%i,%i]" % [start, start + duration]
# add spaces to output to align columns
sol_line += "%-10s" % sol_tmp
end
sol_line += "\n"
sol_line_tasks += "\n"
output += sol_line_tasks
output += sol_line
end
# finally print the solution found
puts "Optimal Schedule Length: %i" % solver.objective_value
puts output# create the model
model = ORTools::CpModel.new
cell_size = 3
line_size = cell_size**2
line = (0...line_size).to_a
cell = (0...cell_size).to_a
initial_grid = [
[0, 6, 0, 0, 5, 0, 0, 2, 0],
[0, 0, 0, 3, 0, 0, 0, 9, 0],
[7, 0, 0, 6, 0, 0, 0, 1, 0],
[0, 0, 6, 0, 3, 0, 4, 0, 0],
[0, 0, 4, 0, 7, 0, 1, 0, 0],
[0, 0, 5, 0, 9, 0, 8, 0, 0],
[0, 4, 0, 0, 0, 1, 0, 0, 6],
[0, 3, 0, 0, 0, 8, 0, 0, 0],
[0, 2, 0, 0, 4, 0, 0, 5, 0]
]
grid = {}
line.each do |i|
line.each do |j|
grid[[i, j]] = model.new_int_var(1, line_size, "grid %i %i" % [i, j])
end
end
# all different on rows
line.each do |i|
model.add_all_different(line.map { |j| grid[[i, j]] })
end
# all different on columns
line.each do |j|
model.add_all_different(line.map { |i| grid[[i, j]] })
end
# all different on cells
cell.each do |i|
cell.each do |j|
one_cell = []
cell.each do |di|
cell.each do |dj|
one_cell << grid[[i * cell_size + di, j * cell_size + dj]]
end
end
model.add_all_different(one_cell)
end
end
# initial values
line.each do |i|
line.each do |j|
if initial_grid[i][j] != 0
model.add(grid[[i, j]] == initial_grid[i][j])
end
end
end
# solve and print solution
solver = ORTools::CpSolver.new
status = solver.solve(model)
if status == :optimal
line.each do |i|
p line.map { |j| solver.value(grid[[i, j]]) }
end
end# From
# Meghan L. Bellows and J. D. Luc Peterson
# "Finding an optimal seating chart for a wedding"
# https://www.improbable.com/news/2012/Optimal-seating-chart.pdf
# https://www.improbable.com/2012/02/12/finding-an-optimal-seating-chart-for-a-wedding
#
# Every year, millions of brides (not to mention their mothers, future
# mothers-in-law, and occasionally grooms) struggle with one of the
# most daunting tasks during the wedding-planning process: the
# seating chart. The guest responses are in, banquet hall is booked,
# menu choices have been made. You think the hard parts are over,
# but you have yet to embark upon the biggest headache of them all.
# In order to make this process easier, we present a mathematical
# formulation that models the seating chart problem. This model can
# be solved to find the optimal arrangement of guests at tables.
# At the very least, it can provide a starting point and hopefully
# minimize stress and arguments.
#
# Adapted from
# https://github.com/google/or-tools/blob/stable/examples/python/wedding_optimal_chart_sat.py
# Easy problem (from the paper)
# num_tables = 2
# table_capacity = 10
# min_known_neighbors = 1
# Slightly harder problem (also from the paper)
num_tables = 5
table_capacity = 4
min_known_neighbors = 1
# Connection matrix: who knows who, and how strong
# is the relation
c = [
[1, 50, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[50, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 50, 1, 1, 1, 1, 10, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 50, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 50, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 50, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 50, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 50, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 10, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 50, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 50, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
]
# Names of the guests. B: Bride side, G: Groom side
names = [
"Deb (B)", "John (B)", "Martha (B)", "Travis (B)", "Allan (B)",
"Lois (B)", "Jayne (B)", "Brad (B)", "Abby (B)", "Mary Helen (G)",
"Lee (G)", "Annika (G)", "Carl (G)", "Colin (G)", "Shirley (G)",
"DeAnn (G)", "Lori (G)"
]
num_guests = c.size
all_tables = num_tables.times.to_a
all_guests = num_guests.times.to_a
# create the cp model
model = ORTools::CpModel.new
# decision variables
seats = {}
all_tables.each do |t|
all_guests.each do |g|
seats[[t, g]] = model.new_bool_var("guest %i seats on table %i" % [g, t])
end
end
pairs = all_guests.combination(2)
colocated = {}
pairs.each do |g1, g2|
colocated[[g1, g2]] = model.new_bool_var("guest %i seats with guest %i" % [g1, g2])
end
same_table = {}
pairs.each do |g1, g2|
all_tables.each do |t|
same_table[[g1, g2, t]] = model.new_bool_var("guest %i seats with guest %i on table %i" % [g1, g2, t])
end
end
# Objective
model.maximize(model.sum((num_guests - 1).times.flat_map { |g1| (g1 + 1).upto(num_guests - 1).select { |g2| c[g1][g2] > 0 }.map { |g2| colocated[[g1, g2]] * c[g1][g2] } }))
#
# Constraints
#
# Everybody seats at one table.
all_guests.each do |g|
model.add(model.sum(all_tables.map { |t| seats[[t, g]] }) == 1)
end
# Tables have a max capacity.
all_tables.each do |t|
model.add(model.sum(all_guests.map { |g| seats[[t, g]] }) <= table_capacity)
end
# Link colocated with seats
pairs.each do |g1, g2|
all_tables.each do |t|
# Link same_table and seats.
model.add_bool_or([seats[[t, g1]].not, seats[[t, g2]].not, same_table[[g1, g2, t]]])
model.add_implication(same_table[[g1, g2, t]], seats[[t, g1]])
model.add_implication(same_table[[g1, g2, t]], seats[[t, g2]])
end
# Link colocated and same_table.
model.add(model.sum(all_tables.map { |t| same_table[[g1, g2, t]] }) == colocated[[g1, g2]])
end
# Min known neighbors rule.
all_guests.each do |g|
model.add(
model.sum(
(g + 1).upto(num_guests - 1).
select { |g2| c[g][g2] > 0 }.
product(all_tables).
map { |g2, t| same_table[[g, g2, t]] }
) +
model.sum(
g.times.
select { |g1| c[g1][g] > 0 }.
product(all_tables).
map { |g1, t| same_table[[g1, g, t]] }
) >= min_known_neighbors
)
end
# Symmetry breaking. First guest seats on the first table.
model.add(seats[[0, 0]] == 1)
# Solve model
solver = ORTools::CpSolver.new
solution_printer = WeddingChartPrinter.new(seats, names, num_tables, num_guests)
solver.solve(model, solution_printer)
puts "Statistics"
puts " - conflicts : %i" % solver.num_conflicts
puts " - branches : %i" % solver.num_branches
puts " - wall time : %f s" % solver.wall_time
puts " - num solutions: %i" % solution_printer.num_solutions# A set partitioning model of a wedding seating problem
# Authors: Stuart Mitchell 2009
max_tables = 5
max_table_size = 4
guests = %w(A B C D E F G I J K L M N O P Q R)
# Find the happiness of the table
# by calculating the maximum distance between the letters
def happiness(table)
(table[0].ord - table[-1].ord).abs
end
# create list of all possible tables
possible_tables = []
(1..max_table_size).each do |i|
possible_tables += guests.combination(i).to_a
end
solver = ORTools::Solver.new("CBC")
# create a binary variable to state that a table setting is used
x = {}
possible_tables.each do |table|
x[table] = solver.int_var(0, 1, "table #{table.join(", ")}")
end
solver.minimize(possible_tables.sum { |table| x[table] * happiness(table) })
# specify the maximum number of tables
solver.add(x.values.sum <= max_tables)
# a guest must seated at one and only one table
guests.each do |guest|
tables_with_guest = possible_tables.select { |table| table.include?(guest) }
solver.add(tables_with_guest.sum { |table| x[table] } == 1)
end
status = solver.solve
puts "The chosen tables are out of a total of %s:" % possible_tables.size
possible_tables.each do |table|
if x[table].solution_value == 1
p table
end
endView the changelog
Everyone is encouraged to help improve this project. Here are a few ways you can help:
- Report bugs
- Fix bugs and submit pull requests
- Write, clarify, or fix documentation
- Suggest or add new features
To get started with development:
git clone https://github.com/ankane/or-tools-ruby.git
cd or-tools-ruby
bundle install
bundle exec rake compile
bundle exec rake testResources
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent