How to model a simple routing problem using nodes and arcs

Question

I have the following problem.

I have a route which begins at node $0$. I want to begin and end in $0$ which is a depot.

Now in this route even customer will be visited in order for example customer 2 will be second, customer 4 the fourth, customer 6 will be the sixth.

However I can visit the odd label customers in any order I please.

So for example if we have n=5 customers one possible tour is (0,1,2,3,4,5,0) or (0,5,2,1,4,3,0) or (0,3,2,1,4,5,0) or some other combination.

If have n=6 customers We have (0,1,2,3,4,5,6,0) or we have (0,3,2,1,4,5,6,0) as another possibility

You want to chose the position for the odd labeled customers to complete the tour at the min cost We assume we know $d_{ij}$ between each pair of customer and between the depot and customers.

Formula this problem as a min cost network flow.

I am not sure how do this. I know we start at 0 and for $n=5$ we can visit 1,3,5 first the second node you must visit is 2 but I am not sure how you get the min distance.

Answer 1

You can formulate this as a linear assignment problem in a bipartite network, which you can think of as a minimum-cost network flow problem with a supply of $1$ for the "left" nodes and a demand of $1$ for the "right" nodes. The left nodes correspond to the odd customers, and the right nodes correspond to the odd positions. The cost of assigning customer $2i+1$ to position $2j+1$ is $d_{2j,2i+1} + d_{2i+1,2j+2}$.