How can I optimize this combination method?
I'd try to go with a different approach. At the moment you're evaluating all the possible combinations, while I think it could be useful to evaluate only the meaningful ones. To do that I'd start with a two phase approach. First you can generate all the valid fleets and then you can sort them using a comparator that takes into account their Range/Variance.

This is the code you can use to generate all the possible fleets:

private static IEnumerable&lt;Fleet&gt; PossibleVoyages(IList&lt;Captain&gt; captains, IList&lt;Crew&gt; crews, int voyagesToPrepare, Fleet fleet)
{
    var possibleVoyages = new List&lt;Fleet&gt;();
    if(voyagesToPrepare == 0)
    {
        possibleVoyages.Add(fleet);
    }
    if(captains.Count &lt; voyagesToPrepare || crews.Count &lt; voyagesToPrepare)
    {
        // We cannot find any valid solution here
        return possibleVoyages;
    }
    else
    {
        foreach(var captain in captains)
        {
            foreach(var crew in crews)
            {
                var newFleet = fleet.Add(CreateShip(captain, crew));
                possibleVoyages.AddRange(
                    PossibleVoyages(
                        FreeCaptains(captains, newFleet),
                        FreeCrews(crews, newFleet),
                        voyagesToPrepare - 1,
                        newFleet));
            }
        }
    }
    return possibleVoyages;
}


I have not implemented the methods FreeCaptains, FreeCrews, and CreateShip but they should be obvious. Fleet act as an immutable collection of ships.

Once you get all the possible voyages you can just sort them using a comparator and Linq sort.

I'm not sure this is going to help much, but it is worth giving it a try.
A possible way to improve it is to keep track of the best fleet we generated so far and to just compare it with every fleet we generate instead of doing all the comparisons at the end. This could possibly prune a lot of solutions once you find a good one and it is definitely worth trying.