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

唐山师范学院本科毕业论文 外文文献及译文 题 目 关于成品油配送调度优化的研究 学 生 杨永静 指导教师 韩志新 副教授 年 级 08级本科班 专 业 物流管理 系 别 经济管理系 A Threshold Accepting Heuristic for Solving the Vehicle Routing Problem with Multiple Use of Vehicles Abstract 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 can’t 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 can’t 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,