车辆路线计划

1、5.4一、优化路线与运输路线设计在整个物流成本中，运输成本所占比列为33%-67%，所以我们必须关注如何降低运输成本问题，最大化地利用运输设备和人员，优化运输线路是降低运输成本的关键。从承运人方面看，合理的车辆路线有了更高的车辆利用率，更高的服务水平，更低的运输成本，并且减少了设备资金投入，以便于更好的进行决策管理。从托运人方面看，使托运人降低了成本，拥有了更高的服务水平。合理的车辆路线计划可以节约运输成本，降低物流成本，缩短运输时间，加快物流速度节约运力，节约资源。在保证货物流向合理的前提下，在整个运输过程中，确保运输质量，以适宜最小的运输环节，最佳的运输路线，最低的运输费用使货物运至目的地

2、。合理的车辆路线计划属于优化运输路线的一部分，就需要我们进行运输路线的决策。运输路线决策就是，找到运输网络中的最佳路线，以尽可能缩短运输时间或运输距离，达到降低运输成本、改善运输服务的目标。运输路线决策问题有三种基本类型：一是起点和终点不同的单一路径规划；二是多个起点和终点的路径规划；三是起点和终点相同的路径规划。二、起点和终点不同的单一路径规划:此类问题可以描述为在一个已知交通运输网络中，寻找从出发地到目的地的最佳路线。这里的“最佳”可以指距离最短、时间最省或是费用最少。数学模型求网络图中二点之间的最短路问题。采用网络规划中求最短路Dijkstra算法（标号算法）。如图1-1中，设置起点为A

3、点，终点为G点，各点间的数字为成本，找出从A点到G点的最佳（成本）路线。1-1从点A到G点的最佳车辆行驶路线为：A一D一F-G。第一步，首先把我们所有的这张把图上的点分成已决点和未决点两个集合，已决点里面还包括起始点即A点为起点、G点为终点，其他所有点都是未决点。第二步，从没有决定的里面找出距离已决点集合最近的点，并且选择距离初始点最近的点加入到已决点里面去，然后重新计算这个点，这个时候我们就可以得到起始点到各个点的距离情况。第三步是然后重复第二个步骤，不断的重复，选出最后一个最近的集合。在本图中，我们从已决点起点A点出发，有三条路径：A点到C点、A点到D点、A点到E点，从成本来看，A点到C点

4、是最少的，反而从A到D和A到E都是比较高的，所以第一次我们选择C这点，当C点选择了之后，对于C来说，他就会有两个选择，一个是到D，一个是到F，我们可以发现A到C，A到D，它的整个成本是10。从A到，C再到F的话，它的整个成本是11，但是我们回过头来看的时候，就会发现，A到D的成本反而是4，这个时候我们就会把C点去掉，重新选择一个D点，我们就得到了A到D作为一个集合，AD为4。对于D来说，就会有三个选择，一个是到E，一个是到G，一个是到F，这就会有三条路径作为它的选择项，D到G的成本为10，D到F再到G的成本为6,而D到E再到G的成本为10，很显然，由D到F再到G的成本最少，属于最短路径，我们选

5、择D-F-G。综合起来，A-D-F-G为A到G最少成本行驶路线，成本为4+5+1=10；根据这个标号算法，我的感觉是：假定1-2-3-4为1-4的最短路线，则1-2-3一定是1-3的最短路线，同时，2-3-4一定是2-4的最短路线。我用本题验证一下：因为我的结论是A-D-F-G为A到G成本最少的最短行驶路线，则A-D-F一定是A到F的最少成本行驶路线，经验证，在由A到F的5条线路：A-C-F成本11、A-D-F成本9、A-D-G-F成本15、A-E-D-F成本12、A-E-G-F成本16中，显然A-D-F的成本是最低的；同理，在由D到G的3条线路中，D-F-G的成本是最低的。通过反证，亦可得A

