- Notifications
You must be signed in to change notification settings - Fork31
Operations research tools for Ruby
License
NotificationsYou must be signed in to change notification settings
ankane/or-tools-ruby
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
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
MathOpt
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("2025-01-01 08:00:00"),ends_at:Time.parse("2025-01-01 16:00:00")},{starts_at:Time.parse("2025-01-02 08:00:00"),ends_at:Time.parse("2025-01-02 16:00:00")}],max_hours:40# optional, applies to entire scheduling period},{availability:[{starts_at:Time.parse("2025-01-01 08:00:00"),ends_at:Time.parse("2025-01-01 16:00:00")},{starts_at:Time.parse("2025-01-03 08:00:00"),ends_at:Time.parse("2025-01-03 16:00:00")}],max_hours:20}]
Specify shifts
shifts=[{starts_at:Time.parse("2025-01-01 08:00:00"),ends_at:Time.parse("2025-01-01 16:00:00")},{starts_at:Time.parse("2025-01-02 08:00:00"),ends_at:Time.parse("2025-01-02 16:00:00")},{starts_at:Time.parse("2025-01-03 08:00:00"),ends_at:Time.parse("2025-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_hoursscheduler.total_hours
Feel free to create an issue if you have a scheduling use case that’s not covered.
Create a seating chart based on personal connections. Usesthis 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_tables
Get assignments by person
seating.assignments
Get 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 - onlylatitude andlongitude 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 by0.6214 for miles
Get total distance
tsp.total_distance
Create 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.solution
It can also solve more advanced puzzles likeThe 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.solution
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],[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
# build the modelmodel=ORTools::MathOpt::Model.new("getting_started_lp")x=model.add_variable(-1.0,1.5,"x")y=model.add_variable(0.0,1.0,"y")model.add_linear_constraint(x +y <=1.5)model.maximize(x +2 *y)# solveresult=model.solve# inspect the solutionputs"Objective value:#{result.objective_value}"puts"x:#{result.variable_values[x]}"puts"y:#{result.variable_values[y]}"
# declare the solversolver=ORTools::Solver.new("GLOP")# create the variablesx=solver.num_var(0,solver.infinity,"x")y=solver.num_var(0,solver.infinity,"y")puts"Number of variables =#{solver.num_variables}"# define the constraintssolver.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 functionsolver.maximize(3 *x +4 *y)# invoke the solverstatus=solver.solve# display the solutionifstatus ==:optimalputs"Solution:"puts"Objective value =#{solver.objective.value}"puts"x =#{x.solution_value}"puts"y =#{y.solution_value}"elseputs"The problem does not have an optimal solution."end
# declare the MIP solversolver=ORTools::Solver.new("CBC")# define the variablesinfinity=solver.infinityx=solver.int_var(0,infinity,"x")y=solver.int_var(0,infinity,"y")puts"Number of variables =#{solver.num_variables}"# define the constraintssolver.add(x +7 *y <=17.5)solver.add(x <=3.5)puts"Number of constraints =#{solver.num_constraints}"# define the objectivesolver.maximize(x +10 *y)# call the solverstatus=solver.solve# display the solutionifstatus ==:optimalputs"Solution:"puts"Objective value =#{solver.objective.value}"puts"x =#{x.solution_value}"puts"y =#{y.solution_value}"elseputs"The problem does not have an optimal solution."end
# declare the modelmodel=ORTools::CpModel.new# create the variablesnum_vals=3x=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 constraintmodel.add(x !=y)# call the solversolver=ORTools::CpSolver.newstatus=solver.solve(model)# display the first solutionifstatus ==:optimal ||status ==:feasibleputs"x =#{solver.value(x)}"puts"y =#{solver.value(y)}"puts"z =#{solver.value(z)}"elseputs"No solution found."end
# declare the modelmodel=ORTools::CpModel.new# create the variablesvar_upper_bound=[50,45,37].maxx=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 constraintsmodel.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 functionmodel.maximize(x*2 +y*2 +z*3)# call the solversolver=ORTools::CpSolver.newstatus=solver.solve(model)# display the solutionifstatus ==:optimal ||status ==:feasibleputs"Maximum of objective function:#{solver.objective_value}"puts"x =#{solver.value(x)}"puts"y =#{solver.value(y)}"puts"z =#{solver.value(z)}"elseputs"No solution found."end
# define the variablesmodel=ORTools::CpModel.newbase=10c=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 constraintsmodel.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 printerclassVarArraySolutionPrinter <ORTools::CpSolverSolutionCallbackattr_reader:solution_countdefinitialize(variables)super()@variables=variables@solution_count=0enddefon_solution_callback@solution_count +=1@variables.eachdo |v|print"%s=%i " %[v.name,value(v)]endputsendend# invoke the solversolver=ORTools::CpSolver.newsolution_printer=VarArraySolutionPrinter.new(letters)status=solver.search_for_all_solutions(model,solution_printer)putsputs"Statistics"puts" - status : %s" %statusputs" - conflicts : %i" %solver.num_conflictsputs" - branches : %i" %solver.num_branchesputs" - wall time : %f s" %solver.wall_timeputs" - solutions found : %i" %solution_printer.solution_count
# declare the modelboard_size=8model=ORTools::CpModel.new# create the variablesqueens=board_size.times.map{ |i|model.new_int_var(0,board_size -1,"x%i" %i)}# create the constraintsboard_size.timesdo |i|diag1=[]diag2=[]board_size.timesdo |j|q1=model.new_int_var(0,2 *board_size,"diag1_%i" %i)diag1 <<q1model.add(q1 ==queens[j] +j)q2=model.new_int_var(-board_size,board_size,"diag2_%i" %i)diag2 <<q2model.add(q2 ==queens[j] -j)endmodel.add_all_different(diag1)model.add_all_different(diag2)end# create a solution printerclassSolutionPrinter <ORTools::CpSolverSolutionCallbackattr_reader:solution_countdefinitialize(variables)super()@variables=variables@solution_count=0enddefon_solution_callback@solution_count +=1@variables.eachdo |v|print"%s = %i " %[v.name,value(v)]endputsendend# call the solver and display the resultssolver=ORTools::CpSolver.newsolution_printer=SolutionPrinter.new(queens)status=solver.search_for_all_solutions(model,solution_printer)putsputs"Solutions found : %i" %solution_printer.solution_count
# create the modelmodel=ORTools::CpModel.new# create the variablesnum_vals=3x=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 constraintmodel.add(x !=y)# create the solversolver=ORTools::CpSolver.new# set a time limit of 10 seconds.solver.parameters.max_time_in_seconds=10# solve the modelstatus=solver.solve(model)# display the first solutionifstatus ==:optimalputs"x =#{solver.value(x)}"puts"y =#{solver.value(y)}"puts"z =#{solver.value(z)}"end
# create the datacosts=[[90,80,75,70],[35,85,55,65],[125,95,90,95],[45,110,95,115],[50,100,90,100]]num_workers=costs.lengthnum_tasks=costs[0].length# create the solversolver=ORTools::Solver.new("CBC")# create the variablesx={}num_workers.timesdo |i|num_tasks.timesdo |j|x[[i,j]]=solver.int_var(0,1,"")endend# create the constraints# each worker is assigned to at most 1 tasknum_workers.timesdo |i|solver.add(num_tasks.times.sum{ |j|x[[i,j]]} <=1)end# each task is assigned to exactly one workernum_tasks.timesdo |j|solver.add(num_workers.times.sum{ |i|x[[i,j]]} ==1)end# create the objective functionobjective_terms=[]num_workers.timesdo |i|num_tasks.timesdo |j|objective_terms <<(costs[i][j] *x[[i,j]])endendsolver.minimize(objective_terms.sum)# invoke the solverstatus=solver.solve# print the solutionifstatus ==:optimal ||status ==:feasibleputs"Total cost =#{solver.objective.value}"num_workers.timesdo |i|num_tasks.timesdo |j|# test if x[i,j] is 1 (with tolerance for floating point arithmetic)ifx[[i,j]].solution_value >0.5puts"Worker#{i} assigned to task#{j}. Cost =#{costs[i][j]}"endendendelseputs"No solution found."end
# create the datacosts=[[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.lengthnum_tasks=costs[1].lengthteam1=[0,2,4]team2=[1,3,5]team_max=2# create the solversolver=ORTools::Solver.new("CBC")# create the variablesx={}num_workers.timesdo |i|num_tasks.timesdo |j|x[[i,j]]=solver.bool_var("x[#{i},#{j}]")endend# add the constraints# each worker is assigned at most 1 tasknum_workers.timesdo |i|solver.add(num_tasks.times.sum{ |j|x[[i,j]]} <=1)end# each task is assigned to exactly one workernum_tasks.timesdo |j|solver.add(num_workers.times.sum{ |i|x[[i,j]]} ==1)end# each team takes at most two taskssolver.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 objectivesolver.minimize(num_workers.times.flat_map{ |i|num_tasks.times.map{ |j|x[[i,j]] *costs[i][j]}}.sum)# invoke the solverstatus=solver.solve# display the resultsifstatus ==:optimal ||status ==:feasibleputs"Total cost =#{solver.objective.value}"num_workers.timesdo |worker|num_tasks.timesdo |task|ifx[[worker,task]].solution_value >0.5puts"Worker#{worker} assigned to task#{task}. Cost =#{costs[worker][task]}"endendendelseputs"No solution found."end
# create the datacosts=[[90,76,75,70],[35,85,55,65],[125,95,90,105],[45,110,95,115],]num_workers=costs.lengthnum_tasks=costs[0].length# create the solverassignment=ORTools::LinearSumAssignment.new# add the constraintsnum_workers.timesdo |worker|num_tasks.timesdo |task|ifcosts[worker][task]assignment.add_arc_with_cost(worker,task,costs[worker][task])endendend# invoke the solverstatus=assignment.solve# display the resultscasestatuswhen:optimalputs"Total cost =#{assignment.optimal_cost}"assignment.num_nodes.timesdo |i|puts"Worker#{i} assigned to task#{assignment.right_mate(i)}. Cost =#{assignment.assignment_cost(i)}"endwhen:infeasibleputs"No assignment is possible."when:possible_overflowputs"Some input costs are too large and may cause an integer overflow."end
# create the datadata={}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]=1data[:depot]=0# create the distance callbackmanager=ORTools::RoutingIndexManager.new(data[:distance_matrix].length,data[:num_vehicles],data[:depot])routing=ORTools::RoutingModel.new(manager)distance_callback=lambdado |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]endtransit_callback_index=routing.register_transit_callback(distance_callback)routing.set_arc_cost_evaluator_of_all_vehicles(transit_callback_index)# run the solverassignment=routing.solve(first_solution_strategy::path_cheapest_arc)# print the solutionputs"Objective:#{assignment.objective_value} miles"index=routing.start(0)plan_output=String.new("Route for vehicle 0:\n")route_distance=0while !routing.end?(index)plan_output +="#{manager.index_to_node(index)} ->"previous_index=indexindex=assignment.value(routing.next_var(index))route_distance +=routing.arc_cost_for_vehicle(previous_index,index,0)endplan_output +="#{manager.index_to_node(index)}\n"putsplan_output
# create the datadata={}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]=4data[:depot]=0# define the distance callbackmanager=ORTools::RoutingIndexManager.new(data[:distance_matrix].length,data[:num_vehicles],data[:depot])routing=ORTools::RoutingModel.new(manager)distance_callback=lambdado |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]endtransit_callback_index=routing.register_transit_callback(distance_callback)routing.set_arc_cost_evaluator_of_all_vehicles(transit_callback_index)# add a distance dimensiondimension_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 solversolution=routing.solve(first_solution_strategy::path_cheapest_arc)# print the solutionmax_route_distance=0data[:num_vehicles].timesdo |vehicle_id|index=routing.start(vehicle_id)plan_output=String.new("Route for vehicle#{vehicle_id}:\n")route_distance=0while !routing.end?(index)plan_output +="#{manager.index_to_node(index)} -> "previous_index=indexindex=solution.value(routing.next_var(index))route_distance +=routing.arc_cost_for_vehicle(previous_index,index,vehicle_id)endplan_output +="#{manager.index_to_node(index)}\n"plan_output +="Distance of the route:#{route_distance}m\n\n"putsplan_outputmax_route_distance=[route_distance,max_route_distance].maxendputs"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]=4data[:depot]=0manager=ORTools::RoutingIndexManager.new(data[:distance_matrix].size,data[:num_vehicles],data[:depot])routing=ORTools::RoutingModel.new(manager)distance_callback=lambdado |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]endtransit_callback_index=routing.register_transit_callback(distance_callback)routing.set_arc_cost_evaluator_of_all_vehicles(transit_callback_index)demand_callback=lambdado |from_index|from_node=manager.index_to_node(from_index)data[:demands][from_node]enddemand_callback_index=routing.register_unary_transit_callback(demand_callback)routing.add_dimension_with_vehicle_capacity(demand_callback_index,0,# null capacity slackdata[:vehicle_capacities],# vehicle maximum capacitiestrue,# start cumul to zero"Capacity")solution=routing.solve(first_solution_strategy::path_cheapest_arc)total_distance=0total_load=0data[:num_vehicles].timesdo |vehicle_id|index=routing.start(vehicle_id)plan_output=String.new("Route for vehicle#{vehicle_id}:\n")route_distance=0route_load=0while !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=indexindex=solution.value(routing.next_var(index))route_distance +=routing.arc_cost_for_vehicle(previous_index,index,vehicle_id)endplan_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"putsplan_outputtotal_distance +=route_distancetotal_load +=route_loadendputs"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]=4data[:depot]=0manager=ORTools::RoutingIndexManager.new(data[:distance_matrix].size,data[:num_vehicles],data[:depot])routing=ORTools::RoutingModel.new(manager)distance_callback=lambdado |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]endtransit_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 slack3000,# vehicle maximum travel distancetrue,# start cumul to zerodimension_name)distance_dimension=routing.mutable_dimension(dimension_name)distance_dimension.global_span_cost_coefficient=100data[:pickups_deliveries].eachdo |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))endsolution=routing.solve(first_solution_strategy::parallel_cheapest_insertion)total_distance=0data[:num_vehicles].timesdo |vehicle_id|index=routing.start(vehicle_id)plan_output=String.new("Route for vehicle#{vehicle_id}:\n")route_distance=0while !routing.end?(index)plan_output +="#{manager.index_to_node(index)} -> "previous_index=indexindex=solution.value(routing.next_var(index))route_distance +=routing.arc_cost_for_vehicle(previous_index,index,vehicle_id)endplan_output +="#{manager.index_to_node(index)}\n"plan_output +="Distance of the route:#{route_distance}m\n\n"putsplan_outputtotal_distance +=route_distanceendputs"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]=4data[:depot]=0manager=ORTools::RoutingIndexManager.new(data[:time_matrix].size,data[:num_vehicles],data[:depot])routing=ORTools::RoutingModel.new(manager)time_callback=lambdado |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]endtransit_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 time30,# maximum time per vehiclefalse,# don't force start cumul to zerotime)time_dimension=routing.mutable_dimension(time)data[:time_windows].each_with_indexdo |time_window,location_idx|nextiflocation_idx ==0index=manager.node_to_index(location_idx)time_dimension.cumul_var(index).set_range(time_window[0],time_window[1])enddata[:num_vehicles].timesdo |vehicle_id|index=routing.start(vehicle_id)time_dimension.cumul_var(index).set_range(data[:time_windows][0][0],data[:time_windows][0][1])enddata[:num_vehicles].timesdo |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)))endsolution=routing.solve(first_solution_strategy::path_cheapest_arc)time_dimension=routing.mutable_dimension("Time")total_time=0data[:num_vehicles].timesdo |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))endtime_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"putsplan_outputtotal_time +=solution.min(time_var)endputs"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]=4data[:vehicle_load_time]=5data[:vehicle_unload_time]=5data[:depot_capacity]=2data[:depot]=0manager=ORTools::RoutingIndexManager.new(data[:time_matrix].size,data[:num_vehicles],data[:depot])routing=ORTools::RoutingModel.new(manager)time_callback=lambdado |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]endtransit_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 time60,# maximum time per vehiclefalse,# don't force start cumul to zerotime)time_dimension=routing.mutable_dimension(time)data[:time_windows].each_with_indexdo |time_window,location_idx|nextiflocation_idx ==0index=manager.node_to_index(location_idx)time_dimension.cumul_var(index).set_range(time_window[0],time_window[1])enddata[:num_vehicles].timesdo |vehicle_id|index=routing.start(vehicle_id)time_dimension.cumul_var(index).set_range(data[:time_windows][0][0],data[:time_windows][0][1])endsolver=routing.solverintervals=[]data[:num_vehicles].timesdo |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")enddepot_usage=[1] *intervals.sizesolver.add(solver.cumulative(intervals,depot_usage,data[:depot_capacity],"depot"))data[:num_vehicles].timesdo |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)))endsolution=routing.solve(first_solution_strategy::path_cheapest_arc)time_dimension=routing.mutable_dimension("Time")total_time=0data[:num_vehicles].timesdo |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))endtime_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"putsplan_outputtotal_time +=solution.min(time_var)endputs"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]=4data[:depot]=0manager=ORTools::RoutingIndexManager.new(data[:distance_matrix].size,data[:num_vehicles],data[:depot])routing=ORTools::RoutingModel.new(manager)distance_callback=lambdado |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]endtransit_callback_index=routing.register_transit_callback(distance_callback)routing.set_arc_cost_evaluator_of_all_vehicles(transit_callback_index)demand_callback=lambdado |from_index|from_node=manager.index_to_node(from_index)data[:demands][from_node]enddemand_callback_index=routing.register_unary_transit_callback(demand_callback)routing.add_dimension_with_vehicle_capacity(demand_callback_index,0,# null capacity slackdata[:vehicle_capacities],# vehicle maximum capacitiestrue,# start cumul to zero"Capacity")penalty=10001.upto(data[:distance_matrix].size -1)do |node|routing.add_disjunction([manager.node_to_index(node)],penalty)endassignment=routing.solve(first_solution_strategy::path_cheapest_arc)dropped_nodes=String.new("Dropped nodes:")routing.size.timesdo |node|nextifrouting.start?(node) ||routing.end?(node)ifassignment.value(routing.next_var(node)) ==nodedropped_nodes +="#{manager.index_to_node(node)}"endendputsdropped_nodestotal_distance=0total_load=0data[:num_vehicles].timesdo |vehicle_id|index=routing.start(vehicle_id)plan_output="Route for vehicle#{vehicle_id}:\n"route_distance=0route_load=0while !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=indexindex=assignment.value(routing.next_var(index))route_distance +=routing.arc_cost_for_vehicle(previous_index,index,vehicle_id)endplan_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"putsplan_outputtotal_distance +=route_distancetotal_load +=route_loadendputs"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,# secondsfirst_solution_strategy::path_cheapest_arc,local_search_metaheuristic::guided_local_search,log_search:true)
# create the datavalues=[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 solversolver=ORTools::KnapsackSolver.new(:branch_and_bound,"KnapsackExample")# call the solversolver.init(values,weights,capacities)computed_value=solver.solvepacked_items=[]packed_weights=[]total_weight=0puts"Total value =#{computed_value}"values.length.timesdo |i|ifsolver.best_solution_contains?(i)packed_items <<ipacked_weights <<weights[0][i]total_weight +=weights[0][i]endendputs"Total weight:#{total_weight}"puts"Packed items:#{packed_items}"puts"Packed weights:#{packed_weights}"
# create the datadata={}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].lengthdata[:all_items]=data[:num_items].times.to_adata[:bin_capacities]=[100,100,100,100,100]data[:num_bins]=data[:bin_capacities].lengthdata[:all_bins]=data[:num_bins].times.to_a# declare the solversolver=ORTools::Solver.new("CBC")# create the variablesx={}data[:all_items].eachdo |i|data[:all_bins].eachdo |b|x[[i,b]]=solver.bool_var("x_#{i}_#{b}")endend# each item is assigned to at most one bindata[:all_items].eachdo |i|solver.add(data[:all_bins].sum{ |b|x[[i,b]]} <=1)end# the amount packed in each bin cannot exceed its capacitydata[:all_bins].eachdo |b|solver.add(data[:all_items].sum{ |i|x[[i,b]] *data[:weights][i]} <=data[:bin_capacities][b])end# maximize total value of packed itemsobjective=solver.objectivedata[:all_items].eachdo |i|data[:all_bins].eachdo |b|objective.set_coefficient(x[[i,b]],data[:values][i])endendobjective.set_maximization# call the solver and print the solutionstatus=solver.solveifstatus ==:optimalputs"Total packed value:#{objective.value}"total_weight=0data[:all_bins].eachdo |b|bin_weight=0bin_value=0puts"Bin#{b}\n\n"data[:all_items].eachdo |i|ifx[[i,b]].solution_value >0puts"Item#{i} - weight:#{data[:weights][i]} value:#{data[:values][i]}"bin_weight +=data[:weights][i]bin_value +=data[:values][i]endendputs"Packed bin weight:#{bin_weight}"puts"Packed bin value:#{bin_value}"putstotal_weight +=bin_weightendputs"Total packed weight:#{total_weight}"elseputs"The problem does not have an optimal solution."end
# create the datadata={}weights=[48,30,19,36,36,27,42,42,36,24,30]data[:weights]=weightsdata[:items]=(0...weights.length).to_adata[:bins]=data[:items]data[:bin_capacity]=100# create the mip solver with the CBC backendsolver=ORTools::Solver.new("CBC")# variables# x[i, j] = 1 if item i is packed in bin jx={}data[:items].eachdo |i|data[:bins].eachdo |j|x[[i,j]]=solver.int_var(0,1,"x_%i_%i" %[i,j])endend# y[j] = 1 if bin j is usedy={}data[:bins].eachdo |j|y[j]=solver.int_var(0,1,"y[%i]" %j)end# constraints# each item must be in exactly one bindata[:items].eachdo |i|solver.add(data[:bins].sum{ |j|x[[i,j]]} ==1)end# the amount packed in each bin cannot exceed its capacitydata[:bins].eachdo |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 usedsolver.minimize(data[:bins].sum{ |j|y[j]})# call the solver and print the solutionstatus=solver.solveifstatus ==:optimalnum_bins=0data[:bins].eachdo |j|ify[j].solution_value ==1bin_items=[]bin_weight=0data[:items].eachdo |i|ifx[[i,j]].solution_value >0bin_items <<ibin_weight +=data[:weights][i]endendifbin_weight >0num_bins +=1puts"Bin number#{j}"puts" Items packed:#{bin_items}"puts" Total weight:#{bin_weight}"putsendendendputsputs"Number of bins used:#{num_bins}"puts"Time =#{solver.wall_time} milliseconds"elseputs"The problem does not have an optimal solution."end
# define the datastart_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 arcsmax_flow=ORTools::SimpleMaxFlow.newstart_nodes.length.timesdo |i|max_flow.add_arc_with_capacity(start_nodes[i],end_nodes[i],capacities[i])end# invoke the solver and display the resultsifmax_flow.solve(0,4) ==:optimalputs"Max flow:#{max_flow.optimal_flow}"putsputs" Arc Flow / Capacity"max_flow.num_arcs.timesdo |i|puts"%1s -> %1s %3s / %3s" %[max_flow.tail(i),max_flow.head(i),max_flow.flow(i),max_flow.capacity(i)]endputs"Source side min-cut:#{max_flow.source_side_min_cut}"puts"Sink side min-cut:#{max_flow.sink_side_min_cut}"elseputs"There was an issue with the max flow input."end
# define the datastart_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 arcsmin_cost_flow=ORTools::SimpleMinCostFlow.newstart_nodes.length.timesdo |i|min_cost_flow.add_arc_with_capacity_and_unit_cost(start_nodes[i],end_nodes[i],capacities[i],unit_costs[i])endsupplies.length.timesdo |i|min_cost_flow.set_node_supply(i,supplies[i])end# invoke the solver and display the resultsifmin_cost_flow.solve ==:optimalputs"Minimum cost#{min_cost_flow.optimal_cost}"putsputs" Arc Flow / Capacity Cost"min_cost_flow.num_arcs.timesdo |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]endelseputs"There was an issue with the min cost flow input."end
# create the solvermin_cost_flow=ORTools::SimpleMinCostFlow.new# create the datastart_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=0sink=9tasks=4# create the graph and constraintsstart_nodes.length.timesdo |i|min_cost_flow.add_arc_with_capacity_and_unit_cost(start_nodes[i],end_nodes[i],capacities[i],costs[i])endsupplies.length.timesdo |i|min_cost_flow.set_node_supply(i,supplies[i])end# invoke the solverifmin_cost_flow.solve ==:optimalputs"Total cost =#{min_cost_flow.optimal_cost}"putsmin_cost_flow.num_arcs.timesdo |arc|ifmin_cost_flow.tail(arc) !=source &&min_cost_flow.head(arc) !=sinkifmin_cost_flow.flow(arc) >0puts"Worker %d assigned to task %d. Cost = %d" %[min_cost_flow.tail(arc),min_cost_flow.head(arc),min_cost_flow.unit_cost(arc)]endendendelseputs"There was an issue with the min cost flow input."end
# define the datanum_nurses=4num_shifts=3num_days=3all_nurses=num_nurses.times.to_aall_shifts=num_shifts.times.to_aall_days=num_days.times.to_a# create the variablesmodel=ORTools::CpModel.newshifts={}all_nurses.eachdo |n|all_days.eachdo |d|all_shifts.eachdo |s|shifts[[n,d,s]]=model.new_bool_var("shift_n%id%is%i" %[n,d,s])endendend# assign nurses to shiftsall_days.eachdo |d|all_shifts.eachdo |s|model.add(model.sum(all_nurses.map{ |n|shifts[[n,d,s]]}) ==1)endendall_nurses.eachdo |n|all_days.eachdo |d|model.add(model.sum(all_shifts.map{ |s|shifts[[n,d,s]]}) <=1)endend# assign shifts evenlymin_shifts_per_nurse=(num_shifts *num_days) /num_nursesmax_shifts_per_nurse=min_shifts_per_nurse +1all_nurses.eachdo |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 printerclassNursesPartialSolutionPrinter <ORTools::CpSolverSolutionCallbackattr_reader:solution_countdefinitialize(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=0enddefon_solution_callbackif@solutions.include?(@solution_count)puts"Solution#{@solution_count}"@num_days.timesdo |d|puts"Day#{d}"@num_nurses.timesdo |n|working=false@num_shifts.timesdo |s|ifvalue(@shifts[[n,d,s]])working=trueputs" Nurse %i works shift %i" %[n,s]endendunlessworkingputs" Nurse#{n} does not work"endendendputsend@solution_count +=1endend# call the solver and display the resultssolver=ORTools::CpSolver.newa_few_solutions=5.times.to_asolution_printer=NursesPartialSolutionPrinter.new(shifts,num_nurses,num_days,num_shifts,a_few_solutions)solver.search_for_all_solutions(model,solution_printer)putsputs"Statistics"puts" - conflicts : %i" %solver.num_conflictsputs" - branches : %i" %solver.num_branchesputs" - wall time : %f s" %solver.wall_timeputs" - solutions found : %i" %solution_printer.solution_count
# create the modelmodel=ORTools::CpModel.newjobs_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]}}.maxall_machines=machines_count.times.to_a# computes horizon dynamically as the sum of all durationshorizon=jobs_data.flat_map{ |job|job.map{ |task|task[1]}}.sum# creates job intervals and add to the corresponding machine listsall_tasks={}machine_to_intervals=Hash.new{ |hash,key|hash[key]=[]}jobs_data.each_with_indexdo |job,job_id|job.each_with_indexdo |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_varendend# create and add disjunctive constraintsall_machines.eachdo |machine|model.add_no_overlap(machine_to_intervals[machine])end# precedences inside a jobjobs_data.each_with_indexdo |job,job_id|(job.size -1).timesdo |task_id|model.add(all_tasks[[job_id,task_id +1]][:start] >=all_tasks[[job_id,task_id]][:end])endend# makespan objectiveobj_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 modelsolver=ORTools::CpSolver.newstatus=solver.solve(model)# create one list of assigned tasks per machineassigned_jobs=Hash.new{ |hash,key|hash[key]=[]}jobs_data.each_with_indexdo |job,job_id|job.each_with_indexdo |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]}endend# create per machine output linesoutput=String.new("")all_machines.eachdo |machine|# sort by starting timeassigned_jobs[machine].sort_by!{ |v|v[:start]}sol_line_tasks="Machine#{machine}: "sol_line=" "assigned_jobs[machine].eachdo |assigned_task|name="job_%i_%i" %[assigned_task[:job],assigned_task[:index]]# add spaces to output to align columnssol_line_tasks +="%-10s" %namestart=assigned_task[:start]duration=assigned_task[:duration]sol_tmp="[%i,%i]" %[start,start +duration]# add spaces to output to align columnssol_line +="%-10s" %sol_tmpendsol_line +="\n"sol_line_tasks +="\n"output +=sol_line_tasksoutput +=sol_lineend# finally print the solution foundputs"Optimal Schedule Length: %i" %solver.objective_valueputsoutput
# create the modelmodel=ORTools::CpModel.newcell_size=3line_size=cell_size**2line=(0...line_size).to_acell=(0...cell_size).to_ainitial_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.eachdo |i|line.eachdo |j|grid[[i,j]]=model.new_int_var(1,line_size,"grid %i %i" %[i,j])endend# all different on rowsline.eachdo |i|model.add_all_different(line.map{ |j|grid[[i,j]]})end# all different on columnsline.eachdo |j|model.add_all_different(line.map{ |i|grid[[i,j]]})end# all different on cellscell.eachdo |i|cell.eachdo |j|one_cell=[]cell.eachdo |di|cell.eachdo |dj|one_cell <<grid[[i *cell_size +di,j *cell_size +dj]]endendmodel.add_all_different(one_cell)endend# initial valuesline.eachdo |i|line.eachdo |j|ifinitial_grid[i][j] !=0model.add(grid[[i,j]] ==initial_grid[i][j])endendend# solve and print solutionsolver=ORTools::CpSolver.newstatus=solver.solve(model)ifstatus ==:optimalline.eachdo |i|pline.map{ |j|solver.value(grid[[i,j]])}endend
# 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=5table_capacity=4min_known_neighbors=1# Connection matrix: who knows who, and how strong# is the relationc=[[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 sidenames=["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.sizeall_tables=num_tables.times.to_aall_guests=num_guests.times.to_a# create the cp modelmodel=ORTools::CpModel.new# decision variablesseats={}all_tables.eachdo |t|all_guests.eachdo |g|seats[[t,g]]=model.new_bool_var("guest %i seats on table %i" %[g,t])endendpairs=all_guests.combination(2)colocated={}pairs.eachdo |g1,g2|colocated[[g1,g2]]=model.new_bool_var("guest %i seats with guest %i" %[g1,g2])endsame_table={}pairs.eachdo |g1,g2|all_tables.eachdo |t|same_table[[g1,g2,t]]=model.new_bool_var("guest %i seats with guest %i on table %i" %[g1,g2,t])endend# Objectivemodel.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.eachdo |g|model.add(model.sum(all_tables.map{ |t|seats[[t,g]]}) ==1)end# Tables have a max capacity.all_tables.eachdo |t|model.add(model.sum(all_guests.map{ |g|seats[[t,g]]}) <=table_capacity)end# Link colocated with seatspairs.eachdo |g1,g2|all_tables.eachdo |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.eachdo |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 modelsolver=ORTools::CpSolver.newsolution_printer=WeddingChartPrinter.new(seats,names,num_tables,num_guests)solver.solve(model,solution_printer)puts"Statistics"puts" - conflicts : %i" %solver.num_conflictsputs" - branches : %i" %solver.num_branchesputs" - wall time : %f s" %solver.wall_timeputs" - num solutions: %i" %solution_printer.num_solutions
# A set partitioning model of a wedding seating problem# Authors: Stuart Mitchell 2009max_tables=5max_table_size=4guests=%w(ABCDEFGIJKLMNOPQR)# Find the happiness of the table# by calculating the maximum distance between the lettersdefhappiness(table)(table[0].ord -table[-1].ord).absend# create list of all possible tablespossible_tables=[](1..max_table_size).eachdo |i|possible_tables +=guests.combination(i).to_aendsolver=ORTools::Solver.new("CBC")# create a binary variable to state that a table setting is usedx={}possible_tables.eachdo |table|x[table]=solver.int_var(0,1,"table#{table.join(", ")}")endsolver.minimize(possible_tables.sum{ |table|x[table] *happiness(table)})# specify the maximum number of tablessolver.add(x.values.sum <=max_tables)# a guest must seated at one and only one tableguests.eachdo |guest|tables_with_guest=possible_tables.select{ |table|table.include?(guest)}solver.add(tables_with_guest.sum{ |table|x[table]} ==1)endstatus=solver.solveputs"The chosen tables are out of a total of %s:" %possible_tables.sizepossible_tables.eachdo |table|ifx[table].solution_value ==1ptableendend
View thechangelog
Everyone is encouraged to help improve this project. Here are a few ways you can help:
- Report bugs
- Fix bugs andsubmit 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.gitcd or-tools-rubybundle installbundleexec rake compilebundleexec raketest
Resources
About
Operations research tools for Ruby
Topics
Resources
License
Uh oh!
There was an error while loading.Please reload this page.
Stars
Watchers
Forks
Packages0
No packages published
Uh oh!
There was an error while loading.Please reload this page.
Contributors11
Uh oh!
There was an error while loading.Please reload this page.