Common Lisp Package: OPEN-VRP.UTIL

README:

FUNCTION

Public

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.

COPY-OBJECT (OBJECT)

A deep-cloner for CLOS.

DISTANCE (I J DIST-ARRAY)

Read from the distance-table with two indices.

EMPTY-ROUTEP (ROUTE)

Given a route, return T if the route only has base-nodes.

ENUMERATE-INTERVAL (N)

Returns a list from 1 to n.

GENERATE-DIST-ARRAY (COORD-LIST)

Given a list of coord pairs, generate an array of distances.

GET-ARRAY-ROW (ARRAY ROW-INDEX)

Given a 2-dimenstional array and a row-index, return the row as a list

GET-BEST-SOLUTION-FROM-MULTI-RUN (SOLUTIONS)

Given a list of solutions (from multi-run), return the best solution.

GET-BUSY-VEHICLES (PROBLEM)

Returns a list of <Vehicles> that are not empty, given a <Problem> object.

GET-MAX (LIST &KEY KEY)

Gets the maximum value from a list, while ignoring the NIL values.

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

GET-MIN (LIST &KEY KEY)

Gets the minimum value from a list, while ignoring the NIL values.

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

INIT-ALGO (SOL ALGO)

Given a solution, sets the :current-sol, :best-fitness and :best-sol slots of the <algo> object. Returns <algo>.

INSERT-AT-END (OBJECT LIST)

Appends the object at the end of the list

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.

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.

LOAD-SOLOMON-VRP-FILE (FILE)

Load testcase from file, which should be Solomon style.

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.

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

MAP0-N (FN N)

maps from 0 to n

MAP1-N (FN N)

maps from 1 to n

MAX-CAR (LIST)

Provided a list, return the maximum value considering the cars

MAX-CDR (LIST)

Provided a list, return the maximum value considering the cdrs

NODE-DISTANCE (N1 N2)

Given two node objects, calculate and return their distance (Cartesian).

NODE-ON-ROUTEP (NODE-ID VEHICLE)

Returns NIL of <vehicle> does not have the node on its route.

ONE-DESTINATIONP (ROUTE)

Return T if there is only one destination on route, excluding base nodes.

RANDOM-LIST-PERMUTATION (LENGTH)

Randomly creates a permutation from 1 to length.

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.

REMOVE-NODE-AT (VEH INDEX)

Removes the <node> from the route of <vehicle> at index

SET-DIST-ARRAY (PROBLEM DIST-ARRAY)

Given a <problem> and a 2-dimensional list or array in dist-array, set it in <problem>

SET-LOG-FILE (PROB PATH)

Sets the output location of the log-file.

SET-LOG-MODE (PROB X)

Sets log-mode: 0 for no log, 1 for log to log-file, 2 for REPL log.

SET-PLOT-FILE (PROB PATH)

Sets the plot output file location.

SORT-IGNORE-NIL (LIST PREDICATE &KEY KEY)

Sorts the sequence with #'< or #'> while passing all NIL values towards the end of result.

SUM (LIST)

