CODEWITHSUNDEEP
c#performancealgorithm
João Dias
João Dias

Reputation: 238

How can I optimize this crew scheduling combination method?

I have this method that is working perfectly fine, but it's very slow, and sometimes I have to wait 15 minutes to get a good result, which is ok, but I'm wondering if I can make it faster.

Basically I'm running best fleet simulations, and I pre-calculate the possible ship combinations for specific voyages, but then I have to get the best fleet combinations for multiple voyages.

Obviously I can't use the same captain or crew in different ships because the voyages take place at the same time, and that's why there's some more conditions in each inner loop.

Any help or directions would be much appreciated.

private static Ship[] GetBestFleet3(IList<Voyage> voyages)
{
    var totalRate = 0;
    var previousStdDev = 100.0;
    Ship[] fleet = null;
    foreach (var ship0 in voyages[0].Ships)
    {
        foreach (var ship1 in voyages[1].Ships.Where(s => s.Captain != ship0.Captain && !s.Crew.Intersect(ship0.Crew).Any()))
        {
            foreach (var ship2 in voyages[2].Ships.Where(s => s.Captain != ship0.Captain && s.Captain != ship1.Captain && !s.Crew.Intersect(ship0.Crew).Any() && !s.Crew.Intersect(ship1.Crew).Any()))
            {
                var stdDev = Statistics.Variance(ship0, ship1, ship2);
                if (ship0.Rate + ship1.Rate + ship2.Rate > totalRate || ship0.Rate + ship1.Rate + ship2.Rate == totalRate && stdDev < previousStdDev)
                {
                    totalRate = ship0.Rate + ship1.Rate + ship2.Rate;
                    previousStdDev = stdDev;
                    fleet = new[] { ship0, ship1, ship2 };

                    if (ship0.Rate >= 100 && ship1.Rate >= 100 && ship1.Rate >= 100)
                    {
                        return fleet;
                    }
                }
            }
        }
    }
    return fleet;
}

Upvotes: 1

Views: 203

Answers (1)

Seanny123
Seanny123

Reputation: 9346

Right now you're doing an exhaustive search (from what I see from your nested for-loops, I'm a little unclear on how the code is running) of fleet-captain combinations, which judging by your run-time is a large search space. If you want something that runs faster, but is not guaranteed to give you the optimal solution, you might want to take a look at meta-heuristic algorithms such as Tabu Search, Simulated Annealing or Genetic Algorithms. I wouldn't recommend Ant-Colony Optimization, because I'm not sure how to translate this into a graph and a friend of mine who did the same type of problem (planes and pilots) didn't see it perform very well.

For research in this direction check out the following papers:

  • Simulated annealing for the multi-objective aircrew rostering problem
  • Multiobjective Genetic Algorithm to Solve the Train Crew Scheduling Problem

Alternatively, you might want to look into parallelizing the exhaustive search, but then the question would be better suited for CodeReview.

Upvotes: 1

Related Questions