1.5 单个运输起点和终点间的路线选择
典型问题及案例
找寻最佳路径
美国ALK联合公司开发的PC Miler和物流公司开发的COMPUMAP是两种商用软件，可以用在网络中找寻最佳路径。它将美国所有的公路和小城市构成的公路网络输入数据库，用户只要在任一软件中敲入运输的起点和终点，程序就可以马上显示出从起点到终点的确切路线，从而选出最短路径，司机可以知道确切的道路、一条最短路径。它所提供的信息非常详细，在各个交叉路口走哪条路、旅途各程的距离，还可以得出各州内的行车里程数并出具各州的燃油税报告，同时用于核查。
解读与阐述
这类问题是最简单的路线选择问题，在实际生活中也很普遍。
这类问题的解决方法一般采用最短路径法，即通过计算选出一条最短路线。它的计算方法，我们通过一个例子来说明。
例如，有一批货希望通过汽车从北京运到上海，请选择一条最短路径。步骤如下：
1. 建立模型
我们可以画出从北京到上海的公路路线，用点代表经过的县或市，用线代表点的可行通道，并将距离标出，A为起点，J为终点。这样我们得到一张北京到上海的高速公路示意图，求出A到J的最短路线即可。
图1-2 北京到上海的高速公路线路
2. 最短路线
计算步骤参照表1-13。
表1-13
续表
（1）第一个已解的节点就是起点A，与A直接相连的节点有B、C、D点；我们可以看出B是距A点最近的节点：记为AB。所以B点是下一站的起点。
（2）接着我们找距A、B点最近的其他点，找到C点；从A到C有A—C，A—B—C；计算A—B—C的距离为156，而A—C距离为138。
（3）我们接下来找距离A、B、C最近的点，有三个候选点D、E、F，计算出距离分别为348、174、228，其中BE的距离最短，E点就是第三次迭代的结果。
（4）重复上述过程直到到达终点J，即第八步，因此，确定出最优路线为A—B—E—I—J。
在节点很多的时候，手工计算比较麻烦，但现在随着计算机技术的广泛应用，最短路径法可以通过计算机编程来解决。所以，只要把所有的路线信息（公路网的节点和节点间的距离）录入数据库，就可以借助计算机计算出所有城市间的距离，从而选择最短路线。
关键点提示
利用最短路径法解决起点和终点间不同路线选择问题的方法有：
1. 利用最短路径法来计算
2. 借助计算机程序来计算