A quick list summer, 4 times as fast as (reduce #'+ list)

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.

TOGGLE-ANIMATE (ALGO)

Toggles animation, which means plotting every iteration in run-frames/ folder

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.

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.

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.

Undocumented

SINGLE (LST)

Private

2D-ARRAY-TO-LIST (ARRAY)

Given a 2-dimensional array, return a list of lists.

2D-LIST-TO-ARRAY (MATRIX)

Given a list of lists, return a 2-dimensional array.

APPEND-RUN-RESULT (FILEPATH RESULTS)

Given the output filepath (with table headers initialized) and a list of algo-objects (as returned by multi-run), append one line that summarizes the run (by calling get-multi-run-stats).

ARROW-TO (DRAWER PIX-X PIX-Y SIZE SKEW)

Draws an arrow as in line-to, but creates an arrow in the middle of size. Use with canvas!

COORD->PIX (DRAWER X)

Given a drawer and a coord, calculate the associated x/y pixel. Includes 1 coord as border.

COUPLE-LISTS (LIST1 LIST2)

Given a list of x and y-coords, return a list of pairs usable. Used for node-coords or time-windows.

DISTANCE-COORD-PAIR (N1 N2)

Calculates distance given two coord pairs. Returns NIL if both coords are the same.

DISTANCE-COORDS (X1 Y1 X2 Y2)

Calculates pythagoras distance

DRAW-NODES (PROB)

Given the <Problem> object, plot the nodes only. Usage only with-canvas!

FLATTEN (TREE)

Traverses the tree in order, collecting non-null leaves into a list.

GET-COLOR

Returns next color. Deterministically random.

GET-FROM-LIST (LIST PRED &KEY KEY)

Gets from list the value (max or min) while ignoring NIL's. Returns NIL if the whole list is nil. Use get-min or get-max!

GET-INDEX-OF (LIST FN &KEY KEY)

Helper function of the below. Use get-min-index or get-max-index!

GET-MULTI-RUN-STATS (ALGO-OBJECTS)

Given a list of algo-objects, as returned by multi-run, return the stats with (values min max avg std runs time time/run)

INSERT-TIME-STAMP-IN-PATH (PATH TIME)

Given path, return the string of the path with the timestamp inserted before the .xxx

MARK-NILL (LIST INDICES)

Marks the indices on list with NIL. DESTRUCTIVE.

MEAN (SAMPLE)

Returns the mean of SAMPLE. SAMPLE must be a sequence of numbers.

SAME-LENGTHP (&REST LISTS)

Returns NIL if lists are not of equal length. Returns their length if all are equal. Accepts NIL arguments or single numbers, which will be ignored. Also accepts 2-dimensional arrays.

SHUFFLE (SEQUENCE &KEY (START 0) END)

Returns a random permutation of SEQUENCE bounded by START and END. Original sequece may be destructively modified, and share storage with the original one. Signals an error if SEQUENCE is not a proper sequence.

STANDARD-DEVIATION (SAMPLE &KEY (BIASED T))

Standard deviation of SAMPLE. Returns the biased standard deviation if BIASED is true (the default), and the square root of the unbiased estimator for variance if BIASED is false (which is not the same as the unbiased estimator for standard deviation). SAMPLE must be a sequence of numbers.

STORE-PIX (DRAWER PIX-X PIX-Y)

Store the position of the path (helper function for arrow calculation).

UNIVERSAL-TIME-TO-STRING (&OPTIONAL (TIME (GET-UNIVERSAL-TIME)))

Returns yymmdd-hhmmss in a string. Used for timestamped log-files.

VRP-OBJECT (OBJECT)

Tests if the object is an instance of a VRP object that needs deep copy. (problem, fleet, vehicle)

WALK-DIRECTORY (DIRNAME FN &KEY DIRECTORIES (IF-DOES-NOT-EXIST ERROR) (TEST (CONSTANTLY T)) (FOLLOW-SYMLINKS T))

Recursively applies the function FN to all files within the directory named by the non-wild pathname designator DIRNAME and all of its sub-directories. FN will only be applied to files for which the function TEST returns a true value. If DIRECTORIES is not NIL, FN and TEST are applied to directories as well. If DIRECTORIES is :DEPTH-FIRST, FN will be applied to the directory's contents first. If DIRECTORIES is :BREADTH-FIRST and TEST returns NIL, the directory's content will be skipped. IF-DOES-NOT-EXIST must be one of :ERROR or :IGNORE where :ERROR means that an error will be signaled if the directory DIRNAME does not exist. If FOLLOW-SYMLINKS is T, then your callback will receive truenames. Otherwise you should get the actual directory contents, which might include symlinks. This might not be supported on all platforms. See LIST-DIRECTORY.

Undocumented

%READ-STRING (STREAM FN)

DRAW-LEGEND-ITEM (DRAWER VEH-OBJ R G B)

GET-MAX-COORD (NODE-COORDS)

GET-MIN-COORD (NODE-COORDS)

READ-STRING-WHILE-MEMBER (STREAM LST)

READ-STRING-WHILE-NOT-MEMBER (STREAM LST)

MACRO

Public

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

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

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)

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

