【作者】 段凤华；

【导师】 符卓；

【作者基本信息】 中南大学 ， 物流工程， 2010， 博士

【摘要】 车辆路径问题是运输组织优化中的核心问题之一。本文将首先对车辆路径问题的特点、分类以及求解算法的研究现状等进行综述。带软时间窗约束的开放式车辆路径问题在实践中广泛存在。它与基本的车辆路径问题的主要不同点,一是不要求车辆完成运输任务后返回原出发点,或者是若要求返回原出发点,则沿原去程路线返回,二是客户希望车辆在给定时间窗内进行服务,如果违背了时间窗,则须支付惩罚。本文对带软时间窗约束的开放式车辆路径问题从理论上进行了研究。通过利用所研究的问题的特点,设计了七种邻域结构、并在搜索过程中引入一种随机多样性等,从而构造了一个求解该问题的禁忌搜索算法。从用随机方式产生的初始解出发,用该禁忌搜索算法对56个标准测试问题进行求解。与相关文献中的结果进行了比较。通过比较,显示了本禁忌搜索算法的优势。在理论研究的基础上,本文运用禁忌搜索算法对长沙市市内邮政运输趟班数据进行了环形和辐射形两种邮路形式、共四种邮车路径规划方案的案例测试。通过比较各种规划方案的结果,显示出通用启发式算法对于依靠经验的传统手工编排趟班的明显优势,表明了在物流发达、经营点众多、分布范围较广、车辆行驶距离较长的大中城市,相对于环形邮路,辐射形邮路具有很大的优势。多车场车辆路径问题广泛存在于多个行业之中,对其研究不仅具有实际应用价值,更是研究供应链集成与协调的基础。多车场带软时间窗约束的开放式车辆路径问题则比单车场带软时间窗约束的开放式车辆路径问题求解更加复杂。本文以客户直接排列方法表示多车场带软时间窗约束的开放式车辆路径问题中的解；对于多车场的处理,则是随机从车场集合中选一个车场并从中派出一辆车,该车完成配送任务后再回到距离这条路径上的最后一个配送点最近的车场。如此循环,直到所有配送任务完成。这样,就从整体上对多车场带软时间窗约束的开放式车辆路径问题进行了求解。分析了农产品物流起点——农产品物流集货运输,将其归结为一类各车辆最后客户相同且确定的带软时间窗约束的不完全开放式车辆路径问题,并提出了一个遗传算法用于求解。通过对提供第三方物流服务的农村汽车货运企业的农产品物流集货运输问题进行模拟,构造了一个农产品物流集货运输路径问题算例,进行了算例测试,获得了满意的优化效果,表明了本遗传算法的优势。更多还原

【Abstract】 Vehicle routing problem (VRP) is the core of transport organizing optimization. In this dissertation, the characteristics, classification and algorithms of the VRP will be reviewed first of all.The Open Vehicle Routing Problem with Soft Time Windows (OVRPSTW) is widespread in practice. OVRPSTW is different to the basic vehicle routing problem (VRP). One difference is that OVRPSTW doesn’t require the vehicle to return to the original starting depot after its completing the task, or if it requires the vehicle to return to the original starting depot, then a back trip along the original route is needed. Another difference is that OVRPSTW demands the service of the vehicle being in the customer’s desired time windows, and if the service of the vehicle violates the customer’s time windows, a penalty must be paid. In this dissertation, OVRPSTW will be studied theoretically. Based on the design of seven kinds of neighborhood structures and the introduction of a randomly diverse search process, a tabu search algorithm is constructed to solve OVRPSTW whose features are exploited. Starting with an initial solution which is generated randomly, the tabu search algorithm is tested with 56 benchmark problems. A comparison with other related approach in the literature is carried out. By the comparison, it shows that the proposed tabu search algorithm is good.Based on the theoretical study, the urban local post transportation network running data of Changsha City Post and the proposed tabu search algorithm are used to test two kinds of post routing, i.e., radial shape post routing and ring shape post routing which have four post routing programs. By comparing the result of every program with each other, the metaheuristic algorithm is visibly advantageous to the traditional planning manually in scheduling, and the radial shape post routing is much more better than the ring shape post routing in a medium-large-sized city which is with well-developed logistics business, a lot of business point, a wider distribution region, and a long vehicle running distance.The Multiple-Depot VRP (MDVRP) widely presents in many businesses. The research on MDVRP not only has practical value, but also is a base on supply-chain integration and coordination. To solve a Multi-Depot OVRPSTW (MDOVRPSTW) is more sophisticated. In this dissertation, the solution shows as arrange-customer-directly, a depot is selected randomly from the set of depots, and a vehicle in the selected depot is selected randomly to deliver to deal with the multiple depots. After completing final distribution in its routing, the selected vehicle goes to the nearest depot from it. Do so cyclically till all of the deliveries are completed. Thus, the MDOVRPSTW is solved integrally.With analyzing the beginning of agricultural products logistics, i.e., the transport logistics of agricultural products pickup, a research about the same and identified last customer of all vehicles which is claasified into a kind of an OVRPSTW named incomplete OVRPSTW (IOVRPSTW) is carried on. Meanwhile, a genetic algorithm is proposed to solve it. With simulating the agricultural products pickup logistics transport routing problem operated by a rural freight company who engages in third-party logistics business, an example of the agricultural products pickup logistics transport routing problem is constructed. The example is tested, and a satisfactorily optimal result is obtained, therefore, the genetic algorithm is indicated to be advantageous.更多还原