open-vrp

API Reference

open-vrp

open-vrp

No packages.

open-vrp-lib

open-vrp-library

OPEN-VRP.CLASSES

  • Struct NODE
    ID
    XCOR
    YCOR
    DEMAND
    START
    END
    DURATION
  • Function NODE-ID (instance)
  • Function NODE-XCOR (instance)
  • Function NODE-YCOR (instance)
  • Function NODE-DEMAND (instance)
  • Function NODE-START (instance)
  • Function NODE-END (instance)
  • Function NODE-DURATION (instance)
  • Function MAKE-NODE (&key ((id id) 0) ((xcor xcor) 0) ((ycor ycor) 0) ((demand demand) 0) ((start start) 0) ((end end) 0) ((duration duration) 0))
  • Struct VEHICLE
    ID
    ROUTE
    CAPACITY
    SPEED
  • Function VEHICLE-ID (instance)
  • Function VEHICLE-ROUTE (instance)
  • Function (setf VEHICLE-ROUTE) (value instance)
  • Function VEHICLE-CAPACITY (instance)
  • Function VEHICLE-SPEED (instance)
  • Function MAKE-VEHICLE (&key ((id id) 0) ((route route) nil) ((capacity capacity) 0) ((speed speed) 1))
  • Class PROBLEM
    NAME   Reader: PROBLEM-NAME
    DESC   Reader: PROBLEM-DESC
    NETWORK   Reader: PROBLEM-NETWORK
    DIST-ARRAY   Accessor: PROBLEM-DIST-ARRAY
    FLEET   Reader: PROBLEM-FLEET
    TO-DEPOT   Accessor: PROBLEM-TO-DEPOT
    DRAWER   Accessor: PROBLEM-DRAWER
    LOG-FILE   Accessor: PROBLEM-LOG-FILE
    LOG-MODE   Accessor: PROBLEM-LOG-MODE
  • Class CVRP  (PROBLEM)
    NAME
    DESC
  • Class VRPTW  (PROBLEM)
    NAME
    DESC
  • Class CVRPTW  (CVRP, VRPTW)
    NAME
    DESC
  • Struct DRAWER
    MIN-COORD
    MAX-COORD
    X-POS
    Y-POS
    MAX-PIX
    LEGENDP
    LEGEND-X
    LEGEND-Y
    FILENAME
    PLOTP
  • Function DRAWER-MIN-COORD (instance)
  • Function (setf DRAWER-MIN-COORD) (value instance)
  • Function DRAWER-MAX-COORD (instance)
  • Function (setf DRAWER-MAX-COORD) (value instance)
  • Function DRAWER-X-POS (instance)
  • Function (setf DRAWER-X-POS) (value instance)
  • Function DRAWER-Y-POS (instance)
  • Function (setf DRAWER-Y-POS) (value instance)
  • Function DRAWER-MAX-PIX (instance)
  • Function (setf DRAWER-MAX-PIX) (value instance)
  • Function DRAWER-LEGENDP (instance)
  • Function (setf DRAWER-LEGENDP) (value instance)
  • Function DRAWER-LEGEND-X (instance)
  • Function (setf DRAWER-LEGEND-X) (value instance)
  • Function DRAWER-LEGEND-Y (instance)
  • Function (setf DRAWER-LEGEND-Y) (value instance)
  • Function DRAWER-FILENAME (instance)
  • Function (setf DRAWER-FILENAME) (value instance)
  • Function DRAWER-PLOTP (instance)
  • Function (setf DRAWER-PLOTP) (value instance)
  • Function MAKE-DRAWER (&key ((min-coord min-coord) nil) ((max-coord max-coord) nil) ((x-pos x-pos) 0) ((y-pos y-pos) 0) ((max-pix max-pix) 1000) ((legendp legendp) t) ((legend-x legend-x) 100) ((legend-y legend-y) 900) ((filename filename) nil) ((plotp plotp) nil))
  • Class ALGO
    NAME   Reader: ALGO-NAME
    DESC   Reader: ALGO-DESC
    BEST-SOL   Accessor: ALGO-BEST-SOL
    BEST-FITNESS   Accessor: ALGO-BEST-FITNESS
    BEST-ITERATION   Accessor: ALGO-BEST-ITERATION
    CURRENT-SOL   Accessor: ALGO-CURRENT-SOL
    ITERATIONS   Accessor: ALGO-ITERATIONS
    ANIMATEP   Accessor: ALGO-ANIMATEP
  • Method NODE ((prob problem) id)
  • Method VEHICLE ((p problem) id)

