Common Lisp Package: OPEN-VRP

README:

Open-VRP

Check out the Wiki for an overview of Open-VRP or scroll down for a summary, fork and get-started!

Synopsis

Open VRP is a framework to model and solve VRP-like problems for students, academics, businesses and hobbyist alike. This framework allows for quick implementation of simple TSP/VRP problems to more complicated VRPTW, PDPTW, MDCPVRPPDTW, or however cool you want to sound. The library is extensibly written in Common Lisp's CLOS. Depending on your interest/purpose, an algorithm can be:

The Problem object (e.g. VRP) and the Algorithm object (e.g. Genetic Algorithm) are modelled seperately and combined with the generic method (solve-prob problem algo). Different solution algorithms can be tested and compared against each other on the same problem (which you only model once).

Current features (v. 0.6.2)

  • TSP, VRP, CVRP, VRPTW, CVRPTW
  • Homogenous/heterogenous fleet
  • Demands, duration, capacity, time-windows, speed
  • Define network using coordinates or (asymettric) distance matrix
  • Tabu Search
  • Logging of search progress (to file or to REPL)
  • Plotting of final solution or after each iteration
  • Test-case loader (Solomon and TSPLIB format)
  • Batch-run to test algo on a directory of test-cases

Vision

Too often have I found myself having to build a VRP model from scratch, just to experiment with some meta-heuristics for a school paper. Academics/students with a background/interest in Mathematics/Operations Research without the skills/patience for die-hard coding (in C++/Java), have no choice but to spend their valuable time stuck in the debug/test/debug cycle. Here is why those in OR should consider Common Lisp as an option.

With this framework, I hope to catalyze the research and application of routing solutions. Researchers in innovative new algorithms should not need to fiddle in the Eclipse debugger screen. They should be able to focus all their energy and effort in devising their heuristics. OR should be kept fun and engaging.

The ultimate vision for Open VRP is a simple intuitive toolkit for the OR community, free for anyone.

Installation

~$ git clone git://github.com/mck-/Open-VRP.git Add this path and evaluate require:

