Simulated Annealing

Among the techniques that Pathfinder uses to optimize cluster routes is simulated annealing. Simulated annealing is a probabilistic technique for approximating the solutions to discrete optimization problems. Compared to other optimization algorithms, it is particularly good with problems that have many local maximums.

The Algorithm

The idea of simulated annealing is very simple. It is a heuristic-guided search where at each step, you generate a random deviation from the current solution to another solution. Next you compute an "energy level" for the original and the new solution. The "energy level" is your objective function. Then, you probabilistically choose to accept or reject the deviation. The probability of accepting is determined by the difference in energy levels and the global temperature value that decreases over the duration of the algorithm.

let t = temperature_scheduler.initial()
let s = initial_state
while t > 0:
  	let s` = s.mutate()
    let delta_e = s`.energy_level() - s.energy_level()
    if random() < exp(-delta_e/t):
      	s = s`
  	t = temperature_scheduler.next()
return s

Mutations

For simulated annealing to be efficient, you need to be able to generate mutations of a given solution quickly. Furthermore, your mutations need to be such that the minimum number of mutations required to transform from one solution to another solution is small. These can be conflicting goals and will likely require trade-offs in your model.

Temperature

The global temperature level can be modeled in several ways. Eventually it needs to decrease, however the rate and shape of decrease are left to the discretion of the implementer. While implementing Pathfinder's routing engine, we experimented with linear and exponential temperature decay patterns. You can see our results here: https://github.com/CSSE497/pathfinder-routing/pull/3. In general, linear decay out-performed exponential decay, but not significantly.

The Framework

We love using open source software, so the first thing we did to solve the k-VRP with simulated annealing was look for a simulated annealing framework in Java. Unfortunately we did not find any mature frameworks to suit our needs, so we rolled our own. Our framework is available on GitHub and Maven Central.

Usage

If you are interested in using our SA library or have any feedback on it, we would love to hear from you at [email protected].

Before you begin you will need to include the library as a dependency in your Maven project.

<dependency>
    <groupId>xyz.thepathfinder</groupId>
    <artifactId>simulatedannealing</artifactId>
    <version>0.0.3</version>
</dependency>

Now to get started, you need to implement the SearchState<T> interface. It defines only one method, T step(), which should return a randomly chosen deviation from the current state. You also need to implement the Problem<T> interface, which initializes a state and evaluates the energey of states.

Next, you need to choose a Scheduler implementation, which determines the speed and shape of the annealing process. We provide two built-in options, LinearDecayScheduler and ExponentialDecayScheduler.

Finally, just create a Solver and call solve! Your final code will look something like this:

Scheduler scheduler = new LinearDecayScheduler(INITIAL_TEMPERATURE, NUMBER_OF_STEPS);
Problem<VRPSearchState> problem = new VehicleRoutingProblem(...);
Solver<VRPSearchState> solver = new Solver(problem, scheduler);
VRPSearchState solution = solver.solve();

Changelog