ExVrp.IteratedLocalSearch (ExVrp v0.4.2)

Copy Markdown View Source

Iterated Local Search with Late Acceptance Hill-Climbing.

This is a direct port of PyVRP's IteratedLocalSearch. The algorithm:

  1. Starts with an initial solution
  2. Each iteration: applies local search to generate a candidate
  3. Accepts the candidate using Late Acceptance Hill-Climbing (LAHC)
  4. Restarts from best solution after N iterations without improvement
  5. Continues until stopping criterion is met

Late Acceptance Hill-Climbing (Burke & Bykov, 2017) accepts moves based on comparison with historical solutions, not just the current solution. This allows temporary worsening moves to escape local optima.

Summary

Types

stop_fn()

Functions

run(problem_data, penalty_manager, local_search, initial_solution, stop_fn, params \\ %Params{}, opts \\ [])

Runs the Iterated Local Search algorithm.

Types

stop_fn()

@type stop_fn() :: (non_neg_integer() -> boolean())

Functions

run(problem_data, penalty_manager, local_search, initial_solution, stop_fn, params \\ %Params{}, opts \\ [])

@spec run(
  reference(),
  ExVrp.PenaltyManager.t(),
  reference(),
  reference(),
  stop_fn(),
  ExVrp.IteratedLocalSearch.Params.t(),
  keyword()
) :: ExVrp.IteratedLocalSearch.Result.t()

Runs the Iterated Local Search algorithm.

Parameters

  • problem_data - Reference to the problem data
  • penalty_manager - PenaltyManager for dynamic penalty adjustment
  • local_search - Persistent LocalSearch resource from Native.create_local_search/1
  • initial_solution - Starting solution reference
  • stop_fn - Function that takes best_cost and returns true to stop
  • params - ILS parameters (optional)

Returns

A Result struct containing the best solution found and statistics.