OPEN-VRP.UTIL

  • Function SINGLE (lst)
  • Function MAP0-N (fn n)
    maps from 0 to n
  • Function MAP1-N (fn n)
    maps from 1 to n
  • Macro MAC (expr)
  • Macro WHILE (test &body body)
  • Macro AIF (test-form then-form &optional else-form)
  • Macro AWHILE (expr &body body)
  • Function SUM (list)
    A quick list summer, 4 times as fast as (reduce #'+ list)
  • Function MAX-CAR (list)
    Provided a list, return the maximum value considering the cars
  • Function MAX-CDR (list)
    Provided a list, return the maximum value considering the cdrs
  • Function COPY-OBJECT (object)
    A deep-cloner for CLOS.
  • Function GET-MIN (list &key key)
    Gets the minimum value from a list, while ignoring the NIL values.
  • Function GET-MAX (list &key key)
    Gets the maximum value from a list, while ignoring the NIL values.
  • Function GET-MIN-INDEX (list &key key)
    Returns index of the smallest value on list, while ignoring NIL. Returns index and its value (closest node and value).
  • Function GET-MAX-INDEX (list &key key)
    Returns index of the largest value on list, while ignoring NIL. Returns index and its value (closest node and value).
  • Function SORT-IGNORE-NIL (list predicate &key key)
    Sorts the sequence with #'< or #'> while passing all NIL values towards the end of result.
  • Function INSERT-BEFORE (object index list)
    Insert object before index of list. 0 implies inserting in front, length of list implies appending at the end. Throws index out of bounds when index is larger.
  • Function INSERT-AT-END (object list)
    Appends the object at the end of the list
  • Function REMOVE-INDEX (index list)
    Given a list, remove the object on index. Does not accept index out of bounds. Returns the new list AND the object that was removed.
  • Macro WITH-TABU-INDICES (tabu-indices fn arg-list)
  • Function ENUMERATE-INTERVAL (n)
    Returns a list from 1 to n.
  • Function RANDOM-LIST-PERMUTATION (length)
    Randomly creates a permutation from 1 to length.
  • Function DISTANCE (i j dist-array)
    Read from the distance-table with two indices.
  • Function NODE-DISTANCE (n1 n2)
    Given two node objects, calculate and return their distance (Cartesian).
  • Function GET-ARRAY-ROW (array row-index)
    Given a 2-dimenstional array and a row-index, return the row as a list
  • Function GENERATE-DIST-ARRAY (coord-list)
    Given a list of coord pairs, generate an array of distances.
  • Macro NEW-NODE (id xcor ycor &key demand start end duration)
  • Generic-Function ROUTE-INDICES (obj)
    When input is a <vehicle>, returns its route as a list of node IDs. When input is <fleet>/<problem>, list all routes.
  • Method ROUTE-INDICES (vehicle)
    Input is not a <vehicle>/<problem> object!
  • Method ROUTE-INDICES (vehicle)
    Input is not a <vehicle>/<problem> object!
  • Method ROUTE-INDICES (vehicle)
    Input is not a <vehicle>/<problem> object!
  • Method ROUTE-INDICES ((v vehicle))
  • Method ROUTE-INDICES ((p problem))
  • Function NODE-ON-ROUTEP (node-id vehicle)
    Returns NIL of <vehicle> does not have the node on its route.
  • Function VEHICLE-WITH-NODE-ID (prob node-id)
    Given a node-ID, return the vehicle-ID that has the node in its route. The function for the input of the base-node 0 is undefined. Returns NIL if node-ID cannot be found.
  • Generic-Function TOTAL-DIST (veh/prob dist-array)
    Returns total distance of the route(s) given a vehicle or a fleet.
  • Method TOTAL-DIST (veh/prob dist-array)
    Expects <problem> as input!
  • Method TOTAL-DIST (veh/prob dist-array)
    Expects <problem> as input!
  • Method TOTAL-DIST (veh/prob dist-array)
    Expects <problem> as input!
  • Method TOTAL-DIST ((v vehicle) dist-array)
  • Method TOTAL-DIST ((p problem) dist-array)
  • Macro NEW-VEHICLE (id base-node to-depot &key capacity speed)
  • Generic-Function FITNESS (problem)
    The generic fitness function. To be defined for each class of <problem> specifically. This function allows for custom fitness-functions for your own defined <problem> classess. The default fitness function is total distance.
  • Method FITNESS (problem)
    Parameter is not a <problem> object!
  • Method FITNESS (problem)
    Parameter is not a <problem> object!
  • Method FITNESS (problem)
    Parameter is not a <problem> object!
  • Method FITNESS ((prob problem))
  • Generic-Function PRINT-ROUTES (prob/algo &optional stream)
    Prints solution given a <problem>/<algo> object. Also prints the total distance when the input is a <problem>/<algo> object.
  • Method PRINT-ROUTES ((prob problem) &optional (stream t))
  • Method PRINT-ROUTES ((a algo) &optional (stream t))
  • Function PRINT-MULTI-RUN-STATS (algo-objects &optional (str t))
    Given a list of algo-objects returned by multi-run, print run-stats.
  • Function PRINT-FINAL-RESULTS (prob algo &optional (stream t))
    Prints final results of run, helper function to :after methods of run-algo and solve-prob.
  • Function PRINT-VRP-OBJECT (object &optional (stream t))
    Given object, will print it's object's slots and values
  • Function PRINT-TIMESTAMP (&optional (stream t))
    Prints timestamp to stream, source from cl-cookbook.
  • Macro WITH-LOG-OR-PRINT ((stream prob time &optional (appendp t)) &body body)
    A wrapper on top of with-open-file, where we use the filepath stored in the :log-file slot of a problem object. When :log-mode is 0, return nil. If 1, use the file stream; if 2, use the T stream. Optional parameter appendp can be set to NIL in order to :supersede if file exists. By default appends. Returns T if logging is succesful. Requires universal-time, to append to log-file.
  • Generic-Function LOG-TO-REPLP (prob/algo)
    Returns T if :log-mode is set to 2, which is REPL.
  • Method LOG-TO-REPLP ((p problem))
  • Method LOG-TO-REPLP ((a algo))
  • Function EMPTY-ROUTEP (route)
    Given a route, return T if the route only has base-nodes.
  • Function GET-BUSY-VEHICLES (problem)
    Returns a list of <Vehicles> that are not empty, given a <Problem> object.
  • Function ONE-DESTINATIONP (route)
    Return T if there is only one destination on route, excluding base nodes.
  • Function INSERT-NODE (veh node index)
    Adds the <Node> object before the index of the route of <vehicle>. An index of 0 implies inserting in front, length of list implies at the end.
  • Function APPEND-NODE (veh node)
    Appends <Node> to the end of the route of <vehicle>. Wrapper of insert-node. If the route includes returning to-depot, then append before the last return to depot.
  • Function REMOVE-NODE-AT (veh index)
    Removes the <node> from the route of <vehicle> at index
  • Generic-Function REMOVE-NODE-ID (veh/prob node-id)
    Removes the <node> with node-ID from the route of <vehicle>. Returns NIL if failed to find node-ID.
  • Method REMOVE-NODE-ID (vehicle node-id)
    Expects <vehicle>/<problem> and int as inputs!
  • Method REMOVE-NODE-ID (vehicle node-id)
    Expects <vehicle>/<problem> and int as inputs!
  • Method REMOVE-NODE-ID (vehicle node-id)
    Expects <vehicle>/<problem> and int as inputs!
  • Method REMOVE-NODE-ID ((v vehicle) node-id)
  • Method REMOVE-NODE-ID ((prob problem) node-id)
  • Generic-Function LAST-NODE (vehicle)
    Returns the last <node> in its route. Depicts the current location (before returning to base).
  • Method LAST-NODE (vehicle)
    Expects <vehicle>
  • Method LAST-NODE (vehicle)
    Expects <vehicle>
  • Method LAST-NODE (vehicle)
    Expects <vehicle>
  • Method LAST-NODE (route)
  • Method LAST-NODE ((v vehicle))
  • Generic-Function 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.
  • Method PLOT-SOLUTION ((sol problem) &optional output-file)
  • Method PLOT-SOLUTION ((a algo) &optional output-file)
  • Generic-Function PLOT-NODES (problem)
    Draws only the nodes in output file.
  • Method PLOT-NODES (problem)
    Expects <Problem> as input!
  • Method PLOT-NODES (problem)
    Expects <Problem> as input!
  • Method PLOT-NODES (problem)
    Expects <Problem> as input!
  • Method PLOT-NODES ((prob problem))
  • Function INIT-ALGO (sol algo)
    Given a solution, sets the :current-sol, :best-fitness and :best-sol slots of the <algo> object. Returns <algo>.
  • Generic-Function RUN-ALGO (problem algo)
    Runs the algo on the problem. Destructive - will have side-effects on the <problem> and <algo> objects. Use solve-prob to prevent <problem> object being touched. Will return the <Algo> object, which will contain the solution (in the form of a copy of the <problem> object) in the :best-sol slot. When defining your own algorithms, make sure to implement a run-algo method for your algo, which sets the <algo> slots appropriately, and returns the <algo> object. For algorithms that just build a solution (like greedy-best-insertion or greedy-append), you can use init-algo to set :current-sol, :best-sol, :best-fitness simultaneously. For search algorithms -- such as local search, population based algorithms -- may make use of the iterate method to automatically set the slots after each iteration.
  • Method RUN-ALGO (problem algo)
    run-algo: Either problem or algo is not defined/correct
  • Method RUN-ALGO (problem algo)
    run-algo: Either problem or algo is not defined/correct
  • Method RUN-ALGO (problem algo)
    run-algo: Either problem or algo is not defined/correct
  • Method RUN-ALGO ((p problem) (a algo))
  • Variable *ALGO-BACKUP*
    open-vrp.util::a
  • Variable *ALGO-BACKUP*
    open-vrp.util::a
  • Method RUN-ALGO ((p problem) (a algo))
  • Variable *START-TIME*
    nil
  • Generic-Function 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.
  • Method SOLVE-PROB (problem algo)
    solve-prob: Either problem or algo is not defined/correct
  • Method SOLVE-PROB (problem algo)
    solve-prob: Either problem or algo is not defined/correct
  • Method SOLVE-PROB (problem algo)
    solve-prob: Either problem or algo is not defined/correct
  • Method SOLVE-PROB ((problem problem) (algo algo))
  • Method SOLVE-PROB ((p problem) (a algo))
  • Method SOLVE-PROB ((p problem) (a algo))
  • Variable *MULTI-RUN-START-TIME*
    nil
  • Macro MULTI-RUN (times &body algo-call)
    Run algo x times and collect all resulting solution objects in a list.
  • Function GET-BEST-SOLUTION-FROM-MULTI-RUN (solutions)
    Given a list of solutions (from multi-run), return the best solution.
  • Macro MULTI-RUN-ALGO (times &body algo-call)
    Run algo x times, print multi-run-stats and return the best result.
  • Generic-Function 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 <algo> object. 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. When :animatep is set to T, will plot current solution in run-frames/
  • Method ITERATE (algo)
    iterate: This algo is not defined.
  • Method ITERATE (algo)
    iterate: This algo is not defined.
  • Method ITERATE (algo)
    iterate: This algo is not defined.
  • Method ITERATE ((a algo))
  • Method ITERATE ((a algo))
  • Generic-Function 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>.
  • Method ITERATE-MORE (algo int)
    iterate-more: expects <Algo> and int as inputs
  • Method ITERATE-MORE (algo int)
    iterate-more: expects <Algo> and int as inputs
  • Method ITERATE-MORE (algo int)
    iterate-more: expects <Algo> and int as inputs
  • Method ITERATE-MORE ((a algo) int)
  • Method ITERATE-MORE ((a algo) int)
  • Generic-Function CONSTRAINTSP (prob)
    Tests weather the solution in the <problem> is complying with the constraints. If the problem is a CVRP, check for capacity. If it is a VRPTW, check for time-windows. For CVRPTW, that inherits from both classes, check both constraints.
  • Method CONSTRAINTSP ((sol cvrp))
  • Method CONSTRAINTSP ((sol vrptw))
  • Macro CONSTRAINTS-CHECK (arglist init-forms next-forms testform &optional endtest)
  • Generic-Function IN-CAPACITYP (veh/cvrp)
    Tests weather the route on <vehicle> is complying with the capacity constraint. Returns T and the remaining capacity if it does. When <CVRP> is provided, test all vehicles.
  • Method IN-CAPACITYP (obj)
    Expects a <Vehicle>/<CVRP> object!
  • Method IN-CAPACITYP (obj)
    Expects a <Vehicle>/<CVRP> object!
  • Method IN-CAPACITYP (obj)
    Expects a <Vehicle>/<CVRP> object!
  • Method IN-CAPACITYP ((v vehicle))
  • Method IN-CAPACITYP ((pr cvrp))
  • Function TRAVEL-TIME (n1 n2 &key dist-array (speed 1))
    Given two <nodes> and optional speed, return the travel-time. When dist-array is not provided, calculate distance directly using coords.
  • Function TIME-AFTER-SERVING-NODE (node arrival-time)
    Given a node to serve and the current time, return the new time (if on-time to begin with). When arrival-time is too early, wait till earliest start time.
  • Function VEH-IN-TIMEP (v &optional dist-array)
    Tests weather the route on <Vehicle> is complying with the time-window constraints. Returns T and the time of finishing its last task.
  • Method IN-TIMEP ((pr vrptw))
  • Condition LIST-OF-NILS  (ERROR)
  • Condition SAME-ORIGIN-DESTINATION  (ERROR)
  • Macro CREATE-NODES (&key node-coords demands time-windows durations dist-matrix)
    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. Note that dist-matrix parameter is not used, but only to create nodes when no other parameter is passed (called from define-problem).
  • Macro 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.
  • Macro 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".
  • Function LOAD-SOLOMON-VRP-FILE (file)
    Load testcase from file, which should be Solomon style.
  • Function 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
  • Macro TOGGLE (place &environment env)
  • Generic-Function TOGGLE-PLOT (problem/algo)
    Toggles plotting on/off of best solution. Config boolean is held by <Drawer> object's plotp slot.
  • Method TOGGLE-PLOT ((pr problem))
  • Method TOGGLE-PLOT ((a algo))
  • Function TOGGLE-ANIMATE (algo)
    Toggles animation, which means plotting every iteration in run-frames/ folder
  • Generic-Function TOGGLE-LEGEND (problem/algo)
    Toggles legend drawing. When <Algo> is provided, toggles :best-sol
  • Method TOGGLE-LEGEND ((pr problem))
  • Method TOGGLE-LEGEND ((a algo))
  • Function SET-PLOT-FILE (prob path)
    Sets the plot output file location.
  • Function SET-LOG-MODE (prob x)
    Sets log-mode: 0 for no log, 1 for log to log-file, 2 for REPL log.
  • Function SET-LOG-FILE (prob path)
    Sets the output location of the log-file.
  • Function SET-DIST-ARRAY (problem dist-array)
    Given a <problem> and a 2-dimensional list or array in dist-array, set it in <problem>
  • Function LOAD-TEST-CASE-FILE (filepath)
    Given a file, will recognize the format based on some cues and dispatch to appropriate reader function to parse the file. File with .vrp extension will be read as TSPLIB.
  • Macro BATCH-RUN ((x dir-path &key (plotp nil) (log-mode 1)) output-file num-times &body algo-call)
    Given a directory, will call algo-call on each file that is loaded using the loader-fn and bound to x. Output-file is a mandatory filepath to which the results will be written. Algo-call must return an <Algo> 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. Will return a list of list of algo objects holding the solutions. Example: (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))).

