外文翻譯--多路程車輛排程問題之門檻接受啟發(fā)式演算法-全文預覽
【正文】 gle 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 Multilevel 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 bined with other properties such as time windows. The VRP has been proved to be NPhard 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.
畢業(yè)設計相關推薦
鄂ICP備17016276號-1