Hello everyone! Just a quick question  I am currently modeling a network flow problem and I would like to know how to model the reverse flow in the network. We have trucks with containers of various sizes and need to find the optimal allocation of containers of different sizes. The truck goes carries goods from source and drops it in sink, becomes empty and gets loaded again in sink and travels back to source. My initial approach was (we have the demand available at each node) to create clusters of demand  so that we can use the containers of different sizes to allocate in each of that respective cluster (for example, cluster 1 has range of demand from 1015, container of 15 units capacity can be allocated. The problem with this approach is that it will become suboptimal as the nodes increase and clusters may not be accurate enough. asked 12 Jan '12, 10:22 Pavan 
this is not a pure network flow problem; as you mention yourself you will need a means to decide about the allocation of flow to different containers. I would suggest modelling your problem as (mixed) integer program. You model a multicommodity flow (maybe one commodity for each sourcesink pair and each container size), then you need additional integer variables which represent how many containers of each type are used between each sourcesink pair (these integer variables are triggered by the amount of flow you send; I assume you pay the container, not the flow). You are right that flow is "traveling in the reverse direction", but in the model this "reverse flow" is not "the same" flow as the "forward flow", therefore I believe that the standard residual network approach of some flow algorithms (as suggested by Paul) will not work. You will need to introduce separate commodities for "forward" and "backward", and as I said, for the different container types as well.
answered 13 Jan '12, 04:44 Marco Luebbecke ♦ 1
the objective here is to allocate various containers in such a way that maximizes the load of container(not to worry about cost of container or cost of flow). Should I breakdown the problem into two different problems for forward and backward flows and use some sort of integer constraints to connect the flows? (I am just thinking out loud)
(13 Jan '12, 06:29)
Pavan
1
Could you please elaborate on why branchandprice is a good method to solve this? Thank you.
(13 Jan '12, 12:25)
NVA
done in an edit.
(13 Jan '12, 12:57)
Marco Luebbecke ♦

It seems to me that you are handling with a Vehicle Routing Problem (VRP) with pickup and delivery. In a short web search, I found the following paper: Vehicle Routing Problems with Simultaneous Pickup and Delivery Services It might be kind of old, but is somewhat a starting point to figure if that is your case. answered 13 Jan '12, 06:52 Thiago Serra 1
the "different container type" feature is not part of standard P&D problems, but this is a good starting point. I believe that exact solutions for the problem as mentioned are very rare (if any), I worked on a similar problem recently, and did not find a lot. so I assumed we start from scratch with the model anyway ;)
(13 Jan '12, 07:00)
Marco Luebbecke ♦
Despite how many VRP types exist, it is always possible to find a new variation (and yet the client will probably induce you to invent another one after you deliver yours).
(13 Jan '12, 07:21)
Thiago Serra
2
I think we still are guessing in the dark here, the model description is not clear to me. There should be a more detailed description by OP on the situation we are trying to model. I am not convinced it have to be a complicated model.
(13 Jan '12, 07:23)
Bo Jensen ♦
Sorry about not being clear, thing is I have been thinking about modeling reverse flow since yesterday, forgot to give clear explanation. Please have a look at my recent post, I made it quite clear.
(13 Jan '12, 09:12)
Pavan

I've found a review of models for reverse logistics, which consists of bringing products and materials back to the original source: answered 13 Jan '12, 07:16 Thiago Serra 
If by "reverse flow" you mean reducing an existing flow (for instance, in an incremental circulation that augments the current solution to a flow problem), the usual approach is to create an "auxiliary" or "augmented" network (not sure how standard the terminology is). Assuming the original network was directed, for each arc ((a,b)) in the original network with capacity (c) and current forward flow (fin [0,c]), the augmented network has an arc ((a,b)) with capacity (cf) and an arc ((b,a)) with capacity (f). If this results in duplicate arcs (for instance, if the original network had an arc ((b,a)) with no flow on it), you merge the arcs by adding their capacities. answered 12 Jan '12, 17:34 Paul Rubin ♦♦ 
Your problem is not welldefined, but I agree with others that you certainly do not have a pure singlecommodity network flow problem. Thus, you will likely need a MIP model. Beyond this, we need more clarification. It seems clear that you know at each node the weight (size) of goods that need to be transported to various destination nodes. Here is what is not clear:
Assuming fixed truck routes, I can certainly envision a MIP model which models the flows of the various container types on all truck route lanes. The container flows assigned to truck routes must be such that the trucks can move that combination of containers. Furthermore, the containers must have enough capacity to pack all of the shipments flowing on those lanes; this would be accomplished by a type of variable upper bound constraint that defines capacity on a lane based on the container flow on that lane. If the truck routes are not fixed, then you would also need to model the selection of truck routes, and this might be effectively done using a set partitioningstyle approach. answered 20 Jan '12, 11:21 Alan Erera @Alan Erera: Still in the process of getting more information by myself. PS: It does not feel comfortable to model when the Client contradicts on problem statement. Not sure if this happens for OR consultants across the globe.
(21 Jan '12, 23:00)
Pavan

How do you define reverse flow, can you give an example ?
I would like to believe this must be a common problem in logistics. There must have been some paper written on allocation problem with reverse flows.
The situation here is we have trucks with containers of various capacities. The containers are differentiated by the capacities (container 1 has capacity of 200 kg and container 2 has 300 kg, etc...).
Now we have demand in all the nodes, where in each node we have to take the container truck, deliver the load in one node (now it gets empty), pickup load from the SAME NODE and move to another node and repeat the same. We can attach more than one container for the truck (could be two or three)
The objective here is to find optimal allocation (number of containers to attach with the main truck) that maximizes the load in the containers. We do not want empty or lightlyfilled container (if the truck with 2 containers capacity is 600 kg, we deliver (with full capacity) it in other node and when our pick up load from OTHER NODE is only 2kg, then its loss for operating that transport to the company)  we need to maximize the load.
I think that this question could be interesting (and I would vote it up), but it needs to be asked more clearly.