揽货最短路径解决方案算法-C＃蚁群优化算法实现

需求为（自己编的，非实际项目）：

某配送中心进行揽货，目标客户数为50个客户，配送中心目前的运力资源如下：

现有车辆5台

单台运力最大行驶距离200千米

单台运力最大载重公斤1吨

问：运力怎样走法才能以最低的成本完成针对这50个客户的揽货行为

是个最优化问题（运筹学），我们只考虑简化后的模型，不考虑路面交通、时间窗口这些复杂计算，用蚁群优化算法来实现接近最优解的计算。

关于蚁群优化算法的理论请看这篇文章：https://www.cnblogs.com/asxinyu/p/Path_Optimization_Tsp_Problem_Ant_System_CSharp.html

里面的基本算法已经写明了，也有demo，本文是针对如何适应到具体业务的介绍（本文用的蚁群核心代码也是上文中改来的）

蚁群主要步骤为：

初始化（如信息素）

开始迭代

构造各个蚂蚁，以及蚂蚁走的路径（核心是针对后续节点的SELECT）

计算适应度

加入优秀蚂蚁到跟踪列表

更新信息素（根据适应度）

结束迭代

给出报告

原文章里用的是TSP做DEMO，比较难看清楚如何应用到实际业务逻辑中

同样的，最困惑的核心中的核心，类似遗传算法，也是适应度值的计算，有的地方是一步一步增加vlaue，比如单纯距离的增加，但是复杂点的都没法这么操作，而是要看整体路径的指标（包括惩罚等）

由于蚁群优化算法和本文代码都能下载，所以只介绍适应度value的计算

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();

var distances = new List();

var weights = new List();

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.需求量_公斤;

当前行驶路径 = "";

当前行驶路径 += "HUB-->" + toNodeId;

当前所需运力数++;

}

}

//回到枢纽

当前行驶距离 += ant.DistanceHelper.customers[ant.PathNodes.Last()].DistanceTo(ant.DistanceHelper.hub);

distances.Add(当前行驶距离);

当前行驶路径 += "-->HUB";

paths.Add(当前行驶路径);

int 惩罚系数 = 0;

if (当前所需运力数 > 拥有运力车辆数)

惩罚系数 = 当前所需运力数 - 拥有运力车辆数;

ant.运输距离顺序 = distances;

ant.运输路径 = paths;

ant.Total行驶距离 = distances.Sum();

ant.Total运力数 = 当前所需运力数;

return ant.Total行驶距离 + 惩罚系数 * 惩罚权重;

}

}

ant.DistanceHelper.hub: 是配送中心的info，有地址信息

ant.DistanceHelper.customers: 是50个客户的info，也有地址信息

目前为了简化，是以街道距离来计算距离的

目前代码只是单目标优化算法，非多目标优化，后续研究研究再发文。

上述代码其实就是第一辆车从配送中心开出到第一个客户位置，然后加上客户需求（揽的货物重量）

接着判断能否开到下一个客户那里揽货，如果里程、重量都在限制条件只能，就开过去，不满足条件就开回枢纽；然后继续判断第二辆车，也是这么个逻辑

最终车辆的数量就是完成这50个客户揽货所需的运力数

万一碰到所需运力超出了限制（代码中为5辆车），这时就需要惩罚，由于最终函数返回是double，而且是越小代表越优越，因此碰到了需要惩罚的情况，实际就是大幅度的增加返回值（适应度值）

红色部分就是惩罚变量部分。

各种优化算法的核心写完框架后基本就不怎么变化了，最易变的其实是适应度函数的计算，如果适应度计算中用到了预测技术，还得在上面那函数里调机器学习的代码，感觉强化学习中动作施加后给出的反馈值也是这么个值

原文：https://www.cnblogs.com/aarond/p/ant_wuliu.html