本小节的建模类型属于0—1整数非线性规划模型，该模型中的部分变量为整数，并且在模型中选择路段的参数和选择哪种运输方式与运输总成本之间存在非线性关系，这类模型多应用于处理实际问题中的运输网络设计，电力的调度以及NP难题。这类模型的求解难度较大，由于模型中的多种变量关系为非线性，如果采用精确算法如分支定界算法求解，这对于变量较多的模型会产生2n次变量分支，十分耗费时间，所以目前该模型多采用启发式算法进行求解，启发式方法的优势是可以利用不同的原理对模型的可行解进行快速搜索，虽然启发式算法的最终解只是将解得取值缩小到一定范围内，但启发式算法得到的解都为可行解，并且可以通过其他方法进一步对启发算法进行改进，优化其求解能力，使解更加精确。
1）Dijkstra算法
Dijkstra算法又称迪杰斯特拉算法，用于求解最短路径问题。该算法适用于已知起终点的网络图，其原理为从网络起点处出发搜索与起点相连的线路，根据所连线路的权值大小选择最小的那条线路，则该线路所连接的下一个节点与起点共同构成研究节点集，并搜索该节点集所连接的路线中权值最小的那个，把下一节点也并入到研究的节点集中，这样一直搜索下去，直至将终点也并入到研究节点集中，运算终止，则在搜索过程中所选择的路线为最短路线。
这个算法适用于解决单一目标模型，也可以对多目标线性模型求解，方法是将多目标模型根据变量之间的关系转为单一目标模型，再运用该算法进行求解。
本小节的目标模型为混合整数非线性优化模型，用该算法并不能求其最优解，但是本小节可以借用其算法原理对遗传算法可行解范围的限制来改进遗传算法，从而取得更精确的解。
2）遗传算法
遗传算法（Genetic Algorithm，GA）是一种来源于生物进化过程的计算机模拟研究。该过程通过模仿染色体的遗传原理，将可行结果不断地进行选择、交叉、变异等过程寻找问题的解。该算法虽然无法求得最优解，但通过一系列的生物遗传过程，大大缩减了可行解的范围，形成局部最优解。目前很多学者通过糅合其他启发式算法对遗传算法进行了改进，希望能进一步缩小解集。遗传算法流程如图5-12所示。
图5-12 遗传算法流程
2. 问题算法
内陆型集装箱中心站中欧班列腹地货源运输组织模型的求解思路为运用Dijkstra方法求得的解作为遗传算法终止运算的判断条件，以Dijkstra方法对遗传算法解的值域进一步缩小为目标，从而优化遗传算法，提高遗传算法精确性。
从上述分析可知，本小节将模型的求解分为两部分。第一部分的取值直接关系到本小节模型的求解结果。本小节采取的思路是根据研究网络符合已知终点从货源地构建网络结构的特点，采用类似Dijkstra的原理，遍历每个货源点附近的线路，并选择合适的运输方式，来完成网络的规划，并将该规划结果带入本小节的模型中从而计算出整个网络的成本；第二部分运用遗传算法进行求解，并用第一部分求得的解作为遗传算法的终止条件，以实现对遗传算法的改进。
1）Dijkstra算法
Dijkstra算法原理如图5-13所示。
图5-13 Dijkstra算法原理
根据前文描述可知，集装箱的运输价格一定程度上与运输距离呈正相关关系，因此可以通过搜索最低运价来实现对运输网络的优化，具体操作如下。
Step1：分别比较每个货源点
vi（i=1，2，3，…，21）(www.daowen.com)
到枢纽点wj（j=1，2，3，4，5）的不同运输方式价格，选择较小的那个。
Step2：分别比较每个货源点
vi（i=1，2，3，…，21）
以及枢纽点wj（j=1，2，3，4，5）到目的点d的不同运输方式价格，同Step 1一样，选择较小的那个。
Step3：利用Dijkstra原理，以货源点v1为例，根据上述所求价格选择离货源点v1最近的枢纽点wj（j=1，2，3，4，5），每两个点间只能选择一个值，按此方法对每个货源点vi依次进行线路选择，最终到达目的点d。如此对每个货源点求解，最终得到一个完整的运输网络。
Step4：将该运输网络带入建立的模型中，并求得最终解，作为模型的初始解。
由上述步骤可知，经过这种精细化的搜索分配，对于网络中的每个货源点来说，会找到最佳的运输路线及运输方式，但是网络中的成本并不是由这些路线的成本加和而得，网络成本还包括所有线路的固定成本及中转成本，这三者之间相互影响共同决定网络运输成本。所以该部分所得的初始解往往不是模型的优解。
2）改进的遗传算法
本小节将问题的求解分为两部分：第一部分假设一个运输价格，在此价格下对运输网络进行优化配置，此部分在于寻找合适运输路径，优化包括固定成本、运输成本及中转成本在内的整体运输网络成本。第二部分，对第一部分得出的运输网络进行运输方式的配置选择，并求解模型。遗传算法要素设计流程如图5-14所示。
图5-14 遗传算法要素设计流程
Step1：编码。本小节的编码分为两段，前一段分是对网络图中节点间的连线进行编码，另一段是对每段线路的运输方式进行编码。本小节只对网络图中有效的线路进行编码，即所有货源点到枢纽点、货源点到目的点及枢纽点到目的点的线路进行十进制整数编码。而每段线路的运输方式有两种：公路和铁路，分别用1、2来表示。该运输线路的编码方式如1—2—1—1，其中每一个数字都代表每一个运输路段选择的运输方式，假设运输路段有n条，则组合方式有2n个。
Step2：初始种群设计。网络节点间的染色体1~n个线路段采用随机排列的方式生成，但是要保证编码的第一个数字属于货源点线路段的集合R1，染色体最后一位基因数字是在目的点线路集合R0。运输方式的编码采用随机生成的方式。
Step3：适应度函数设计。本小节两部分求解均为最小值求解，所以此处将适应度函数设为
，为求解模型的目标函数的倒数。
Step4：遗传算子设计。选择算子，本小节采用的是轮盘赌法，将个体的适应度值比上总染色体的适应度值。过程为转动sizepop次轮盘，随机选择轮盘旋转圈数，令pick为随机数，再让pick减去第i个染色体所占概率，对初始种群中的染色体全部进行该项循环操作，总共会有sizepop次循环，当pick为负数时，循环才会终止。交叉算子：本小节采用的是单点交叉的方法，用交叉概率选择要交叉的部分及是否交叉，在该交叉部分，运输路径部分之间进行交叉，不会产生运输路径与运输方式之间进行交叉。变异算子：方法是随机选择一个数，若该数字小于变异概率则不进行变异操作，若该数字大于变异概率则进行变异。变异位置也是同样的设置，即随机选择交叉变量，但是变量应为一个染色体上的不同位置进行数字的调换。
Step 5：迭代次数为1 000次，得出结果。将得出的结果与Dijkstra算法中得出的结果进行对比，如果该数小于初始结果，则该值为最终结果，如果该值大于初始结果，则令初始结果为最优值。
改进后的遗传算法如图5-15所示。
图5-15 改进后的遗传算法
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