Also exports

  • OPEN-VRP.CLASSES:VEHICLE
  • OPEN-VRP.CLASSES:NODE

OPEN-VRP.ALGO

No exported symbols.

OPEN-VRP.TEST

No exported symbols.

Also exports

  • IT.BESE.FIVEAM:RUN!

OPEN-VRP

No exported symbols.

Also exports

  • OPEN-VRP.UTIL:SOLVE-PROB
  • OPEN-VRP.TEST:SOLOMON100
  • OPEN-VRP.ALGO:GREEDY-NN
  • OPEN-VRP.ALGO:GREEDY-APPEND
  • OPEN-VRP.UTIL:LOAD-TSPLIB-VRP-FILE
  • OPEN-VRP.TEST:TEST-TSP
  • OPEN-VRP.UTIL:PLOT-SOLUTION
  • OPEN-VRP.TEST:SOLOMON25
  • OPEN-VRP.UTIL:PRINT-ROUTES
  • OPEN-VRP.TEST:TEST-VRP
  • OPEN-VRP.UTIL:DEFINE-PROBLEM
  • OPEN-VRP.ALGO:TABU-SEARCH
  • IT.BESE.FIVEAM:RUN!
  • OPEN-VRP.TEST:CHRISTOFIDES-2
  • OPEN-VRP.ALGO:GREEDY-BEST-INSERTION
  • OPEN-VRP.TEST:CHRISTOFIDES-1
  • OPEN-VRP.UTIL:ITERATE-MORE