Algorithms

pdppy.algorithms

Implementations of Pickup Delivery Problem algorithms and solvers for instances.

Algorithms and solvers take in graphical instances consistent with the description of H found in instances.request_graph and return a graphical representation of the tour which contains the edges in the final solution produced by the algorithm or solver. The implementations represent a series of developed algorithms, heuristics, integer programming and linear programming solvers for instances of the PDP.

All functions follow the same basic structure:

H: graph

Request graph instance.

P: graph

PDP tour solution. Contains all attributes from H. Contains only the edges representative of the final tour. Edges have additional attribute ‘value’ set to 1 if the edge is contained in the final tour. (All edges in P should have attribute ‘value’ == 1 with the exception of P found from linear_prog which may have fractional solutions.)

Functions

path_build_alg(H)	1-TT: Path Build Algorithm: Heuristic.
two_traversal_tree_alg(H)	2-TT: Two Traversal Tree Algorithm: Heuristic.
cheapest_feasible_insertion(H)	CFI: Cheapest Feasible Insertion Algorithm: Heuristic.
four_traversal_mst_alg(H)	4-TT: Four Traversal Minimum Spanning Tree Algorithm: 4-factor approx.
five_traversal_alg(H)	5-TT: Five Traversal Spanning Tree Algorithm: 5-factor approx.
double_tour_alg(H)	2-CHR: Double Tour Algorithm: 4-factor approx.
linear_prog(H)	LP: Linear Program Relaxation for the PDP.
branch_cut_integer_prog(H[, warm_start, …])	IP: Branch and Cut Integer Program for the PDP.