第20次课 运输调运决策（车辆行驶最短路径）求解方法

第7章运输决策第20次课运输调运决策（车辆行驶最短路径）求解方法3知识点1运输调运决策求解方法-最小元素法、沃格尔法知识点2车辆行驶最短路径求解方法-里程节约算法、节点扫描算法主要知识点（重难点）4问题思考学习启示1.什么是“三段式”教学模式（方法）？2.什么是“三段式”学习模式（方法）？写写画画：进行数字计算，数字如何计算得来？（关键：步骤一，一通百通）2.

画图，画出示意图、位置图。7.3运输计划编制

运输计划编制，即车辆运行路线和时间安排，是车辆运行路线选择问题的延伸，受到的约束条件更多。

例如，(1)每个停留点规定的提货数量和送货数量；(2)所使用的多种类型的车辆的载重量和载货容积；(3)车辆在路线上休息前允许的最大的行驶时间；(4)停留点规定的在一天内可以进行的提货的时间；(5)可能只允许送货后再提货的时间；(6)司机可能只能在一天的特定时间进行短时间的休息或进餐。

这些约束条件大大地使问题复杂化，甚至使人们难以去寻求最优化的解。这里的问题是车辆是从一个仓库出发，向多个停留点送货，然后在同一天内返回到该仓库，要安排一个满意的运行路线和时间。7.3.1制定调运方案

运输问题

人们在从事生产活动中，不可避免要进行物资调运工作，如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区。根据各地的生产量和需求量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小，这样的问题就是运输问题。7.3.1制定调运方案

【例7-3】如图7-12所示的网络图，有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个销粮区，其需求量分别为5，7，8，3（万吨）。箭条旁的数字为产量地到需求地（销地）的运价（元/吨），图7-12也可以用表7-3表示，问如何安排一个运输计划，使总的运输费用最少。7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

表上作业法

表上作业法求解步骤：

先用最小元素法或沃格尔法寻找初始调运方案，再通过闭合回路法或位势法微调调运方案，直至得到最佳方案。

（1）最小元素法

最小元素法的基本思想是就近供应，即从最小的运价开始尽量满足供销关系，然后从次小的运价开始，一直到给出初始基本可行解为止。

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

（2）沃格尔（Vogel）法

最小元素法的缺陷是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。沃格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次最小运费，这就是一个差额，差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。7.3.1制定调运方案

