外文翻譯--多路程車輛排程問題之門檻接受啟發(fā)式演算法

1、<p>　　唐山師范學(xué)院本科畢業(yè)論文</p><p><b>　　外文文獻及譯文</b></p><p>　　題 目 關(guān)于成品油配送調(diào)度優(yōu)化的研究</p><p>　　學(xué) 生 楊永靜</p><p>　　指導(dǎo)教師 韓志新 副教授</p><p>　　年 級

2、 08級本科班</p><p>　　專 業(yè) 物流管理</p><p>　　系 別 經(jīng)濟管理系</p><p>　　A Threshold Accepting Heuristic for Solving the Vehicle Routing Problem with Multiple Use of Vehicles</p><

3、p>　　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 o

4、nce during the planning period. This is not consistent with practical satiation, so we address a variant problem of the VRP, the vehicle routing problem.</p><p>　　With multiple use of vehicles (VRPM), to sui

5、t 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 veh

6、icle 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

7、the heuristic ca</p><p>　　Keywords VRP, multiple use of vehicles, heuristic, threshold accepting</p><p>　　Transportation lies at the heart of human effort for a long time. The transportation of

8、 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 t

9、o customers or downriver manufacturer. Other industries such as hypermarket or store need support of transportation, too. Therefore, transportation becomes a necessary activity of industries.</p><p>　　From t

10、he 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 co

11、st 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 ma

12、rket of product changes more rapidly and the life cycl</p><p>　　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

13、 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

14、 each vehicle can only assign one planning route. However, the VRP is a hard combinatorial optimization problem and it is a </p><p>　　Therefore, it is impractical to find the optimal solution in

15、 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 M

16、ulti-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.</p><p>

17、　　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 th

18、an 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 daily</p><p>　　working-hour. It means that each vehicle can only b

19、e 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

20、 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 Veh

21、icles (VR</p><p>　　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 th

22、at 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 probl

23、em is the VRP in each vehicle. At last, the TSP in each single route of the VRP is the third</p><p>　　However, the research of the VRPM is not much in the literature. Homes et al. (1989) did an empirical stu

24、dy 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

25、 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 </p><p>　　The VRP has been prove

26、d 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 th

27、e 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

28、 is accepted probability. The TA modif</p><p>　　多路程車輛排程問題之門檻接受啟發(fā)式演算法</p><p><b>　　摘要</b></p><p>　　基本型車輛途程問題是為一車隊中每一車輛規(guī)劃唯一配送路線以滿足所有客戶之需求，即每一路線由單一車輛負(fù)責(zé)運送，在規(guī)劃期間內(nèi)每一車輛只能使用一次。此一

29、限制與實物應(yīng)用上有很大之出入，在實物應(yīng)用情況中，經(jīng)常是單一車輛運送一個以上路線，這使車輛途程問題困難度增加。本研究旨為多路程車輛途程問題(Vehicle Routing Problem with Multiple Use of Vehicles, VRPM)提出新的啟發(fā)式方法。多路程車輛途程問題將基本型車輛途程問題中的限制放寬，使各車輛可不止使用一次，例如可指派多條路線給同一車輛，此外每輛車的總旅行時間皆不可超過其工作時間限制。本研究引

30、用文獻上之慣例，多路程車輛途程問題之第一目標(biāo)為求出一個不含任何超時工作車輛之可行解，第二目標(biāo)為當(dāng)無法找到可行解時，加入超時工作懲罰值并求取成本最低之不可行解。本研究開發(fā)一種兩段式之新啟發(fā)式方法求解多路程車輛途程問題，包含起始解產(chǎn)生流程和改善流程。起始解產(chǎn)生流程是根據(jù)節(jié)省法和先分路線再分群之概念，再以松弛整數(shù)規(guī)劃之方式指派多路線給每一車輛。改善解流程為根據(jù)確定型之門檻接受法，以整合型方式組合各核心方法，以文獻中9題</p>

31、<p>　　關(guān)鍵字：車輛途程問題，多路程，啟發(fā)式方法，門檻接受法</p><p>　　運輸業(yè)成為人類努力降低物流成本的中心已經(jīng)有很長一段時間了。資源和貨物的運輸與配送增長了人類的經(jīng)濟支出，因為交通運輸覆蓋了世界上大多數(shù)的社會活動和經(jīng)濟活動。制造商需要運輸來獲得物料，以及將他們的產(chǎn)品送到顧客或者下游制造商手中。其他的產(chǎn)業(yè)部門，如超級市場或者商店也需要運輸配送的支持。由此可見，運輸業(yè)已成為各個產(chǎn)業(yè)部門的必不

32、可少的環(huán)節(jié)。</p><p>　　從物流的角度分析，運輸在配送管理中起著重要的作用。因為運輸計劃對諸如固定成本（車輛成本、構(gòu)建倉庫的成本），變動成本（汽油成本、庫存成本），司機的超時成本，延時懲罰成本有重大的影響。另一方面，隨著世界貿(mào)易組織的建立，全世界的工廠之間的競爭日益激烈。而且，在如今，市場上的產(chǎn)品更新?lián)Q代速度越來越快，產(chǎn)品生命周期變得越來越短。</p><p>　　隨著近年國內(nèi)快遞