6、-D-F-G为A到G最少成本行驶路线。三、多个起点和终点的路径规划如图1-2，设置起点为A点，终点为E点和B点，设计最佳的行驶路线。图1-2我认为这个问题可以理解用两辆车从A点出发，分别到E点和B点，如何分别设计这两辆车辆的最佳路线问题。设置起点为A点，终点为E点的车辆最佳路线计划为：A一D一E。我们从A点出来，我们发现它可以到C点、到D点，、到E点这三个点，根据成本最优，我们可以发现从A点到C点是成本最少的。而从A点到D点和A点到E点都比较高，所以第一次我们选择C这个点。当C点确定为已决点后，对于C点来说，他有两个选择，一个是到D点，一个是到F点，我们可以发现A点到C点再到D点，它的整个成本

7、是10。从A点到C点再到F点的话，它的整个成本是11,然而，A点到D点的成本反而是4，这个时候我们就会把C点去掉，重新选择D点作为已决点，这样以来，我们就得到了A点到D点作为一个集合，而不是A点到C点了。当A点到D点之后，对于D点来说，那我们直接就选择D点到E点，这样以来，我们就得到了A点到D点再到E点的选择，从A点到D点到到E点的成本是4+1=5，从A点到E点的成本是6,从A点到C点到D点再到E点的成本是3+7+1=11。所以A-D-E的路线计划是成本最低的路线。设置起点为A点，终点为B点车辆最佳路线计划为：A-D-F-G-B。从A点出发，它可以到C点、到D点、到E点这三个地方，从成本来看，

8、从A点到C点是最少的。反而从A点到D点和A点到E点都是比较高的，所以第一次我们选择C这个点，当C点选择了之后，对于C来说，他就会有两个选择，一个是到D点，一个是到F点，我们可以发现A点到C点再到D点，它的整个成本是10。从A点到C点再到F点的话，它的整个成本是11，但是我们回过头来看的时候，就会发现，A点到D点的成本反而是4，这个时候我们就会把C点去掉，重新选择一个D点，这样以来，我们就得到了A到D作为一个集合，而不是A到C了。当A到D之后，对于D来说，就会有三个选择，一个是到E,一个是到G，一个是到F,这就会有三条路径作为它的选择项。显然这就选择了E点，选择E点之后，就会出现A到D再到E的集

9、合。接下来步骤显然是从E步骤开始往前走了，E步骤往前走的时候，就会到G这个步骤，我们可以发现E到G到再B点的路径是12块钱，所以这个时候，我们需要再回过头来重新审视原来的选择，原来选择从D到F到B是10块钱，这时就会把E点给去掉了，E点就不需要用了，再选F点作为一个选择点，这样以来，我们就得到了A到D再到F的选择，当F选择确定了之后，对于F来说，就会有两个选择，一个是直接到B，一个是到G再到B,F到B的成本是是5块钱，然而从F到G再到B的成本是1+3=4说以5大于4,所以选择先到G点再到B点。A-D-F-G-B成本是4+5+1+3=13是我认为成本最低的一个路线计划，也是最佳路线计划。四、起点

10、和终点相同的路径规划如图1-3设置起点和终点均为A点，图中各个点均要经过，设计出最佳路线。E9G图1-3最佳路线为A-C-F-B-G-E-D-A。根据来自实践的经验：合理的经停线路中各条线路之间是不交叉的，并且只要有可能路径就会呈凸形或水滴状。按照“线路不交叉”和“凸形或水滴状”的两条原则，画出线路规划图合理的运输路线，一辆运货车顺次途经各停车点的路线要呈凸状，或泪滴形，各条线路之间是不交叉的。本着“线路不交叉”和“凸形或水滴状”的原则寻求最短成本的原则：我们从A出来，我们发现它可以到C到D,可以到E这三个地方，从成本来看，我们马上就可以知道从A到C是最简单的，最少的，只要三块钱。所以第一次我们选择C这个点，当C点选择了之后，对于C来说，C点有两个选择，一个是D点一个是F点，因为C-D-F成本是5+7=12，然而C-F是8,所以我们选择F点，对于F点有两个选择就是B点和G点，虽然F点到G的成本远远小于F到B的成本，我们本着不重复不交叉的原则所以选择