(push "/path/to/Open-VRP/" asdf:*central-registry*) (require 'open-vrp) (in-package :open-vrp)

Usage Check the Wiki for more documentation, the following is a short summary of the main functionality.

solve-prob expects a problem object and an algo object.

test-vrp, solomon25, solomon100, christofides-1 and christofides-2 are pre-loaded demo problems. To use Tabu Search:

(solve-prob test-vrp (make-instance 'tabu-search :iterations 10 :animatep T)) (solve-prob solomon100 (make-instance 'tabu-search :iterations 100)) (solve-prob christofides-2 (make-instance 'tabu-search :iterations 50))

By default, problems will plot to plots/name.png and log to run-logs/name.txt where name refers to the :name slot of the Problem object. (toggle-plot <problem>) to disable plotting the final solution. Use (set-log-mode <problem> x) to switch from [0] no logging, [1] logging to file or [2] logging to the REPL.

If you don't like the legend in the plot, turn it off with (toggle-legend <problem>).

When :animatep is set to T, each iteration will produce a plot in run-frames/Iteration x.png (much slower, since it needs to plot each iteration). You may use (toggle-animate <algo>) to turn it on/off.

You can define your own problem objects with:

(define-problem "VRP" fleet-size :node-coords-list node-coords :to-depot T) (define-problem "CVRP" fleet-size :node-coords-list node-coords :demands demands-list :capacities capacity-list) (define-problem "VRPTW" fleet-size :node-coords-list node-coords :time-windows time-windows :durations durations :speeds speed)

where node-coords is a list of pairs, demands-list a list of associated demands (must be same length), and fleet-size is the number of vehicles. When a demands-list and vehicle capacity are provided, the resulting problem is a CVRP. If time-windows (list of pairs) and durations are given, the resulting problem object is a VRPTW. When everything is provided, it creates a CVRPTW. Each class of problem has its own specific constraints to check.

You may also provide a(n asymmetric) distance matrix instead of node-coords (real-life problems). You won't be able to plot the solution without node-coords though.

(define-problem "ASYM-CVRP" 3 :demands '(0 1 2 3 2 1) :capacities 8 :dist-array dist-aray) Note that the above will create 6 nodes, so the dimensions of the dist-array must be 6x6. Also note that we provide a single number for capacities (instead of a list with length 3), which means that all vehicles will have a capacity of 8. Single numbers are allowed for :demands, :durations, :capacites and :speeds

Or to load a problem from a text-file (currently supports Solomon-format and TSPLIB cvrp format):

(defvar test-case-solomon (load-test-case-file "path-to-solomon-file-format.txt")) (defvar test-case-tsplib (load-test-case-file "path-to-tsplib-file-format.vrp"))

When the algo is finished running, it returns the Algo object, which contains :current-sol and :best-sol. Use iterate-more to keep searching:

(iterate-more <algo> int)

Output

An example output of Solomon's VRPTW 100-customers benchmark test-case, solved with Tabu Search.

alt Optimal solution

TODO

  • Extend VRP model to PDPTW
  • Run logs/statistics for test-result gathering (including batch runs)
  • User-interface (better macros)
  • Plotting can be improved (real-time output instead of .png files)
  • ...

License

Open-VRP is licensed under the terms of the Lisp Lesser GNU Public License, known as the LLGPL. The LLGPL consists of a preamble (see above URL) and the LGPL. Where these conflict, the preamble takes precedence. Open-VRP is referenced in the preamble as the "LIBRARY."

FUNCTION

Public

LOAD-TSPLIB-VRP-FILE (FILE)

Load a subset of the VRP in the TSPLIB. Do not support time windows. ################### NAME: xxxx ... DIMENSION: xxx ... EDGE_WEIGHT_FORMAT: FUNCTION ... EDGE_WEIGHT_TYPE: EXACT_2D CAPACITY: xxx ... NODE_COORD_SECTION .... DEPOT_SECTION 1 -1 EOF #################### EDGE_WEIGHT_FORMAT and EDGE_WEIGHT_TYPE are optional

RUN! (&OPTIONAL (TEST-SPEC *SUITE*))

Equivalent to (explain (run TEST-SPEC)).

Private

FLATTEN (TREE)

Traverses the tree in order, collecting non-null leaves into a list.

SHUFFLE (SEQUENCE &KEY (START 0) END)

Returns a random permutation of SEQUENCE bounded by START and END. Original sequece may be destructively modified, and share storage with the original one. Signals an error if SEQUENCE is not a proper sequence.

MACRO

Public

DEFINE-PROBLEM (NAME FLEET-SIZE &KEY NODE-COORDS-LIST DEMANDS CAPACITIES TIME-WINDOWS-LIST DURATIONS SPEEDS (TO-DEPOT T) PLOT-FILENAME LOG-FILENAME DIST-MATRIX LOG-MODE PLOTP)

Creates the appropriate <Problem> object from the inputs. Extra key attributes only accept lists that are of equal length to node-coords-list or fleet-size (depending on what attributes it sets). For demands, durations, capacities and speeds, will also accept a single value, which will set all attributes to this value. A(n asymmetric) dist-matrix may be passed, instead of node-coords, in which case plotting will be disabled. dist-matrix must be a list of lists or 2-dimensional array. With only the demands-list and capacities, creates a CVRP problem. With time-windows, creates a VRPTW problem. When durations and speeds are not provided, defaults to 0 and 1. When plot-filename is not given, it will plot in "plots/name.png". When log-filename is not given, it will log by default in "run-logs/name.txt".

Private

WITH-GENSYMS (NAMES &BODY FORMS)

Binds each variable named by a symbol in NAMES to a unique symbol around FORMS. Each of NAMES must either be either a symbol, or of the form: (symbol string-designator) Bare symbols appearing in NAMES are equivalent to: (symbol symbol) The string-designator is used as the argument to GENSYM when constructing the unique symbol the named variable will be bound to.

GENERIC-FUNCTION

Public

ITERATE-MORE (ALGO INT)

When an algo finished (i.e. iterations = 0) using iterate-more allows you to keep running it x more iterations. Also resets :best-iteration, which the stopping condition uses. Calls run-algo on the :current-sol of and with <algo>.

PLOT-SOLUTION (PROBLEM/ALGO &OPTIONAL OUTPUT-FILE)

Given a solution object (<problem>/<algo>), draw the solution in output file given in the drawer object's :filename slot (which is held in problem-drawer slot). When <algo> object as input, draw the best found solution by that algo object.

SOLVE-PROB (PROBLEM ALGO)

Solves the problem with the algo. Uses run-algo, but leaves the <problem> object untouched (<Algo> will suffer side-effects). Works with a clone (copy-object in lib/simple-utils.lisp). NON-destructive wrapper to the run-algo method.