行车路线和时刻表制定的改进方法研究

行车路线和时刻表制定的改进方法研究摘要：运输中起迄点相同的配送问题是目前许多配送企业面临的一个难题，对于需求站点较多、需求批量小而频次多的零担运输的情况，寻求最佳配送方案更是难以实现。本文从需求站点的路线分类下手，引入模糊聚类分析方法，对所有需求站点进行科学分类，并用动态规划的方法对各站点群进行求解，从而确定最佳行车路线和时刻表。最后与传统方法所做出的配送方案相比较，实现了成本的较大节约，具有良好的可操作性，可以有效地解决路线规划的问题。关键词：行车路线，模糊聚类，动态规划，时间窗口TheresearchofimprovingthemethodsofRoutingsandSchedulesdevelopmentAbstract:Theissueofthetransportationwhichcomesbacktothesamepointisthedistributionofmanydistributionenterprisesarefacingaproblem,todemandmoresites,demandvolumeandfrequencyofthesmallnumberofthetransportload,findthebestdistributionprogramismoredifficulttoachieve.FromSiteClassificationstartline,theintroductionoffuzzyclusteringanalysisofallsitesdemandforscientificclassification,andusedynamicprogrammingmethodforthesite-solving,inordertodeterminethebestroutesandschedules.Finallymadebythetraditionalmethodofdistributionprogram,comparedtothecostofthelargereconomies,withgoodworkability,canbeeffectivelyresolvedrouteplanning.Keywords:routings,fuzzyclustering,dynamicprogramming,thetimewindow运输是物流决策中的关键所在，除采购产品的成本外，一般来讲，运输成本占物流总成本的40%左右，比仓储成本、库存成本等任何其他物流成本所占的比重都高。对于运输问题，需要解决的包括运输方式的选择、运输路线的选择、车辆调度和合并运输这些内容。其中最常见的问题就是，找到运输工具在公路网、铁路线、水运航道和航空线运行的最佳路线以尽可能的缩短运输时间或运输距离。运输路线选择问题种类繁多，在这里将其分为三类：一是起讫点不同的单一路径规划；二是多个起讫点的路径规划；三是起讫点相同的路径规划。第三类问题时起讫点不同问题的扩展形式，由于要求车辆必须回到起点行程才结束，问题的难度提高了。本文就是针对起讫点相同的路径规划这一问题展开的，我们的目标是找出途径站点的最佳顺序，使行车路线必须经过所有站点，且总出行时间或总距离最短。人们已经提出不少方法来解决起讫点重合的路径问题。对于现实的运输问题，使用感知式和启发式的求解方法，例如扫描法（TheSweepMethod）、节约法（TheSavingMethod）等方法来解决。但这些方法都或多或少的存在一些问题，扫描法将分派车辆服务地点和决定行车路线分成两步，对诸如在途总运行时间和时间窗口等问题处理得不好。而节约法将各个站点合并来确定各条路线，无法满足约束条件，例如不符合时间窗口的要求、超过车辆的承载能力、在途时间过长等，而导致节约距离最多的点不能并入路线，只能考虑节约距离次多的点。如果运输问题中包括很多站点，要找出最优路径是不切实际的，因为现实中还有其他问题，例如驾驶员的总驾驶时间限制、途中用餐及休息时间、服务水平的高低问题等，因此，现实问题的规模太大，即使使用最快的计算机进行计算，求最优解的时间也非常长。所以，我们面临的问题就是找出一种有效的方法，确保我们所规划的每一条运输路线上的站点及其顺序是合理的，并且所有这些运输路线加起来的总运输距离是最短的，同时满足现实约束条件。合理路线和时刻表的制定应服从以下原则：（1）安排车辆负责相互距离最接近的站点的货物运输，站点群应该尽可能得紧凑；（2）安排行车路线时应该尽量避免各条线路交叉；（3）注意时间窗口的限制；（4）各行车路线应尽可能呈水滴状或凸形；（5）对于遥远而无法归入群落的站点，可以采用外包的配送方式。由上述的五点原则可以看出，合理的分配站点是解决问题的关键。在这里，我们引入一种科学的分类方法——模糊聚类分析方法。聚类分析又称点群分析、群分析等，是按照研究对象在性质上的亲疏关系进行分类的一种多元统计方法，它能够反映样本之间的内在组合关系。现实中的分类问题大多伴随模糊性，类与类之间并无清晰的界限，在聚类分析中引进模糊技术更为合理，也就是模糊聚类分析。本文将应用模糊聚类分析对需求站点进行分类,确定企业自营物流的需求点和物流外包的需求点,通过建立车辆调度的数学模型,使用动态规划的方法确定各类中的行车最优路线。1、配送站点模糊聚类分析（1）数据标准化对于论域U={x1,x2,…，xn}为被分类的对象，每个对象又有m个指标表示其形状，于是得到原始数据矩阵为：X=[ijx]n*m。根据模糊矩阵的要求将数据标准化，通过平移标准差变换压缩到[0，1]区间上。11x12x…1mx21x22x…2mx…………n1xn2x…nmx（2）标定（建立模糊矩阵）使用距离法确定聚类统计量)x,x(Rrjiij，在这里采用欧式距离。欧式距离为：m1k2)jkxikx()jx,ix(d令)x,cd(x1rjiij，其中c为适当选取的参数。（3）聚类（并画出聚类图）根据聚类图，按照每一辆卡车的装载量合理的分配站点，并计算出相关系数。2建立数学模型问题可以描述为：从某个仓库用多台配送车辆向多个客户送货，每个客户的位置和货物需求量一定，各配送车辆的载重量一定，各司机每天的工作时间上限一定，要求合理安排车辆配送路线，使目标函数得到优化，并满足以下条件：每条配送路径上各客户的需求量之和不超过配送车辆的载重量；每条配送路线所花费的时间不超过司机的最长驾驶时间；必须满足每个客户的需求，该客户的需求货物只能由一辆车一次性配送。设仓库有K台配送车辆，每台车辆的载重量为KQ(k=1,2,…,K)，需要向L个客户送货，每个客户的货物需求量为iq(i=1,2,…,L)，需求站点i到j的运距为ijd，物流中心到各客户的距离为0id(i=1,2,…,L)。再设kn为第k台车辆配送的客户数(kn=0表示未使用第k台车辆)，用集合KR表示第k条路径。其中的元素kir表示客户kir在路径k中的顺序为i(不包括物流配送中心)，并令k0r=0表示物流中心。以配送总里程最短为目标函数，建立车辆优化调度问题的数学模型为：（1）以需要访问的站点数作为阶段，状态变量为ms，ms为车辆当前所在的站点，kR/ms为车辆尚未到达的站点，其中ms∈kR。（2）决策变量mu与ms有关，是在ms的状态下做出的选择，允许决策集合为kR/ms，mu形成的序列即为决策序列。（3）从第m个状态到达第m+1个状态的状态转移方程为),(1mmmmsuTs。（4）指标函数为)(),({)(11kmmmmmmsfsudoptsf从ms出发，遍访kR中的每一个点回到仓库的最优路线。3、实例分析某公司有5辆送货汽车以及足够的司机为预售客户提供服务，每辆卡车可装载500箱货物，卡车的运行成本为每英里0.9美元，每小时付司机13美元。卡车必须在早晨6：30至8：30之间离开仓库开始送货。如果司机每天在路上的时间超过8小时（不包括午餐时间），就要支付双倍的标准工资。运输途中有半小时的午餐时间，午餐时间应该在中午11：30至13：30之间。有几个客户要求在特定时间（时间窗口）送货。在时间窗口开始或结束之后，不允许送货。客户数据间表1。该地区的公路网建设得很好，没有河流、湖泊或其他需要绕行的障碍。运输距离和运输时间是直接相关的，平均车速为25英里/小时。客户序号坐标送货时间X（英里）Y（英里）需求量（箱）服务时间（分钟）时间窗口17.528.5120608:00-17:002109200908:00-10:3031224120608:00-17:0041330150808:00-17:00513.53450408:00-17:00617.516.590508:00-17:0072338.5140708:00-8:3082316.560408:00-17:00923.525110608:00-17:00102733.5180908:00-10:4511292830208:00-11:0014:00-16:0012114090508:00-8:3013324080508:00-10:00147.518503012:30-17:3015513.5160908:00-12:4516238100608:00-17:0017278140608:00-17:001836850308:00-17:0019324905012:00-16:002032.522150708:00-17:002131.51380408:00-17:00总计2240箱1190分钟仓库1335表1由于运输不受道路状况的影响，在分析这21个需求站点时，可以仅仅针对其地理位置使用模糊聚类分析。使用MATLAB编程，聚类图如下图1所示：图1根据上图，按照卡车运量可将21个客户分为为五组，这种分类的相干系数为0.6731。如表2所示：第一条运输线路16，17，18，18，21第二条运输线路9，10，11，20第三条运输线路2，8，14，15第四条运输线路1，3，5，6，12第五条运输线路4，7，13表2将每条线路按照各自时间窗口的要求使用动态规划求得其各条线路的途径站点顺序、出发时间和最终回到仓库的时间如下表3：线路名称出发时间途径站点顺序回仓库时间第一条运输线路7：5516，17，午餐，19，18，2115：59第二条运输线路7：2610，11，20，午餐，914：06第三条运输线路7：098，2，15，午餐，1414：30第四条运输线路7：4712，1，3，午餐，6，514：45第五条运输线路7：347，13，4，午餐13：16表35条路线共行驶295.29925英里，5位司机工作时间总和为31.6453小时，一天的运输成本为677.1582683美元。若是用扫描法安排路线，其结果如下表4所示：线路名称出发时间途径站点顺序第一条运输线路7：4512，15，1，14，5第二条运输线路7：332，3，4第三条运输线路7：221，16，17，8，9第四条运输线路8：0011，20，18，21，19第五条运输线路7：397，13，10，6表45条路线共行驶375.29978英里，5位司机工作时间总和为34.8253小时，一天的运输成本为790.75626美元。二者相比较，每天可节约113美元的成本。4、结果分析（1）将各个站点进行模糊聚类分析，根据各需求点的地理位置进行合理的划分，然后采用动态规划的算法求解客户子类中的最优运输路线，为解决行车路线选择问题提供了新的思路和途径。（2）使用模糊聚类的方法可以使站点群更加紧凑，站点之间的行车时间最短。最大程度的避免了不同行车线路的交叉，加大了对每一辆车的充分利用。（3）各个站点群使用动态规划的方法保证了各个群的路线是最佳路线。参考文献：[1]BusinessLogisticsManagement，(美)罗纳德·H·巴罗教授（RonaldH.Ballou）著，机械工业出版社，2002年1月。[2]动态规划：确定性和随机模型，(美)柏塞克斯(Bertsekas,D.P.)著，西安交通大学出版社，1990