33、和全球運送業(yè)務(wù)的增長，一個徹底的、可靠的運輸計劃成為具有較強競爭力的必備條件。</p><p>　　著名的車輛路徑問題是運輸?shù)暮诵膯栴}之一。車輛路徑問題的目標(biāo)是在既定的客戶量、既定的車輛、既定的簡單倉庫的情況下建立一個使總成本最少的運輸計劃，車輛的裝載能力和偶爾出現(xiàn)的車輛路線限制也得考慮在內(nèi)。在計劃期間內(nèi)，只能分配一個計劃路線給一個運輸車輛。然而，車輛路徑問題是一個堅硬的組合優(yōu)化問題,是一個旅行商問題的概括。旅行

34、商問題的目標(biāo)是構(gòu)建旅游客戶，使這趟旅行的總成本降低到最小。既然旅行商問題已經(jīng)被證明了是艱難的NP問題，那么，車輛路徑問題也是艱難的NP問題。這類問題描述起來很簡單，但是解決起來非常困難，NP難題的計算時間使問題的難度成指數(shù)倍數(shù)的增長。</p><p>　　因此，在一個NP難題中，用確切的方法找到最優(yōu)解是不切實際的。根據(jù)現(xiàn)實全球的運輸過程中的不同情景，會產(chǎn)生許多復(fù)雜的延伸性問題，如具有時間窗的車輛路徑問題、多路徑車

35、輛路徑問題、混合車隊車輛路徑問題、期間固定的車輛路徑問題、帶有回程的車輛路徑問題等等。一些學(xué)者的研究問題結(jié)合了兩種以上的擴展屬性。全臺灣從北到南的總長僅僅為394千米，在臺灣，大多數(shù)的飛機位于西部，因此，大部分的工廠也都位于西部，在這里，運輸?shù)睦锍瘫绕渌麌乙??；镜能囕v路徑問題是假設(shè)每一輛可以使用的車都可以在正常的工作時間、在計劃的時間內(nèi)被用來任意指派。這意味著每一輛車只能在一條指定的配送路線上被指派一次。但是，在臺灣，一個配送路線

36、計劃的總配送時間要比計劃總時間的一半還要短。因此，如果一輛車可以被指派多條路徑的話，我們就可以用較少的車輛來完成整個配送計劃。這更符合臺灣的環(huán)境和現(xiàn)實世界的配送應(yīng)用。這個延伸問題被稱為多用途車輛的車輛路徑問題或者是具有多路程排程問題的車輛路徑問題。</p><p>　　但是，在許多現(xiàn)實世界的應(yīng)用中，多用途車輛的車輛路徑問題比單純的車輛路徑問題要復(fù)雜的多，在現(xiàn)實的應(yīng)用過程中，車輛路徑問題僅僅是復(fù)雜路徑問題的一個層次

37、而已。例如，將每輛車被指派多于一條路線的問題考慮在內(nèi)的車輛路徑計劃問題是一個三層次的決策問題。</p><p>　　頂層是將車輛指派給合適的客戶的指派問題，中間層是每輛車輛的車輛路徑問題，最后一層是車輛路徑問題的每一條路線的旅行商問題。由于它的與車輛路徑問題的多層次決策問題，這種問題被稱為多層次車輛路徑問題。</p><p>　　然而，在文學(xué)界，對于多用途車輛的車輛路徑問題的研究并不多，在

38、1989年，Homes對有關(guān)多用途車輛的配送問題做了一個實證研究。在1990年，F(xiàn)leischmann在他的論文中提出了用裝箱問題來解決多用途車輛路徑問題。在1996年，Taillard等人提出了基于禁止搜索算法和用于多用途車輛路徑問題的裝箱問題的啟發(fā)式算法。在1998年，Brandao和Mercer提出了一種基于禁止搜索法去解決多用途車輛路徑問題的啟發(fā)式算法，已經(jīng)有了一定的關(guān)于多用途車輛路徑問題和將諸如時間窗的性質(zhì)在內(nèi)的研究。<

39、/p><p>　　車輛路徑問題已經(jīng)被Lenstra和Rinnooy證實是NP難題的優(yōu)化問題，多用途車輛路徑問題比單純的車輛路徑問題要困難得多。因此，啟發(fā)式算法是解決多用途車輛路徑問題的較為實際的方法，大多數(shù)的對于多用途車輛的路徑問題的研究都是基于禁止搜索算法研究出來的。門檻接受法是在1990年由Dueck和Scheuer提出來的，禁止搜索的概念是基于模擬退火方法提出來，在模擬退火方法中，比精確解決方法模糊的解決方案是

40、有可能被接受的。門檻接受法在接受模糊的解決方案時將模擬退火方法進行了修改，但新舊解決方案之間的差異比門檻接受法要小的話，模糊解決方案是可以被接受的，否則，模擬解決方案就是不可以被接受的。門檻接受法已被應(yīng)用于許多問題，并取得了好的結(jié)果。Dueck和Scheuer在1990年解決了旅行商問題，并發(fā)現(xiàn)了比模擬退火法要好的方法。Lin于1995年將門檻接受法用于計劃問題上，并取得了比模擬退火法好的效果。Han于1996年將門檻接受法用于旅行商問