ExVrp.DurationSegment (ExVrp v0.4.2)

Copy Markdown View Source

Duration segments for tracking route timing during optimization.

Duration segments can be efficiently concatenated, and track statistics about route and trip duration and time warp resulting from visiting clients in the concatenated order.

This is a core data structure used by the local search operators to efficiently evaluate moves.

Example

ds1 = ExVrp.DurationSegment.new(5, 0, 0, 5, 0)
ds2 = ExVrp.DurationSegment.new(0, 5, 3, 6, 0)
merged = ExVrp.DurationSegment.merge(4, ds1, ds2)
ExVrp.DurationSegment.time_warp(merged)

Summary

Functions

Returns the total duration of the whole segment.

Returns the earliest end time of the current trip.

Returns the latest end time of the current trip.

Finalises this segment at the back (end of segment).

Finalises this segment at the front (start of segment).

Merges two duration segments with an edge duration.

Returns the latest end time of the previous trip.

Returns the release time of clients on the current trip.

Returns the slack in the route schedule.

Returns the earliest start time for the current trip.

Returns the latest start time for the current trip.

Returns the time warp on this whole segment.

Types

t()

@type t() :: reference()

Functions

duration(segment)

@spec duration(t()) :: integer()

Returns the total duration of the whole segment.

end_early(segment)

@spec end_early(t()) :: integer()

Returns the earliest end time of the current trip.

end_late(segment)

@spec end_late(t()) :: integer()

Returns the latest end time of the current trip.

finalise_back(segment)

@spec finalise_back(t()) :: t()

Finalises this segment at the back (end of segment).

Returns a new segment where release times have been reset, and all other statistics have been suitably adjusted. This is useful with multiple trips because the finalised segment can be concatenated with segments of later trips.

finalise_front(segment)

@spec finalise_front(t()) :: t()

Finalises this segment at the front (start of segment).

Returns a new segment where release times have been reset, and all other statistics have been suitably adjusted. This is useful with multiple trips because the finalised segment can be concatenated with segments of earlier trips.

merge(edge_duration, first, second)

@spec merge(integer(), t(), t()) :: t()

Merges two duration segments with an edge duration.

Parameters

  • edge_duration - Duration to travel between the segments
  • first - First duration segment
  • second - Second duration segment

Returns

A new merged duration segment.

new(duration, time_warp, start_early, start_late, release_time, cum_duration \\ 0, cum_time_warp \\ 0, prev_end_late \\ 9_223_372_036_854_775_807)

@spec new(
  integer(),
  integer(),
  integer(),
  integer(),
  integer(),
  integer(),
  integer(),
  integer()
) :: t()

Creates a new duration segment.

Parameters

  • duration - Total duration of current trip
  • time_warp - Total time warp on current trip
  • start_early - Earliest start time of current trip
  • start_late - Latest start time of current trip
  • release_time - Earliest moment to start this trip segment
  • cum_duration - Cumulative duration of other trips (default 0)
  • cum_time_warp - Cumulative time warp of other trips (default 0)
  • prev_end_late - Latest end time of previous trip (default INT_MAX)

prev_end_late(segment)

@spec prev_end_late(t()) :: integer()

Returns the latest end time of the previous trip.

release_time(segment)

@spec release_time(t()) :: integer()

Returns the release time of clients on the current trip.

slack(segment)

@spec slack(t()) :: integer()

Returns the slack in the route schedule.

This is the amount of time by which the start of the current trip can be delayed without increasing the overall route duration.

start_early(segment)

@spec start_early(t()) :: integer()

Returns the earliest start time for the current trip.

start_late(segment)

@spec start_late(t()) :: integer()

Returns the latest start time for the current trip.

time_warp(segment, max_duration \\ 9_223_372_036_854_775_807)

@spec time_warp(t(), integer()) :: integer()

Returns the time warp on this whole segment.

If max_duration is provided, any excess duration beyond it is also counted as time warp.