Home

Open-VRP is a toolkit to model and solve VRP-like problems. 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. Tabu Search) 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).

Overview

Problem class

The Problem object defines the problem. It holds a network of Node objects, a fleet of Vehicle objects and a Drawer object for plotting. This class is inherited by CVRP and VRPTW, and should be inherited when you define your own problem class.

Important: An instance of Problem is used to represent solutions. We refer to a Problem object if the routes of the fleet are empty, whereas once we solve the Problem and set the fleet's routes, we refer to the instance as a solution.

• name: Name of the problem
• desc(optional): Description of the problem
• network: Holds a vector of Node objects
• fleet: Holds a list of Vehicle objects
• drawer: Holds a Drawer object.
• dist-array: A pre-calculated distance array, for quick distance lookup
• to-depot: Boolean that configures whether vehicles require to return to depot at the end.
• log-mode: Can be 0, 1 or 2. When set to 0, completely turns off logging. Log-mode 1 is default, which logs into a log-file. REPL output will only be the final best solution. When set to 2, all logging output goes to the REPL. (log-mode <Problem>/<Algo>) is a generic slot reader. Can be set with (set-log-mode <Problem> int)
• log-file: Path to log-file. By default set by define-problem macro to run-logs/name.txt

Node class

A Node class defines a node on the network and have a unique :id. A vector of Node objects is used to define the network, as held in the Problem's :network slot. We define a route as a list of Node objects, as held in the Vehicle's :route slot.

• id: A unique ID for each node, with 0 indicating the base node. Use this ID to compare nodes (not Node)
• xcor: X-coord
• ycor: Y-coord
• demand (optional): The demand of the node, for capacitated VRP
• start (optional): The earliest start time of serving node, for VRPTW
• end (optional): The latest start time of serving node
• duration (optional): Duration of serving node

Use (node <Problem> id) to get a Node object, given a Problem object and an integer (id).

Vehicle class

The Vehicle class defines the vehicle and have a unique :id. A list of Vehicles is used to define a fleet, as held in the Problem's :fleet slot.

• id: Unique ID for the vehicle
• route: Holds a list of Node objects to depict the route (solution) that the vehicle will travel
• capacity (optional): Maximum capacity of the vehicle (must be initialized for CVRP)
• speed (optional): Traveling speed of the vehicle (must be initialized for VRPTW, default 1)

Algo class

The Algo class defines the algorithm and holds the algorithm parameters, and determines which method to be dispatched to when calling run-algo. The Algo object is also a container that keeps track of the number of iterations left, the current solution, and the best solution/fitness found so far.

• name(optional): Name of the algo
• desc(optional): Description of the algo
• iterations: Number of iterations to go (used by the Iterator)
• current-sol: Current solution (A Problem instance)
• best-sol: Best solution found (A Problem instance)
• best-fitness: Fitness of the best solution found
• animatep: Boolean when set to T (default NIL) will plot every iteration to run-frames/Iteration x.png. Can be toggled with (toggle-animatep <algo>).

Drawer class

An instance of Drawer is held in an Problem instance's :drawer slot. The Drawer class holds data related to plotting (such as coords, pixels). The following shows only the relevant slots to the outside.

• filename: Path to the output png file. Will be automatically set by define-problem to plots/name.png
• legendp: Boolean slot (default T) to plot a legend when plot-solution is called.
• plotp: Boolean slot (default T) which enables plotting final solution when solve-prob is called.

Library

solver.lisp

High-level methods to start solving.

• (run-algo <Problem> <Algo>) is the main method to solve a Problem with an Algo. Will return the Algo object. When defining your own algorithms, this method must be implemented. This method is destructive and will alter the Problem object. Use solve-prob instead when solving.
• (solve-prob <Problem> <Algo>) wrapper for run-algo that leaves the Problem alone. Undestructive, but still alters the Algo object, as it sets the slots for :best-fitness, :best-sol and :current-sol.
• (multi-run int algo-call) is a macro that accepts an integer and an algo-call (which is usually a solve-prob call) and returns a list of Algo objects. Useful for multi-start heuristics that have a random element in the search, so that not every solution returned is the same.
• (multi-run-algo int algo-call) calls multi-run, but prints stats and returns only the best Algo object.
• (init-algo <Problem> <Algo>) is a helper setter function to be used in run-algo to set algo slots after running the algo. Destructive.
• (iterate <Algo>) runs the algo one iteration. Implementation of this method should use the algo's slot current-sol as current solution and destructively adjust it to a new solution. When algo's slot iterations is 0, then print the best solution found by this algo object. Returns the object when finished. After each iterate, will automatically check if a new best solution has been found and adjust the :best-sol and :best-fitness slots for you.
• (iterate-more <Algo> int) resumes the run with int number of extra iterations.

