Optimal temporal paths
Lax330177.OptimalPaths · concepts/Lax330177/OptimalPaths.lean · lax-330177
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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
In the paper
- page 3 of this submission's paper
Lean source view on GitHub
| 1 | import Lax330177.Durations |
| 2 | import Mathlib.Order.Filter.Extr |
| 3 | import Mathlib.Algebra.BigOperators.Group.Finset.Basic |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Optimal temporal paths |
| 8 | type: definition |
| 9 | --- |
| 10 | Fix two vertices, traversal times, a release time and an inclusive arrival deadline. |
| 11 | A shortest path minimizes traversals. A fastest path minimizes elapsed time from |
| 12 | first departure to final arrival. Foremost paths minimize arrival, and latest |
| 13 | departure paths maximize departure. Minimum waiting paths minimize the sum of |
| 14 | idle gaps at internal vertices. Initial waiting and time after arrival do not |
| 15 | contribute. A zero-edge path occupies its vertex at any one instant in the window. |
| 16 | Every 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 | -/ |
| 20 | namespace Lax330177.OptimalPaths |
| 21 | open Lax330177.Representations Lax330177.Durations |
| 22 | |
| 23 | structure 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 | |
| 30 | variable {n : ℕ} {G : Graph n} (q : Query G) |
| 31 | |
| 32 | structure 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 | |
| 50 | variable {q} |
| 51 | def Candidate.elapsed (p : Candidate q) := p.arrival - p.departure |
| 52 | |
| 53 | def 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 | |
| 58 | def Shortest (p : Candidate q) := IsMinOn Candidate.hops Set.univ p |
| 59 | def Fastest (p : Candidate q) := IsMinOn Candidate.elapsed Set.univ p |
| 60 | def Foremost (p : Candidate q) := IsMinOn Candidate.arrival Set.univ p |
| 61 | abbrev EarliestArrival (p : Candidate q) := Foremost p |
| 62 | def LatestDeparture (p : Candidate q) := IsMaxOn Candidate.departure Set.univ p |
| 63 | def MinimumWaiting (p : Candidate q) := IsMinOn Candidate.waiting Set.univ p |
| 64 | |
| 65 | end Lax330177.OptimalPaths |
| 66 | |
| 67 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments