运输路线优化

《运输路线优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运输路线优化1运输路线和时间安排的原则运输路线的选择影响到运输设备和人员的利用，正确地确定合理的运输路线可以降低运输成本，因此运输路线的确定是运输决策的一个重要领域。安排运输路线和时间的几个原则如下：将相互接近的停留点的货物装在一辆车上运送，以便停留点之间的运行距离最小化；车辆的运输路线应将邻近的停留点串起来，以使停留点之间的运输距离最小化，这样也就使总的路线上的运输时间最短。将集聚在一起的停留点安排同一天送货，要避免不是同一天送货的停留点在运行路线上重叠；运行路线从离仓库最远的停留点开始。运行路线从离仓库最远的停留点开始，送货车辆依次装

2、载临近这个关键停留点的一些停留点的货物，这辆货车满载后，再安排另一辆货车装载另一个最远的停留点的货物。仓库4.一辆货车顺次途径各停留点的路线尽量不交叉，要成泪滴状。●●●●●●●●●●●●在多种规格车型的车队中，应优先使用载重量最大的货车。在运输货物时，最好是使用一辆载重量大到能将路线上所有停留点所要求运送的货物都装载的货车，这样可以将服务区停留点的总的运行距离或时间最小化。提货应混在送货过程中进行，而不要在运行路线结束后再进行。提货应尽可能在送货过程中进行，以减少交叉路程量，而在送货结束后再进行提货经常会发生路程交叉。对偏离集聚停留点路

3、线远的单独的停留点可专门安排车辆送货。偏离集聚停留点少，特别是那些送货量小的停留点一般要花费大量的时间和费用，因此适用小载重量的车辆专门为这些停留点送货是合理的。另一个可供选择的方案是租用车辆或采用公共服务（如邮政服务）为这些停车点送货。8.应当避免停留点工作时间太短的约束。停留点工作时间太短会迫使途经停留点的顺序偏离理想状态。2运输路线决策运输路线决策就是，找到运输网络中的最佳路线，以尽可能缩短运输时间或运输距离，达到降低运输成本、改善运输服务的目标。运输路线决策问题有三种基本类型：一是起点和终点不同的单一路径规划；二是多个起点和终点的

4、路径规划；三是起点和终点相同的路径规划。一、起点和终点不同的单一路径规划此类问题可以描述为在一个已知交通运输网络中，寻找从出发地到目的地的最佳路线。这里的“最佳”可以指距离最短、时间最省或是费用最少。数学模型——求网络图中二点之间的最短路问题。采用网络规划中求最短路Dijkstra算法（标号算法）。除了距离以外，还需要考虑通过交通网络的时间长短。对分离的、单个始发点和终点的网络运输路线选择问题，最简单和直观的方法是最短路线法。初始，除始发点外，所有节点都被认为是未解的，即均未确定是否在选定的运输路线上。始发点作为已解的点，计算从原点开始。

5、一般的计算方法是：(1)第n次迭代的目标。寻求第n次最近始发点的节点，重复n＝1，2，…，直到最近的节点是终点为止。(2)第n次迭代的输入值。(n—1)个最近始发点的节点是由以前的迭代根据离始发点最短路线和距离计算而得的。(3)第n个最近节点的侯选点。每个已解的节点由线路分支通向一个或多个尚未解的节点，这些未解的节点中有一个以最短路线分支连接的是候选点。(4)第n个最近的节点的计算。将每个已解节点及其候选点之间的距离和从始发点到该已解节点之间的距离加起来，总距离最短的候选点即是第n个最近的节点。也就是始发点到达该点最短距离的路径。以下面的

6、实例可以具体说明最短运输路线是怎样计算的。【例】如图所示是一张公路运输网示意图，其中A是起点，J是终点，B、C、D、E、G、H、I是网络中的结点，结点与结点之间以线路连接，线路上标明了两个结点的距离，以运行时间（分）表示。要求确定一条从起点A到终点J的最短的运输路线。●●●●●●●●●●A起点BEIJ终点HFCDG84908413834815648132150906013212648126●●●●●●●●●66120我们首先列出一张如表格3—3所示的表格。第一个已解的节点就是起点或点A。与A点直接连接的解的节点有B、C和D点。第一步，我们

7、可以看到B点是距A点最近的节点，记为AB。由于B点是唯一选择，所以它成为已解的节点。随后，找出距A点和B点最近的未解的节点。只要列出距各个已解的节点最近的连接点，我们有A--C，B—C。记为第二步。注意从起点通过已解的节点到某一节点所需的时间应该等于到达这个已解节点的最短时间加上已解节点与未解节点之间的时间，也就是说，从A点经过B点到达C的距离为AB+BC＝90+66＝156分，而从A直达C的时间为138分。现在C也成了已解的节点。第三次迭代要找到与各已解节点直接连接的最近的未解节点。如表3—3所示，有三个候选点，从起点到这三个候选点D、

8、E、F所需的时间，相应为348、174、228分，其中连接BE的时间最短，为174分，因此正点就是第三次迭代的结果。重复上述过程直到到达终点J，即第八步。最小的路线时间是384分，连线在表3—