API

vrpy.VehicleRoutingProblem

class vrpy.vrp.VehicleRoutingProblem(G, num_stops=None, load_capacity=None, duration=None, time_windows=False, pickup_delivery=False, distribution_collection=False, drop_penalty=None, fixed_cost=0, num_vehicles=None, use_all_vehicles=False, periodic=None, mixed_fleet=False, minimize_global_span=False)

Stores the underlying network of the VRP and parameters for solving with a column generation approach.

Parameters
  • G (DiGraph) – The underlying network.

  • num_stops (int, optional) – Maximum number of stops. Defaults to None.

  • load_capacity (list, optional) – Maximum load per vehicle. Each item of the list points to a different capacity. Defaults to None.

  • duration (int, optional) – Maximum duration of route. Defaults to None.

  • time_windows (bool, optional) – True if time windows on vertices. Defaults to False.

  • pickup_delivery (bool, optional) – True if pickup and delivery constraints. Defaults to False.

  • distribution_collection (bool, optional) – True if distribution and collection are simultaneously enforced. Defaults to False.

  • drop_penalty (int, optional) – Value of penalty if node is dropped. Defaults to None.

  • fixed_cost (int, optional) – Fixed cost per vehicle. Defaults to 0.

  • num_vehicles (int, optional) – Maximum number of vehicles available. Defaults to None (in this case num_vehicles is unbounded).

  • use_all_vehicles (bool, optional) – True if all vehicles specified by num_vehicles should be used. Defaults to False.

  • periodic (int, optional) – Time span if vertices are to be visited periodically. Defaults to None.

  • mixed_fleet (bool, optional) – True if heterogeneous fleet. Defaults to False.

  • minimize_global_span (bool, optional) – True if global span is minimized (instead of total cost). Defaults to False.

property arrival_time

Returns nested dict. First key : route id ; second key : node ; value : arrival time.

property best_routes

Returns dict of best routes found. Keys : route_id; values : list of ordered nodes from Source to Sink.

property best_routes_cost

Returns dict with route ids as keys and route costs as values.

property best_routes_duration

Returns dict with route ids as keys and route durations as values.

property best_routes_load

Returns dict with route ids as keys and route loads as values.

property best_value

Returns value of best solution found.

property departure_time

Returns nested dict. First key : route id ; second key : node ; value : departure time.

property node_load

Returns nested dict. First key : route id ; second key : node ; value : load. If truck is collecting, load refers to accumulated load on truck. If truck is distributing, load refers to accumulated amount that has been unloaded. If simultaneous distribution and collection, load refers to truck load when leaving the node.

property schedule

If Periodic CVRP, returns a dict with keys a day number and values the route IDs scheduled this day.

solve(initial_routes=None, preassignments=None, pricing_strategy='BestEdges1', cspy=True, elementary=False, time_limit=None, solver='cbc', dive=False, greedy=False, max_iter=None, run_exact=1, heuristic_only=False)

Iteratively generates columns with negative reduced cost and solves as MIP.

Parameters
  • initial_routes (list, optional) – List of routes (ordered list of nodes). Feasible solution for first iteration. Defaults to None.

  • preassignments (list, optional) – List of preassigned routes (ordered list of nodes). If the route contains Source and Sink nodes, it is locked, otherwise it may be extended. Defaults to None.

  • pricing_strategy (str, optional) –

    Strategy used for solving the sub problem. Options available :

    • ”Exact”: the subproblem is solved exactly;

    • ”BestEdges1”: some edges are removed;

    • ”BestEdges2”: some edges are removed (with a different strategy);

    • ”BestPaths”: some edges are removed (with a different strategy);

    • ”Hyper”: choose from the above using a hyper_heuristic (see hyper_heuristic.py);

    Defaults to “BestEdges1”.

  • cspy (bool, optional) – True if cspy is used for subproblem. Defaults to True.

  • elementary (bool, optional) – True if only cspy’s elementary algorithm is to be used. Otherwise, a mix is used: only use elementary when a route is repeated. In this case, also a threshold is used to avoid running for too long. If dive=True then this is also forced to be True. Defaults to False.

  • time_limit (int, optional) – Maximum number of seconds allowed for solving (for finding columns). Defaults to None.

  • solver (str, optional) – Solver used. Three options available: “cbc”, “cplex”, “gurobi”. Using “cplex” or “gurobi” requires installation. Not available by default. Additionally, “gurobi” requires pulp to be installed from source. Defaults to “cbc”, available by default.

  • dive (bool, optional) – True if diving heuristic is used. Defaults to False.

  • greedy (bool, optional) – True if randomized greedy algorithm is used to generate extra columns. Only valid for capacity constraints, time constraints, num stops constraints. Defaults to False.

  • max_iter (int, optional) – maximum number of iterations for the column generation procedure.

  • run_exact (int, optional) – if a pricing strategy is selected, this parameter controls the number of iterations after which the exact algorithm is run. Defaults to 1.

  • heuristic_only (bool, optional) – True if Clarke & Wright solution is return without entering column generation loop. Defaults to False.

Returns

Optimal solution of MIP based on generated columns

Return type

float

Notes

The input graph must have single Source and Sink nodes with no incoming or outgoing edges respectively. These dummy nodes represent the depot which is split for modeling convenience. The Source and Sink cannot have a demand, if one is given it is ignored with a warning.

Please read sections Vehicle Routing Problems, Solving Options and Examples for details and examples on each of the above arguments.