如何在Rails应用中使用Google OR-Tools解决TSP问题？

Got it, since Google OR-Tools doesn’t offer official Ruby bindings, you’ve got three solid, practical paths to integrate TSP solving into your Rails app. Let’s break them down, starting with the easiest one (since you already have a working Python implementation):

Option 1: Call Your Working Python TSP Script from Ruby (Quickest Win) #

This is the simplest approach because you can leverage your existing Python code without rewriting anything. The idea is to wrap your Python solver into a script that accepts input (like a distance matrix) and outputs results in a Ruby-friendly format (JSON), then call that script from your Rails app.

Step 1: Refactor Your Python Script for I/O #

Update your Python TSP code to read input from stdin and write output to stdout as JSON. Here’s an example:

import sys
import json
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def solve_tsp(distance_matrix):
    # Your existing TSP logic here (matches what you already have working)
    size = len(distance_matrix)
    manager = pywrapcp.RoutingIndexManager(size, 1, 0)
    routing = pywrapcp.RoutingModel(manager)

    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    
    solution = routing.SolveWithParameters(search_parameters)
    if solution:
        route = []
        index = routing.Start(0)
        while not routing.IsEnd(index):
            route.append(manager.IndexToNode(index))
            index = solution.Value(routing.NextVar(index))
        route.append(manager.IndexToNode(index))
        return {"route": route, "total_distance": solution.ObjectiveValue()}
    else:
        return {"error": "No valid solution found"}

if __name__ == "__main__":
    # Read input from stdin (sent from Ruby)
    input_data = json.loads(sys.stdin.read())
    result = solve_tsp(input_data["distance_matrix"])
    # Output result as JSON
    print(json.dumps(result))

Save this as lib/tsp_solver.py in your Rails project.

Step 2: Call the Script from Rails #

Use Ruby’s Open3 module (safer than system or backticks) to execute the script, pass input, and parse the output. Add this method to a Rails service or controller:

require 'open3'
require 'json'

def solve_tsp(distance_matrix)
    # Prepare input as JSON
    input_payload = JSON.generate(distance_matrix: distance_matrix)
    script_path = Rails.root.join('lib', 'tsp_solver.py').to_s

    # Execute the Python script and capture output
    stdout_str, stderr_str, status = Open3.capture3('python3', script_path, stdin_data: input_payload)

    if status.success?
        JSON.parse(stdout_str)
    else
        { error: "TSP solver failed", details: stderr_str.strip }
    end
end

# Example usage
distance_matrix = [
    [0, 2451, 713, 1018, 1631],
    [2451, 0, 1745, 1524, 831],
    [713, 1745, 0, 355, 920],
    [1018, 1524, 355, 0, 700],
    [1631, 831, 920, 700, 0]
]
result = solve_tsp(distance_matrix)
puts "Optimal route: #{result['route']}"
puts "Total distance: #{result['total_distance']}"

Option 2: Use Ruby FFI to Bind to OR-Tools' C++ Library (High Performance) #

If you need low-latency access and want to avoid spawning Python processes, you can use Ruby’s Foreign Function Interface (FFI) to call OR-Tools’ C++ library directly. This is more work but offers better performance.

Step 1: Install OR-Tools C++ Library #

Follow the official OR-Tools C++ installation guide for your OS (Linux/macOS/Windows).

Step 2: Add the FFI Gem #

Add gem 'ffi' to your Gemfile, then run bundle install.

Step 3: Bind OR-Tools Functions #

You’ll need to map OR-Tools’ C++ structs and functions to Ruby via FFI. Here’s a simplified example (you’ll need to expand this based on your TSP needs):

require 'ffi'

module ORTools
    extend FFI::Library
    # Path to your OR-Tools shared library (adjust for your OS)
    ffi_lib '/usr/local/lib/libortools.so'

    # Define structs matching OR-Tools' C API
    class RoutingIndexManager < FFI::Struct
        layout :size, :int,
               :num_vehicles, :int,
               :depot, :int
    end

    # Attach OR-Tools functions (refer to OR-Tools' C headers for exact signatures)
    attach_function :RoutingIndexManager_Create, [:int, :int, :int], :pointer
    attach_function :RoutingIndexManager_Destroy, [:pointer], :void
    # Add more functions for RoutingModel, SolveWithParameters, etc.
end

# Example solver skeleton (you'll need to implement full logic)
def solve_tsp_with_ffi(distance_matrix)
    manager = ORTools::RoutingIndexManager_Create(distance_matrix.size, 1, 0)
    # Build routing model, register distance callback, set parameters, solve...
    # Don't forget to clean up resources with ORTools::RoutingIndexManager_Destroy(manager)
end

Note: This approach requires deep familiarity with OR-Tools’ C++ API, as you’ll need to map dozens of structs and functions. It’s best for performance-critical applications.

Option 3: Wrap the Python Solver in a REST API (Microservice Approach) #

If you want to separate your TSP solver from your Rails app (e.g., for scaling or to avoid Python dependencies on your Rails server), wrap the Python solver in a simple REST API and call it from Rails.

Step 1: Build the Python API #

Use FastAPI for a lightweight, fast API:

from fastapi import FastAPI
from pydantic import BaseModel
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

app = FastAPI()

class TSPInput(BaseModel):
    distance_matrix: list[list[int]]

def solve_tsp(distance_matrix):
    # Same solve function as Option 1
    size = len(distance_matrix)
    manager = pywrapcp.RoutingIndexManager(size, 1, 0)
    routing = pywrapcp.RoutingModel(manager)

    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    
    solution = routing.SolveWithParameters(search_parameters)
    if solution:
        route = []
        index = routing.Start(0)
        while not routing.IsEnd(index):
            route.append(manager.IndexToNode(index))
            index = solution.Value(routing.NextVar(index))
        route.append(manager.IndexToNode(index))
        return {"route": route, "total_distance": solution.ObjectiveValue()}
    else:
        return {"error": "No valid solution found"}

@app.post("/solve-tsp")
async def solve_tsp_endpoint(input: TSPInput):
    return solve_tsp(input.distance_matrix)

Run the API with uvicorn tsp_api:app --host 0.0.0.0 --port 8000.

Step 2: Call the API from Rails #

Use HTTParty (add gem 'httparty' to your Gemfile) to send requests to the API:

require 'httparty'
require 'json'

def solve_tsp_via_api(distance_matrix)
    response = HTTParty.post(
        'http://localhost:8000/solve-tsp',
        body: { distance_matrix: distance_matrix }.to_json,
        headers: { 'Content-Type' => 'application/json' }
    )

    response.success? ? response.parsed_response : { error: "API request failed", details: response.body }
end

Recommendation #

Start with Option 1—it’s the fastest to implement since you already have working Python code. Only consider Options 2 or 3 if you have specific performance or architecture needs.

内容的提问来源于stack exchange，提问作者umang-malhotra