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

# 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的差距。