运输线路选择案例题.doc

例一：某运输企业需将货主货物用公路运输方式从地运送到地其公路路线图如图8—2所示图中圆点代表公路的连接处，两个圆点之间所标数字为两点之间运输所需时间，以运行时间（分）表示试计算货物从地运送到地的最短运输线路第一步骤：从第一个已解的结点或起点A开始，计算与起点A相连接的未解结点B,C,D点通过计算可知：A点到B点需要分钟，A点到C点需要分钟；A点到D点需要分钟由此可看到C点是距A点最近的结点，记为AC所以，C点是惟一的选择，它成为已解的结点第二步骤：找出距A点和C点最近的未解的结点，B、F结点是距已知结点A、C最近的连接点，我们知道有A点到B点；A点到C点再到F点注意从起点通过已知结点到某一结点所需的时间应该等于到达这个已解结点的最短时间加上已解结点与未解结点之间的时间也就是说，从A点到B点的时间为72分钟；从A点到C点再到F点的时间等于AC结点的时间加CF结点的时间，即：AC+CF=70+77=147分钟由此可知，B点为已解结点第三步骤：现在需要找到与各已知结点直接连接的最近的未解结点如图所示，有三个候选点，分别是D、E、F，从已知结点到这三个未解结点的最短时间分别为分钟、分钟、分钟，其中连接AD的时间最短，为分钟。

由此得知，D点为已知结点重复上述过程直到到达终点J，即第八步最小的路线时间是分钟，连接图表上以星符号标出的路线，可知，最短路线为A—C—F—H—J在结点很多时，可利用计算机进行求解通过把有关各结点和结点之间数据资料输入数据库，选好运输路线的起点和终点后，计算机就可以计算出从起点到终点的最短路径需要说明的是，计算机计算的绝对的最短路径并不一定是实际运输中的最短路径，因为该方法并没有考虑各条路线的运输质量所以最短路径的选择需要先设定运行时间和距离的权数，通过权数来综合计算实际的最短路径最短路径计算表如表8—5表8—5最短路径计算表计算程序已知结占八、、与已知结点连接的未解结点相关总成本计算过程第个最近结点最小成本最新连接ABCDC*ACCBF+=BABABCDEF+=DADBCDEFGEHBE*CFDEFGIGGDGEFIHH*FHEIIEIHJIHG*HJ。