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

行车路线和时刻表制定的改进方法研究 摘 要：运输中起迄点相同的配送问题是目前许多配送企业面临的一个难题，对于需求站点较多、需求批量小而频次多的零担运输的情况，寻求最佳配送方案更是难以实现。本文从需求站点的路线分类下手，引入模糊聚类分析方法，对所有需求站点进行科学分类，并用动态规划的方法对各站点群进行求解，从而确定最佳行车路线和时刻表。最后与传统方法所做出的配送方案相比较，实现了成本的较大节约，具有良好的可操作性，可以有效地解决路线规划的问题。 关键词：行车路线，模糊聚类，动态规划，时间窗口 The research of improving the methods of Routings and Schedules development Abstract: 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 distribution 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 by 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%左右，比仓储成本、库存成本等任何其他物流成本所占的比重都高。对于运输问题，需要解决的包括运输方式的选择、运输路线的选择、车辆调度和合并运输这些内容。其中最常见的问题就是，找到运输工具在公路网、铁路线、水运航道和航空线运行的最佳路线以尽可能的缩短运输时间或运输距离。 运输路线选择问题种类繁多，在这里将其分为三类：一是起讫点不同的单一路径规划；二是多个起讫点的路径规划；三是起讫点相同的路径规划。第三类问题时起讫点不同问题的扩展形式，由于要求车辆必须回到起点行程才结束，问题的难度提高了。本文就是针对起讫点相同的路径规划这一问题展开的，我们的目标是找出途径站点的最佳顺序，使行车路线必须经过所有站点，且总出行时间或总距离最短。 人们已经提出不少方法来解决起讫点重合的路径问题。对于现实的运输问题，使用感知式和启发式的求解方法，例如扫描法（The Sweep Method）、节约法（The Saving Method）等方法来解决。但这些方法都或多或少的存在一些问题，扫描法将分派车辆服务地点和决定行车路线分成两步，对诸如在途总运行时间和时间窗口等问题处理得不好。而节约法将各个站点合并来确定各条路线，无法满足约束条件，例如不符合时间窗口的要求、超过车辆的承载能力、在途时间过长等，而导致节约距离最多的点不能并入路线，只能考虑节约距离次多的点。如果运输问题中包括很多站点，要找出最优路径是不切实际的，因为现实中还有其他问题，例如驾驶员的总驾驶时间限制、途中用餐及休息时间、服务水平的高低问题等，因此，现实问题的规模太大，即使使用最快的计算机进行计算，求最优解的时间也非常长。 所以，我们面临的问题就是找出一种有效的方法，确保我们所规划的每一条运输路线上的站点及其顺序是合理的，并且所有这些运输路线加起来的总运输距离是最短的，同时满足现实约束条件。合理路线和时刻表的制定应服从以下原则： （1）安排车辆负责相互距离最接近的站点的货物运输