Question Type 7: Applying the postman problem to real world contexts Exercises

A network of seven roads connects five locations $A, B, C, D,$ and $E$. The lengths of the roads are as follows:

• $AB = 4\text{ km}$
• $BC = 3\text{ km}$
• $CD = 5\text{ km}$
• $DE = 2\text{ km}$
• $EA = 6\text{ km}$
• $AC = 4\text{ km}$
• $BD = 7\text{ km}$

Find the length of the shortest closed route that covers each road at least once.

A garbage truck must traverse a straight path of streets between intersections $A$–$B$ ($4\text{ km}$), $B$–$C$ ($3\text{ km}$), and $C$–$D$ ($5\text{ km}$), then return to $A$. Determine the length of the shortest closed route covering each street at least once.

A municipal inspector must check each road of a small network. A central junction $B$ connects to $A$, $C$, $D$, and $E$ via roads $BA = 3\text{ km}$, $BC = 5\text{ km}$, $BD = 4\text{ km}$, and $BE = 2\text{ km}$. Find the length of the shortest closed route covering all roads at least once.

A worker must clear debris along the four edges of a rectangular block with intersection nodes $A, B, C$, and $D$ in that order. The street lengths are $AB = 2\text{ km}$, $BC = 3\text{ km}$, $CD = 2\text{ km}$, and $DA = 3\text{ km}$. Find the minimum distance required to start and end at $A$ while traversing each street at least once.

A courier must use these one-way streets: $A \to B = 3 \text{ km}$, $B \to C = 4 \text{ km}$, $C \to A = 5 \text{ km}$, $B \to D = 2 \text{ km}$ and $D \to C = 1 \text{ km}$.

Find the minimum distance of a closed route covering each directed street at least once.

A road network has the following edges with given lengths: $A\text{--}B = 2\text{ km}$, $B\text{--}C = 4\text{ km}$, $C\text{--}D = 5\text{ km}$, $D\text{--}E = 6\text{ km}$, and a branch $C\text{--}F = 3\text{ km}$. A maintenance vehicle must start and end at node $A$, traversing each road at least once. Determine the minimum total distance the vehicle must travel.

Consider the network with nodes $A$, $B$, $C$, $D$ and edges $AB=3$ km, $BC=4$ km, $CD=5$ km, $DA=6$ km, $AC=2$ km, $BD=1$ km.

Determine the minimum distance for a closed route covering every edge at least once.

Three intersections $X$, $Y$, and $Z$ are connected such that the distance $X\text{--}Y = 6\text{ km}$ and the distance $Y\text{--}Z = 4\text{ km}$. A road worker must start and end at intersection $X$, covering each street at least once.

Determine the minimum length of the worker's route.

A delivery service operates on a mixed network. The two-way streets are $A-B$ ($3\text{ km}$), $B-D$ ($1\text{ km}$), and $C-D$ ($5\text{ km}$). The one-way streets are $B \rightarrow C$ ($4\text{ km}$) and $D \rightarrow A$ ($2\text{ km}$).

Find the length of the shortest closed route that traverses every street in its allowed direction at least once.

A mail carrier travels on one-way streets forming a directed network: $A \to B = 3 \text{ km}$, $B \to C = 4 \text{ km}$, $C \to A = 5 \text{ km}$, $B \to D = 2 \text{ km}$, and $D \to B = 2 \text{ km}$. Determine the length of the shortest closed route that covers each one-way street at least once.

A postal worker must deliver mail along three streets connecting intersections $A, B$, and $C$. The streets have lengths $AB = 5\text{ km}, BC = 5\text{ km}$, and $AC = 5\text{ km}$. Find the length of the shortest closed route that covers each street at least once.