MATLAB实现遗传算法求解路网路由问题

1.路网路由问题简介

路网路由问题实际上可以理解为在一个城市里面存在如下图所示的一个路网，找一条最短的路径从一个节点到另一个节点。

目标函数（最小化路径总成本）

其中：

决策变量

• xij∈{0,1}：若边 (i,j)在路径上，则 xij=1，否则为 0
• A是所有边的集合
• cij是边 (i,j)的权重（如距离、时间等）

约束条件

(1)无重复访问约束（每个节点最多进入/离开一次）

(2)子环消除约束（MTZ约束，防止路径成环）

2.遗传算法求解路网路由问题的思路

采用遗传算法随机产生一个1到N随机排序的排序编码S0,通过一种设计一种递归算法转换为一个可行路径S,使得路径S满足约束(1)和(2). 总体流程如下:

3.程序代码截图

4.程序结果

遗传算法优化得到的最优目标函数

bestValue =

   10.5320

遗传算法优化得到的最优染色体

bestChrom =

  列 1 至 18

    11     1     4    24     8    12    21    14    23    17     6    13     3    22    15    20    10    18

  列 19 至 25

     7     9    25    16     5     2    19

>>