Heavily stuck on a graph task

Question

You have a graph with K ports and N cities, there are M ships in each port which carry X load units each (all of them are fully loaded at the beginning and can't reload at any time and all of them carry the same quantity of cargo). Every city needs some amount of cargo (may need the same amount, may not - depends on the input) and a ship can only unload its cargo in a city if it fulfills the city's whole needs (i.e. if a city needs 10 units of cargo, you can't unload 7 from one ship and 3 from the other - either one supplies all 10 units or it has no business of stopping there).

Every port is connected to every other port and every other city (cities are also connected with each other - basically everything is connected with everything) and you know the distance from each point to any other. What is the minimal cost (sum of the distances) all the ships must traverse and what are their respective routes if all the cities have to have their needs fulfilled and each ship has to end its journey in the same port that it started from?

That's a task I'm working on as a way of sharpening my problem solving skills. I thought about a greedy approach of choosing the closest cities and then going to the closest ones first but this falls short on a simple case like (suppose there is one ship in each port):

C1 <--11km--> P1 <--10km--> C2 <--10km--> P2 
where P are ports and C are cities 
(There should also be direct edges from C1 to C2 or P1 to P2 for example 
but I omitted them for clarity - let's just assume here all the verices
lie on the same line and so we could ignore them)

cause the ship from P1 will go to C2 thus making the route to C1 longer while the optimal solution would be for it to go to C1 which lies farther and let the ship from P2 handle C2. What is a correct way of solving this, then? Or maybe it's NP-complete and there's none? I tried thinking about it in terms of TSP, for example, but it's not too similar cause you don't look for Hamiltonian cycles here.

Answer 1

Your problem is NP-hard as can be seen as follows. Imagine you have two ports where you have 2 ships at one port and as many ships as you want at the other port, and the cost of travelling from the first port to any city is basically zero and the cost of travelling from the second port to any city is very large. Also imagine the cost of travelling from any city to another is very small. Suppose the ships each have cargo capacity M and the total cargo demand of the cities is 2*M. Then you want to split the cities into two sets where the total demand of each set of cities is M, so that you can use the two ships of capacity M that have cheap travel cost from the first port. Otherwise you have to use the other ships from the other port as well and incur a very large travel cost. However, finding a split of a set of numbers into two disjoint sets that have the same sum is an NP-complete problem. Thus your problem is NP-hard.

Thus, heuristics or brute force are probably your best way to go.

Answer 2

Ok, so I think you could do this with an A* state space search algorithm. It's similar to Dykstra's shortest path, but uses a heuristic function on the nodes.

I think you can model one ship journey as an edge on the graph, and each node will contain your info on where each ship is, how much cargo it has, and how much cargo has been delivered to each city.

State node:
  List of ships
  List of cities

Ship:
  Cargo Capacity
  Current Location

City:
  Cargo Delivered

So above is just data to be stored for each state. Other data like a ship's home city, or how much total cargo a city needs, cannot be changed by actions, and so it's not part of the state, it's just useful background information.

An edge on the graph would be an action of moving a ship and delivering cargo if it's a city. The edge weight would just be the distance between cities.

You are also going to have to make that heuristic function that gives a sort of fitness value for each state. We want a low fitness value to be good, and high to be bad. One idea that comes to mind for the heuristic is to look at the amount of cargo still needed at all of the cities added together, plus perhaps add 1 for each ship not at its home port. This heuristic is not consistent or admissible, I don't believe. It's sort of a fitness function.

Another heuristic option is to count the not-fully-supplied cities, and add the number of ships not at their home harbor. This heuristic would be admissible (never estimates higher than the actual cost), but I'm not sure if it would be better. There are a lot of ways you could go on the heuristic.

Then the other main thing you need is an Expand(Node n) function that gives you all of the possible successor states based on all the possible actions you could take.

Whatever heuristic you use, you should make it return zero if you are at the goal state. So if all cities have their cargo, and all ships are at their home port, it will return zero.

Then you just run it through a standard A* search! Here's the Wikipedia page for that, if you're unfamiliar with it. I'm sure there are lots of other good resources for learning it too. Let me know if you'd like some more explanation of the A* algorithm part of the problem. http://en.wikipedia.org/wiki/A*_search_algorithm

You have all the building blocks once you cover the things I mentioned: representation of a state, background information your heuristic function can access, a heuristic function which also checks for the goal state, and an expansion function that gets successor states based on possible actions, that computes edge weights using the background data. Now you just use those few building blocks in your implementation of the A* search algorithm, and bam, you have a good solution. Keep in mind that it may not provably be the optimal solution, and may not be guaranteed to find a solution. I believe the properties of your heuristic function (is it admissible and/or consistent?) will determine whether a solution or the optimal solution are guaranteed.