init-macros.lisp

Important macros that help you quickly define your problem. Usually you'll only need define-problem.

• (create-nodes (&key node-coords demands time-windows durations) Will return a vector of nodes that are numbered starting from 0 (which should be the base node, by convention over configuration). All attribute parameters are optional but must be of the same length.
• (create-vehicles (fleet-size base-node to-depot &key capacities speeds) Returns a list of vehicles, starting with ID 0. The starting location of their routes are all initialized at base-node. When to-depot is set to T, initialize their routes with 2 base nodes (departure and destination). For capacities and speeds, only accepts a list that is of equal lenght to fleet-size.

(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)

This is the most important macro of the Open-VRP library -- calls create-nodes and create-vehicles. It creates the appropriate 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 a 2-dimensional array.

With only the demands-list and capacities, creates a CVRP problem. With time-windows, it 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.

Note that name and fleet-size are mandatory parameters. Name will be used to derive the default plot-filename and log-filename. When fleet-size is unknown (e.g. in Issue #12), an arbitrarily large number may be chosen -- this will not affect the performance of Tabu Search, since more than one idle vehicle will not be considered. get-busy-vehicles is used for this purpose.

config-functions.lisp

Collection of callable configuration functions

• (toggle-plot <Problem>) toggles whether a call to solve-prob will result in plotting final solution
• (toggle-legend <Problem>/<Algo>) toggles the legend
• (toggle-animate <Algo>) toggles animation, which means plotting every iteration in run-frames/ folder
• (set-plot-file <Problem> path) overrides the plot output file location that was generated by default to plots/name.png
• (set-log-file <Problem> path) overrides the log output file location that was generated by default to run-logs/name.txt
• (set-log-mode <Problem> int) sets log-mode: 0 for no log, 1 for log to log-file, 2 for REPL log.
• (set-dist-array <Problem> dist-array) dist-array may be a 2-dimensional list or array -- used generally for setting an asymmetric distance matrix

network.lisp

Network related functions.

• (node <Problem> <Algo>) returns a Node given a Problem instance and an integer indicating the ID.
• (distance int int dist-array) is a lookup function that requires 2 node IDs and the pre-calculated dist-array (held in Problem)
• (node-distance <Node> <Node>) calculates the distance given two Node objects
• (generate-dist-array coords-list) returns an array of all the distances, given a list of coords (pairs of x and y)
• (new-node id xcor ycor &key demand start end duration) is a macro to create a Node object. Will set slots according to the inputs provided. Used by create-nodes to initialize the network for a problem.

fleet.lisp

Fleet related functions, which hold the solution, so also solution related functions including total-dist and route-indices.

• (vehicle <Problem> <Algo>) returns a Vehicle given a Problem instance and an integer indicating the ID.
• (route-indices <Vehicle>/<Problem>) returns a list of node IDs. Accepts Vehicle or Problem.
• (vehicle-with-node <Problem> int) returns Vehicle that has the node on its route. Expects Problem and integer (node ID).
• (total-dist <Vehicle>/<Problem>) returns the total distance given a Vehicle/Problem object.
• (new-vehicle id base-node to-depot &key capacity speed) is a macro to create a Vehicle object. Used by create-vehicles to initialize a fleet for a problem. Expects id, base-node and to-depot and optionally capacity and speed. Will initialize the vehicle's route to base-node (when to-depot is T, two base-nodes - one for return)

route.lisp

Route related functions. A route is a list of _Node_s, which is held in a Vehicle's :route slot.

• (get-busy-vehicles <Problem>) returns a list of Vehicles that leave their base, i.e. have Nodes to visit.
• (empty-routep <Vehicle>) returns T if route only has base nodes.
• (one-destinationp route) returns T if route only has one destination, excluding base nodes.
• (insert-node <Vehicle> <Node> int) expects a Vehicle instance, a Node instance and an index, before which the Node will be inserted.
• (append-node <Vehicle> <Node>) expects a Vehicle and Node, and will append the Node at the end of the Vehicle's route. When to-depot is set to T, all routes are initialized to have 2 base nodes. In this case, append-node will append the node before the vehicle returns to base.
• (remove-node-at <Vehicle> int) removes the node from route of vehicle at index
• (remove-node-id <Vehicle> int) removes the node with node-ID from the route of vehicle. Returns NIL if failed to find node-ID. Also accepts a Problem instance.
• (last-node <Vehicle>/route) returns the last Node in the Vehicle's route (before returning to base).

constraints.lisp

Constraints related functions. Note the distinction between checking feasibility of a solution and a move.

• (constraintsp <Problem>) is a generic method that checks the appropriate constraints. Accepts one argument, which is a Problem instance. For example, when the argument is of CVRP class, check if the solution complies with capacity constraints. If the argument inherits from VRPTW, check if the solution complies with time-windows. When the problem is of CVRPTW class (which inherits from both CVRP and VRPTW) checks all constraints.
• (in-capacityp <Vehicle>/<CVRP>) tests for capacity constraints. Accepts a Vehicle or CVRP as input. The latter will check for the whole fleet. When called with a Vehicle, will return capacity left as a second value.
• (in-timep <Vehicle>/<VRPTW>) tests for time-window constraints. Accepts a Vehicle or VRPTW as input. The latter will check for the whole fleet. When called with a Vehicle, will return time of finished last task as a second value.

fitness.lisp

Fitness function. It is possible to implement your own fitness function for your own problem.

• fitness accepts a Problem instance and returns fitness value and a second value (boolean) that tests the feasibility. By default returns the total distance. Used by Iterator, print-routes and plot-solution.

draw-solution.lisp

Functions related to plotting, uses vecto.

• (plot-solution <Problem>/<Algo>) can accept a Problem or Algo instance. In the latter case, will plot the Problem instance held in the :best-sol slot of Algo. Uses the Drawer object held in the Problem instance for the canvas configuration, the default path to output file and the boolean :legend to draw a legend (or not).
• (plot-nodes <Problem>) will only plot the nodes. Accepts a Problem object.

output.lisp

Print output and logging related functions.

• (print-routes <Problem>/<Algo> &optional stream) will print the solution that is held in the Problem or the :best-sol of an Algo instance.
• (print-multi-run-stats list) expects a list of algo-instances (as returned by multi-run macro) and prints some stats (mean, stdv, min, max, total run-time).
• (print-vrp-object object &optional (stream t)) prints object's slots and values (while ignoring :network, :dist-array and :fleet slots of Problem object (due to its size))
• (with-log-or-file (stream <Problem> &optional appendp) &body body) macro on top of with-open-file, where we use the filepath stored in the :log-file slot of a problem object. Will check log-mode to decide what to do. Optional parameter appendp can be set to NIL in order to :supersede if file exists. By default appends.
• (log-to-replp <Problem>/<Algo>) tests if the log-mode is set to 2. Used to print minimum output to REPL if no output to REPL is provided when log-mode is other than 2.

batch-run.lisp

Tools for batch-run -- useful for thorough testing of algo on a directory of cases

• (defmacro batch-run ((x dir-path) output-file num-times &body algo-call) Given a directory path, will call algo-call on each file that is loaded using liad-test-case-file and bound to x. Output-file is a mandatory filepath to which the results will be written (in a table). Algo-call must return an object (e.g. multi-run-algo or solve-prob). Num-times is the number of times the algo-call will run on each test-case, which will be used for stats. Returns a matrix of all objects that contain the solutions.

(batch-run (test-case \"test-cases/Solomon-25/\")
	      \"run-logs/Solomon-25-batch.txt\" 20
       (solve-prob test-case (make-instance 'tabu-search :iterations 300)))

read-test-case.lisp

A generic test-case loader from file.

• (load-test-case-file filepath) takes an input file and will attempt to recognize the format and dispatch to appropriate reader. Currently supports Solomon and TSPLIB formats.

read-solomon.lisp

Create a problem object by reading a Solomon style txt file.

• (load-solomon-vrp-file file.txt) reads an input txt file, and returns a Problem that encapsulates the test case.

read-cvrp.lisp

Create a problem object by reading a TSPLIB style txt file.

• (load-tsplib-vrp-file file.vrp) reads an input txt file, and returns a Problem that encapsulates the test case.