MULTI-RUN (TIMES &BODY ALGO-CALL)

Run algo x times and collect all resulting solution objects in a list.

MULTI-RUN-ALGO (TIMES &BODY ALGO-CALL)

Run algo x times, print multi-run-stats and return the best result.

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.

Undocumented

AIF (TEST-FORM THEN-FORM &OPTIONAL ELSE-FORM)

AWHILE (EXPR &BODY BODY)

CONSTRAINTS-CHECK (ARGLIST INIT-FORMS NEXT-FORMS TESTFORM &OPTIONAL ENDTEST)

MAC (EXPR)

NEW-NODE (ID XCOR YCOR &KEY DEMAND START END DURATION)

NEW-VEHICLE (ID BASE-NODE TO-DEPOT &KEY CAPACITY SPEED)

TOGGLE (PLACE &ENVIRONMENT ENV)

WHILE (TEST &BODY BODY)

WITH-TABU-INDICES (TABU-INDICES FN ARG-LIST)

Private

CHANGE-ROUTE (VEHICLE &BODY BODY)

Expands into binding the vehicles route to r and setting it to result of body.

WITH-GENSYMS (NAMES &BODY FORMS)

Binds each variable named by a symbol in NAMES to a unique symbol around FORMS. Each of NAMES must either be either a symbol, or of the form: (symbol string-designator) Bare symbols appearing in NAMES are equivalent to: (symbol symbol) The string-designator is used as the argument to GENSYM when constructing the unique symbol the named variable will be bound to.

Undocumented

USE-NODE (DRAWER NODE &BODY BODY)

GENERIC-FUNCTION

Public

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.

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.

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.

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/

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

LAST-NODE (VEHICLE)

Returns the last <node> in its route. Depicts the current location (before returning to base).

LOG-TO-REPLP (PROB/ALGO)

Returns T if :log-mode is set to 2, which is REPL.

PLOT-NODES (PROBLEM)

Draws only the nodes in output file.

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.

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.

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.

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.

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.

TOGGLE-LEGEND (PROBLEM/ALGO)

Toggles legend drawing. When <Algo> is provided, toggles :best-sol

TOGGLE-PLOT (PROBLEM/ALGO)

Toggles plotting on/off of best solution. Config boolean is held by <Drawer> object's plotp slot.

TOTAL-DIST (VEH/PROB DIST-ARRAY)

Returns total distance of the route(s) given a vehicle or a fleet.

Undocumented

IN-TIMEP (PR)

NODE (PROB ID)

VEHICLE (P ID)

Private

Undocumented

SETFCLASS-SLOTS (NEW-VALUE SLOT-CLASS)

FROM (CONDITION)

FUNC (CONDITION)

INDEX (CONDITION)

KEY (CONDITION)

LISTS (CONDITION)

LS (CONDITION)

PRED (CONDITION)

PROB (CONDITION)

SOL (CONDITION)

TO (CONDITION)

VEH (CONDITION)

SLOT-ACCESSOR

Private

Undocumented

CLASS-SLOTS (CLASS)

SLOT-DEFINITION-NAME (SLOT-DEFINITION)

SETFSLOT-DEFINITION-NAME (NEW-VALUE SLOT-DEFINITION)

VARIABLE

Public

Undocumented

*MULTI-RUN-START-TIME*

*START-TIME*

Private

Undocumented

*B*

*FINISH-TIME*

*G*

*MULTI-RUN-FINISH-TIME*

*R*

CLASS

Public

Undocumented

NODE (PROB ID)

VEHICLE (P ID)

CONDITION

Public

Undocumented

LIST-OF-NILS

SAME-ORIGIN-DESTINATION

Private

Undocumented

EMPTY-NETWORK

FILE-NOT-RECOGNIZED

INDEX-OUT-OF-BOUNDS

INFEASIBLE-SOLUTION

MISSING-DRAWER-OBJECT

NO-CAPACITIES-VEHICLE

NO-SPEED-VEHICLE

NOT-EQUAL-LENGTH

UNACCEPTED-PREDICATE