【作者】 胡大伟；

【导师】 郭晓汾；

【作者基本信息】 长安大学 ， 载运工具运用工程， 2008， 博士

【摘要】 随着物质需求的多样性和不规则性以及贸易呈全球化趋势的发展,作为“第三利润源泉”的物流,其作用和地位显得比任何时候都更为重要,对经济活动的影响也日益明显。目前,许多发达国家和地区已形成了比较成熟的物流管理理念、先进的物流技术和高效的物流运营系统。我国在进入21世纪之后,也逐渐加快了现代物流的发展,以提高生产企业在国际上的竞争能力。为此企业管理者都希望能协调物流系统中的各个环节,以最低的价格、最好的服务来满足顾客的需要,所以物流决策显得极为重要。在传统的物流决策模型中,定位—配给问题(location allocation problems, LAP)和车辆运输路线问题(vehicle routing problem,VRP)是最值得关注的两个方面。但是在LAP模型中仅考虑设施(工厂、库存点、分销中心等)的定位与货物配给之间的相互关系,却忽视了对车辆巡回行程路线的考虑,这就有可能导致分销成本的增长;而在VRP模型中,虽然考虑了车辆在各个客户点间巡回访问的特性,使提高运输效率成为可能,但却没有分析设施的选址问题,这将会使得整个物流系统成本仍有一定的下降空间。因此,本文运用系统分析的思想和方法,研究了物流系统中的设施定位配给和车辆路线组合优化问题——定位车辆路线问题(location routing problem,LRP)。由于LRP及其扩展模型属于NP-hard问题,在具有一定规模节点数情况下目前仍难以求得最优解。因此对LRP模型进行系统化优化求解研究具有重要的理论价值,其理论意义则在于针对NP-hard模型大规模数值计算的解法突破和创新,同时也是发展基于电子商务的城市物流配送理论的重要理论基础,这将为日后面对巨大交易量的电子商务环境下开发自动物流配送调度系统软件具有非常重要的现实意义。本文在分析了物流系统中选址、运输以及库存的互相制约关系基础上,从提高物流系统整体效率为出发点,站在理论研究层面,针对物流集成化数学模型及其启发式解法进行了系统研究,即从系统化的角度分析和研究了复杂物流环境下的LRP优化问题,论文从问题的界定、模型的建立、模型的检验、启发式算法求解途径、组合优化求解思路、算法实现及数据分析等多个方面对LRP问题进行了深入、具体的研究分析,得到了如下研究成果:(1)论文系统性地研究了LRP数学模型,对定位-配给问题、车辆路线问题、定位-车辆路线问题、带库存的定位-车辆路线问题典型数学模型及其构成进行了科学描述,通过小规模测试数据采用LINGO软件对LRP数学模型给予了标定,为今后人们在此方面的进一步研究奠定了模型基础;(2)针对LRP数学模型属性特点,分别采用禁忌搜索算法(Tabu search algorithm,TS)、模拟退火算法(Simulated annealing algorithm,SA)对LRP数学模型进行了优化求解,编制了相应算法程序软件,并采用具有一定规模的仿真测试数据测算了所提出算法求解LRP模型的有效性,同时经过大量数值模拟计算找出了其算法求解LRP模型的优良参数搭配。通过与有关文献对比,证明本文提出的求解思路对于LRP模型求解更具有优良特性;(3)提出了遗传-模拟退火组合算法和遗传-禁忌搜索组合算法求解LRP模型的思路,并进行了相应的算法研究,通过编制计算软件和具有一定规模的数据测试,实现了组合启发式算法求解LRP模型的设想,这对于发展和完善组合优化理论亦具有重要的科学理论价值。(4)分析了在库存管理策略下,库存控制策略对设施选址和路线优化问题的影响,在此基础上建立了更为复杂的定位-路线-库存组合优化模型(Combined Location Routing and Inventory Problems,CLRIP),并设计了求解该模型的一种两阶段启发式算法,通过小规模测试数据测算证明带库存的定位路线组合优化模型比定位-路线问题和库存控制模型独立优化的情形更能有效降低物流系统成本,并为进一步深入研究该问题的解法提供了基本思路。(5)提供了LRP模型从8个节点至200个节点不同规模情形下的系列测试数据源,为今后开展LRP研究者提供了算法科学对比途径,同时为建立LRP模型测试数据库做出了开创性基础工作。更多还原

