城市配送中心车辆路径优化问题研究论文PPT修

1、城市配送中心车辆路径城市配送中心车辆路径 优化问题研究优化问题研究 答答 辩辩 人：人： 学学 号：号： 专专 业：业： 一、研究目的 车辆路径问题是运输配送中的难题之一，车辆路径问题是运输配送中的难题之一， 也是物流系统优化的关键一环。也是物流系统优化的关键一环。 国内外学国内外学 者进行了广泛而深入的研究，提出了不同者进行了广泛而深入的研究，提出了不同 条件下的多种求解方法。各种方法都优点条件下的多种求解方法。各种方法都优点 和不足之处，也有其应用上的局限和障碍和不足之处，也有其应用上的局限和障碍 ，有效而充分地运用这些方法解决实际问，有效而充分地运用这些方法解决实际问 题，使之服务于物流

2、配送实践，使得配送题，使之服务于物流配送实践，使得配送 花费最少，时间最短，车辆、人员的利用花费最少，时间最短，车辆、人员的利用 率最高。率最高。 二、研究思路 第一章，讲述研究意义、以及配送车辆路线的研第一章，讲述研究意义、以及配送车辆路线的研 究现状、发展现状和总体思路等问题。究现状、发展现状和总体思路等问题。 第二章，介绍物流配送、车辆路线的相关概念。第二章，介绍物流配送、车辆路线的相关概念。 并对单车辆路径问题进行了介绍。并对单车辆路径问题进行了介绍。 第三章，对车辆路径问题进行研究。对车辆路径第三章，对车辆路径问题进行研究。对车辆路径 问题进行综合性了解，对相关知识进行了比较详问题进

3、行综合性了解，对相关知识进行了比较详 细的描述。介绍了一下，比较常用的方法。细的描述。介绍了一下，比较常用的方法。 第四章，车辆路径问题的数学模型建立及求解方第四章，车辆路径问题的数学模型建立及求解方 法。这也是本文的主体部分。建立车辆路径问题法。这也是本文的主体部分。建立车辆路径问题 的数学模型，并介绍了相关求解方法。的数学模型，并介绍了相关求解方法。 第五章，案例及结果分析。运用节约里程法和第五章，案例及结果分析。运用节约里程法和 LogwareLogware软件计算案例结果，并对结果进行分析。软件计算案例结果，并对结果进行分析。 。 三、车辆路径问题的方法三、车辆路径问题的方法 节约里程

