lsa-planer

LSA-Planer Professional – Planungssoftware für Lichtsignalanlagen nach RiLSA 2015 und § 45 StVO. EUPL-1.2.

/ src domain plan phaseneinteilung.ts

13,7 KB Rohdatei
src/domain/plan/phaseneinteilung.ts — 342 Zeilen
1 import { leiteAb } from '../geometrie/ableitung';
2 import { buildSignalPlan } from './signalPlan';
3 import { createPhase } from '../model/factory';
4 import type { Project } from '../model/project';
5 import type { Seconds } from '../units';
6
7 /**
8 * Zulaessige Phaseneinteilungen aufzaehlen und reihen.
9 *
10 * DIE BEDINGUNG, UNTER DER ES DIESES MODUL UEBERHAUPT GEBEN DARF, und sie ist
11 * keine Feinheit: Eine Reihung nach kleinster Umlaufzeit bevorzugt WENIGE
12 * Phasen, also viele gleichzeitig freigegebene Signalgruppen. Gleichzeitigkeit
13 * ist im Datenbestand aber schon dann erlaubt, wenn kein Konflikt ERFASST ist -
14 * "geprueft vertraeglich" und "noch nicht betrachtet" sehen darin gleich aus.
15 * Mit jedem entfallenden Phasenuebergang faellt zudem eine Zwischenzeit
16 * ersatzlos weg.
17 *
18 * Deshalb: OHNE POSITIVEN BELEG DER VERTRAEGLICHKEIT JEDES PAARES ERSCHEINT
19 * KEIN EINZIGER VORSCHLAG. Nicht ein gekennzeichneter, nicht ein grauer - gar
20 * keiner. Statt dessen sagt die Auskunft, welche Paare unbelegt sind.
21 *
22 * WOHER DER BELEG KOMMT (Weg A des Befunds, ohne Schemasprung): aus dem
23 * massstaeblich auswertbaren Lageplan. Kreuzen sich die gezeichneten Fahrlinien
24 * zweier Gruppen nicht, ist das eine Aussage ueber die Oertlichkeit und keine
25 * Abwesenheit einer Eingabe. Wo kein solcher Lageplan vorliegt, gibt es diese
26 * Auskunft nicht - und dann eben keine Vorschlaege.
27 */
28
29 /** Wie die Vertraeglichkeit eines Paares belegt ist. */
30 export type Belegart = 'feindlich' | 'belegt' | 'ohne-beleg';
31
32 export interface Paarbeleg {
33 readonly aId: string;
34 readonly bId: string;
35 readonly aName: string;
36 readonly bName: string;
37 readonly art: Belegart;
38 readonly grund: string;
39 }
40
41 export interface Belegstand {
42 readonly paare: readonly Paarbeleg[];
43 /** Die Paare, die den Vorschlaegen im Weg stehen. */
44 readonly ohneBeleg: readonly Paarbeleg[];
45 readonly vollstaendig: boolean;
46 }
47
48 /**
49 * Wieviele Einteilungen hoechstens aufgezaehlt werden.
50 *
51 * GEZAEHLT WIRD, BEVOR AUFGEZAEHLT WIRD (zweites Risiko des Befunds): Der
52 * Suchraum haengt an der Zahl der ERFASSTEN Konflikte, nicht an der Zahl der
53 * Gruppen - ausgerechnet das schlecht gepflegte Projekt haette den groessten
54 * Suchraum und bekaeme die meisten Vorschlaege. Beide Schranken sind gesetzt
55 * und stammen aus keinem Regelwerk.
56 */
57 export const MAX_PHASENMENGEN = 400;
58 export const MAX_VORSCHLAEGE = 12;
59
60 export interface Phasenvorschlag {
61 /** Die Signalgruppen je Phase, in der Reihenfolge des Vorschlags. */
62 readonly phasen: readonly (readonly string[])[];
63 readonly umlaufzeit: Seconds;
64 /** Entspricht der Vorschlag der heutigen Einteilung des Projekts? */
65 readonly heutige: boolean;
66 }
67
68 export type Suchhindernis = 'ohne-beleg' | 'zu-wenige-gruppen' | 'zu-viele-moeglichkeiten';
69
70 export interface Einteilungssuche {
71 readonly hindernis: Suchhindernis | null;
72 readonly beleg: Belegstand;
73 /** Wieviele Phasenmengen betrachtet wurden - die Zahl vor dem Aufzaehlen. */
74 readonly phasenmengen: number;
75 readonly vorschlaege: readonly Phasenvorschlag[];
76 }
77
78 function paarSchluessel(a: string, b: string): string {
79 return a < b ? `${a}|${b}` : `${b}|${a}`;
80 }
81
82 /**
83 * Der Belegstand jedes Signalgruppenpaares.
84 *
85 * Drei Faelle, und der dritte ist der wichtige:
86 * 1. Eine erfasste Konfliktbeziehung - feindlich, und das ist eine Aussage.
87 * 2. Der Lageplan zeigt kreuzungsfreie Fahrlinien beider Gruppen -
88 * vertraeglich, und auch das ist eine Aussage.
89 * 3. Alles Uebrige - KEINE Aussage. Nicht "vertraeglich", sondern "nicht
90 * betrachtet".
91 */
92 export function vertraeglichkeitsbelege(project: Project): Belegstand {
93 const gruppen = project.signalGroups;
94 const feindlich = new Set(project.conflicts.map((c) => paarSchluessel(c.fromId, c.toId)));
95
96 const ableitung = leiteAb(project, project.lageplan);
97 const linieZuGruppe = new Map(
98 project.lageplan.linien
99 .filter((l) => l.signalGroupId !== null)
100 .map((l) => [l.id, l.signalGroupId!]),
101 );
102 /*
103 * Je Gruppenpaar: Wieviele Linienpaare hat die Ableitung beurteilt, und
104 * wieviele davon sprechen fuer Vertraeglichkeit? Ein einziges Paar mit
105 * "kreuzt" oder "zu pruefen" verdirbt den Beleg - eine Gruppe faehrt so
106 * viele Stroeme, wie sie fuehrt, und jeder einzelne muss vertraeglich sein.
107 */
108 const beurteilt = new Map<string, { gut: number; schlecht: number }>();
109 for (const vorschlag of ableitung.vertraeglichkeit) {
110 const a = linieZuGruppe.get(vorschlag.aLinieId);
111 const b = linieZuGruppe.get(vorschlag.bLinieId);
112 if (a === undefined || b === undefined || a === b) continue;
113 const schluessel = paarSchluessel(a, b);
114 const stand = beurteilt.get(schluessel) ?? { gut: 0, schlecht: 0 };
115 if (!vorschlag.feindlich && !vorschlag.zuPruefen) stand.gut += 1;
116 else stand.schlecht += 1;
117 beurteilt.set(schluessel, stand);
118 }
119
120 const paare: Paarbeleg[] = [];
121 for (let i = 0; i < gruppen.length; i += 1) {
122 for (let j = i + 1; j < gruppen.length; j += 1) {
123 const a = gruppen[i]!;
124 const b = gruppen[j]!;
125 const schluessel = paarSchluessel(a.id, b.id);
126 const gemeinsam = { aId: a.id, bId: b.id, aName: a.name, bName: b.name };
127 if (feindlich.has(schluessel)) {
128 paare.push({
129 ...gemeinsam,
130 art: 'feindlich',
131 grund: 'Als feindliche Beziehung erfasst.',
132 });
133 continue;
134 }
135 /*
136 * KEIN ZWEITER VORBEHALT AUF `ableitung.auswertbar`: Ohne auswertbaren
137 * Lageplan gibt `leiteAb` eine leere Vertraeglichkeitsliste zurueck, und
138 * `beurteilt` ist dann leer - die Abfrage waere ein Zweig, den keine
139 * Eingabe erreicht. Ein unerreichbarer Zweig sieht aus wie Vorsicht und
140 * ist eine Luecke im Nachweis. Die Auswertbarkeit steht dafuer im Grund
141 * des unbelegten Paares, wo sie der Bearbeiter braucht.
142 */
143 const stand = beurteilt.get(schluessel);
144 if (stand !== undefined && stand.gut > 0 && stand.schlecht === 0) {
145 paare.push({
146 ...gemeinsam,
147 art: 'belegt',
148 grund: `Im Lageplan geprüft: ${String(stand.gut)} Strompaar(e), keine Kreuzung.`,
149 });
150 continue;
151 }
152 paare.push({
153 ...gemeinsam,
154 art: 'ohne-beleg',
155 grund: !ableitung.auswertbar
156 ? 'Kein maßstäblich auswertbarer Lageplan – die Verträglichkeit ist nicht belegt, ' +
157 'sondern nur nicht erfasst.'
158 : 'Für dieses Paar liegt keine geprüfte Aussage vor: Es fehlen gezeichnete Fahrlinien ' +
159 'beider Gruppen, oder die Zeichnung ist uneindeutig.',
160 });
161 }
162 }
163
164 const ohneBeleg = paare.filter((p) => p.art === 'ohne-beleg');
165 return { paare, ohneBeleg, vollstaendig: ohneBeleg.length === 0 };
166 }
167
168 /**
169 * Alle maximalen Mengen paarweise vertraeglicher Gruppen (Bron-Kerbosch).
170 *
171 * MAXIMAL und nicht beliebig: Eine Phase, der sich eine weitere vertraegliche
172 * Gruppe hinzufuegen liesse, verschenkt Freigabezeit - sie waere nie die
173 * Antwort auf "welche Einteilung ergibt die kuerzeste Umlaufzeit". Die Suche
174 * bricht ab, sobald `MAX_PHASENMENGEN` erreicht ist; die Zahl steht dann in
175 * der Auskunft.
176 */
177 export function maximaleMengen(
178 ids: readonly string[],
179 vertraeglich: (a: string, b: string) => boolean,
180 ): { mengen: string[][]; abgebrochen: boolean } {
181 const mengen: string[][] = [];
182 let abgebrochen = false;
183
184 const erweitere = (aktuell: string[], kandidaten: string[], geprueft: string[]): void => {
185 if (abgebrochen) return;
186 if (kandidaten.length === 0 && geprueft.length === 0) {
187 mengen.push([...aktuell]);
188 if (mengen.length >= MAX_PHASENMENGEN) abgebrochen = true;
189 return;
190 }
191 const rest = [...kandidaten];
192 const bereits = [...geprueft];
193 for (const id of kandidaten) {
194 erweitere(
195 [...aktuell, id],
196 rest.filter((k) => k !== id && vertraeglich(id, k)),
197 bereits.filter((g) => vertraeglich(id, g)),
198 );
199 rest.splice(rest.indexOf(id), 1);
200 bereits.push(id);
201 // Der Uebersetzer sieht `abgebrochen` hier als unveraendert an: Gesetzt
202 // wird es im rekursiven Aufruf darueber, und dessen Wirkung verfolgt die
203 // Flussanalyse nicht. Ohne diese Abfrage laeuft die Suche nach dem
204 // Abbruch weiter durch den ganzen Baum.
205 // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition -- der rekursive Aufruf setzt das Merkmal; siehe darueber
206 if (abgebrochen) return;
207 }
208 };
209
210 erweitere([], [...ids], []);
211 return { mengen, abgebrochen };
212 }
213
214 /** Alle Ueberdeckungen aus `anzahl` Mengen, die jede Gruppe erfassen. */
215 function ueberdeckungen(
216 mengen: readonly (readonly string[])[],
217 ids: readonly string[],
218 anzahl: number,
219 hoechstens: number,
220 ): string[][][] {
221 const treffer: string[][][] = [];
222 const waehle = (ab: number, gewaehlt: (readonly string[])[], abgedeckt: Set<string>): void => {
223 if (treffer.length >= hoechstens) return;
224 if (gewaehlt.length === anzahl) {
225 if (abgedeckt.size === ids.length) treffer.push(gewaehlt.map((m) => [...m]));
226 return;
227 }
228 for (let i = ab; i < mengen.length; i += 1) {
229 const menge = mengen[i]!;
230 /*
231 * BESCHNITTEN WIRD NUR, WAS NICHTS BEITRAEGT: Eine Menge, deren Gruppen
232 * alle schon abgedeckt sind, macht die Ueberdeckung nicht vollstaendiger
233 * - sie erzeugte nur dieselbe Loesung mit einer Phase mehr. Ueber die
234 * VOLLSTAENDIGKEIT entscheidet allein die Abfrage oben; dieses
235 * Beschneiden ist eine Abkuerzung und darf das Ergebnis nicht aendern.
236 */
237 const naechste = new Set([...abgedeckt, ...menge]);
238 if (naechste.size === abgedeckt.size) continue;
239 waehle(i + 1, [...gewaehlt, menge], naechste);
240 if (treffer.length >= hoechstens) return;
241 }
242 };
243 waehle(0, [], new Set());
244 return treffer;
245 }
246
247 /** Die Umlaufzeit, die eine Einteilung ergibt - am wirklichen Planaufbau. */
248 function umlaufzeitVon(project: Project, phasen: readonly (readonly string[])[]): Seconds {
249 const angelegt = phasen.map((gruppen, index) =>
250 createPhase(`Phase ${String(index + 1)}`, [...gruppen]),
251 );
252 const probe: Project = {
253 ...project,
254 phases: angelegt,
255 program: { ...project.program, phaseOrder: angelegt.map((p) => p.id) },
256 };
257 return buildSignalPlan(probe).cycleTime;
258 }
259
260 /** Die heutige Einteilung als Mengen von Gruppenkennungen. */
261 function heutigeEinteilung(project: Project): Set<string> {
262 return new Set(project.phases.map((p) => [...p.signalGroupIds].sort().join('|')));
263 }
264
265 /**
266 * Sucht zulaessige Phaseneinteilungen und reiht sie nach Umlaufzeit.
267 *
268 * Gibt IMMER eine Auskunft zurueck - auch die, dass keine Vorschlaege gemacht
269 * werden. Ein leeres Ergebnis ohne Grund waere hier das Schlimmste: Der
270 * Bearbeiter hielte es fuer "es gibt keine".
271 */
272 export function sucheEinteilungen(project: Project): Einteilungssuche {
273 const beleg = vertraeglichkeitsbelege(project);
274 const ids = project.signalGroups.map((g) => g.id);
275
276 if (ids.length < 2) {
277 return { hindernis: 'zu-wenige-gruppen', beleg, phasenmengen: 0, vorschlaege: [] };
278 }
279 if (!beleg.vollstaendig) {
280 return { hindernis: 'ohne-beleg', beleg, phasenmengen: 0, vorschlaege: [] };
281 }
282
283 const belegt = new Set(
284 beleg.paare.filter((p) => p.art === 'belegt').map((p) => paarSchluessel(p.aId, p.bId)),
285 );
286 const vertraeglich = (a: string, b: string): boolean => belegt.has(paarSchluessel(a, b));
287
288 const { mengen, abgebrochen } = maximaleMengen(ids, vertraeglich);
289 if (abgebrochen) {
290 return {
291 hindernis: 'zu-viele-moeglichkeiten',
292 beleg,
293 phasenmengen: mengen.length,
294 vorschlaege: [],
295 };
296 }
297
298 /*
299 * Von der kleinsten Phasenzahl aufwaerts, hoechstens eine Stufe weiter: Der
300 * Vorschlag mit den wenigsten Phasen ist der mit den wenigsten Uebergaengen,
301 * und die naechste Stufe zeigt, was eine zusaetzliche Phase kostet. Alles
302 * darueber waere eine Liste ohne Aussage.
303 */
304 const gefunden: string[][][] = [];
305 let ersteStufe: number | null = null;
306 for (let k = 1; k <= Math.min(mengen.length, ids.length); k += 1) {
307 if (ersteStufe !== null && k > ersteStufe + 1) break;
308 const treffer = ueberdeckungen(mengen, ids, k, MAX_VORSCHLAEGE - gefunden.length);
309 if (treffer.length > 0 && ersteStufe === null) ersteStufe = k;
310 gefunden.push(...treffer);
311 if (gefunden.length >= MAX_VORSCHLAEGE) break;
312 }
313
314 const heute = heutigeEinteilung(project);
315 const vorschlaege = gefunden
316 .map((phasen) => ({
317 phasen,
318 umlaufzeit: umlaufzeitVon(project, phasen),
319 heutige:
320 phasen.length === heute.size && phasen.every((p) => heute.has([...p].sort().join('|'))),
321 }))
322 // Nach Umlaufzeit, bei Gleichstand nach der Zahl der Phasen: Zwei
323 // Einteilungen mit derselben Umlaufzeit unterscheiden sich in den
324 // Uebergaengen, und weniger Uebergaenge sind weniger Zwischenzeiten.
325 .sort((a, b) => a.umlaufzeit - b.umlaufzeit || a.phasen.length - b.phasen.length);
326
327 return { hindernis: null, beleg, phasenmengen: mengen.length, vorschlaege };
328 }
329
330 /** Klartext zu einem Hindernis - eine Stelle fuer Ansicht und Ausdruck. */
331 export const SUCHHINDERNIS_TEXT: Readonly<Record<Suchhindernis, string>> = {
332 'ohne-beleg':
333 'Für mindestens ein Signalgruppenpaar ist die Verträglichkeit nicht belegt. Solange das so ' +
334 'ist, wird keine einzige Einteilung vorgeschlagen: Ein Vorschlag würde Gruppen gleichzeitig ' +
335 'freigeben, von denen niemand geprüft hat, ob sie sich vertragen – und mit jedem ' +
336 'entfallenden Phasenübergang fiele eine Zwischenzeit ersatzlos weg.',
337 'zu-wenige-gruppen': 'Für eine Phaseneinteilung braucht es mindestens zwei Signalgruppen.',
338 'zu-viele-moeglichkeiten':
339 'Dieses Projekt lässt zu viele Phasenmengen zu, als dass eine Aufzählung eine Hilfe wäre. ' +
340 'Das spricht in der Regel für zu wenige erfasste Konfliktbeziehungen: Je weniger Konflikte ' +
341 'erfasst sind, desto mehr Gruppen gelten als gleichzeitig freigebbar.',
342 };