Reasonable neighbours for a bees algorithm on a not-complete digraph

Question

I am trying to solve an optimization problem for a graph, where basically there is a cost for transporting "package" over a single edge, and I have multiple sources and destinations for multiple "packages". As the initial solution I take just the shortest path for each package, but eventually I would expect the algorithm to merge some of the paths, because transporting multiple packages on a single edge is generally cheaper than transporting them through different edges.

EDIT: The whole graph is a connected component so all vertices are reachable.

I am using the bees algorithm, where I have sourced my pseudocode from wikipedia: https://en.wikipedia.org/wiki/Bees_algorithm

Sadly, the algorithm does almost no improvements. I believe this is because of a poor choice of the neighbourhood function. The biggest problem is the fact, that the graph is not complete and all the paths can only use existing edges.

Here are the ideas for a neighbourhood of size s <- (0, 1], where the number of paths in the system is N:

• Pick s/2*N paths, for each path randomly increase the cost of one of the edges on the path to a really high value, and find the shortest path again, restore previous cost.
• Pick s/4*N pairs of paths, for each pair: select a random vertex on one of the paths, then force both paths to go through this vertex (so shortest path from source1 -> selected_vertex -> target1 and source2 -> selected_vertex -> target2).
• Pick s/4*N paths, increase the cost of every edge on the path to three times its previous value, find another path in the new graph, then restore previous weights.
• Pick s/4*N paths, and ensure all of those paths go through a randomly selected vertex.

For each neighbourhood generation i randomly pick one of the aforementioned methods.

Sadly, this neighbourhood function, along with following algorithm setup:

• 10 scout bees
• 3 elite sites / 5 forager bees each
• 4 best sites / 2 forager bees each
• patch size starts at 1.0 and gets reduced by 0.1

Tends to yield very poor result. The whole cost function looks more like a random noise. (The image looks the same kind of noisy after 1500 iterations).

I believe those poor results arise from the usage of bad neighbourhood functions. To the best of my research, I was not able to find a paper or article describing better methods of neighbour generation. How can I come up with better neighbours? Any help would be appreciated.

Answer 1

transporting multiple packages on a single edge is generally cheaper

How much cheaper?

Transporting a package over a longer path i order to share an edge will only help if the cost saving from sharing is greater than the extra expense of going over a longer path.

So what is the ratio of

sharing cost saving / cost of extra edge in path

If this is less than 1 in most cases, then you cannot expect any optimization to be successful, no matter how you organize your neighbors.