4、算法节约里程算法 蚁群算法蚁群算法 LOGWARE软件软件 遗传算法遗传算法 车辆路径问车辆路径问 题的解决方题的解决方 法法 模拟退火算法模拟退火算法 四、配送车辆影响因素四、配送车辆影响因素 不确定性因素不确定性因素 确定性因素确定性因素 配送车辆的影响因素配送车辆的影响因素 车速车速 路径路径 载重量载重量 费用费用 堵车，路障堵车，路障 其他打断时间其他打断时间 五、本文中使用的方法五、本文中使用的方法 1 1、节约里程法（、节约里程法（VSPVSP规划法）规划法） 基本原理：基本原理： ijji cccjis 00 ),( 2、 LOGWARE软件软件 LOGWARE 是为了分析多种

5、物流管理与供应链问是为了分析多种物流管理与供应链问 题和例子的精选软件程序集合。它包含有十六个题和例子的精选软件程序集合。它包含有十六个 模块组件。模块组件。 六、案例分析六、案例分析 有一配送中心有一配送中心p，A-S表示表示p附近需要配送的各零附近需要配送的各零 售商，早上售商，早上8点开始配送，要求与当天点开始配送，要求与当天14点之前必须配点之前必须配 送完毕，每辆车每天平均工作时间不超过送完毕，每辆车每天平均工作时间不超过6.5小时，在小时，在 每个送货点停留的时间为每个送货点停留的时间为10分钟，途中速度为分钟，途中速度为25km/h， 假设工厂只拥有假设工厂只拥有20吨车，每次出

6、发最多能带吨车，每次出发最多能带20吨的重吨的重 量而且每次不超过量而且每次不超过6小时。并且限制车辆一次运输的最小时。并且限制车辆一次运输的最 远距离为远距离为40公里，配送中心位于坐标原点，每个送货公里，配送中心位于坐标原点，每个送货 点的位置和货物重量如下表所示，并且假设街道的长点的位置和货物重量如下表所示，并且假设街道的长 度是两点间直线距离的度是两点间直线距离的1.21倍。请问怎样安排运输路倍。请问怎样安排运输路 线，使配送中心需要的最少员工数和车辆数，运输距线，使配送中心需要的最少员工数和车辆数，运输距 离最小？离最小？ 案例案例 x坐标坐标 y坐标坐标 需求量（需求量（t） x坐

7、标坐标 y坐标坐标 需求（需求（t） P 0.00 0.00 J -1.00 5.00 6 A -5.00 -1.00 6 K 1.00 7.00 5 B -4.00 1.00 5 L 1.00 3.00 4 C -2.00 0.00 8 M 2.00 6.00 8 D -6.00 9.00 5 N 3.00 12.00 6 E -5.00 7.00 7 O 4.00 1.00 4 F -3.00 4.00 8 P 5.00 5.00 5 G -3.00 5.00 3 Q 7.00 1.00 3 H -1.00 3.00 9 R 9.00 2.00 6 I 6.00 10.00 5 S 10.

8、00 7.00 8 一、节约里程法一、节约里程法 第一步，计算配送中心到配送点间的最短距离，画出第一步，计算配送中心到配送点间的最短距离，画出 距离表。由于知道各个配送点间的坐标，利用勾股定距离表。由于知道各个配送点间的坐标，利用勾股定 理即可算出配送中心与配送点间的距离。理即可算出配送中心与配送点间的距离。 pABCDEF P05.14.12210.829.175 A5.102.243.1610.0685.39 B4.122.2402.248.256.083.16 C23.162.2409.8534.12 第二步，根据距离表，利用节约法计算出用户间的第二步，根据距离表，利用节约法计算出用户间

9、的 节约里程，并由大到小排列，编制节约里程顺序表。节约里程，并由大到小排列，编制节约里程顺序表。 L=（La+Lb）Lab 例如例如L1=(LpA+LpB)LAB=(5.10+4.12)2.24=6.98 p-I-N 20.43 p-E-I 9.43 p-I-S 18.87 p-J-N 9.41 p-D-E 17.75 p-J-K 9.34 p-R-S 16.33 p-F-G 8.9 第三步，根据节约里程顺序表和配送中心的约束条件，绘第三步，根据节约里程顺序表和配送中心的约束条件，绘 制配送路线。制配送路线。 七次解之后，得到最终配送路七次解之后，得到最终配送路 线所示，总配送重量线所示，总配

10、送重量111t，总，总 共走行里程共走行里程117.33km，共节约，共节约 里程里程141.96km。 第四次解得到的线路第四次解得到的线路 根据实例所给出的信息，运用根据实例所给出的信息，运用Logware软件软件 解决问题，将各个数值填入到相应的地方解决问题，将各个数值填入到相应的地方 。 二、二、Logware 软件软件 数据填写完成后，点击数据填写完成后，点击Solve按钮，就可以得到解按钮，就可以得到解 决的路线图决的路线图。 软件运行得出结果：总共走行里程软件运行得出结果：总共走行里程116.7km，共，共 节约里程节约里程142.59km。利用节约里程法算出的结果和。利用节约里

11、程法算出的结果和 用软件得出的结果不是完全相同，但是总共走行里程用软件得出的结果不是完全相同，但是总共走行里程 数与共节约里程基本相同，两个结果的差值仅为数与共节约里程基本相同，两个结果的差值仅为 0.63km。由于两种方法各有优缺点，所得结果不尽。由于两种方法各有优缺点，所得结果不尽 相同，节约里程法没有考虑配送时间，还有配送中所相同，节约里程法没有考虑配送时间，还有配送中所 花费的费用问题；花费的费用问题；Logware软件考虑了相关的时间和软件考虑了相关的时间和 费用问题。费用问题。 解决方案运行完成后，在按下解决方案运行完成后，在按下Report就可以得到就可以得到 一份报告。这份报告

12、提供了关于所有路径和在各个路一份报告。这份报告提供了关于所有路径和在各个路 径上详细花费，和所耗时间的概要信息。径上详细花费，和所耗时间的概要信息。 总结总结 （1 1）车辆线路问题安排是车辆线路问题安排是 运输配送中的难题之一，配运输配送中的难题之一，配 送车辆线路问题可以减少企送车辆线路问题可以减少企 业的相关费用，有利于优化业的相关费用，有利于优化 社会资源，带来社会利润。社会资源，带来社会利润。 （2）在对配送车辆路径选）在对配送车辆路径选 择的过程中，本文只选用了择的过程中，本文只选用了 两种便捷的方法，还有更加两种便捷的方法，还有更加 有效的方法需要在今后的工有效的方法需要在今后的工 作中展开研究。作中展开研究。 （3）通过本文的研究，发）通过本文的研究，发 现配送车辆路径研究给企业现配送车辆路径研究给企业 带来