Background Information

I am currently doing research for my final year project in college. I am planning on building an ambulance booking system that will ease the process of booking an ambulance for patient transfer - that is to transfer a patient from one hospital to another.

A subsystem of the overall booking system will be a broker system. This will select the optimal ambulance company of n number of companies based on a number of hard constraints:

  • Price
  • Capacity
  • Average time to transfer a patient (this will be calculated over time)
  • Is it active at this current time (some companies only run during the day)
  • Type of ambulance (normal or cardiac)

Edit: This list of constraints is expected to grow as I further my research on the problem. For example since I first this question I have added a new constraint:

  • Urgency (Is the situation urgent or can we be lenient with time)

Choice of Algorithm

The problem I am having is that I do not know what type of algorithm to use. I was just going to use a brute force search but my supervisor said the performance of that algorithm will decrease exponentially as the number of companies and hard constraints grow.

I have been searching Google and Google Scholar to find possible algorithms to use but so far I have had little luck. Can anybody suggest some algorithms to look up? Relevant links/resources would also be appreciated.

  • 1
    $\begingroup$ Your title says "growing no. of constraints" your description suggests otherwise. Please clarify. $\endgroup$ – PleaseHelp Nov 2 '14 at 18:35
  • 2
    $\begingroup$ Anyway, Your constraints can be represented through a database. You could write a query that eliminates non-available ambulances [3rd and 4th constraint and probably 2nd constraint too] and then on that table you could apply your algorithm - which would depend on how would you[or patient?] decides the trade-off between price and average time. $\endgroup$ – PleaseHelp Nov 2 '14 at 18:49
  • 2
    $\begingroup$ Why would a brute force search take exponential time? What are you searching over? If you're looking to simply select one company, then you'd just need to evaluate each company, check the constraints, and remember the lowest cost company you've seen so far. If there are n companies and m constraints, that'd take O(nm) time. Hardly exponential. $\endgroup$ – Tom van der Zanden Nov 2 '14 at 22:39