多目标多式联运配送路径研究.docVIP

多目标多式联运配送路径研究 　　摘 要：讨论了一类运量已知的多式联运配送问题。提出了基于成本最小化和时间最小化两个目标函数，并利用Dijkstra算法结合GA算法进行求解，最后用一个算例加以证明。 　　关键词：多式联运；配送路径；Dijkstra算法；GA算法 　　中图分类号：F252.14 文献标识码：A 　　随着中国经济高速发展以及经济全球化的发展趋势，单一的运输方式已经无法满足国际运输市场的需求，只有多式联运才能很好的解决来自全球运输市场多方面的需求。多式联运是由两种及其以上的交通工具相互衔接、转运而共同完成的运输过程，这种运输形式统称为复合运输，我国习惯上称之为多式联运。《联合国国际货物多式联运公约》对国际多式联运所下的定义是：按照多式联运合同，以至少两种不同的运输方式，有多式联运经营人把货物从一国境内接运货物的地点运至另一国境内制定交付货物的地点。而中国海商法对于国内多式联运的规定是，必须有种方式是海运。本文中的多式联运意从第一种解释，在各种运输方式协调作业中不一定要有海运。 　　随着物流技术的不断进步，以及对多式联运需求的增加，国内外对多式联运的研究也逐步深入。文献[1]到文献[3]均以成本最小为目标函数对多式联运进行研究，没有涉及到时间最短的目标；文献[4]研究了基于多式联运的最短路径问题，并给出了顺序算法的求解过程；文献[5]讨论了一类基于满足客户要求时间下的最小成本的多式联运问题，并通过粒子群优化算法进行了求解；文献[6]从节点作业随机的角度出发，研究了基于最小成本的多式联运问题；文献[7]虽然建立了基于最小成本和最短时间的两个目标函数，但是其通过蚁群算法给出了路径固定前提下基于最小成本的最短时间解；文献[8]基于软时间窗的车辆路径问题；文献[9]针对综合运输网进行了最短时间下的最佳路径问题研究，基于时间因素提出了多式联运的最佳路径。 　　从以上分析可以看出，如今对多式联运的多目标研究甚少，有极少数建立了多目标函数模型，但是求解时通过权重法简化成了单目标函数，这样就脱离了实际，因此本文意在通过主次目标对目标函数进行求解，达到进一步接近实际的效果。 　　1 模型的建立 　　2 基于GA的优化算法 　　多目标多式联运问题属于NP-Hard问题，本文将通过遗传算法与Dijkstra结合对其进行求解。本文讨论中的运费与货物重量和运输点间距离有关，由于讨论的是一类定质量的运输问题，故先用Dijkstra算法求出最短路径，然后再用GA算法确定各路段运输方式。Dijkstra求最短路径相对简单，故对GA算法进行详细阐述。 　　2.1 编码。本文采用自然编码方式。例如有5个中转节点，其编号为1到5号。首先将这5个节点进行随机排列，如1，4，3，5，2；在该数列前后加入0和6（其中0为出发点，6为到达点），则该数列变为0，1，4，3，5，2，6，即找到了一条配送路径为0→1→4→3→5→2→6。 　　对该条路径每一段进行运输工具选择，会选择6次，将四种交通运输方式编号如表1所示。 　　随机产生6个1～4的正整数，例如2，1，1，3，4，1，对应上面路径的每一段的运输方式。 　　2.2 适应函数。首先以首要目标函数作为适应函数，选出多种最优方案，然后以次要目标作为第二个适应函数再次进行筛选。相同的是个体所对应目标函数值Z即为此个体的适应值。 　　2.3 选择操作。取种群各染色体适应值倒数除以倒数之和，作为各染色体被选择的概率；采用轮盘赌的方式选择染色体复制到新种群，直到新种群规模与父代相同为止。 　　2.5 计算过程 　　Step 1：各参数初始化，并设置达到最大迭代次数gen max为算法终止条件； 　　Step 10：重复1～9选出10个最优方案进行第二目标函数运算（运算过程同第一目标），选出满足第二目标的最优方案。 　　3 算例分析 　　某运输任务需从起始点将一批重量为8的货物运至终点。生成的网络拓扑图如图1所示。其中各点旁边的数字为点编号，在该算例中2号点为起始点（方块），8号点为终点（圆圈）。 　　相邻两个运输节点间可选的运输方式及单位成本和时间如表2所示；不同运输方式之间的中转成本和时间如表2所示。 　　其中数值含义为单位运费/运输时间。例如35/5/7表示从点2至点6和从点2至点7的单位运费均为35，而从点2至点6所需时间为5，从点2至点7所需时间为7。 　　不同运输方式之间单位转换费用和时间如表3所示。其中数值含义为单位转换费用/转运时间。 　　设种群规模为40，迭代次数为1 000次。在CPU2.0GHz，内存2GB的计算机上多次利用遗传算法求出的最短时间为11秒，其中一种运输方式分配为1，1，1，2，如图2所示。 　　用Dijkstra算法求出最短路径为