沃格尔法(Vogel'smethod)，是线性规划中用来编制最优计划方案的方法。在运输问题上，对于每个供应地或销售地，均可由它到各销售地或到各供应地的运价中找出最小运价和次小运价，并称这两个运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按照最小运价安排运输所造成的运费损失不大；反之，如果罚数的值很大，不按照最小运价组织运输就会造成很大损失，故应尽量按照最小运价安排运输。

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.1制定调运方案

7.3.4

里程节约算法

节约法，用于多车辆路径问题，能同时确定车辆数及车辆行驶路径，其目标是使所有车量总里程最短，且使所需车辆总数最少。

节约法的基本原理是：如果将运输问题中的两个回路合并成一个回路，就对缩短线路总里程（即节约了距离）并减少了一辆卡车。如图7-22所示，将两个回路合并成一个回路后，节约的距离为ΔAB=CAO+CBO-CAB。7.3.4

里程节约算法

7.3.4

里程节约算法

7.3.5

节点扫描算法

扫描法，是一种先进行客户分群在确定车辆最短路线的算法。求解过程分为两步：第一步是指派车辆服务的站点或客户点；第二步是决定每辆车的行车路线。

用扫描法确定车辆运行路线的方法十分简单，可以通过手工计算或直接在图纸上完成，也可以利用计算机编程求解。一般来说，它求解所得方案的误差率在10%左右，这样的误差率通常是可以被接受的，因为调度员往往需要在接到最后一份订单后一小时内就制定出车辆运行路线。由于扫描法是分阶段操作的，因此有些时间方面的问题，如路线上的总时间和停留点工作时间的约束等，难以妥善地处理。

7.3.5

节点扫描算法

扫描法的原理：先以物流中心为原点，计算出所有客户点的极坐标，然后依角度大小以逆时针或顺时针方向扫描，若满足车辆装载容量即划分为一群；在划分完的每个客户群内，用最短路径算法求出车辆最佳行驶路径。具体步骤如下：①以物流中心为原点，将所有客户点的极坐标计算出来。②选定极坐标轴，按顺时针或逆时针方向旋转，依角度大小开始扫描。③将扫描经过的客户点需求量进行累加，当客户需求总量达到一辆车的载重量限制且不超过载重量极限时，就将这些客户划分为一群，即由同一辆车完成送货服务。接着，按照同样的方法对其余客户划分新的客户群，指派新的车辆。④重复步骤③，直到所有的客户都被划分到一个群里。⑤在每个群内部用最短路径方法求出车辆行驶最短路径。7.3.5

节点扫描算法

7.3.6

运输路线和时间安排原则

除根据定量计算的最优路径和调运方案外，运行路线和时间安排的决策者，如车辆调度员，在长期的实际工作经验中为满意的运行路线和时间安排提炼出下列八条原则。7.3.6

运输路线和时间安排原则

1．将相互接近的停留点的货物装在一辆车上运送车辆的运行路线应将相互接近的停留点串起来，以便停留点之间的运行距离最小化，这样也就使总的路线上的运行时间最小化。图7-26所示的是将有关停留点的货分配给车辆，从而将各点串起来的示意图。其中图7-26(a),串得不合理，车辆的运行路线长，要尽量避免，图7-26(b)是合理的串法。7.3.6

运输路线和时间安排原则

7.3.6

运输路线和时间安排原则

2．将集聚在一起的停留点安排同一天送货当停留点的送货时间是定在一周的不同天数进行时，应当将积聚在一起的停留点安排在同一天送货，要避免不是同一天送货的停留点在运行路线上重叠，这样可有助于使所需的服务车辆数目最小化以及一周中的车辆运行时间和距离最小化。图7-27所示的是好的集聚和差的集聚的例子。7.3.6

运输路线和时间安排原则

7.3.6

运输路线和时间安排原则

3．运行路线从离仓库最远的停留点开始合理的运行路线应从离仓库最远的停留点开始将该集聚区的停留点串起来，然后返回仓库。一旦确认了最远的停留点之后，送货车辆应满载贴邻这个关键停留点的一些停留点的货物。这辆运货车满载后，再选择另一个最远的停留点，用另一辆运货车转载贴邻第二个最远停留点的一些停留点的货物，按此程序进行下去，直至所有停留点的货物都分配给运货车辆。4．一辆运货车顺次途经各停留点的路线要成凸状运货车辆顺序途经各停留点的路线不应交叉，并应成凸状。不过，停留点工作时间的约束和在停留点送货后再提货的要求往往会导致路线交叉。7.3.6

运输路线和时间安排原则

5．最有效的运行路线通常是使用大载重量的送货车辆最好是使用一辆载重量大到能将路线上所有停留点所要求运送的货物都装载的送货车，这样一来可将服务备停留点的总的运行距离或时间最小化。因此在多种规格车型的车队中，应优先使用载重量最大的送货车。6．提货应混在送货过程中进行，而不要在运行路线结束后再进行提货应尽可能在送货过程中进行，以减少交叉路程量，而在送货结束后再进行提货经常会发生交叉路程。提货混在送货过程中进行，究竟能做到什么程度，则取决于送货车辆的形状、提货量以及所提的货物对车辆内后续送货通道的影响程度。7.3.6

运输路线和时间安排原则

7．对偏离集聚停留点路线远的单独的停留点可应用另一个送货方案偏离集聚停留点远的停留点，特别是那些送货量小的停留点一般要花费大量的司机时间和车辆费用，因此使用小载重量的车辆专门为这些停留点送货是经济的，其经济效益取决于该停留点的偏离度和送货量。偏离度越大，送货量越小，使用小载重量的车辆专门为这些停留点送货越经济。另一个可供选择的方案是租用车辆为这些停留点送货。8．应当避免停留点工作时间太短的约束停留点工作时间太短常会迫使途经停留点的顺序偏离理想状态。由于停留点的工作时间约束一般不是绝对的，因此如果停留点的工作时间确实影响到合理的送货路线，则可以与停留点商量，调整其工作时间或放宽其工作时间约束。7.3.6

运输路线和时间安排原则

上述的原则可以很容易传授给运作人员，从而帮助他们制定出满意的（不一定必须是最优的）现实可行的合理路线和时间安排。当然上述的原则也仅是合理路线设计的指引，运作人员面对的车辆运作的许多复杂情况并不是上述原则所能全部包容的。遇到特殊的约束条件，运作人员要根据自己的经验随机处理。本课小结本课讲授知识点，主要包括：知识点1