1、 唐山师范学院本科毕业论文 外文 文献及译文 题 目 关于成品油配送调度优化的研究 学 生 杨永静 指导教师 韩志新 副教授 年 级 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
2、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),
3、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 fi
4、nd 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 pr
5、ocedure 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
6、 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 o
7、ur 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 accepting Transportation lies at the heart of human effort for a long time. The transportation of resources and goods
8、 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
9、 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 depot
10、s, 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 pro
11、duct 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
12、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
13、 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-ha
14、rd, 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
15、. 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
16、 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
17、other country. The basic VRP supposes that each available vehicle can only be used once in the planning period such as an eight hours daily working-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 le
18、ss 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 P
19、roblem 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 mor
20、e 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.
