揽货最短路径解决方案算法 - C# 蚁群优化算法实现
需求为(自己编的,非实际项目):
某配送中心进行揽货,目标客户数为50个客户,配送中心目前的运力资源如下:
- 现有车辆5台
- 单台运力最大行驶距离200千米
- 单台运力最大载重公斤1吨
问:运力怎样走法才能以最低的成本完成针对这50个客户的揽货行为
是个最优化问题(运筹学),我们只考虑简化后的模型,不考虑路面交通、时间窗口这些复杂计算,用蚁群优化算法来实现接近最优解的计算。
class FitnessValueCalculator { private static int 拥有运力车辆数 = 5; private static int 单台运力最大行驶距离 = 200; private static int 单台运力最大载重公斤 = 1000; private static double 惩罚权重 = 20; public static double Calculator(ShortestDeliverAnt ant) { var paths = new List<string>(); var distances = new List<double>(); var weights = new List<double>(); double 当前行驶距离 = 0; double 当前运力载重 = 0; string 当前行驶路径 = ""; int 当前所需运力数 = 1; //计算枢纽到第一个客户配送距离 当前行驶路径 += "HUB-->" + ant.PathNodes.First(); 当前行驶距离 += ant.DistanceHelper.hub.DistanceTo(ant.DistanceHelper.customers[ant.PathNodes.First()]); 当前运力载重 += ant.DistanceHelper.customers[ant.PathNodes.First()].需求量_公斤; foreach (var path in ant.Edges) { var fromNodeId = path.Key; var toNodeId = path.Value; var fromNode = ant.DistanceHelper.customers[fromNodeId]; var toNode = ant.DistanceHelper.customers[toNodeId]; double newAddedDistance2Customer = 0; double newAddedDistance2Hub = 0; double newAddedWeight = 0; newAddedDistance2Customer = fromNode.DistanceTo(toNode); newAddedDistance2Hub = toNode.DistanceTo(ant.DistanceHelper.hub); newAddedWeight = toNode.需求量_公斤; if (当前行驶距离 + newAddedDistance2Customer + newAddedDistance2Hub <= 单台运力最大行驶距离 && 当前运力载重 <= 单台运力最大载重公斤) { 当前行驶距离 += newAddedDistance2Customer; 当前运力载重 += newAddedWeight; 当前行驶路径 += "-->" + toNodeId; } else { //加当前客户距离、以及回到HUB的距离 当前行驶距离 += fromNode.DistanceTo(ant.DistanceHelper.hub); distances.Add(当前行驶距离); weights.Add(当前运力载重); 当前行驶路径 += "-->HUB"; paths.Add(当前行驶路径); //RESET 当前行驶距离 = 0; 当前行驶距离 += ant.DistanceHelper.hub.DistanceTo(toNode); 当前运力载重 = 0; 当前运力载重 += toNode.需求量_公斤; 当前行驶路径 = ""