Problem $2.$

AOAcide is a chemical company that needs to transport two large shipments from two different locations to a production plant. The shipments have equal volume and contain the same chemical $($i$.$e$.,$ except for the origin location they can be considered indistinguishable$).$ The transport takes place through an urban area, and for safety reasons the routes should be as short as possible. Also, both shipments are delivered in a large container, and cannot be split into multiple smaller shipments.

A schematic map of the area is given below, indicating the possible route segments that can be taken. Nodes $1$ and $2$ correspond to the two points of origin. Node $P$ corresponds to the destination plant. All other nodes correspond to an intersection of two roads. An arc between two nodes corresponds to a road segment, and has an associated length in miles, as indicated in the figure. The Excel file problem set$3$ S$24$PT$.$xIsx lists all these segments and their lengths.

The area also contains a river $($indicated by the light grey curve$)$ that can be crossed by bridge or by a tunnel. The road segments $(5,8)$ and $(6,9)$ contain a bridge crossing the river, while the road segment $(7,10)$ contains a tunnel. For safety reasons, the city allows each bridge and tunnel to be crossed by at most one of the shipments. For example, the shipments cannot both traverse the road segment $(5,8).$ AOAcide wishes to determine a delivery route for both shipments with minimum total distance.

We will approach this problem as a network flow and formulate it using linear programming.

$1.)$ Complete the network by adding supply, demand, and any non$-$trivial lower or upper bounds.

$($The trivial bounds $0,$ are already assumed to be present and do not have to be added.$)$ We next formulate the linear programming model. As decision variables, we define $x_{ij}$ for every arc from node $i$ to node $j$ in the network.

$2.)$ What values can variable $x_{ij}$ take, and what does $x_{ij}$ represent, for an arc from node $i$ to node $j?$ Formulate the objective function and the flow conservation constraints for each node.

$3.)$ In addition to the flow conservation constraints, do we need any other constraints for a correct formulation of the problem? If so$,$ write them down here.