能否借助OptaPlanner在Java应用中实现禁忌搜索算法？

Absolutely! OptaPlanner is a fantastic choice here—way more active and supported than the discontinued OpenTS, and it has first-class support for tabu search, which fits perfectly with your VRP variant that includes real-world data like item barcodes. Let me break down how to make this work:

1. OptaPlanner’s Built-In Tabu Search Support #

OptaPlanner doesn’t just support tabu search—it integrates it seamlessly into its solver framework. You can use it as a standalone local search algorithm, or pair it with a construction heuristic (like first-fit-decreasing) to generate a solid initial solution before refining it with tabu search. This is way more flexible than rolling your own or relying on a stale library like OpenTS.

2. Adapting to Your VRP’s Extra Attributes (e.g., Barcodes) #

Your additional business data (like item barcodes) won’t be a problem at all. OptaPlanner’s domain model is designed to handle custom fields effortlessly:

• Just add fields like private String barcode; to your entity classes (e.g., Item or Delivery). These are treated as business data, not planning variables, so they won’t interfere with the algorithm’s logic—you can use them in your score calculations or custom move logic if needed.
• The solver only cares about planning variables (like which vehicle a delivery is assigned to, or the order of visits), so your extra attributes are just there for your business logic.

3. Configuring Tabu Search in OptaPlanner #

You can set up tabu search using either XML configuration or the Java API. Here’s a quick XML example tailored to VRP:

<solver>
  <!-- Define your solution and entity classes -->
  <solutionClass>com.yourcompany.vrp.YourVRPSolution</solutionClass>
  <entityClass>com.yourcompany.vrp.DeliveryVisit</entityClass>

  <!-- Score calculation (adjust to your constraints: distance, time windows, etc.) -->
  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    <easyScoreCalculatorClass>com.yourcompany.vrp.YourVRPScoreCalculator</easyScoreCalculatorClass>
  </scoreDirectorFactory>

  <!-- Stop after 60 seconds (tweak this as needed) -->
  <termination>
    <secondsSpentLimit>60</secondsSpentLimit>
  </termination>

  <!-- Generate initial solution with a construction heuristic -->
  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>

  <!-- Enable tabu search as the local search algorithm -->
  <localSearch>
    <localSearchType>TABU_SEARCH</localSearchType>
    <tabuSearch>
      <!-- Adjust tabu size based on your problem scale (5-10 is a good starting point) -->
      <tabuSize>7</tabuSize>
      <!-- Allow overriding tabu if the solution is better than the last accepted one -->
      <aspirationType>LAST_ACCEPTED_SCORE</aspirationType>
    </tabuSearch>
    <!-- Custom move selector for VRP-specific moves (swap visits, reassign to vehicles, etc.) -->
    <moveSelector>
      <moveListFactoryClass>com.yourcompany.vrp.YourVRPMoveFactory</moveListFactoryClass>
    </moveSelector>
  </localSearch>
</solver>

The moveListFactoryClass lets you define exactly what moves are considered (e.g., swapping two delivery visits between vehicles, moving a visit to a different position in a route)—OptaPlanner’s tabu search will track these moves and avoid repeating them for the tabu duration.

4. Customizing Tabu Logic (If Needed) #

If you need custom tabu rules (e.g., forbidding moves that involve items with specific barcodes), OptaPlanner lets you extend its tabu search implementation:

• Implement a custom TabuAcceptor to define exactly which moves should be tabu.
• Or use a TabuStrategy to track specific aspects of the solution (like which vehicles have handled certain barcodes) instead of just moves.

5. Why This Is Better Than OpenTS #

Unlike OpenTS (which is no longer maintained), OptaPlanner is actively developed with regular updates, a strong community, and tons of documentation. You’ll also get access to other algorithms (like simulated annealing, late acceptance) that you can mix with tabu search if you want to refine your solution further.

Quick Tips to Get Started #

• Start with OptaPlanner’s official VRP example—clone it, add your barcode fields, and tweak the score calculator to match your constraints.
• Experiment with tabu size and aspiration criteria—smaller problems might work with a tabu size of 5, while larger ones need 10+.
• Use the solver’s built-in benchmarking tools to compare tabu search with other algorithms and find the best setup for your data.

内容的提问来源于stack exchange，提问作者Emanuele Guerrazzi