杨永静 外文文献原文及译文.doc

唐山师范学院本科毕业论文外文文献及译文题 目 关于成品油配送调度优化的研究学 生 杨永静指导教师 韩志新 副教授年 级 08级本科班专 业 物流管理系 别 经济管理系A Threshold Accepting Heuristic for Solving the Vehicle Routing Problem with Multiple Use of VehiclesAbstract The basic vehicle routing problem(VRP)is planning a set of routes for a fleet of vehicles, one route for each vehicle, to handle the need of customers with assumption that each vehicle can be used only once during the planning period. This is not consistent with practical satiation, so we address a variant problem of the VRP, the vehicle routing problem.With multiple use of vehicles (VRPM), to suit the practical situation, and present a new heuristic for solving the VRPM .The VRPM extents the VRP by using vehicle more than once, i.e. several routes can be assigned to one vehicle. The total travel time of each vehicle cant exceed a working time limit M. The first object of VRPM is to find a feasible solution with none of vehicle has overtime situation. The second one is to find the lowest solution with an overtime penalty while the heuristic cant find feasible solution. We develop a two phase new heuristic method for solving the VRPM which contains initial solution construction procedure and improving procedure. The construction procedure is based on saving method and principle of route first-cluster second. At the last part of construction procedure we assign routes to vehicles by integer programming. The improving procedure is based on the deterministic threshold accepting heuristic method with integrated core methods. We test the new heurist method with a set of 9 test problems taken from the literature. Our new method can solve some problems feasibly, and for infeasible problems, the new method can solve them with penalties. Although some computational results by our new heuristic are not so good as those by previous researches, we do develop a new heuristic method to solve the VRPM.Keywords VRP, multiple use of vehicles, heuristic, threshold acceptingTransportation lies at the heart of human effort for a long time. The transportation of resources and goods advances the human economy because transportation supports most of the social and economic activity in the world. Manufacturing needs transportation to obtain materials and transport their products to customers or downriver manufacturer. Other industries such as hypermarket or store need support of transportation, too. Therefore, transportation becomes a necessary activity of industries.From the view point of logistics, transportation plays an important role in distribution management. Because the plan of transportation has great influence on cost such as the fixed cost of vehicles and depots, the variable cost of gas, overtime pay of driver and the penalty cost of delay. On the other hand as the establishing of the world trade organization, industries all over the world compete bitterer and bitterer. Besides nowadays the market of product changes more rapidly and the life cycle of product becomes much shorter. As the rising of home delivery and global shipping recent year, a thorough and reliable plan of transportation has become a necessary condition of high competitiveness.The well known Vehicle Routing Problem (VRP) is one of the core problems of transportation. The goal of VRP is to establish a distribution plan which has the minimum total cost (distance) with a number of customers (nodes), vehicles and a single depot. The vehicles capacity and sometimes the distance limit of vehicles are concerned, too. In the planning period each vehicle can only assign one planning route. However, the VRP is a hard combinatorial optimization problem and it is a generalization of the Traveling Salesman Problem (TSP).The goal of TSP is to construct a tour of customers (nodes) such that the total cost (distance) of this tour is minimized. Since the TSP has been shown to be NP-hard, the VRP is NP-hard, too. This kind of problem is easy to describe, but very difficult to solve. The computation time of the NP-hardness problem increases exponentially with the problem size.Therefore, it is impractical to find the optimal solution in a NP-hardness problem with an exact approach. According to the different situation in the real world transportation there are many harder problems with extended properties such as the VRP with time window (VRPTW), the Multi-depot VRP (MDVRP), the Heterogeneous Fleet VRP, the Period VRP (PVRP), and VRP with Backhauls, etc. Some academics study on the problems which combine more than two kinds of extended properties.The length of Taiwan from north to south is only about 394 kilometer and most of the plains in Taiwan lie in the west. Therefore, most industries are located at the west and the distance of transportation is shorter than the other country. The basic VRP supposes that each available vehicle can only be used once in the planning period such as an eight hours dailyworking-hour. It means that each vehicle can only be assigned one route to distribute. But the total distribution time of one planning route in Taiwan may be less than a half of the planning period. Hence, we can use fewer vehicles to finish the distribution plan if each vehicle can be assign more than one route. It is more conform to the environment of Taiwan and the real world distribution applications. This extend problem is called the Vehicle Routing Problem with Multiple Use of Vehicles (VRPM) or the Multi-trip Vehicle Routing Problem (MTVRP).But the VRPM in many real world applications is more complex than the VRP. The VRP is only one level of the complex routing problem in the real world applications. For example, the VRPM that allows for more than one route assigned to each vehicle is a three levels problem of decision making. At the top level is an assignment problem about assigning customers (nodes) to vehicles, and the second level problem is the VRP in each vehicle. At last, the TSP in each single route of the VRP is the third level problem. Because of its multiple levels of decision problems relating to the VRP, this kind of problem is called a Multi-level Vehicle Routing Problem (MLVRP).However, the research of the VRPM is not much in the literature. Homes et al. (1989) did an empirical study of the real distribution problem related to the VRPM. In 1990, Fleischmann suggested using bin packing to solve the VRPM in his working paper. Then, Taillard et al. (1996) proposed a heuristic based on the Tabu Search method (TS) and bin packing for solving the VRPM. Brandao and Mercer (1998) presented a heuristic based on the TS for solving the VRPM. There is some research related to the VRPM and combined with other properties such as time windows.The VRP has been proved to be NP-hard optimization problem by Lenstra and Rinnooy Kan (1981) and the VRPM is much harder than the VRP. Therefore, heuristic method is practical to solve the VRPM. Most of the research of the VRPM is based on the TS. The Threshold Accepting method (TA) is proposed by Dueck and Scheuer (1990) and the concept of the TA is based on the Simulated Annealing method (SA).In the SA the solution which is worse than the previous solution is accepted probability. The TA modifies the SA by accepting the worse solution while the difference between the new solution and old solution less than the threshold. If the difference is less than the threshold, the worse solution is accepted. Otherwise, the worse solution is rejected. The TA has been applied on some problems and has good performance. Dueck and Scheuer (1990) solved the Traveling Salesman Problem (TSP) and discovered the performance is better than the SA. Lin et al. (1995) applied the TA on the Scheduling problems and discovered the performance is better than the SA. Han et al. (1996) applied the TA on the TSP and tested by 15 test problems. The TA can obtain the optimum solution of 13 test problems. Han et al. (1997) applied the TA on the VRP and discovered the TA has good performance on the VRP. However, there is not a heuristic based on the TA for solving the VRPM in the past research. Therefore, our motivation and main goal in this thesis is to develop a heuristic method for solving the VRPM based on the TA.多路程车辆排程问题之门槛接受启发式演算法摘要基本型车辆途程问题是为一车队中每一车辆规划唯一配送路线以满足所有客戶之需求，即每一路线由单一车辆负责运送，在规划期间內每一车辆只能使用一次。此一限制与实物应用上有很大之出入，在实物应用情况中，经常是单一车辆运送一个以上路线，这使车辆途程问题困难度增加。本研究旨为多路程车辆途程问题(Vehicle Routing Problem with Multiple Use of Vehicles, VRPM)提出新的启发式方法。多路程车辆途程问题将基本型车辆途程问题中的限制放宽，使各车辆可不止使用一次，例如可指派多条路线给同一车辆，此外每辆车的总旅行時间皆不可超过其工作時間限制。本研究引用文献上之惯例，多路程车辆途程问题之第一目标为求出一個不含任何超时工作车辆之可行解，第二目标为当无法找到可行解时，加入超时工作惩罚值并求取成本最低之不可行解。本研究开发一种两段式之新启发式方法求解多路程车辆途程问题，包含起始解产生流程和改善流程。起始解产生流程是根据节省法和先分路线再分群之概念，再以松弛整数规划之方式指派多路线给每一车辆。改善解流程为根据确定型之门槛接受法，以整合型方式组合各核心方法，以文献中9题测试例题测试新方法。新启发式方法可以在部分测试例题中求得可行解，在其他测试例题中可以求出包含超时惩罚值的不可行解。虽然部份测试結果仍不如过去相关文献中之结果，我们还是成功应用门槛接受法发展出一个新启发式方法求解多路程车辆途程问题。关键字：车辆途程问题，多路程，启发式方法，门槛接受法运输业成为人类努力降低物流成本的中心已经有很长一段时间了。资源和货物的运输与配送增长了人类的经济支出，因为交通运输覆盖了世界上大多数的社会活动和经济活动。制造商需要运输来获得物料，以及将他们的产品送到顾客或者下游制造商手中。其他的产业部门，如超级市场或者商店也需要运输配送的支持。由此可见，运输业已成为各个产业部门的必不可少的环节。从物流的角度分析，运输在配送管理中起着重要的作用。因为运输计划对诸如固定成本（车辆成本、构建仓库的成本），变动成本（汽油成本、库存成本），司机的超时成本，延时惩罚成本有重大的影响。另一方面，随着世界贸易组织的建立，全世界的工厂之间的竞争日益激烈。而且，在如今，市场上的产品更新换代速度越来越快，产品生命周期变得越来越短。随着近年国内快递和全球运送业务的增长，一个彻底的、可靠的运输计划成为具有较强竞争力的必备条件。著名的车辆路径问题是运输的核心问题之一。车辆路径问题的目标是在既定的客户量、既定的车辆、既定的简单仓库的情况下建立一个使总成本最少的运输计划，车辆的装载能力和偶尔出现的车辆路线限制也得考虑在内。在计划期间内，只能分配一个计划路线给一个运输车辆。然而，车辆路径问题是一个坚硬的组合优化问题,是一个旅行商问题的概括。旅行商问题的目标是构建旅游客户，使这趟旅行的总成本降低到最小。既然旅行商问题已经被证明了是艰难的NP问题，那么，车辆路径问题也是艰难的NP问题。这类问题描述起来很简单，但是解决起来非常困难，NP难题的计算时间使问题的难度成指数倍数的增长。因此，在一个NP难题中，用确切的方法找到最优解是不切实际的。根据现实全球的运输过程中的不同情景，会产生许多复杂的延伸性问题，如具有时间窗的车辆路径问题、多路径车辆路径问题、混合车队车辆路径问题、期间固定的车辆路径问题、带有回程的车辆路径问题等等。一些学者的研究问题结合了两种以上的扩展属性。全台湾从北到南的总长仅仅为394千米，在台湾，大多数的飞机位于西部，因此，大部分的工厂也都位于西部，在这里，运输的里程比其他国家要短。基本的车辆路径问题是假设每一辆可以使用的车都可以在正常的工作时间、在计划的时间内被用来任意指派。这意味着每一辆车只能在一条指定的配送路线上被指派一次。但是，在台湾，一个配送路线计划的总配送时间要比计划总时间的一半还要短。因此，如果一辆车可以被指派多条路径的话，我们就可以用较少的车辆来完成整个配送计划。这更符合台湾的环境和现实世界的配送应用。这个延伸问