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 10-15, container of 15 units capacity can be allocated. The problem with this approach is that it will become sub-optimal as the nodes increase and clusters may not be accurate enough.

asked 12 Jan '12, 10:22

Pavan's gravatar image

Pavan
3002621
accept rate: 0%

edited 13 Jan '12, 05:29

2

How do you define reverse flow, can you give an example ?

(12 Jan '12, 10:25) Bo Jensen ♦

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.

(13 Jan '12, 06:31) Pavan

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), pick-up 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 lightly-filled 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.

(13 Jan '12, 09:10) Pavan

I think that this question could be interesting (and I would vote it up), but it needs to be asked more clearly.

(20 Jan '12, 11:22) Alan Erera

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 source-sink pair and each container size), then you need additional integer variables which represent how many containers of each type are used between each source-sink 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.

edit: from the additional problem description I gather that there is a VRP/pickup/delivery component (with a particular structure, the route seems to be a sequence of depot -- pickup1 -- delivery1=pickup2 -- delivery2=pickup3 -- etc.), and a bin packing component of the problem. edit: Having different classes of constraints like in this situation, a decomposition along the lines of Dantzig/Wolfe may be appropriate: eg., bin packing (and visit of each customer) in the master, routing constraints in the subproblem. This would lead to a column generation/branch-and-price approach to solve the problem. Afaik, all exact approaches to routing problems are based on decomposition techniques.

this relates to my previous question: again a set covering/packing master problem...

link

answered 13 Jan '12, 04:44

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

edited 13 Jan '12, 12:57

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 branch-and-price 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 pick-up and delivery. In a short web search, I found the following paper:

Vehicle Routing Problems with Simultaneous Pick-up and Delivery Services

It might be kind of old, but is somewhat a starting point to figure if that is your case.

link

answered 13 Jan '12, 06:52

Thiago%20Serra's gravatar image

Thiago Serra
1.2k413
accept rate: 1%

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:

Quantitative models for reverse logistics: A review

link

answered 13 Jan '12, 07:16

Thiago%20Serra's gravatar image

Thiago Serra
1.2k413
accept rate: 1%

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 (c-f) 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.

link

answered 12 Jan '12, 17:34

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Your problem is not well-defined, but I agree with others that you certainly do not have a pure single-commodity 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:

  1. Is this a single period problem where for example you simply need all "demands" executed in the period (say, a day or a week)?
  2. Are the routes traveled by trucks fixed, or are they also decisions?

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 partitioning-style approach.

link

answered 20 Jan '12, 11:21

Alan%20Erera's gravatar image

Alan Erera
1.0k37
accept rate: 12%

@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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×127
×14
×4

Asked: 12 Jan '12, 10:22

Seen: 46,209 times

Last updated: 01 Feb '12, 11:09

OR-Exchange! Your site for questions, answers, and announcements about operations research.