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

时间:2022-05-10 16:42:39

需求为(自己编的,非实际项目):

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

  1. 现有车辆5台
  2. 单台运力最大行驶距离200千米
  3. 单台运力最大载重公斤1吨

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

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

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

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

蚁群主要步骤为:

  1. 初始化(如信息素)
  2. 开始迭代
    1. 构造各个蚂蚁,以及蚂蚁走的路径(核心是针对后续节点的SELECT)
    2. 计算适应度
    3. 加入优秀蚂蚁到跟踪列表
    4. 更新信息素(根据适应度)
  3. 结束迭代
  4. 给出报告

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

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

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

下载

class FitnessValueCalculator
{
private static int 拥有运力车辆数 = ;
private static int 单台运力最大行驶距离 = ;
private static int 单台运力最大载重公斤 = ;
private static double 惩罚权重 = ; public static double Calculator(ShortestDeliverAnt ant)
{
var paths = new List<string>(); var distances = new List<double>();
var weights = new List<double>(); double 当前行驶距离 = ;
double 当前运力载重 = ;
string 当前行驶路径 = "";
int 当前所需运力数 = ; //计算枢纽到第一个客户配送距离
当前行驶路径 += "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 = ;
double newAddedDistance2Hub = ;
double newAddedWeight = ; 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
当前行驶距离 = ;
当前行驶距离 += ant.DistanceHelper.hub.DistanceTo(toNode); 当前运力载重 = ;
当前运力载重 += 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,而且是越小代表越优越,因此碰到了需要惩罚的情况,实际就是大幅度的增加返回值(适应度值)
红色部分就是惩罚变量部分。 各种优化算法的核心写完框架后基本就不怎么变化了,最易变的其实是适应度函数的计算,如果适应度计算中用到了预测技术,还得在上面那函数里调机器学习的代码,感觉强化学习中动作施加后给出的反馈值也是这么个值

代码下载

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

揽货最短路径解决方案算法 - C# 蚁群优化算法实现的更多相关文章

  1. C&num; 蚁群优化算法实现

    C# 蚁群优化算法实现 需求为(自己编的,非实际项目): 某配送中心进行揽货,目标客户数为50个客户,配送中心目前的运力资源如下: 现有车辆5台 单台运力最大行驶距离200千米 单台运力最大载重公斤1 ...

  2. &lbrack;Algorithm&rsqb; 群体智能优化算法之粒子群优化算法

    同进化算法(见博客<[Evolutionary Algorithm] 进化算法简介>,进化算法是受生物进化机制启发而产生的一系列算法)和人工神经网络算法(Neural Networks,简 ...

  3. 揽货最短路径解决方案算法 - V2(增加了时间维度-客户允许的服务时间段,C&num;&sol;JAVA同步实现,带python作图)

    继上篇,这里改进增加了客户允许服务的时间范围这个维度,并且把C#版本翻译成java,加强了更加形象的图表展示路径(继续是用python的matplotlib作图). 这里的时间范围维度是指:每个客户都 ...

  4. MATLAB粒子群优化算法(PSO)

    MATLAB粒子群优化算法(PSO) 作者:凯鲁嘎吉 - 博客园 http://www.cnblogs.com/kailugaji/ 一.介绍 粒子群优化算法(Particle Swarm Optim ...

  5. 粒子群优化算法PSO及matlab实现

    算法学习自:MATLAB与机器学习教学视频 1.粒子群优化算法概述 粒子群优化(PSO, particle swarm optimization)算法是计算智能领域,除了蚁群算法,鱼群算法之外的一种群 ...

  6. 计算智能(CI)之粒子群优化算法(PSO)(一)

    欢迎大家关注我们的网站和系列教程:http://www.tensorflownews.com/,学习更多的机器学习.深度学习的知识! 计算智能(Computational Intelligence , ...

  7. 粒子群优化算法&lpar;PSO&rpar;之基于离散化的特征选择&lpar;FS&rpar;(二)

    欢迎大家关注我们的网站和系列教程:http://www.tensorflownews.com/,学习更多的机器学习.深度学习的知识! 作者:Geppetto 前面我们介绍了特征选择(Feature S ...

  8. 粒子群优化算法&lpar;PSO&rpar;之基于离散化的特征选择&lpar;FS&rpar;(一)

    欢迎大家关注我们的网站和系列教程:http://www.tensorflownews.com/,学习更多的机器学习.深度学习的知识! 作者:Geppetto 在机器学习中,离散化(Discretiza ...

  9. 【CI】CN&period;一种多尺度协同变异的微粒群优化算法

    [论文标题]一种多尺度协同变异的微粒群优化算法 (2010) [论文作者]陶新民,刘福荣, 刘  玉 , 童智靖 [论文链接]Paper(14-pages // Single column) [摘要] ...

随机推荐

  1. PHP5&period;3、PHP5&period;4下安装ZendOptimizer或Zend Guard Loader的方法

    现在很多PHP程序都需要ZendOptimizer环境,但是ZendOptimizer在PHP5.2之后已经被支持,那怎么办,Zend也不会这么做,原来PHP5.3开始ZendOptimizer正式改 ...

  2. Adaptive Backgrounds – jQuery 自适应背景插件

    Adaptive Backgrounds 是一款很特别的 jQuery 插件,可以从图像中提取主导颜色并将它应用到它的父元素.这个插件利用 Canvas 元素和 ImageData 对象.需要注意的是 ...

  3. BZOJ3236&colon; &lbrack;Ahoi2013&rsqb;作业

    Description Input Output Sample Input 3 4 1 2 2 1 2 1 3 1 2 1 1 1 3 1 3 2 3 2 3 Sample Output 2 2 1 ...

  4. ecshop 调用指定分类的推荐&comma;热卖&comma;新品

    未测试 1.includes/lib_goods.php文件.把SQL语句改一下,与category表关联即可 将 $sql = 'SELECT g.goods_id,g.goods_name, g. ...

  5. swift3&period;0基础语法

    swift 3.0 基础语法 目录 01-变量和常量 02-运算符 03-可选项 04-条件语句 05-循环 06-字符串 07-元组 08-数组 09-字典 10-对象和类 11-枚举 12-属性 ...

  6. 使用Ctex总结1

    使用Ctex应该是每一个做学术研究的人要学会掌握的. 它的基本结构: \documentclass[11pt,two side,a4paper]{cctart}%使用cctart可以让摘要变成中文,比 ...

  7. IEqualityComparer&lt&semi;T&gt&semi;接口

    IEqualityComparer<T>接口的对象的主要作用在于自定义判断两个对象是否相等. 其中最常用的方法: bool Equals(T x, T y); 实现该方法用于比较两个对象是 ...

  8. MongoDB数据库安装及配置环境终极教程&lpar;windows10系统&rpar;

    本文是笔者花时间踩坑踩生气了写出来的!转载请注明出处@http://www.cnblogs.com/tim100/!请尊重我的劳动成果!谢谢! 今天,给大家说说在windows10系统下MongoDB ...

  9. 经典面试题:从 URL 输入到页面展现到底发生什么?

    前言 打开浏览器从输入网址到网页呈现在大家面前,背后到底发生了什么?经历怎么样的一个过程?先给大家来张总体流程图,具体步骤请看下文分解! 本文首发地址为GitHub 博客,写文章不易,请多多支持与关注 ...

  10. 【OCR技术系列之七】端到端不定长文字识别CRNN算法详解

    在以前的OCR任务中,识别过程分为两步:单字切割和分类任务.我们一般都会讲一连串文字的文本文件先利用投影法切割出单个字体,在送入CNN里进行文字分类.但是此法已经有点过时了,现在更流行的是基于深度学习 ...