4
$\begingroup$

I am working on a project related to an emergency evacuation:

Find the minimum time to make $n$ people to evacuate the city (travel time of the slowest). There is 1 vehicle that can contain $p$ people and travel at the speed of the slowest person of the group. One person has to bring back the vehicle used for transportation.

This problem is a generalization to the bridge crossing / torch problem.

I found solution for $p \leq 2$ which comes down to sort the people by travel time and to iterate pairwise whether it is better for the pair of people to travel together using 2 runners or to travel separately using 1 runner.

I tried to adapt it for $p=3$ but things escalated quickly and I ended up with many strategies to compare for every group of 3 persons with 1, 2, 3 runners and could not find a way to generalize for $p \geq 3$.

$\endgroup$
  • $\begingroup$ If a recurrence relation cannot be found, it is likely that it is NP-hard if p is unbounded. If p is constant, it feels like there is a polynomial-time algorithm with respect to n. (It would be exponential with respect to p.) $\endgroup$ – user21820 Mar 28 '18 at 2:29
  • $\begingroup$ I am not entirely sure that I understand the problem---people cannot move unless they are in the vehicle? There is no walking out? Also, I am unfamiliar with "the bridge crossing / torch problem". Could you please explain the rules in a little more detail? $\endgroup$ – Xander Henderson Mar 28 '18 at 2:29
  • $\begingroup$ @XanderHenderson: en.wikipedia.org/wiki/Bridge_and_torch_problem $\endgroup$ – user21820 Mar 28 '18 at 2:31
  • $\begingroup$ @MaxFt The PDF at the bottom of the Bridge and torch problem Wikipedia page has a polynomial-time solution. Is checking references so hard? $\endgroup$ – dtldarek Mar 28 '18 at 9:23
  • $\begingroup$ @dtldarek Bridge and torch problem page from Wikipedia does not at all deal with my problem. Do not think any references deal with the problem of $p\geq 3$. If you find an article I would be grateful $\endgroup$ – Max Mar 28 '18 at 14:00
2
$\begingroup$

I would check out the paper The capacity-$C$ torch problem (behind a paywall) and this similar (same?) paper The Capacity-$C$ Torch Problem Full Version (including all proofs) (pdf) by Backhouse and Truong. Since the answer to your question is the subject of these research papers, it'd be tough to synthesize their algorithms into a response here, so I won't, but they appear to contain an algorithm that solves the question you are seeking to answer.

Abstract The torch problem (also known as the bridge problem or the flashlight problem) is about getting a number of people across a bridge as quickly as possible under certain constraints. Although a very simply stated problem, the solution is surprisingly non-trivial. The case in which there are just four people and the capacity of the bridge is two is a well-known puzzle, widely publicised on the Internet. We consider the general problem where the number of people, their individual crossing times and the capacity of the bridge are all input parameters. We present two methods to determine the shortest total crossing time: the first expresses the problem as an integer-programming problem that can be solved by a standard linear-programming package, and the second expresses the problem as a shortest-path problem in an acyclic directed graph, i.e. as a dynamic-programming problem. The complexity of the linear-programming solution is difficult to predict; its main purpose is to act as an independent test of the correctness of the results returned by the second solution method. The dynamic-programming solution has best- and worst-case time complexity proportional to the square of the number of people. An empirical comparison of the efficiency of both methods is also presented.

$\endgroup$
  • 1
    $\begingroup$ Thank you I am taking a look at it. It seems to be what I wanted ! I will see if I can understand the principles of the algorithms. $\endgroup$ – Max Mar 29 '18 at 15:48

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.