1
$\begingroup$

I am working on a fake-ish research proposal for an undergraduate "writing for engineers" course. I am currently exploring the idea of a graph theory problem which models damage to a network flow. The main idea being that nodes on the graph have some amount of demand for resources, but edge capacities have been restricted/damaged. An edge $e$ in this model has:

  • some capacity $c_e$ - amount of supply that can traverse the edge
  • some weight $w_e$ - time to traverse the edge
  • some repair cost $r_e$ - amount of man hours to increase capacity 1 unit
  • some max capacity $m_e$ - when capacity reaches this point, no further repairs are possible.

A vertex $v$ in this model has:

  • some amount of demand for resource $d_v$ - negative demand implies a source/supply.

The model works by simulation over discrete time intervals, say "hours". Each hour labor can be sent on a path towards a new edge, capacities are updated to reflect repairs,and unmet demand is recorded as $u_i$ for the $i^{th}$ hour.The problem is to minimize the $\sum_{i} u_i$ over the time it takes to restore all edges to maximum capacity.

My question is, does this sound remotely useful? Can anyone with experience in computer science / graph theory research point me in the direction of something that sounds remotely similar to this? Ultimately I am trying to construct an application of graph theory optimize aspects of recovering from a natural disaster.

$\endgroup$
  • $\begingroup$ You are actually seeking for some Stochastic Processes course final project. $\endgroup$ – Brethlosze Nov 24 '17 at 5:17
  • $\begingroup$ In my problem formulation I am presuming a lot of information is provided, while I see who most of the qualities of this graph should be supplied by a stochastic process, my focus is not in constructing the graph, but rather solving the optimization problem more or less how I stated it. $\endgroup$ – hulud Nov 24 '17 at 5:51
  • $\begingroup$ Well, if simulation is not the focus, but optimization, i see the problem is really direct to solve after formulating it. You should write both the constraints and the objective function in the standard way, and thus the solution will arise straightforwardly. This is very similar to a Markov Chain model. But clarify yourself in what is the focus... $\endgroup$ – Brethlosze Nov 24 '17 at 6:00
  • $\begingroup$ Such a solution would be completely intractable though no? The underlying problem is derivation of the facilities location problem which is known to be NP-hard. I suppose this question is too open ended for this setting, I am not really looking for a mathematical solution, but rather similar problems with a body of research around them into how the algorithmic complexity was managed, whether by heuristics / approximation or some other method. $\endgroup$ – hulud Nov 24 '17 at 15:29
  • $\begingroup$ Well i insist on the stochastic process systemic approach. Things as queues, waiting times, event times, event rates, are standard, no need to innovate in there. Some solvers for simulate systems are available too. IF you dont intend to do anything else, and do not have experience, that is your best choice. By the way saying that the problem is NPh dont add anything new.... most if not all models with discrete variables are. $\endgroup$ – Brethlosze Nov 24 '17 at 19:00
0
$\begingroup$

In case anyone stumbles into this ill conceived question, following is a list of relevant research on similar models to the one I describe. The relevant field I was looking for is coined humanitarian logistics, and seeks to model logistical problems in humanitarian crises effectively. The main challenge is constructing a model that is accurate enough to be useful, but not so complex as to be completely intractable in what can be extremely time sensitive decisions.

A mathematical model for post-disaster road restoration: Enabling accessibility and evacuation

A hierarchical compromise model for the joint optimization of recovery operations and distribution of emergency goods in Humanitarian Logistics

Are sort of two ends of the tractability spectrum for this problem. My particular ultimate goal is papers more in line with the approach in:

A Serious Video Game To Support Decision Making On Refugee Aid Deployment Policy

Where rather then heuristically guiding intractability, or attempting to simplify the model, aspects of the problem are pushed onto a human for decision making.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.