NIFTW

This module provides efficient implementations to solve NIFTW problems.

Classification

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

  • Node-based (N): The consumption of operational resources, e.g., goods or materials, occurs at stops or nodes.

  • Independent (I): The replenishment time is fixed and not dependent on the quantity of the operational resource being replenished, ensuring consistent replenishment durations.

  • Full Replenishment (F): The operational resources are always fully restocked.

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

In the N-I-F-TW setting, the routing considerations are centred around node-specific resource consumption, constant replenishment times, the necessity for full replenishment, and strict adherence to time windows. This scenario is typical in various real-world applications where resources are consumed at stops, replenishment times are consistent, and routes are strictly governed by time constraints, such as in certain types of delivery or service routing problems.

API

class routingblocks.niftw.Evaluation(vehicle_resource_capacity: float, vehicle_storage_capacity: float, replenishment_time: float)

Bases: PyEvaluation

Evaluation for NIFTW problems. Works only with arcs and vertices created using create_niftw_arc and create_niftw_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 by 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 recharge an empty battery.

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

  • replenishment_time (float) – The time penalty incurred to replenish all the resources carried by the vehicle.

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

Data stored on arcs in an NIFTW 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 recharge the resources consumed when traveling between the two vertices connected by the arc.

class routingblocks.niftw.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 NIFTW 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.

class routingblocks.niftw.FacilityPlacementOptimizer(instance: Instance, battery_capacity_time: float, replenishment_time: float)

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

Parameters:

  • instance (Instance) – The instance to optimize.

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

  • replenishment_time (float) – The time penalty incurred to replenish all the resources carried by the 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]

routingblocks.niftw.create_niftw_arc(data: NIFTWArcData)

Creates an arc for an NIFTW 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 (NIFTWArcData) – The data to associate with this vertex

Returns:

Return type:

Arc

routingblocks.niftw.create_niftw_vertex(vertex_id: int, str_id: str, is_station: bool, is_depot: bool, data: NIFTWVertexData)

Creates a vertex for an NIFTW 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_station (bool) – Whether the vertex is a station.

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

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

Returns:

Return type:

Vertex