ADPTW

This module provides efficient implementations to solve ADPTW problems.

Classification

The A-D-P-TW class of vehicle routing routing problems with intermediate stops encompassed problems with the following attributes (cf. Schiffer et al. [SSWL19]):

  • Arc-based (A): The consumption of operational resources, e.g. fuel, is continuous and occurs when travelling between nodes.

  • Dependent (D): The replenishment time is dependent on the quantity of the operational resource being replenished, meaning more time is needed for larger quantities.

  • Partial Replenishment (P): The operational resources can be partially restocked, implying that the replenishment process can be interrupted at any time, i.e., does not need to fully replenish the resource in question.

  • Time Windows (TW): The scheduled stops need to be visited within node-specific periods.

In this setting, the routing strategy must consider continuous resource consumption, variable replenishment times, the option for partial replenishment, and adherence to designated time windows. This combination of factors is one of the most challenging routing problems, and is often encountered in real-world applications, e.g., the Electric Vehicle Routing Problem with Time Windows and Partial Replenishment (EVRP-TW-PR).

API

class routingblocks.adptw.Evaluation(vehicle_resource_capacity: float, vehicle_storage_capacity: float)

Bases: PyEvaluation

Evaluation for ADPTW problems. Works only with arcs and vertices created using create_adptw_arc and create_adptw_vertex. Uses a set of penalty factors to penalize infeasible solutions.

Variables:

  • overload_penalty_factor – The penalty factor for overloading the vehicle.

  • resource_penalty_factor – The penalty factor for consuming more resources than carried the vehicle.

  • time_shift_penalty_factor – The penalty factor for time shifts.

Parameters:

  • vehicle_resource_capacity (float) – The vehicle’s battery capacity expressed in units of time, that is, the time it takes to fully replenish the resource of an empty vehicle.

  • vehicle_storage_capacity (float) – The vehicle’s storage capacity. Determines how much demand can be served in a single route.

overload_penalty_factor
resource_penalty_factor
time_shift_penalty_factor
class routingblocks.adptw.ArcData(distance: float, travel_time: float, consumption: float)

Data stored on arcs in an ADPTW problem setting.

Parameters:

  • distance (float) – The distance between the two vertices connected by the arc.

  • travel_time (float) – The time it takes to travel between the two vertices connected by the arc.

  • consumption (float) – The time required to replenish the resource consumed when traveling between the two vertices connected by the arc.

class routingblocks.adptw.VertexData(x: float, y: float, demand: float, earliest_time_of_arrival: float, latest_time_of_arrival: float, service_time: float)

Data stored on vertices in an ADPTW problem setting.

Parameters:

  • x (float) – The x coordinate of the vertex.

  • y (float) – The y coordinate of the vertex.

  • demand (float) – The demand of the vertex. 0 for station and depot vertices.

  • earliest_time_of_arrival (float) – The earliest time at which service at the vertex can begin.

  • latest_time_of_arrival (float) – The latest time at which service at the vertex can begin.

  • service_time (float) – The time needed to serve the vertex.

routingblocks.adptw.create_adptw_arc(data: ADPTWArcData)

Creates an arc for an ADPTW problem setting. Stores :param data directly as a native C++ object.

Warning

The data member of the created arc is not accessible from python. Doing so will likely result in a crash.

Parameters:

data (ADPTWArcData) – The data to associate with this vertex

Returns:

Return type:

Arc

routingblocks.adptw.create_adptw_vertex(vertex_id: int, str_id: str, is_facility: bool, is_depot: bool, data: ADPTWVertexData)

Creates a vertex for an ADPTW problem setting. Stores :param data directly as a native C++ object.

Warning

The data member of the created vertex is not accessible from python. Doing so will likely result in a crash.

Parameters:

  • vertex_id (int) – The unique identifier of the vertex.

  • str_id (str) – A human-readable string identifier for the vertex.

  • is_facility (bool) – Whether the vertex is a replenishment facility.

  • is_depot (bool) – Whether the vertex is a depot.

  • data (ADPTWVertexData) – The data to associate with this vertex.

Returns:

Return type:

Vertex

class routingblocks.adptw.FacilityPlacementOptimizer(instance: Instance, resource_capacity_time: float)

ADPTW-specific detour insertion algorithm. Inserts visits to replenishment facilities at optimal locations into a route.

Parameters:

  • instance (Instance) – The instance.

  • resource_capacity_time (float) – The vehicle’s resource capacity expressed in units of time, that is, the time it takes to fully replenish the resource of an empty vehicle.

optimize(route_vertex_ids: List[VertexID])

Optimizes the route by inserting visits to replenishment facilities at optimal locations. :param route_vertex_ids: The vertex ids of the route to optimize. :return: The optimized route as a list of vertex ids.

Parameters:

route_vertex_ids (List[VertexID]) –

Return type:

List[VertexID]