方案1运输方式的选择

方案1运输方式的选择 方案1、运输方式的选择 现要求将20吨货物从城市1运输到城市5，运输路径固定为从城市1先后经过城市2、城市3、城市4到城市5。运输期间可以自由选择三种不同的运输方式:铁路、公路、航空运输。但是为了便于运输，在运输路径中相邻的两个地点之间只能采取一种运输方式。另外，规定若交接前后交通工具为不同类型，将会因更换运输方式产生额外支出。 应选择怎样的运输方案才能使总支出最少, 下表一给出了每一对城市之间运输一吨货物的成本。第二张表列出了在更换运输方式时每吨货物需要的额外支出。 不同路径上选择不同运输方式的单位成本 城市1-2 城市2-3 城市3-4 城市4-5 铁路 30 25 40 60 公路 25 40 45 50 航空 40 20 50 45 更换运输工具的单位费用 转换为铁路 转换为公路 转换为航空 从铁路 0 5 12 从公路 8 0 10 从航空 15 10 0 : 本可以套用经典的最短路分段问题。 一共4段路径:1-2、2-3、3-4、4-5。 将城市1看做顶点1。 注意到有三种运输方式从城市1到2，因此将城市2化为3个顶点:T2、G2、H2(T2表示通过铁路到城市2;G2表示通过公路到城市2;H2表示通过航空方式到城市2)。 类似地，城市i都可化作3个顶点:Ti、Gi、Hi，i=2，3，4，5(分别表示通过铁路、公路、航空方式到城市i)。 根据路径，连有向线段。连线上的权为运输一吨货物的总成本。 比如从T2到T3表示从城市2运输到城市3，保持铁路运输方式不变，运费为25，故权为25。 又如从G4到H5表示，从城市4经航空运输到城市5，运费为45，由于运输方式由公路转为航空，更换运输工具的费用为10，即总费用55，故权为55。 为了求从城市1到城市5运输的最少支出，即求图论模型中从起点(代表城市1)到终点(代表城市5)的最短路，由于代表城市5的顶点共3个:T5、G5、H5(分别表示通过铁路、公路、航空方式到城市5)。不妨再取一个虚拟顶点5代表终点(城市5)，其中，从顶点T5(G5、H5)到顶点5的权为0(没有任何费用支出)。 求解结果: 结论: 从城市1运输1吨货物到城市5的最省费用为150，因此运输20吨的费用为3000。 运输方案为:从城市1通过铁路运输先后经过城市2、城市3、城市4、再转为公路运输到达目的地城市5。