第二节运输线路决策Word文档格式.docx

第二节运输线路决策Word文档格式.docx

《第二节运输线路决策Word文档格式.docx》由会员分享，可在线阅读，更多相关《第二节运输线路决策Word文档格式.docx（9页珍藏版）》请在冰点文库上搜索。

此类问题能够描述为在一个已知交通运输网络中，寻找从动身地到目的地的最佳路线。

那个地点的“最佳”能够指距离最短、时刻最省或是费用最少。

数学模型——求网络图中二点之间的最短路问题。

采纳网络规划中求最短路Dijkstra算法（标号算法）。

除了距离以外，还需要考虑通过交通网络的时刻长短。

标号算法1、最短路与最大流

例题1

例如，从上图中找出V1与V8之间的最短路线。

例题2要把A市的一批物资运送到市的一批物资运送到B市例题要把市的一批物资运送到市，依照两个都市之间可选择的行车路线地图，绘制了图5—13的公路网络。

要的公路网络。

可选择的行车路线地图，绘制了图的公路网络求查找一条线路最短的运输路线。

求查找一条线路最短的运输路线。

解：

从终点开始逐步逆向推算

（1）与终点10联接的结点有两个，即结点9和8；

从结点9到结点10只有一条线路，该线路为最短线路，长度100，记为：

（9-10）100；

同样，结点8到结点10的最短线路为150，记为（8-10）150；

（2）结点6。

与6联接的只有一个结点9，6至9的最短里程为200。

而9至终点10的最短里程为100．因此6至终点10的最短里程为200十100＝300。

记为：

（6-9-10）300。

（3）结点5。

与5联接的结点有9、8两个。

5至9再至终点的最短里程为400十100＝500，

5至8再至终点的最短里程为250十155＝400。

400＜500，因此5至终点的最短里程为400，记为：

（5-8-10）400。

（4）结点7。

至终点的最短里程为125十150＝275，

（5）结点4。

与4联接的结点有5、6、7三个。

结点4至6再到终点的最短里程为200十300=500；

结点4至5再到终点的最短里程为175十400＝575；

结点4至7再到终点的最短里程为275十275＝550。

三个里程中以500为最小，因此结点4至l0的最短里程记为（46—9—10）500。

（6）结点2和3。

用同样的方法，得到：

结点2到终点的最短里程为600。

（26—9—10）600。

结点3到终点的最短里程为575。

（37—8—10）575。

（5）最后看结点1。

结点1能够通过三个结点2、3、4连接到终点。

结点。

1通过结点2再到终点的最短里程100十600＝700，路径为（1—2—6—9—10）700

结点1通过结点4再到终点的最短里程150十500＝650，路径为（1—4—6—9—10）650

结点1通过结点3再到终点的最短里程175十575＝750，路径为（1—3—7—8—10）750

以上三个里程中以650为最小，即A币到B市的最短里程，对应的最短路线为：

1—4—6—9—10

二、多个起点和多个终点的路径规划问题

多个起点和终点的路径优化，需要确定各供求地点之间的最佳供应关系。

运用线性规划,数学模型能够描述为：

有m个产地Ai，i=1，2，…，m，可供应量分别为ai，i=1，2，…，m；

有n个销地Bj，j=1，2，…，n，需要量分别为bj，j=1，2，…，n；

产销平稳，从Ai到Bj运输单位物资的运价（也能够是时刻或距离）为cij。

问如何调运这些物资，使得运费（或时刻、吨公里数）最少？

常见的解决方法有：

1、单纯形法2、图表分析法3、图上作业法4、表上作业法

5、供求不平稳运输模型

三、起点和终点相同的路径规划

起点和终点相同的路径规划问题是物流配送业务中的常见问题。

由于要求车辆必须返回起点，问题的难度提高了。

由于要求车辆必须返回起点，问题的难度提高了。

解决这类问题的目标是找出途中通过的点的顺序，使运输工具依次通过问题的目标是找出途中通过的点的顺序，使运输工具依次通过所有送货点并满足各点对送货时刻的要求并满足各点对送货时刻的要求，所有送货点并满足各点对送货时刻的要求，且总出行时刻或总距离最短。

