【《利用遗传算法规划港口多式联运的通道案例分析》6300字】

利用遗传算法规划港口多式联运的通道案例分析目录TOC\o"1-3"\h\u11041.1遗传算法的应用 1284641.1.1编码方式的设计 1117291.1.2初始化种群 270071.1.3适应度函数的设计 384051.1.4遗传算子的设计 317311.1.5运行参数 540911.2遗传算法的成本计算结果及分析 7106151.2.1从南昌出发运往其他城市的成本 7192071.2.2从其他城市出发途经南昌运往其他城市的成本 11133121.2.3从省内城市出发到达南昌或途经南昌运往其他城市的成本 1323121.2.4确定物流通道 141.1遗传算法的应用在应用于求解像多式联运的优化问题时，遗传算法ADDINNE.Ref.{A79A671F-54CD-4401-9C2F-101070EDAEE4}很早就提供了一个完整的框架，也就是编码思路，因此只需要针对多式联运，设计算法的基本要素，如下文所述。1.1.1编码方式的设计解决规划多式联运的通道或者路径问题时，第一个处理好多式联运的路径表示为基因型的编码串。本文利用实数进行编码方式，主要是要理解和实现，具体安排为：地点和运输方式的代码前后排列交替间隔编码，编码串的长度不固定，与路径中途径节点相关。首尾两端是确定的值，表示起点和终点，偶数位置表示地点，奇数位置表示运输方式。地点的ID为正数，来源于多式联运的网络拓扑。运输方式的代码为负数，-1、-2分别表示铁、水。以7项指标划分的城市，其ID将上海、重庆、广州分别设为1、2、3；二类城市为北京、石家庄、南京、杭州、合肥、福州、济南、郑州、武汉、长沙等设置为4、5、6、7、8、9、10、11、12、13等等；三类城市，例如天津设置为20、太原设置为21、呼和浩特设置为22、沈阳设置为23、长春设置为24、哈尔滨设置为25、南昌设置为26、海口设置为27、拉萨设置为28、兰州设置为29、西宁设置为30、乌鲁木齐设置为31。例如长沙—南昌—上海，如果转运方式为铁路转水路，则表示为如下图：13-126-21图4-1多式联运路径编码在染色体中出现重复地点ID需要进行相应的去除。去除方式为：如果染色体中含有重复地点ID，那么将这个染色体处理一下，从首尾两端开始寻找重复的地点ID（包括起点和终点），一旦找到第一对ID重复的编码位置，接着把其中间所有的基因序列都删除，剩下的基因序列就是最为精简的染色体。这样也符合多式联运实际情况。染色体之间的相似度。要求染色体之间的差异性较大，此时就需要一个能够反应染色体间相似程度的数值；就种群来说为了进化，需要多样性，所以要删掉重复个体。相似度也可就作为判断两个染色体相似程度的依据。1.1.2初始化种群遗传算法是以种群为基础来进行迭代进化。开始进化时从初始的种群开始，经过选择算子、遗传算子生成下一代种群，如此迭代，得到最优。本文针对多式联运通道规划问题，在确定路径起始点的情况下开始初始化种群，然后随机生成多条可以连接这始发地和目的地的路径，设置路径的数量和种群的规模相等。下面介绍本文的如何以迭代方式来随机生成一条路径。这里采用随机生成数字1至7的随机排列的方法，选出起点和终点之间的路径，要求起点在终点之前，然后以均匀分布将运输方式插入到地点之间。这样找到一条路径，以此反复，找到多条。图4-2生成多式联运的路径1.1.3适应度函数的设计多式联运通道规划的模型中，对于一条给定的多式联运通道，根据目标函数计算得到的成本、路径等数值都是正数。因而可以直接作为适应度函数。多式联运的需求为成本最低、路径最短，因此适应度函数值越小，个体越优秀。由于遗传算法的随机性，在染色体表示的路径中，可能存在两个相邻的地点之间在指定运输方式网络不存在可达路径或者没有这个运输方式。需要做处理：设定一个固定的较大数值作为最大值，在指定运输方式下两个不可达节点之间的距离用该最大值表示。这样在计算适应度时，得到的结果会比可行解的适应度差，在进化的过程中被淘汰。这里将考虑运费、时间、距离三个维度，优先级别从高到低。1.1.4遗传算子的设计1、选择算子的设计采用排序选择方式来选择部分个体遗传进入下一代种群中：（1）计算种群中所有个体的适应度；（2）适应度由小到大，对种群中所有个体排序；（3）按照个体在种群中所处位置分配被选中进入下一代种群的概率。2、交叉算子的设计遗传算法中交叉算子将配对的两个父代染色体交换部分基因序列，产生新的子代染色体。交叉算子的确定需要考虑到现有染色体中优良基因序列不能有过多的破坏并且能够组合产生较为优秀的个体。在多式联运通道规划的遗传算法实现中，采取的是单点交叉。交叉点的选取范围为除首位外的所有地点。交叉点选好之后，N染色体前半部分与M染色体后半部分组合，N染色体后半部分与M染色体前半部分组合，这样得到两个新的个体。如果交叉点是同一个地点的话，那么生成两条新的通道；否则，新的个体还需要在两个交叉点生成一条路径衔接。交叉完成后，两个新的个体进行去重操作。交叉发生在配对好的个体N和M之间，首先分别在个体N和M之间选定各自交叉点，对于通道来说，交叉点选取的是地点。然后判断他们选取的交叉点是否相同。图4-3相同交叉点的交叉算子示意图图4-4不同交叉点的交叉算子示意图对于已经配对好的两个父代染色体，通过n次随机选取交叉点，可以得到2n个新的染色体，并选出最优的即适应度值最低的两个作为最终交叉算子的结果。n的值可以取3~5。3、变异算子的设计在多式联运通道路径规划的遗传算法中，染色体的长度是可改变的，随机选中种群的个体，然后随机确定变异的位置。变异是指产生新的地点替换掉原来的地点，同时更新与它相邻地点的运输方式，若地点不可达则淘汰掉；或者改变两地之间的运输方式，若运输方式被限制则淘汰。图10-5变异地点的变异算子示意图图10-6变异运输方式的变异算子示意图1.1.5运行参数运输成本水路平均运输成本0.3元/吨10公里，铁路平均运输成本0.8元/吨10公里，公路平均运输成本0.50元/吨公里（武汉宜昌收费标准）。相同距离和重量的货物，成本上公路运输是水路运输的近17倍，铁路运输是水路运输的近3倍。假设一年运输100万吨货物。2、地点ID通过之前的分析，这里选择典型城市的货运站：北京、上海、广州、南京、武汉、长沙，ID分别为1，2，3，4，5，6，南昌为7。3、运输工具及距离为了方便运算，原本用数字-1、-2、-3表示现用数字1、2、3分别代表水、铁、公路运输方式，并且处在路径的奇数位。城市之间每种运输方式的距离如下表，数据来源《中国交通运营里程图》第二版。所选城市之间各种运输方式均可使用，表格中0代表原点到原点，数据呈现对称性。获知ADDINNE.Ref.{EF270A41-BDAC-4858-B8CF-0EA1FAE887F7}[5]水、铁、公路运输方式的平均速率为34km/h、70km/h、100km/h。表4-1各个城市之间水路距离（公里）水路北京上海广州南京武汉长沙南昌北京0136929121760249327252225上海13690154339211251356856广州2912154301935266828992399南京176039219350733964464武汉2493112526687330231548长沙2725135628999642310600南昌222585623994645486000表4-2各个城市之间铁路距离（公里）铁路北京上海广州南京武汉长沙南昌北京0146023131157122915872005上海14600182330215571199837广州2313182302126155711991042南京115730221260122912001140武汉12291557155712290358776长沙15871199119912003580418南昌2005837104211407764180表4-3各个城市之间公路距离（公里）公路北京上海广州南京武汉长沙南昌北京0121221221010115014871405上海1212014342988201053697广州2122143401366980671781续表4-3各个城市之间公路距离（公里）公路北京上海广州南京武汉长沙南昌南京101029813660542889598武汉11508209805420335359长沙148710536718893350334南昌140569778159835933401.2遗传算法的成本计算结果及分析1.2.1从南昌出发运往其他城市的成本下面以南昌（ID为7）为出发点，分别运往北京（ID为1）、上海（ID为2）、广州（ID为3）、南京（ID为4）、武汉（ID为5）、长沙（ID为6）6个城市，遗传算法的结果如下。每个起点到终点的路径选了费用按照从低到高的顺序的前6条。费用按照参数选取计算。表4-4遗传算法计算南昌-北京路径的结果起点及终点序号路径运输方式运输成本（元/吨）运输时间（小时）运输距离（公里）南昌-北京17-1166.7565222527-2-11-166.7565222537-2-12-1108.0352220647-2-11-2142.4846231657-4-12-114468290067-12160.4292005南昌到北京的路径中成本最低的是从南昌出发水运再海运至北京，对应序号1，以及从南昌出发水运途经上海转海运至北京，对应序号2，运输时间最短的是从南昌出发全程铁路运输至北京，对应序号6，线路最短的是从南昌出发铁路运输至北京，对应序号6。对于给予物流时间充裕，同时物流成本限制为低价位的货物，全程水运及海运至北京是最佳选择。对于要求运输不能超过3天，同时要求物流成本在100元/吨以下，适宜通过铁路运输到上海转海运至北京。对于物流时间要求较高，同时要求物流成本较低的货物，适宜通过铁路运输到北京。图4-7南昌-北京铁水联运示意图表4-5遗传算法计算南昌-上海路径的结果起点及终点序号路径运输方式运输成本（元/吨）运输时间（小时）运输距离（公里）南昌-上海17-2125.682585627-2266.961283737-5-22-195.8344190147-5-6-4-22-1-2-2189.1739250957-4-22-3240.219143867-5-3-6-21-2-2-1272.2904480南昌到上海的路径中运输成本最低的是序号1从南昌沿长江流域水运至上海，运输时间最短的是序号2从南昌开始铁路运输至上海，运输距离最短的是序号2从南昌开始铁路运输至上海。对于物流时间要求一般高，同时要求物流费用在30元/吨以下，适宜选择水运至上海。对于物流时间不超过三天，同时要求物流成本在100元/吨以下的货物，适宜通过铁路运输到上海。表4-6遗传算法计算南昌-广州路径的结果起点及终点序号路径运输方式运输成本（元/吨）运输时间（小时）运输距离（公里）南昌-广州17-2-31-171.9771239927-3171.9771239937-3283.3615104247-4-2-31-1-2171.5251267957-5-6-4-22-1-2-2189.1739250967-4-32-3240.2191438南昌到广州的路径中运输成本最低的是序号1从南昌沿长江流域水运至上海再转海运至广州，运输时间最短的是序号3从南昌全程铁路运输至广州，运输距离最短的是序号3从南昌铁路运输至广州。对于物流到达时间要求为3天，但要求物流成本在80元/吨以下的货物，适宜选择水运路经上海至广州。对于物流到达时间要求在1天内，同时要求物流成本在100元/吨以下的货物，适宜通过铁路运输到广州。表4-7遗传算法计算南昌-南京路径的结果起点及终点序号路径运输方式运输成本（元/吨）运输时间（小时）运输距离（公里）南昌-南京17-41161654827-5-42-181.0733150937-4291.216114047-5-41-2109.3628159757-6-43-1195.9232129867-5-43-1201.49251092南昌到南京的路径中运输成本最低的是序号1从南昌沿长江流域水运至南京，运输时间最短的是序号1从南昌全程水路运输至南京，运输距离最短的是序号1从南昌水路运输至南京。无论物流时间要求高或者要求一般高，又同时要求物流成本最低的货物，都适宜选择水运至南京。表4-8遗传算法计算南昌-武汉路径的结果起点及终点序号路径运输方式运输成本（元/吨）运输时间（小时）运输距离（公里）南昌-武汉17-5111.041136827-5262.081277637-4-52-1113.1938187347-6-2-52-2-1163.1156274157-53179.5435967-4-53-1320.99281331南昌到武汉的路径中运输成本最低的是序号1从南昌沿长江流域水运至武汉，运输时间最短的是序号1从南昌全程水路运输至武汉，运输距离最短的是序号1从南昌全程水路运输至武汉。无论物流时间要求高或者要求一般高，又同时要求物流成本最低的货物，都适宜选择水运至武汉。表4-9遗传算法计算南昌-长沙路径的结果起点及终点序号路径运输方式运输成本（元/吨）运输时间（小时）运输距离（公里）南昌-长沙17-61181860027-6233.44641837-4-61-2109.9231166447-2-62-2162.8830203657-63167433467-4-5-62-1-3280.69412208南昌到长沙的路径中运输成本最低的是序号1从南昌沿长江流域及内河水运至长沙，运输时间最短的是序号5从南昌全程公路运输至长沙，运输距离最短的是序号5从南昌公路运输至长沙。对于要求物流到达时间为1天，同时要求物流成本在20元/吨以下，适宜选择水运至长沙。对于要求物流时间为最快的小时达，同时要求物流成本较低50元/吨的货物，适宜选择铁路运输至长沙。1.2.2从其他城市出发途经南昌运往其他城市的成本另外以长沙（ID改为4）为出发点，运往上海（ID改为1）、南京（ID为2）2个城市，武汉（ID改为3），南昌（ID改为5），遗传算法的结果如下。每个起点到终点的路径选了费用按照从低到高的顺序的前4条。费用按照参数选取计算。表4-10遗传算法计算长沙-上海路径的结果起点及终点序号路径运输方式运输成本（元/吨）运输时间（小时）运输距离（公里）长沙-上海14-1140.6840135624-5-12-159.1231127434-5-11-281.9630143744-1295.92171199长沙-上海的路径中运输成本最低的是序号1从长沙沿内河及长江流域水运至上海，运输时间最短的是序号4从长沙全程铁路运输至上海，运输距离最短的是序号4从长沙全程铁路运输至上海。对于要求物流到达时间为2天，同时要求物流成本为最低（低于50元/吨）的货物，适宜选择水运至上海。对于要求物流时间为1.5天，同时要求物流成本低于100元/吨以下的货物，适宜选择从长沙铁路运输至南昌再转水运至上海。图4-8长沙—上海铁水联运运输通道表4-11遗传算法计算长沙-南京路径的结果起点及终点序号路径运输方式运输成本（元/吨）运输时间（小时）运输距离（公里）长沙-南京14-2128.922996424-5-22-147.362088234-3-22-150.6327109144-2296171200长沙-南京的路径中运输成本最低的是序号1从长沙沿内河及长江流域水运至南京，运输时间最短的是序号4从长沙全程铁路运输至南京，运输距离最短的是序号2从长沙出发铁路运输至南昌转水路运输至南京。对于物流时间要求一般高，同时要求物流成本最低的货物，适宜选择全程水运至南京。图4-9长沙—南京铁水联运运输通道对于物流时间要求较高，同时要求物流成本较低的货物，适宜选择铁路运输至南昌再转水运至南京。1.2.3从省内城市出发到达南昌或途经南昌运往其他城市的成本江西省有省级以上科技园区的地区为九江市、永修、南昌市、景德镇市、德兴市、贵溪市、上高、新余市、宜春市、萍乡市、吉安市、吉水、赣县、南康市共14个地区，其中邻近内河河道的为赣县、南康市、吉安市、吉水、南昌市、景德镇市、德兴市、贵溪市、九江市、永修共10个地区，考虑提高未来龙头岗码头的物流运输影响力，分析某些地区用不同的运输方式到达南昌的物流成本，以及赣州地区出发途经南昌龙头岗运往上海、武汉两地的物流成本。表4-12遗传算法计算的结果起点及终点序号路径运输方式运输成本（元/吨）运输时间（小时）运输距离（公里）赣州-上海1赣州-南昌-上海水水39.183913062赣州-南昌-上海铁水58.963112723赣州-南昌-上海公水220.68291246赣州-武汉1赣州-南昌-武汉水水29.94299982赣州-南昌-武汉铁水49.72229643赣州-南昌-武汉公水211.4420938鹰潭-南昌1鹰潭-南昌水