Using Open VRP: build your algo with the Iterator

Open-VRP includes a framework to facilitate you with building your algorithms (algo/iterator.lisp). It is designed to take advantage of the similarities between local-search type of algorithms and prevent code-duplication. Currently implemented using the Iterator framework is Tabu Search. Refer to the implementation as an example.

Any kind of algorithm that goes through this cycle could be implemented with the Iterator. Population-based algorithms are not advised to use the Iterator.

When you build your search algorithm with the Iterator framework, you take advantage of:

• logging the progress of the search and printing the solution
• automatically setting the algo-object's slots
  • :best-sol - when new best solution is found
  • :best-fitness - idem
  • :current-sol - after each iteration
• call iterate to step/perform one iteration at a time
• using iterate-more to resume the search with more iterations (after finishing or breaking)
• Define up to 6 generic methods: initialize, generate-moves, assess-move, select-move, perform-move and iterate. The Iterator takes care of the rest.

---

Before you can use the Iterator, you need to define your algo-class and write run-algo for your problem/algo combination (read more). You will also need to define your-move class that inherits from move. See algo/TS-classdef.lisp for an example.

(defclass my-move (move)
  (...))

The parameters in the move class define the move, e.g. node-id and vehicle-id (as used in our Tabu-Search(TS) implementation.

The following describes shortly what is expected from the 6 parts of your algorithm. It is not necessary to implement and use all methods. You may also write your own functions that do the trick, e.g. the generate-insertion-moves in algo/best-insertion.lisp only generates moves concerning a given node-id and vehicle-id.

For an extensive example algorithm using the Iterator, check out the description of the Tabu-Search implementation.

• (defmethod initialize ((prob problem) (algo my-algo))...) method to initialize the algo-slots to an initial solution. Use init-algo to set :best-sol, :best-fitness and :current-sol in one go.
• (defmethod generate-moves ((algo my-algo))...) defines what moves will be created to be potential candidates for the coming iteration. Should return a list of my-move objects, to be passed to assess-moves. You may use map-node-ID and map-veh-ID macros as in the TS implementation.
• optional, but recommended(defmethod assess-move ((sol problem) (algo my-algo))...) defines how we assess a single move/chromosome. Should set the :move-fitness slots of the move object upon assessing. The default behaviour of this method is generic and should work once perform-move is implemented. It will perform the move on a clone of the solution and calculate the difference in fitness. Although you may omit implementing this method, it is strongly advised as it may speed up the algo significantly. Note that assess-move and assess-moves are different! The latter is plural, and accepts a list of moves.
• optional (defmethod select-move ((algo my-algo) moves)...) takes a list of assessed moves, and returns the best move to be performed. For TS, needs implementation to select the best non-tabu move.
• (defmethod peform-move ((mv my-move))...) takes the selected move and performs it on the current solution to produce and return a new solution. This method is pivotal to your algorithm and must be implemented.
• (defmethod iterate ((algo my-algo))...) to define specifics for your iteration. This method is included in the general library as it may also be useful for writing your own algos. The :after method (in lib/solver.lisp) will decrease :iterations in your algo object by one, checks if new best solution has been found and sets your algo's :best-sol and :best-fitness. An :around method is implemented in the TS as a way to implement a stopping condition.

Again, this is just a short overview -- the best way to grasp the ideas is to look at examples. Please proceed to the description of the Tabu Search implementation.