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
• build using the toolkit of shared operators or the Iterator framework
• or 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).

It consists of a library and an Iterator framework to write your search algorithms. The library is contained in the lib folder. The Iterator framework and implemented algorithms are in the algo folder.

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(optional): 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.

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

Library

solver.lisp

• run-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.
• init-algo is a helper function to be used in run-algo to set algo slots after running the algo.
• solve-prob 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.
• solve-plot calls solve-prob and plot-solution
• multi-run 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 calls multi-run, but prints stats and returns only the best Algo object.

network.lisp

• node returns a Node given a Problem instance and an integer indicating the ID.
• distance is a lookup function that requires 2 node IDs and the pre-calculated dist-array (held in Problem)
• node-distance calculates the distance given two Node objects
• generate-dist-array returns an array of all the distances, given a list of coords (pairs of x and y)
• new-node 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

• vehicle returns a Vehicle given a Problem instance and an integer indicating the ID.
• route-indices returns a list of node IDs. Accepts Vehicle or Problem.
• vehicle-with-node returns Vehicle that has the node on its route. Expects Problem and integer (node ID).
• total-dist returns the total distance given a Vehicle/Problem object.
• new-vehicle 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

• get-busy-vehicles returns a list of Vehicles that leave their base, i.e. have Nodes to visit.
• empty-routep returns T if route only has base nodes.
• one-destinationp returns T if route only has one destination, excluding base nodes.
• insert-node expects a Vehicle instance, a Node instance and an index, before which the Node will be inserted.
• append-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 removes the node from route of vehicle at index
• remove-node-id 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 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 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 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 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 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 will only plot the nodes. Accepts a Problem object.

output.lisp

• print-routes will print the solution that is held in the Problem or the :best-sol of an Algo instance.
• print-multi-run-stats expects a list of algo-instances (as returned by multi-run macro) and prints some stats

read-solomon.lisp

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