I need some help finding references to solutions to this problem. This is the basis of a real-world application I'm working on, rather than an academic problem.

There are 4 main objects:

  • Water (litres)
  • Producer (location)
  • Consumer (location)
  • Carrier (water).

Consumers can order water. A carrier will collect it from the producer (if necessary) and deliver it to the consumer. Everything has a cost associated with it. Each producer has its own price. The carriers charge per KM (like a taxi). A carrier may already have enough water for a particular order. There are thousands of carriers, hundreds of providers, and millions of consumers.

I'm trying to design a system that optimises cost, time, and distance travelled.

A major complicating factor is the cost of running the algorithm. I need to find real driving distances for the carriers and getting them is expensive, both in real money and time, because I have to use the google maps API to find this and the carriers are constantly moving so I can't cache their location for more than a few minutes. I need to prune away most of the potential solution space with a heuristic before examining a few candidate solutions in detail. I will have the ability to calculate basic straight line (great circle) distances without an API call, but driving distances only available via API.

My first attempt is:

when an order is received,
 find any carriers with sufficient water within a given distance (a) of consumer (line of sight)
 if carriers found
   for each carrier, calculate driving distance and cost
   find all providers within given distance (b) of consumer (line of sight)
   for each provider, find all carriers within given distance (c) of provider (line of sight)
   for each carrier, calculate sum of distance to provider and then to consumer along with costs
 select carrier with lowest cost and engage

I can then optimise given distances a, b, and c. I can prune the graph a little if I only allow a carrier to be associated with its closest producer.

This is only the first generation of the problem. I want to extend it with carrier capacity so that I can potentially batch orders, but then I have to solve the travelling salesman problem too.

So, does anyone know of any prior art that comes close? I've looked in detail at taxi algorithms, and they don't come close to this level of complexity. I've looked at travelling salesman, but this is in a different class. I've also thought that maybe I don't need an algorithm but should do this with an AI but unfortunately, I don't have the math skills to even get started with that.

  • Actually, the Google API is free for 150k requests. A rough calculation suggests that with an un-pruned search space I'll hit that limit in a day in a single country. – Software Engineer Nov 18 at 22:22
  • Thanks for the 'fuel truck dispatching' reference. That looks like it might yield some useful info :) – Software Engineer Nov 18 at 22:23

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.