《2022年行车路线和时刻表制定改进方法研究报告》由会员分享,可在线阅读,更多相关《2022年行车路线和时刻表制定改进方法研究报告(7页珍藏版)》请在金锄头文库上搜索。
1、个人资料整理仅限学习使用行车路线和时刻表制定的改进方法研究摘 要: 运输中起迄点相同的配送问题是目前许多配送企业面临的一个难题,对于需求站点较多、需求批量小而频次多的零担运输的情况,寻求最佳配送方案更是难以实现。本文从需求站点的路线分类下手,引入模糊聚类分析方法,对所有需求站点进行科学分类,并用动态规划的方法对各站点群进行求解,从而确定最佳行车路线和时刻表。最后与传统方法所做出的配送方案相比较,实现了成本的较大节约,具有良好的可操作性,可以有效地解决路线规划的问题。关键词: 行车路线,模糊聚类,动态规划,时间窗口The research of improving themethods of R
2、outings and Schedules developmentAbstract:The issue of the transportation which comes back to the same point is the distribution of many distribution enterprises are facing a problem, to demand more sites, demand volume and frequency of the small number of the transport load, find the best distribut
3、ion program is more difficult to achieve. From Site Classification start line, the introduction of fuzzy clustering analysis of all sites demand for scientific classification, and use dynamic programming method for the site-solving, in order to determine the best routes and schedules. Finally made b
4、y the traditional method of distribution program, compared to the cost of the larger economies, with good workability, can be effectively resolved route planning. Keywords: routings, fuzzy clustering, dynamic programming, the time window运输是物流决策中的关键所在,除采购产品的成本外,一般来讲,运输成本占物流总成本的40% 左右,比仓储成本、库存成本等任何其他物
5、流成本所占精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页,共 7 页个人资料整理仅限学习使用的比重都高。对于运输问题,需要解决的包括运输方式的选择、运输路线的选择、车辆调度和合并运输这些内容。其中最常见的问题就是,找到运输工具在公路网、铁路线、水运航道和航空线运行的最佳路线以尽可能的缩短运输时间或运输距离。运输路线选择问题种类繁多,在这里将其分为三类:一是起讫点不同的单一路径规划;二是多个起讫点的路径规划;三是起讫点相同的路径规划。第三类问题时起讫点不同问题的扩展形式,由于要求车辆必须回到起点行程才结束,问题的难度提高了。本文就是针对起讫点
6、相同的路径规划这一问题展开的,我们的目标是找出途径站点的最佳顺序,使行车路线必须经过所有站点,且总出行时间或总距离最短。人们已经提出不少方法来解决起讫点重合的路径问题。对于现实的运输问题,使用感知式和启发式的求解方法,例如扫描法The Sweep Method)、节约法The Saving Method )等方法来解决。但这些方法都或多或少的存在一些问题,扫描法将分派车辆服务地点和决定行车路线分成两步,对诸如在途总运行时间和时间窗口等问题处理得不好。而节约法将各个站点合并来确定各条路线,无法满足约束条件,例如不符合时间窗口的要求、超过车辆的承载能力、在途时间过长等,而导致节约距离最多的点不能并
7、入路线,只能考虑节约距离次多的点。如果运输问题中包括很多站点,要找出最优路径是不切实际的,因为现实中还有其他问题,例如驾驶员的总驾驶时间限制、途中用餐及休息时间、服务水平的高低问题等,因此,现实问题的规模太大,即使使用最快的计算机进行计算,求最优解的时间也非常长。所以,我们面临的问题就是找出一种有效的方法,确保我们所规划的每一条运输路线上的站点及其顺序是合理的,并且所有这些运输路线加起来的总运输距离是最短的,同时满足现实约束条件。合理路线和时刻表的制定应服从以下原则:1)安排车辆负责相互距离最接近的站点的货物运输,站点群应该尽可能得紧凑;2)安排行车路线时应该尽量避免各条线路交叉;3)注意时间
8、窗口的限制;4)各行车路线应尽可能呈水滴状或凸形;5)对于遥远而无法归入群落的站点,可以采用外包的配送方式。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页,共 7 页个人资料整理仅限学习使用由上述的五点原则可以看出,合理的分配站点是解决问题的关键。在这里,我们引入一种科学的分类方法模糊聚类分析方法。聚类分析又称点群分析、群分析等,是按照研究对象在性质上的亲疏关系进行分类的一种多元统计方法,它能够反映样本之间的内在组合关系。现实中的分类问题大多伴随模糊性,类与类之间并无清晰的界限,在聚类分析中引进模糊技术更为合理,也就是模糊聚类分析。本文将应
9、用模糊聚类分析对需求站点进行分类, 确定企业自营物流的需求点和物流外包的需求点, 通过建立车辆调度的数学模型, 使用动态规划的方法确定各类中的行车最优路线。1、配送站点模糊聚类分析1)数据标准化对于论域 U=x1,x2, ,xn 为被分类的对象,每个对象又有m个指标表示其形状,于是得到原始数据矩阵为:X=n*m。根据模糊矩阵的要求将数据标准化,通过平移标准差变换压缩到0 ,1 区间上。2)标定 建立模糊矩阵)使用距离法确定聚类统计量,在这里采用欧式距离。欧式距离为:令,其中 c 为适当选取的参数。3)聚类 ,需要向 L个客户送货,每个客户的货物需求量为(i=1,2,L,需求站点 i 到 j 的
10、运距为,物流中心到各客户的距离为 (i=1,2,L。再设为第 k 台车辆配送的客户数 (=0 表示未使用第k 台车辆 ,用集合表示第 k 条路径。其中的元素表示客户在路径k 中的顺序为i( 不包括物流配送中心,并令=0 表示物流中心。以配送总里程最短为目标函数,建立车辆优化调度问题的数学模型为:1)以需要访问的站点数作为阶段,状态变量为,为车辆当前所在的站点,/为车辆尚未到达的站点,其中。2)决策变量与有关,是在的状态下做出的选择,允许决策集合为/,形成的序列即为决策序列。3)从第 m个状态到达第 m+1个状态的状态转移方程为。4)指标函数为从出发,遍访中的每一个点回到仓库的最优路线。3、实例
11、分析某公司有5 辆送货汽车以及足够的司机为预售客户提供服务,每辆卡车可装载 500 箱货物,卡车的运行成本为每英里0.9 美元,每小时付司机13 美元。卡车必须在早晨6:30 至 8:30 之间离开仓库开始送货。如果司机每天在精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页,共 7 页个人资料整理仅限学习使用路上的时间超过8 小时 不包括午餐时间),就要支付双倍的标准工资。运输途中有半小时的午餐时间,午餐时间应该在中午11:30 至 13:30 之间。有几个客户要求在特定时间 时间窗口)送货。在时间窗口开始或结束之后,不允许送货。客户数据间表
12、1。该地区的公路网建设得很好,没有河流、湖泊或其他需要绕行的障碍。运输距离和运输时间是直接相关的,平均车速为25 英里/ 小时。客户序号坐标送货时间X 英里)Y 英里)需求量箱)服务时间分钟)时间窗口1 7.5 28.5 120 60 8:00-17:00 2 10 9 200 90 8:00-10:30 3 12 24 120 60 8:00-17:00 4 13 30 150 80 8:00-17:00 5 13.5 34 50 40 8:00-17:00 6 17.5 16.5 90 50 8:00-17:00 7 23 38.5 140 70 8:00-8:30 8 23 16.5 6
13、0 40 8:00-17:00 9 23.5 25 110 60 8:00-17:00 10 27 33.5 180 90 8:00-10:45 11 29 28 30 20 8:00-11:00 14:00-16:00 12 11 40 90 50 8:00-8:30 13 32 40 80 50 8:00-10:00 14 7.5 18 50 30 12:30-17:30 15 5 13.5 160 90 8:00-12:45 16 23 8 100 60 8:00-17:00 17 27 8 140 60 8:00-17:00 18 36 8 50 30 8:00-17:00 19 32
14、 4 90 50 12:00-16:00 20 32.5 22 150 70 8:00-17:00 21 31.5 13 80 40 8:00-17:00 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页,共 7 页个人资料整理仅限学习使用总计2240 箱1190 分钟仓库13 35 表 1 由于运输不受道路状况的影响,在分析这21 个需求站点时,可以仅仅针对其地理位置使用模糊聚类分析。使用MATLAB 编程,聚类图如下图1 所示:图 1 根据上图,按照卡车运量可将21 个客户分为为五组,这种分类的相干系数为 0.6731。如表 2 所示:第
15、一条运输线路16,17,18,18,21 第二条运输线路9,10,11,20 第三条运输线路2,8,14,15 第四条运输线路1,3,5,6,12 第五条运输线路4,7,13 表 2 将每条线路按照各自时间窗口的要求使用动态规划求得其各条线路的途径站点顺序、出发时间和最终回到仓库的时间如下表3:线路名称出发时间途径站点顺序回仓库时间第一条运输线路7:55 16,17,午餐, 19,18,21 15:59 第二条运输线路7:26 10,11,20,午餐, 9 14:06 第三条运输线路7:09 8, 2,15,午餐, 14 14:30 第四条运输线路7:47 12, 1,3,午餐, 6,5 14
16、:45 第五条运输线路7:34 7,13,4,午餐13:16 表 3 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页,共 7 页个人资料整理仅限学习使用5 条路线共行驶 295.29925 英里, 5 位司机工作时间总和为31.6453 小时,一天的运输成本为677.1582683 美元。若是用扫描法安排路线,其结果如下表4 所示:线路名称出发时间途径站点顺序第一条运输线路7:45 12,15,1,14,5 第二条运输线路7:33 2,3,4 第三条运输线路7:22 1,16,17, 8,9 第四条运输线路8:00 11,20,18,21,
17、19 第五条运输线路7:39 7,13,10, 6 表 4 5 条路线共行驶 375.29978 英里, 5 位司机工作时间总和为34.8253 小时,一天的运输成本为790.75626 美元。二者相比较,每天可节约113 美元的成本。4、结果分析1)将各个站点进行模糊聚类分析,根据各需求点的地理位置进行合理的划分,然后采用动态规划的算法求解客户子类中的最优运输路线,为解决行车路线选择问题提供了新的思路和途径。2)使用模糊聚类的方法可以使站点群更加紧凑,站点之间的行车时间最短。最大程度的避免了不同行车线路的交叉,加大了对每一辆车的充分利用。 罗 纳 德 H 巴 罗 教 授 柏塞克斯 (Bertsekas,D.P. 著,西安交通大学出版社, 1990年 1 月。3 模糊数学,楼世博,孙章,陈化成著,科学出版社,1987年。4Matlab数理统计 (6.X,陈桂明,戚红雨著,科学出版社,2002年 9 月。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页,共 7 页