旅行推销员（NP难题距离最短。

——“旅行推销员（TSP）”问题，属于NP难题。

旅行推销员TSP）问题，属于NP难题。

随着问题中包含节点个数和约束条件的增加，随着问题中包含节点个数和约束条件的增加，求解问题的复杂程度增加，要找到最优路径专门困难。

杂程度增加，要找到最优路径专门困难。

即使用最快的运算机进行运算，求最优解的时刻也专门长。

进行运算，求最优解的时刻也专门长。

启发式求解法是求解这类问题的好方法。

类问题的好方法。

见p206页例题3

运输批量越大，运输费率越低。

将小批量物资合并成大批量物资进行运输是降低运输成本的要紧方法。

输是降低运输成本的要紧方法。

（三）合理路线和时刻安排的原则

原则１将相互接近的停留点的物资装在一辆车内运送，以便使停留点之间的运行距离最小化。

（a）差的串联（b）更好的串联

原则2：

将集聚在一起的停留点安排同一天送货，要幸免不是同一天送货的停留点在运行线路上重叠。

原则3：

合理的运输路线一辆运货车顺次途经各停车点的路线要呈凸状，或泪点的路线要呈凸状，一辆运货车顺次途经各点的路线要呈凸状滴形，各条线路之间是不交叉。

原则4：

运行线路从仓库最远的停留点开始，送货车辆一次装载邻近那个关键停留点的一些停留点的物资，这辆运货车装载满后，再安排另一辆运货车装载另一个最远的停留点的物资

原则5：

有多种规格的车型，应优先使用载重量最大的送货车，将路线上所有要求运送的物资都装载。

原则6：

提货应混在送货过程中进行，而不要在运行线路结束后再运行。

原则7：

对偏离集聚停车点路线远的单独的停车点能够使用点点小载重量的车辆专门为这些停车点单独送货。

另一个可供选点择的方案是租用车辆或采纳公共服务（如邮政服务）为这些停车点送货。

原则8：

应当幸免停车点工作时刻太短的约束。

2、制定车辆路径优化方法

物流配送路径优化常见的约束条件包括：

停车点的工作时刻约束，车辆的类型，最大的运行时刻、不同区段的车速限制，运行途中的障碍物（湖泊、山脉等、交通管制）、司机的短时刻休息等。

假如问题中包含送货点的个数专门多，附加了许多约束条件，问题求解就变得十分复杂。

（四）运输路线和时刻表的制定方法

（1）人工运算方法——扫描法人工运算方法扫描法

问题：

关于若干个停车点（客户）安排最优行车路线。

第一步，将仓库（动身点）和所有的停车点位置画在地图上或坐标图上；

第二步，通过仓库位置放置一直尺，然后顺时针或逆时针方向转动，直到直尺交到一个停车点。

询问：

累计的装货量是否超过送货的载重量或容积（第一要使用最大的送货车辆）。

如是，最后的停车点排除，将路线确定下来。

然后再从那个停车点开始连续扫描，开始一条新的路线。

这样扫描下去，直至全部的停留点都被分配到路线上。

第三步，对每条路线安排运行顺序，以求运行距离最小化。

方案的误差率在10%左右。

例4从各客户点提货，然后将物资运回仓库。

全天的提货量见图5-13。

送货车每次可运载10000件。

要求确定：

需多少条路线（即多少辆送货车）；

每条路线上有哪几个客户点；

送货车辆服务有关客户点的顺序。

图5-13停留点提货量数据停留点提货量数据

扫描法:

手工运算。

车的载货量是扫描法手工运算。

车的载货量是10000件。

需要多少条线手工运算件每条线路上的站点如何排列？

需要多少条线手工运算件每条线路上的站点如何让排列？

（2）节约法（最优插入法）初始路线

（3）相关软件——智能调度系统

智能调度系统（IDS）是采纳GIS技术、最优路径算法、运筹学和数据库等先进技术开发的物流软件，用于车辆调度和服务线路规划（包括时刻打算和线路规划）