資料載入處理中...
臺灣人文及社會科學引文索引資料庫系統
:::
網站導覽
國圖首頁
聯絡我們
操作說明
English
行動版
(18.116.65.130)
登入
字型:
**字體大小變更功能,需開啟瀏覽器的JAVASCRIPT,如您的瀏覽器不支援,
IE6請利用鍵盤按住ALT鍵 + V → X → (G)最大(L)較大(M)中(S)較小(A)小,來選擇適合您的文字大小,
如為IE7以上、Firefoxy或Chrome瀏覽器則可利用鍵盤 Ctrl + (+)放大 (-)縮小來改變字型大小。
來源文獻查詢
引文查詢
瀏覽查詢
作者權威檔
引用/點閱統計
我的研究室
資料庫說明
相關網站
來源文獻查詢
/
簡易查詢
/
查詢結果列表
/
詳目列表
:::
詳目顯示
第 1 筆 / 總合 1 筆
/1
頁
來源文獻資料
摘要
外文摘要
引文資料
題名:
應用門檻接受法求解車輛路線問題之研究
書刊名:
運輸計劃
作者:
韓復華
/
楊智凱
/
卓裕仁
作者(外文):
Han, Anthony Fu-wha
/
Yang, Jyh-kai
/
Cho, Yuh-jen
出版日期:
1997
卷期:
26:2
頁次:
頁253-280
主題關鍵詞:
車輛路線問題
;
門檻接受法
;
啟發式解法
;
Vehicle routing problem
;
VRP
;
Threshold accepting algorithm
;
Heuristics
原始連結:
連回原系統網址
相關次數:
被引用次數:期刊(
11
) 博士論文(0) 專書(0) 專書論文(0)
排除自我引用:
7
共同引用:
13
點閱:64
門檻接受法(threshold accepting, TA)源於模擬降溫法(simulated annealing, SA),TA與SA均具有避免陷入局部解的特性,其不同處主要在TA改變SA機率性接受暫劣解的方 式為確定性的遞減門檻數列。國內外研究TA新方法的文獻尚不多見,目前僅見應用於旅行推 銷員問題(TSP)與若干工作排程的問題方面,本文係國內外文獻上首次將TA延伸應用於車輛路 線問題(VRP)上之研究。本文除詳細探討TA解題架構之設計與相關參數之選擇,並自國際電腦 網路題庫中選取11題標竿測試例題(節點數自51至200點),在SUN SPARC 10工作站上 以C語言撰寫程式進行測試。測試結果發現,以修正之循序節省法求得起始解,採整合式執行 組合方式(2-exchange節線交換法加上1-1及1-2節點交換法)改善起始解,用長度為30的梯狀 遞減門檻數列,在起始門檻值為0.2%時,11個測試例題與文獻已知最佳結果之平均誤差 百分比為4.64%,平均運算時間為115.17CPU秒。測試過程中,經由TA法對1 1個測試例題找到最好結果的平均誤差僅1.71%,另對測試例題中最大規模的200個節 點之例題(M-n200-k17.vrp),更求得優於文獻已知最佳結果之突破性發現。
以文找文
Originating from the simulated annedling(SA)approach, threshold accapting (TA)is a new general purpose algorithm presented by Dueck and Scheuer in 1990 for the solution of combinatorial optimization problems. Threshold accepting is generally an improvement method for initial solution. While traditional exchange heuristic methods are limited to local search, TA can avoid caving into local optimum. For routing problems, Dueck and Scheuer had applied the TA method to the famous 442-cities TSP of Grotschel and reported better results than that obtained by SA. Recently, Han et al. has accomplished a comprehensive application analysis of TA over a test bank of 15 TSP problems from the TSPLIB. This research extends the applications of TA to VRP. There are 11 benchmark test problems with 51 to 200 nodes were selected from literature for our test. Results found that the overall average cost of the best results obtained by TA is even lower than that reported in existing literature. Moreover, among the 11 VRP test problems, this research using TA has updated the best known solution for the test problem M-n200-k17.vrp with 200 nodes.
以文找文
期刊論文
1.
Bodin, L.、Golden, B.、Assad, A.、Ball, M.(1983)。Routing and Scheduling of Vehicle and Crews: The state of the art。Computers and Operations Research,10(2),63-211。
2.
Jaikumar, R.、Fisher, M. L.(1981)。A generalized assignment heuristic for vehicle routing。Networks,11(2),109-124。
3.
Christofides, N.、Eilon, S.(1969)。An Algorithm for Vehicle Dispatching Problem。Operational Research Quarterly,20(3),309-318。
4.
Dueck, G.、Scheuer, T.(1990)。Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing。Journal of Computational Physics,90(1),161-175。
5.
Gillett, B. E.、Miller, L. R.(1974)。A heuristic algorithm for the vehicle-dispatch problem。Operations Research,22(2),340-349。
6.
Osman, I. H.(1993)。Metastrategy Simulated Annealing and Tabu Search Algorithm for the Vehicle Routing problem。Annals of Operations Reseach,41,421-451。
7.
Lin, S.、Kernighan, B.(1973)。An Effective Heuristic Algorithm for Traveling Salesman Problem。Operations Research,21,498-516。
8.
Golden, B. L.、Skiscim, C. C.(1986)。Using simulated annealing to solve routing and location problems。Naval Research Logistics Quarterly,33,261-279。
9.
Reinelt, G.(1991)。TSPLIB--A traveling salesman problem library。ORSA Journal on Computing,3(4),548-562。
10.
Foster, B. A.、Ryan, D. M.(1976)。An Integer Programming Approach to the Vehicle Scheduling Problem。Operations Research Quarterly,27(2),367-384。
11.
Glover, F.(1990)。Tabu Search。ORSA Journal on Computing,2(1),4-32。
12.
Lin, C. K. Y.、Haley, K. B.、Sparks, C.(1995)。A Comparative Study of Both Standard and Adaptive Versions of Threshold Accepting and Simulated Annealing Algorithms in Three Scheduling Problems。European Journal of Operational Research,83(2),330-346。
13.
Toussaint, K. J.、Golden, B. L.(1994)。Exchange Heuristics to Improve the Clarity of Base / Time Plots。Computers & Operations Research,21(5),573-586。
14.
Clarke, G. U.、Wright, J. W.(1964)。Scheduling of Vehicles from a Central Depot to a Number of Delivery Points。Operations Research,12(4),568-581。
15.
韓復華、楊智凱(19960600)。門檻接受法在TSP問題上之應用。運輸計劃,25(2),163-187。
延伸查詢
16.
Glover, F.(1989)。Tabu Search。ORSA Journal on Computing,1,190-206。
17.
Kirkpatrick, Scott、Gelatt, C. D. Jr.、Vecchi, M. P.(1983)。Optimization by simulated annealing。Science,220(4598),671-680。
18.
Mole, R.、Jameson, S.(1976)。A sequential route-building algorithm employing a generalized savings criterion。Operational Research Quarterly,27(2),503-511。
19.
Althofer, I.、Koschnick, K. U.(1991)。On the Convergence of Threshold Accepting。Applied Mathematics and Optimization,24,183-195。
20.
Alfa, A. S.、Heragu, S. S.、Chen, M.(1991)。A 3-opt Based Simulated Annealing Algorithm for Vehicle Routing Problem。Computers and Industrial Engineering,21(1),635-639。
21.
Taillard, E. D.(1993)。Parallel Iterative Search Methods for Vehicle Routing Problems。Networks,23,661-673。
22.
Sampson, S.、Weiss, E.(1993)。Local Search Techniques for the Resource Constrained Project Scheduling Problem。Naval Research Logistics,40,665-675。
會議論文
1.
韓復華、陳正元(1992)。車輛路線問題啓發式解法在PC上執行績效之研究。中華民國運輸學會第七屆研討會,649-662。
延伸查詢
2.
韓復華、楊智凱(1995)。以門檻接受法改善路網成本之研究。中華民國運輸學會第十屆研討會,335-342。
延伸查詢
3.
韓復華、盧嘉棟、陳國清(1996)。TA在TSP問題執行應用之研究。中華民國第一屆運輸網路研討會,179-188。
延伸查詢
研究報告
1.
韓復華(1995)。全國商品物流配送決策支援系統發展。
延伸查詢
2.
韓復華、張靖(1996)。車輛路線問題研究:SA、TA、NM、SSS與交換型啓發式解法之綜合應用分析。
延伸查詢
學位論文
1.
陳正元(1992)。節省法與路線間交換改善法在車輛路線問題(VRP)上之應用(碩士論文)。國立交通大學。
延伸查詢
2.
楊智凱(1995)。以門檻接受法改善TSP及VRP路網成本之研究(碩士論文)。國立交通大學。
延伸查詢
圖書
1.
Aarts, E. H. L.、Van Laarhoven, P. J. M.、Lenstra, J. K.、Ulder, N. L. J.(1992)。Job Shop Scheduling by Local Search。Eindhoven:Department of Mathematics and Computing Science, Eindhoven University of Technology。
2.
Reinelt, G.(1994)。The Traveling Salesman: Computational Solutions for TSP Applications。Springer-Verlag。
3.
Chrisofides, N.、Mingozzi, A.、Toth, P.、Sandi, C.(1979)。Combinatorial Optimization。New York, NY:John Wiley & Sons。
其他
1.
陳國清,盧嘉棟(1996)。TA-TSP應用研究。
延伸查詢
圖書論文
1.
Fisher, M. L.(1995)。Vehicle Routing。Network Routing, Handbooks in Operations Research and Management Science。
推文
當script無法執行時可按︰
推文
推薦
當script無法執行時可按︰
推薦
引用網址
當script無法執行時可按︰
引用網址
引用嵌入語法
當script無法執行時可按︰
引用嵌入語法
轉寄
當script無法執行時可按︰
轉寄
top
:::
相關期刊
相關論文
相關專書
相關著作
熱門點閱
1.
應用螞蟻演算法提升售後服務保修專員指派績效之研究
2.
以適應性重置門檻接受法求解多車種固定車隊車輛路線問題之研究
3.
國際快遞業運務員最適取件路線規劃問題
4.
通勤交通車路線問題模式與巨集啟發式解法
5.
應用時窗分割與整數化策略簡化時窗收卸貨問題之研究
6.
改良型巢狀分割法應用於旅行推銷員問題之研究
7.
以基因演算法求解最小化設置時間單機排程問題
8.
含凹形節線成本最小成本轉運問題鄰近搜尋法之研究
9.
以螞蟻群聚最佳化整合噪音擾動法求解TSP問題
10.
定期貨櫃船舶航線規劃模式與求解演算法之研究
11.
巨集啟發式解法在求解大規模旅行推銷員問題之應用
12.
交通建設計畫評選模式及其解法之研究--以中小型交通建設計畫的評選為例
13.
節點塗色問題求解演算法之研究
14.
以禁忌搜尋演算法求解確定型及隨機型多車種車輛途程問題
15.
廢家電資源回收體系之建立與費率分析
無相關博士論文
無相關書籍
無相關著作
1.
應用螞蟻演算法於時窗限制車輛途程問題之研究
QR Code