基于节点拆分指派问题的多式联运路径优化问题研
究
随着现代物流业与交通运输业的飞速发展，多式联运打破运输方式间的界限，在现代经济的发展中起到尤为重要的作用，已经成为降低物流成本的有效措施，成为提高市场竞争力的有效手段。国民经济和社会发展“十三五”规划的发布，表明国家对物流、对多式联运的重视程度也已经有了显著提高。
国内外众多学者在多式联运方面做出了广泛而深刻的研究。王清斌研究了带有时间约束的、以总运输成本最小为目标的混合整数规划模型；Hu Z H设计了免疫近似算法来解决应急调度的路径优化；JANSEN研究了模拟基于港口的集装箱运营规划；Grabener T研究了基于时间窗的城市交通多目标路径优化模型，并利用改进的Martins算法求解；佟璐认为多式联运路径的选择受到多方面相关因素的影响，并将问题转化成为广义最短路径优化问题；雷定猷等将长大货物作为研究目标，将多目标多式联运问题简化，并采用遗传算法求解；周骞等用遗传算法求解了以配送成本最低和时间成本最小为目标的配送网络优化模型。 1 问题描述
在多式联运网络中，存在一个起始节点和一个终止节点以及若干中间节点，任意两个节点之间可能存在若干种运输方式，由一种运输方式转变为另一种运输方式需要一定的转运时间和转运成本。总成本包含运输成本和转运成本，总时间包含运输时间和转运时间。要解决的问题是：从起始节点到终止节点之间寻找一条运输路径使得总成本最低，同时总时间最短。 2 模型假设和符号说明 2.1 模型假设
（1）运输过程中的运量不可分割，在某一节点处发生运输方式的变化时，该节点和下一可达节点之间只能选择一种运输方式。 （2）在节点处发生运输方式的变化时，只考虑转运时间和转运成本；在两节点之間只考虑运输时间和运输成本。 （3）运输方式的改变只能发生在节点处。
（4）每个运输节点都具备运输方式转变的所有条件，即在任一节点处发生运输方式的转变都是可行的。 2.2 符号说明
A表示所有节点集合，i∈A；A表示初始节点；A表示终止节点；B表示节点i可到达的节点集合，j∈B；D表示运输方式的集合，k，l∈D；c表示节点i，j之间选择第k种运输方式的运输成本；t表示节点i，j之间选择第k种运输方式的运输时间；c表示在节点i，运输方式由k转换到l所需费用；t表示在节点i，运输方式由k转换到l所需时间；x
式（1）、式（2）为目标函数，其中式（1）使总成本最低，式（2）使总时间最短；式（3）至式（9）为约束条件，其中式（3）至式（5）保证模型的解能获得一条从起始节点到终止节点的路径，式（6）使若路径经过节点i，则i，j两个节点之间只能选择一种运输方式，式（7）保证运输的连续性，式（8）、式（9）使决策变量只能取0或1。 4 模型求解 4.1 模型简化
由于多目标模型的多个目标函数之间往往互不相容，因此导致求解复杂，为简化求解，加入成本和时间的权重系数，将多目标函数转化为单目标函数，用其反映在路径选择中分别对成本和时间的重视程度。
4.2 网络变形
图1中，包含3个网络节点，其中a为初始节点，a为中间节点，a为终止节点。因为每个路径存在几种运输方式，所以将节点进行拆分，若经由a节点进出有两种运输方式，经由a节点进出有两种运输
方式，则将节点拆分后的网络图如图2所示。
图2中，a为虚拟初始节点，a、a为a节点拆分后的中间节点，a、a为a节点拆分后的中间节点，a为终止节点。每个路径代表一种运输方式或转运方式。 4.3 变化后的模型符号说明
A表示变化后所有节点集合，i∈A；A表示变化后的初始节点；A表示变化后的终止节点；c表示节点i，j之间产生的成本；t表示节点i，j之间产生的时间；x=
；α表示运输过程中成本的权重系数；β表示运输过程中时间的权重系数；μ表示货物的单位时间价值，即集装箱迟到目的地1h所产生的成本或费用，由货物的种类及数量决定。 4.4 变化后的模型
式（10）为目标函数，目标是总成本最小；式（11）至式（16）为约束条件，其中式（12）至式（14）保证模型的解能获得一条从起始节点到终止节点的路径，式（7）保证路径方向由起始节点指向终止节点，式（16）使决策变量只能取0或1。 5 算例分析
一个20英尺集装箱从郑州运往韩国首尔，途中有济南、济宁两个中转站以及青岛、连云港两个港口。各城市之间的运输网络如图3所示。其中，郑州到济南、郑州到济宁、济宁到济南间的运输方式包含公路运输和铁路运输，济南到青岛有公路运输和铁路运输，济宁到连云港之间有公路运输和铁路运输，济南到连云港只存在公路运输，青岛、连云港和韩国首尔间只存在水路运输。各节点之间的运输网络如图4所示。各节点之间的运输成本如表1所示；其中，不存在运输路径的两节点运输成本取一个足够大的数，本例中取1 000 000元。 图4中，0代表虚拟初始节点，1代表在郑州选择公路运输，2代表在郑州选择铁路运输，3代表在济宁选择公路运输，4代表在济宁选择铁路运输，5代表在济南选择公路运输，6代表在济南选择铁路运输，7代表在青岛选择公路运输，8代表在青岛选择铁路运输，9代
基于节点拆分指派问题的多式联运路径优化问题研究
