物流配送车辆优化调度问题的探讨.doc

物流配送车辆优化调度问题的探讨物流配送车辆优化调度问题的探讨 摘 要随着经济的不断发展，城市正发生着日新月异的变化。城市的发展离不开大量货车的使用，所以如何解决物流配送车辆优化调度的问题就逐步成为城市建设发展的焦点。物流配送车辆优化调度的问题，即对固定的装（卸）货地点，选择较为适当的行车路线让车辆井然有序的从各个路点通过，并且在按照要求完成任务的情况下还起到了一定的优化作用。本文从物流配送的概述和流程开始深入，针对物流配送车辆优化调度问题的分类和优化算法方面做了详细的介绍，还进一步的分析了国内外在物流配送车辆优化调度问题上的研究现状以及以后的发展方向。 1 物流配送概述及其流程 1.1 物流配送的基本概述 将目标货物从发货人送至收货人的过程被称为配送。由于配送最终的目标是收货人，即为消费者，因此，配送也是物流系统中的一个至关重要的步骤。配送不仅仅局限于配货和送货。满足客户的需求，配送需要在满足客户对货物种类数量的基础上，在保证按时送达客户的基础上选取更快，更节约成本的配送方案，实现利益最大化。 1.2 物流配送系统的优化 为找到一个最佳的物流配送方案，应该从以下几个方面着手：配送车辆的调度，对集货线路的选取，对送货路线的选择，实现集货送货相统一。对配送系统的优化不仅可以增加物流的经济效益，更有助于实现科学化、现代化物流管理，显著提升物流的服务质量，提高物流公司信誉，从而有效地降低物流成本。 1.3 物流配送的流程 随着物流配送的发展，现代物流配送水平的提高，货物流通性大大增强，传统的存储环节作用正逐渐式微，也使得配送环节取代存储环节成为物流中最重要的部分。而作为配送的核心配送车辆对货物的集货、配送和送货过程越来越被重视，如何选取最优配送路线，是对整个物流质量的考验，关系着物流整体的运输速度、服务成本和经济效益。随着电子商务的崛起，以集货作业和配货作业为主体的新物流模式已然形成。 2 车辆优化调度问题的分类和优化算法 2.1 车辆优化调度问题的分类 根据不同的性质，可将车辆优化调度问题分成不同的类型。 按照运输任务可将车辆优化调度问题分为三类，即纯装、纯卸、装卸混合三类问题。 按照车辆的载货情况可将车辆优化调度问题分为两类，即满载、非满载问题。满载是指货量大于车载量，需要多辆车运输。非满载是指车载量大于货量，一辆车就能完成任务。 按照车辆类型可将车辆优化调度问题分为两类，即单车型、多车型问题。 按照车辆是否返回可将车辆优化调度问题分为两类，即车辆开放（车辆不返回）、车辆封闭（车辆返回）问题。 按照优化的目标可将车辆优化调度问题分为两类，即单目标、多目标问题。 按照有无休息时间可将车辆优化调度问题分为两类，即有休息时间调度、无休息时间调度问题。 2.2 车辆优化调度问题的优化算法 2.2.1 精确算法 精确算法又称最优化算法，是指求出最佳解的算法。其算法有很多，比如切割平面法、网络流算法等。 精确算法有一个弊端，就是其计算量随着需要解决的问题规模的增大而大幅度的增大。由于这个弊端，精确算法只能适合解决规模较小的问题。因为精确算法适应能力较差，一般这种算法最适合解决一个特定的问题，所以在实际应用中这种算法不是很受提倡。 2.2.2 启发式算法 启发式算法完全不同于精确算法，它追求的是解决问题的满意性而不是最优性。它是一种用直观、经验构造出来的算法。到目前为止，启发式算法已经有好多种，最主要是以下两种算法。 构造启发式算法，其实质就是按照标准将不在同一条线路的所有点逐个的增加进来。在算法的每一步上，都要将当前的线路构型和另外的线路构型比较后，综合改进得到最后可行的构型。这类算法的代表算法是：最邻近法、扫描法、节约法等。 智能化启发式算法就是在人工智能的启发式算法的基础上发展的。它的主要算法有：蚁群算法、神经网络算法等。 启发式算法在解决大规模的PDPTW问题上分为经典启发式算法和现代启发式算法。 经典启发式算法主要有路径构造算法和路径改造算法等。路径构造算法其实质就是分解算法，就是将一个问题分为两个阶段（路由和排序）来解决。路径改造算法是在路径构造算法上改进的，其第一个阶段就是找到一个可行解，下一阶段就是调整客户端，在满足可行的条件下，对路径进行调整，使其比当前路径更加优化，一直按照这样优化下去，直到不能优化为止。 现代启发式算法中，最主要的就是禁忌搜索算法和模拟退火算法。 禁忌搜索算法是禁忌搜索算法的一种变形，是现代局部搜索技术的一种。其实质是近期被多次循环搜索过的算法被禁用。它的优点是减少需要考虑的移动次数，最终达到减少计算时间的目的。改进阶段和混合阶段是禁忌搜索算法的主要步骤，一个是得到最优解，另一个是跳出最优解。 模拟退火算法。其算法具体过程是：在随机产生的可行解，每次循环时都随机挑选出一个好的和一个较差的可行解，这样就避免陷入局部最优解里。这个算法的弊端就是执行起来速度较慢。基于这个弊端提出了好几类优化后的算法，这些算法在实际应用中都很有效果。 2.3 动态求解算法 动态车辆调度问题相对前两种比较其问题的规模较大解决起来相对比较困难些。并且这种算法的要求是在短时间内就要相应其实时信息。从求解策略上把动态求解算法分为重新优化策略和局域优化策略。 2.3.1 重新优化策略 重新优化策略就是当接收到一个新的实时信息时，要重新开始寻找始发到结束的最优车辆的行车路径。实质就是静态方法解决动态问题。研究运送大宗商品的车辆调度问题就是一个较为成功的运用重新优化策略的例子。还有在动态单车问题上，采用了乘子调整技术的静态算法。其算法过程是：当有新实时信息时，就采用动态重新优化法解决，可是这种算法最多能解决十种问题。 重新优化策略的缺点是每次接到新的实时信息时都要重新优化设计，这样下去当接收的实时信息较多时，其计算量是较大的。当遇到需要迅速解决的问题时，根本没有时间去进行重新优化，所以这种算法在实际运用上是不可实现的。 2.3.2 局域优化策略 局域优化策略的实质是：提前拟定一些路径的模板，当收到实时信息时，就在提前拟定的模板里进行搜索，找个适合的路径进行使用。这种策略和重新优化策略相比较，路径可能是较差的，但是计算量是大大的减少了，从而节约了许多的时间。局域优化策略在实际的车辆调度上比较适用，所以受到重视和近一步的研究。再后来提出的插入法较为适用，改进后的插入法其具体实现方法是：当接收到新的实时信息时，不直接进行优化调度，而是等待以后的需求，这样就可以降低它的短视行为。还可以把插入法和优化算法结合起来使用，在对路径优化以后再获得更好的解。 3 车辆优化调度问题的研究现状 物流配送车辆优化调度问题在国外的应用要比国内发展迅速。其发展已经涉及各个领域，不论是工业材料的运输、网购的货运配送和运输、连锁店的货物发送等这样的大型车辆调度方面，还是报纸、牛奶投递等这样的小调度方面对于线路优化的运用都会取得较为理想的经济效益。最典型的例子就是全球闻名的沃尔玛特公司，它们就是运用了最先进的物流配送指挥系统所以才会在同行中遥遥领先。随着对物流配送车辆优化调度问题的深入研究，物流配送车辆优化调度不仅在汽车领域发展，现在还应用在了航空、轮船方面。在不久的将来，相信其发展领域会更加广阔。 在我国境内，车辆调度问题的发展比国外晚发展近乎三十年，所以现在我国对于较为复杂的车辆调度路径问题研究还是相对落后。由于我国对这方面研究起步较晚，对于通用理论研究不够深入，再加上我国对于应用研究的问题提出虽多但是都是在具体算法上的改进，并没有创新，所以我国在车辆优化调度的问题上根本无法满足配送业和物流业的发展需求。随着物流业在市场上的地位日益重要。为了克服我国在车辆优化调度上局限性较强的弱点，我国逐渐开始对车辆优化调度问题进行深入的研究并且现在已经取得初步的成功。 4 结 论 随着物流业和配送业在市场上的发展需求逐步扩大，车辆优化调度问题日益重要。国外在车辆优化调度问题上发展较快，已经在生产和生活方面广泛应用并且得到了很好的经济效益。可是我国在车辆优化调度问题上的发展起步较晚，发展速度相对较慢，不能满足我国经济发展的需求。所以为了使我国国民经济发展迅速、人们生活质量提高，就要在物流配送业上大力研究发展车辆优化调度问题。其主要研究方向就是：根据车辆优