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:

• written from scratch
• tweaked from existing implementations - (currently only Tabu Search implemented)

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.

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."