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.
• (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.

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
• (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.

read-solomon.lisp

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

• (load-testcase-solomon 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.txt) reads an input txt file, and returns a Problem that encapsulates the test case.