Using Open VRP: writing your algo from scratch

You can use the Open-VRP library to write your own algorithms from scratch. The source of the library is contained in the lib folder and can be loaded with (require :open-vrp-lib) or (asdf:operate 'asdf:load-op :open-vrp-lib). Check the Home page to see what this library has.

The following assumes the usage of the standard pre-defined problem types VRP, CVRP, VRPTW and CVRPTW with the fitness function of minimizing total distance. It is also possible to define your own problem/fitness function.

• define your problem with define-problem or load from a text-file with load-testcase-solomon or load-tsplib-vrp-file (currently supports Solomon and TSPLIB style text files, feel free to add your own favorite benchmarks/text-files).

• create your own file with the following:

(in-package open-vrp.algo)

(defclass my-algo (algo) (...))

(defmethod run-algo ((p problem) (a my-algo))
   ...
   (init-algo p a)
    a)

• Beware of two different kinds of algorithms: Type 1 that finds a solution heuristically and when found, we are done; Type 2 that is a search algorithm which iterates over solutions and returns the best one. init-algo will set the algo-object's :current-sol, :best-sol and :best-fitness. For a Type 1 algorithm, :best-sol and :current-sol is the same, since there is just one iteration -- :iterations is essentially unnecessary. Type 2 algorithms need to be initialized (using init-algo or a Type 1 algo) and may implement a call to the generic method iterate. Tabu Search is a Type 2 algorithm. Greedy-NN as an example below is a Type 1.

• call (solve-prob problem (make-instance 'my-algo)) with your problem and algo objects. solve-prob calls run-algo but will solve with a copy of the problem object, and will leave your original problem object untouched (recommended).

• solve-prob will return your algo object; make sure that your run-algo method calls init-algo to set the slots in the algo object and that the method returns the algo object.

• call (plot-solution my-algo &optional path-to-output.png) for plotting the best solution found in your algo object. solve-plot will call solve-prob and plot-solution in succession.

Example with a Greedy Nearest Neighborhood algo:

OPEN-VRP> (defvar *tsp-coords* (list (cons 0 0) (cons 1 0) (cons 1 1) (cons 0 1)))
*tsp-coords*
OPEN-VRP> (define-problem "tsp" *tsp-coords* 1 nil)
#<VRP {xxxxxxx}>
OPEN-VRP> (solve-plot * (make-instance 'greedy-nn))

"Final solution of run with GREEDY-NN"
----------------------
Fitness: 3.0
-------------
Route: (0 1 2 3)
---------------