1
$\begingroup$

I'd like to optimize the flow of materials through a network. There are vertices (i.e. physical locations) and edges (i.e. links between the physical locations).

Inputs:

  • locations
  • transactional data: historic start-time, end-time, and cost for material movements between the locations
  • loss function (e.g. time, cost)

Outputs:

  • optimal path through the network in order to minimize loss
  • a distribution that describes the expected performance of that network configuration. This would be used to set service levels (e.g. 99% of materials will move from point A to point B in x hours)

The time and cost to move goods from one location to another has a stochastic element to it.

each vertex is a distribution

One link might be generally fast, but somewhat unreliable. Or perhaps it performs really well at certain times, and badly at other times. The optimal route through the network is dynamic and will vary according to the loss function.

The problem is similar to shortest path, except that its weights are probability distributions rather than single-point estimates. So given its similarity to a shortest path problem, it made some sense (to me, at least) to approach the problem as a graph, and hence use a graph database (e.g. it could potentially be framed as a bootstrapped version of this: http://iansrobinson.com/2013/06/24/cypher-calculating-shortest-weighted-path/).

Does this seem like a sensible approach? Are there other techniques/approaches/technologies I should consider?

$\endgroup$
8
  • $\begingroup$ I have trouble extracting a clear problem statement from the question. Can you elaborate more on what exactly is given? Do you know the network structure? In what way is it specified? What do you want to estimate? $\endgroup$
    – bayerj
    Oct 17, 2014 at 19:58
  • $\begingroup$ How do you propose to compare different distributions. What is the loss function here? You have to define your problem clearly before you start talking about what Java library you'll use to work with graphs. Depending on the details, this could be solvable with dynamic programming. $\endgroup$
    – Kirill
    Oct 17, 2014 at 21:04
  • $\begingroup$ Thank you both for the valuable feedback. I have edited the question in an attempt to state the problem more clearly. $\endgroup$ Oct 17, 2014 at 23:05
  • $\begingroup$ You might want to read up on some network flow algorithms $\endgroup$
    – bdeonovic
    Oct 18, 2014 at 0:14
  • $\begingroup$ Thanks @Benjamin. Looking through the list of network flow network algorithms, I did not see anything that's stochastic. And yet, I imagine that every company with a distribution network has a problem like this. I don't suppose they're all modeled with single-point estimates for weights. I half-expected there to be a common, off-the-shelf algorithm that everyone uses for this problem. I'll continue to do some Google research and may buy something like this: amazon.com/Supply-Chain-Network-Design-Optimization-ebook/dp/… $\endgroup$ Oct 18, 2014 at 15:37

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.