【Abstract】 Along with the development of substance needing variety and irregularly all over the world, logistics as“the third profit source”has played a more important role in the economic activity than any time. At present, many developed countries have formed comparatively mature logistics management concepts,advanced logistics techniques and effective logistics operating systems. Entering the 21th century, the Chinese government has made a rapid development in logistics, in order to enhance its international competition ability. Now all the business managers hope to run every link in the logistics system well to satisfy the client’s need with the lowest price and best service. So the decision-making of logistics is very important.In the traditional decision-making of logistics model, location allocation problems (LAP) and vehicle routing problem (VRP) are the most concerned problems. But the LAP only considers the locations of facilities (such as factory, Inventory place, sale centers etc.) and the relationship between facilities and goods distributions, ignoring the vehicle’s route, which may has a significant effect on the cost. Although the VRP considers the characteristic of vehicle’s circuit visit in every client, which may improve the transport efficiency, but it doesn’t analyze the locations of facilities, which can makes the cost to drop in logistics systems. Therefore, by the means of systems analysis, this thesis studies the facilities location distribution and the vehicle routing combination optimize problem—location routing problem(LRP)in logistics systems.As the LRP and its extending model belong to NP-hard problem, it is difficult to get the model’s optimal solving when nodes amount is so much. Consequently, it is meaningful to systematically get optimal solving of LRP models. Contribution of the research is the innovation in big scale mathematical calculation of NP-hard problem and it is also the academic foundation of developed city logistics distribution systems on account of electronic commerce. The research has extraordinary significance to developed self-action logistics distribution software in large amount of electronic commerce dealings. This thesis bases on the restricted relationship in location choosing, transporting and inventory in logistics systems, in order to promote whole efficiency of logistics systems, from the theory research points of view, to systemically analyze the LRP models optimize problem in complex logistics environment. This thesis studies in a deep going the LRP by bounding the problem, establishing the model, testing the model, getting solving by heuristic algorithm, combination optimize algorithm achieving and analyzing data, in the end, gets the conclusions as:(1)This thesis investigates the LRP math model, and describes the math model of location-distribution problem, vehicle routing problem, location routing problem, inventory location routing problem, and scales the LRP math problem by LINGO software with small scale data, which is the basic model base for the future study of LRP.(2)According to the characteristics of LRP math model, this thesis uses Tabu search algorithm(TS) and Simulated annealing algorithm(SA) to get the optimize value of LRP math model, and programs corresponding algorithm software ,then uses the simulated data to substantiate the validity of the algorithm to LRP model. Meanwhile, it finds out the proper parameters corresponding to LRP model. Compared with relative literature, the thought of this thesis has a more excellent means to LRP model solving.(3)This thesis develops the genetic -simulated annealing algorithm and genetic- tabu search algorithm to get the optimize value on the LRP math model. By programming the account software and testing with some data, the heuristic combined algorithm gets the optimize value of LRP come true. It has an important science role in improved and developed of combined optimize theory research.(4)This thesis analyzes the effect of inventory control strategy on the facilities location and route optimize problems, and establishes more complex Combined Location Routing and Inventory Problems(CLRIP) model, and designs a two-stage heuristic algorithm to get the optimize value. By testing with small scale data, it proves that Combined Location Routing and Inventory Problems model can more effectively reduce the logistics cost than the Location-route problem model ,or the inventory control problem model. Besides the heuristic algorithm provided a basic thoughts for analyze solving process of the LRP model in depth.(5)This thesis provides 8 to 200 nodes testing data source in different scales based on the LRP model, supplies an approach of every algorithm scientific contrasted for the future LRP researchers and does some initiative work for establishing LRP model testing data source.更多还原