While this submission is a draft, it cannot be used by other submissions.

Optimal temporal paths

Lax330177.OptimalPaths · concepts/Lax330177/OptimalPaths.lean · lax-330177

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    Fix two vertices, traversal times, a release time and an inclusive arrival deadline. A shortest path minimizes traversals. A fastest path minimizes elapsed time from first departure to final arrival. Foremost paths minimize arrival, and latest departure paths maximize departure. Minimum waiting paths minimize the sum of idle gaps at internal vertices. Initial waiting and time after arrival do not contribute. A zero-edge path occupies its vertex at any one instant in the window. Every feasible query admits an optimizer for each of the five criteria.

    • Each objective attains its optimum. Fix the endpoints, traversal times, release time and arrival deadline. If at least one feasible path exists, then each of the five criteria has an optimal path. The optimizing path may depend on the criterion.
    Concept map
    5 concepts; 9 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    In the paper

    • page 3 of this submission's paper

    Lean source view on GitHub

    1import Lax330177.Durations
    2import Mathlib.Order.Filter.Extr
    3import Mathlib.Algebra.BigOperators.Group.Finset.Basic
    4
    5/-!
    6---
    7title: Optimal temporal paths
    8type: definition
    9---
    10Fix two vertices, traversal times, a release time and an inclusive arrival deadline.
    11A shortest path minimizes traversals. A fastest path minimizes elapsed time from
    12first departure to final arrival. Foremost paths minimize arrival, and latest
    13departure paths maximize departure. Minimum waiting paths minimize the sum of
    14idle gaps at internal vertices. Initial waiting and time after arrival do not
    15contribute. A zero-edge path occupies its vertex at any one instant in the window.
    16Every feasible query admits an optimizer for each of the five criteria.
    17
    18- [Each objective attains its optimum.](Lax330177Proofs.OptimalPaths.optima_exist.html) Fix the endpoints, traversal times, release time and arrival deadline. If at least one feasible path exists, then each of the five criteria has an optimal path. The optimizing path may depend on the criterion.
    19-/
    20namespace Lax330177.OptimalPaths
    21open Lax330177.Representations Lax330177.Durations
    22
    23structure Query {n : ℕ} (G : Graph n) where
    24 source : Fin n
    25 target : Fin n
    26 release : ℕ
    27 deadline : ℕ
    28 transit : Fin G.lifetime → Fin n → Fin n → ℕ
    29
    30variable {n : ℕ} {G : Graph n} (q : Query G)
    31
    32structure Candidate where
    33 hops : ℕ
    34 vertex : Fin (hops+1) → Fin n
    35 time : Fin hops → Fin G.lifetime
    36 feasible : DurationPath G q.transit vertex time
    37 starts : vertex 0 = q.source
    38 ends : vertex (Fin.last hops) = q.target
    39 departure : ℕ
    40 arrival : ℕ
    41 released : q.release ≤ departure
    42 inOrder : departure ≤ arrival
    43 onTime : arrival ≤ q.deadline
    44 first : ∀ h : 0 < hops, departure = (time ⟨0,h⟩).val
    45 last : ∀ h : 0 < hops,
    46 let i : Fin hops := ⟨hops-1, by omega⟩
    47 arrival = (time i).val + q.transit (time i) (vertex i.castSucc) (vertex i.succ)
    48 instantaneous : hops = 0 → departure = arrival
    49
    50variable {q}
    51def Candidate.elapsed (p : Candidate q) := p.arrival - p.departure
    52
    53def Candidate.waiting (p : Candidate q) : ℕ :=
    54 ∑ i : Fin p.hops, if h : i.val + 1 < p.hops then
    55 (p.time ⟨i.val+1,h⟩).val - ((p.time i).val + q.transit (p.time i) (p.vertex i.castSucc) (p.vertex i.succ))
    56 else 0
    57
    58def Shortest (p : Candidate q) := IsMinOn Candidate.hops Set.univ p
    59def Fastest (p : Candidate q) := IsMinOn Candidate.elapsed Set.univ p
    60def Foremost (p : Candidate q) := IsMinOn Candidate.arrival Set.univ p
    61abbrev EarliestArrival (p : Candidate q) := Foremost p
    62def LatestDeparture (p : Candidate q) := IsMaxOn Candidate.departure Set.univ p
    63def MinimumWaiting (p : Candidate q) := IsMinOn Candidate.waiting Set.univ p
    64
    65end Lax330177.OptimalPaths
    66
    67

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…