/CVRP-GA

基于C++,使用遗传算法解决物流运输中的VRP问题

Primary LanguageC++

CVRP-GA

基于C++,使用遗传算法解决物流运输中的VRP问题

##1.导言 当今社会,随着像阿里,京东这样的电商巨头的崛起,我国的物流行业也变得空前的繁荣。特别是诸如淘宝双十一的日子里,更是达到了全民网购这种盛况。而随之而来的则是物流的运输问题。物流公司为了获得更高的利益,目标是在完成物流任务的条件下,通过合理的运输路径安排,使得使用最少的货车,运输的总里程也最少,货车利用率更高。而这也就是经典的CVRP问题。由于该问题为NP-hard问题,使用传统的算法较难解决,所以这里我们使用启发式智能算法中的遗传算法,去解决这个问题。

##2.实验过程 ####在使用遗传算法解决CVRP问题时,步骤如下:

  1. 输入要选择的数据文件,种群大小,遗传进化的代数。
  2. 读取数据文件,得到每个客户点的坐标、运载需求量,以及货车最大装载量。
  3. 按种群大小与客户数量,初始化种群。假设种群大小为100,有75个客户,初始化的方式为产生一个100 * 75的二维vector,然后对这100条染色体,每一条都产生一个1~75随机排序的数列。
  4. 算出种群中每一条染色体的适应度。具体方法是,从左往右遍历染色体,并在里面插入0(代表原点仓库)。每两个0之间,则代表一趟货车的运输路线。而插入的方法是多个0之间的距离尽量远,让每一趟货车经过的点尽量多,直至再加就要超过货车的载重。
  5. 根据每条染色体的适应度,求每条染色体累积概率。产生0到1之间的一个随机数,对轮盘转动种群大小的次数,选择下一代(或者转动种群大小-1的次数,最后一条染色体固定为当前最高适应度的染色体)。
  6. 进行遗传操作。与传统的交叉和变异的遗传方式不同,这里使用一种称为Inver- Over算子的遗传操作。具体步骤是设定一个变异概率p 。先在染色体中随机选择一个起始客户C,如C=5,。产生一个随机小数,若小于p,则第二个客户C’来自同一个个体的另外一个任意客户,如C’ =2,然后客户C与C’之间的部分被导致(不包括城市C);若小数大于p,则从种群中任意再选择一个染色体,找出C=5在该个体中,下一个位置客户的值,如下一个客户为9,则回到原来的个体,C’=9,客户5到9之间被导致(不包括C=5)。这种遗传的思路在于,它能尽量利用种群中获得的信息,来指引个体的变异或者导致操作,最后使得遗传算子比较高效。
  7. 判断当前迭代的代数。若迭代次数已够,则进入第8步,否则回到第4步。
  8. 输出迭代中,最高适应度染色体的客户排列情况,以及该染色体的运输花费。

##3. 程序运行 ####运行程序时,需要输入以下三样数据: 1.所使用的数据文件名字,如:"../tc/tai75a.dat" 2.种群大小,如: "300" 3.遗传迭代的代数,如:"10000"

程序运行的时间,取决于种群大小与迭代代数的大小,需要耐心等候。最终的最优解,将在程序最后输出。

##4.结果分析 ####在对第一个数据样本”tai75a.dat”进行测试时,采用种群大小为300,迭代次数为10000代得到最少花费为1955,目标值是1618,大概有300的差距;而当把种群大小设到500,然后迭代20万代,得到最少花费为1660,目标值是1618,大概只有40的差距。

Alt text Alt text