時依性路段暨時窗限制下單一車輛路線問題之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：91

、訪客IP：3.137.178.131

姓名

劉金維(Liu Chin-Wei) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

時依性路段暨時窗限制下單一車輛路線問題之研究
(ISSUES of THE TIME DEPENDENT SINGLE VEHICLE ROUTING AND SCHEDULING PROBLEM WITH TIME WINDOWS)

相關論文

★ 捷運乘客舒適度調查分析以台北高運量板南-土城線為例	★ 飛航組員及客艙組員影響溝通協調關鍵因素之研究
★ 廢棄機車回收廠區位選址之研究	★ 航空客運業綠色行銷與措施對消費者忠誠度影響
★ 以高齡者觀點評估台北市政府轉運站滿意度及行為意向之研究	★ 自行車接駁軌道運輸關鍵因素之探討-以捷運為例
★ 捷運車廂內廣播系統旅客服務品質之研究 -以台北市捷運為例	★ 小汽車駕駛人之行為意向研究
★ BRT路線試營運對用路人與乘客服務水準之影響評估―以台中市BRT藍線為例	★ 高鐵車站接駁公車營運前後服務水準之評估與比較-以苗栗高鐵站為例
★ 營建公司財務績效評估模式之研究	★ 都會區基地開發道路交通衝擊預測模式之建立─應用多元迴歸與模糊迴歸分析
★ 無道碴軌道型式決策模式之研究(應用價值工程及多屬性決策理論)	★ 建設公司全面品質管理. 產品定位與規劃績效關係之研究
★ 地方基層建設引用專案營建管理最適統合方式之研究	★ 宅配服務之生產力與行銷策略之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

本論文係以宅配運輸（或稱快遞配送）之車輛路線規劃問題為研究主題，分別探討在時依性路網（time dependent network）下，含時窗限制（time window）之靜態與動態單一車輛路線規劃兩課題。本研究所探討之靜態問題可視為一含路段阻抗暨時窗限制下旅行推銷員問題（Time Dependent Traveling Salesman Problem with Time Windows, TDTSPTW），由於此問題路段成本具時依性，因此，無論在問題複雜度（complexity）或網圖性質（graphic property）上，都與一般旅行推銷員問題有所不同。此外，本論文另一個研究課題為動態單一車輛路線規劃問題（Single Vehicle Routing and Scheduling Problem, SVRSP），此問題除具前述靜態研究課題所有限制外，其顧客資訊係非一次到達。因此，車輛巡行路線的規劃將隨著所掌握的顧客資訊持續地進行更新。有關上述研究課題之問題性質、數學模式、求解方法及相關數值例分析結果，已於本論文第三章（靜態問題）及第四章（動態問題）內，進行詳細之描述。

摘要(英)

The thesis is focused on the static and dynamic single vehicle routing and scheduling problems for the express carriers. The static one is as the Time Dependent Traveling Salesman Problem with Time Windows（TDTSPTW）. The time dependent link cost makes a lot of difference in computational complexity and graphic property, between TDTSPTW and TSP. The other topic is the Dynamic Single Vehicle Routing and Scheduling Problem（SVRSP）. The problem not only contains all the characteristics of the TDTSPTW, but the demand pattern is not deterministic. Therefore, the routing plan must be updated when any new request is accepted. All the issues mentioned above are supplied with some numerical tests to demonstrate proposed dynamic programming based algorithms.

關鍵字(中)

★ 車輛路線
★ 動態規劃
★ 時窗限制
★ 時依性

關鍵字(英)

★ VEHICLE ROUTING
★ DYNAMIC PROGRAMMING
★ TIME WINDOWS
★ TIME DEPENDENT

論文目次

封面
摘要
ABSTRACT
誌謝
目錄
圖目錄
表目錄
第一章　緒論
１．１　研究背景與動機
１．２　研究目的與範圍
１．３　研究流程
第二章　文獻回顧
２．１　旅行推銷員問題之一般特性論述
２．２　含時依性路段阻抗、時窗限制之旅行推銷員問題
２．３　線上型卅動態車輛路程規劃問題
２．４　綜合討論
第三章　含時依性路段阻抗暨時窗限制下旅行推銷員問題研究
３．１　問題描述
３．２　路段阻抗衡量方式之比較
３．３　模式建構
３．４　問題求解複雜度及理論性質探討
３．５　演算法開發
３．６　數值範例分析
３．７　綜合討論
第四章　動態單一車輛路線規劃問題
４．１　問題描述
４．２　模式建構
４．３　問題複雜度與性質分析
４．４　演算法開發
４．５　數值範例分析
４．６　綜合討論
第五章　結論與建議
５．１　結論與貢獻
５．２　建議
參考文獻
附錄

參考文獻

一、中文部份
小倉昌男，「小倉昌男的經營學」，小知堂文化事業有限公司，台北，2000。
交通部運輸研究所，台灣地區發展智慧型運輸系統綱要計畫，1999。
李宗儒、翁基華，「具工作負荷平衡之車輛途程問題研究」，運輸學刊，第11卷第1期，頁59-72，1999。
李宗儒、翁基華，「配銷系統之車輛途程問題於農業運銷的應用-以規劃農會超市宅配送為例」，台灣土地金融季刊，第34卷第1期，頁147-160，1997。
李宗儒、曾敏雅，「都會區夜間之物流配送規劃」，1999國際物流研討會論文集，頁562-569，1999。
周建新，「以隨時演算法解決及時性路徑規劃問題」，國立台灣大學資訊工程研究所碩士論文，1995。
周富得、李慶恩，「雙機流程型工廠動態排程之研究」，工業工程季刊，第15卷第四期，頁315-324，1998。
紀婉容，「以混合基因演算法解決動態路徑規劃問題」，國立台灣大學資訊工程研究所碩士論文，1997。
倉石俊，「流通巨人黑貓大隊」，小知堂文化事業有限公司，台北，1991。
高嘉和，「統一進軍宅急便、配送業者急應變」，自由時報，1999.11.22。
梅明德，「線上型時窗限制車輛路線問題之模式與求解演算法」，國立中央大學土木工程學系博士論文，1999。
陳春益、林正章、高玉明，「路線貨運業貨物排程模式之研究」，運輸計畫季刊，第26卷第2期，頁327-352，1997。
曾國雄、王日昌、黃明居，「以基因演算法與樣板路徑求解旅行推銷員問題」，運輸計畫季刊，第25卷第3期，頁493-516，1996。
零售市場雜誌社，「九八年台灣地區超市、大型店成長報告」，第304期，頁11-21, 1998。
零售市場雜誌社，「八十七年度CVS成長報告」，第306期，頁18-28, 1999。
趙孝蜀，「三個幾何學問題的即時演算法」，國立清華大學資訊科學學系碩士論文，1992。
劉浚明，「數學規劃理論與實務」，華泰書局，1995。
潘順興、陳稼興、陳振明，「遺傳演算法於配送點選擇之應用」，資訊管理研究，第2卷第1期，頁49-75，1997。
蔡英德，「隨機線上演算法之研究」，國立清華大學資訊科學學系博士論文，1993。
錢炳全，「多堆疊問題之線上演算法的研究」，國立交通大學資訊工程研究所博士論文，1992。
謝浩明、王隆昌，「台茂購物中心開幕交通維持計畫」，台茂股份有限公司委託，1999。
謝浩明、劉金維，「時間相依暨時窗限制下旅行推銷員問題研究」，運輸學刊，第12卷，第1期，2000（接受刊登）。
韓復華、卓裕仁、陳國清，「五種巨集式啟發式方法在VRP問題上的應用與比較」，中華民國第四屆運輸網路研討會，頁72~82，1999。
韓復華、楊智凱，「門檻接受法在TSP問題上之應用」，運輸計畫季刊，第25卷第2期，頁163-188，1996。
二、英文部份
Ahn,B.H. and Shin, J.Y., “ Vehicle-routing with Time Windows and Time-varying Congestion,” Journal of Operational Research Society, Vol.42, No.5, pp.393-400, 1991.
Aho, A. V., Hopcroft, J. E. and Ullman, J. D., The Design and Analysis of Computer Algorithm, Addison-Wesley, Reading, MA.,1974.
Amelia, C. R. and Thomas, F. G., “ Freight Operation’s Perceptions of Congestion Problems and the Application of Advanced Technologies︰Results from a 1998 Survey of 1200 Companies Operating in California,” Transportation Journal, Spring, pp.57-67, 1999.
Baker,E., “ An Exact Algorithm for the Time Constrained Traveling Salesman Problem,” Operations Research, Vol.31, pp.938-945, 1983.
Ball, M.O., Magnanti, T.L., Monma, C. L. and Nemhauser, G. L., Handbooks in Operations Research and Management Science Volume 8 ︰Network Routing, Elsevier Science B. V., 1995.
Bellman,R., Dynamic Programming, Princeton University Press, New Jersey, 1957.
Bertsekas, D. P., Dynamic Programming and Stochastic Control, Academic Press, New York, 1976.
Bertsimas, D. and van Ryzin, G., “ A stochastic and dynamic vehicle routing problem in the Euclidean plane,” Operations Research, Vol.39, pp.601-615, 1991.
Bidin,L., Golden,B., Assad,A., and Ball, M., “ Routing and Scheduling of Vehicles and Crews：the State of the Art,” Computers and Operations Research, Vol.10, No.2, pp.63~211, 1983.
Bland, R.G. and Shallcross, D.F., “Large Traveling Salesman Problems Arising Experiments in X-ray Crystallography︰A Preliminary Report on Computation,” Operations Research Letters, Vol. 8, pp.125-128, 1989.
Brown,G.B., Ellis, C.J., Graves,G.W. and Ronen, D. “Real-time, Wide Area Dispatch of Mobil Tank Trucks,” Interfaces, Vol. 17, No. 1, pp.107-120, 1987.
Carlton, W. B. and Barnes, J. W.,“ Solving The Traveling Salesman Problem with Time Windows Using Tabu Search,”IIE Transactions, Vol.28, No.8, pp.617-629, 1996.
Christofides,N. and Eilon, S., “Algorithm for Large Scale Traveling Salesman Problems,” Operational Research Quarterly, Vol. 23, pp.511-518, 1972.
Christofids, N., Mingozzi, A., and Toth, P., “ State Space Relaxation for the Computation of Bounds to Routing Problems, Network, Vol.11, pp.145-164, 1981.
Dantzig,G.B., Fulkerson, D. R. and Johnson, S. M., “ Solution of a Large-scale Traveling Salesman Problem,” Operations Research, Vol.2, pp.393~410, 1954.
Desrosiers, J., Soumis, F. and Desochers, M., “Routing with Time Windows by Column Generation,” Networks, Vol.14, pp.545-565,1984.
Dueck,G. and Scheuer, T.,“ Threshold Accepting：A General Purpose Optimization Algorithm Superior to Simulated Annealing,” Journal of Computational Physics, Vol. 90, pp.161-175, 1990.
Dumas, Y., J. Desorsiers, E. G., and M. Solomon, “ An Optimal Algorithm for the Traveling Salesman Problem with Time Windows,” Operations Research, Vol.43, pp.367-371, 1995.
Fischetti, M. and Toth, P.,“ A Polyhedral Approach to The Asymmetric Traveling Salesman Problem,”Management Science, Vol.43, No.11, pp.1520-1536, 1997.
Fischetti, M., Gonzaiez, J. J. S. and Toth, P.,“ A Branch-and-Cut Algorithm for The Symmetric Generalized Traveling Salesman Problem,”Operations Research, Vol.45, No.3, pp.378-394,
Fox, K., Gavish, B. and Graves, S., “An N-Constraint Formulation of the (Time Dependent) Traveling Salesman Problem,” Operations Research, Vol. 28, pp.1018-1021,1980.
Fox,K.R., “Production Scheduling on Parallel Lines with Dependencies,” Ph.D. Dissertation, The Johns Hopkins University, Baltimore, Md., 1973.
Fu, P. and Teply, S., “On-line and Off-line Routing and Scheduling of Dial-a-Ride Paratransit Vehicle,” Computer-Aided Civil and Infrastructure Engineering, Vol. 14, No. 5, pp. 309-319, 1999.
Garfinkel, R.S., “Minimizing Wallpaper Waste, Part I︰A Class of Traveling Salesman Problems,” Operations Research, Vol.25, pp.741-751, 1977.
Gendreau, M., Hertz, A. and Laporte, G.,“ New Insertion and Post-optimization Procedure for The Traveling Salesman Problem,”Operations Research, Vol.40, No.6, pp.1086-1094, 1992.
Gendreau, M., Hertz, Al, Laporte, G. and Stan, M.,“ A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows,”Operations Research, Vol.46, No.3, pp.330-335, 1998.
Gendreau, M., Laporte, G. and Vigo, D.,“ Heuristics for the Traveling Salesman Problem with Pickup and Delivery,”Computers & Operations Research, Vol.26, No.7, pp.699-714, 1999.
Giampiero,E.G.B., “A Real-time Routing Model for Hazardous Materials,” European Journal of Operational Research, Vol. 75, pp. 508-520, 1994.
Golden, B.L. and Assad, A.A., Vehicle Routing : Methods and Studies, North-Holland, pp.223-248, 1988.
Gutin, G.,“ Exponential Neighborhood Local Search for The Traveling Salesman Problem,” Computers & Operations Research, Vol.26, No.4, pp.313-320, 1999.
Hill,A.V., and Benton, W.C., “ Modeling Intra-City Time-Dependent Travel Speed for Vehicle Scheduling problems,” Journal of Operational Research Society, Vol. 43, pp.343-351, 1992.
Jason, D.P.,“A Stochastic and Dynamic Routing Policy Using Branching Process with State Dependent Immigration,”European Journal of Operational Research, Vol.95, pp.167-177, 1996.
Jpseph,Y. T., Leung, T. W. and Gilbert, H. Y., “ On Line Routing of Real-Time Message,” Journal of Parallel and Distributed Computing, Vol. 34, pp. 211-217, 1996.
Knox, J.,“ Tabu Search Performance on The Symmetric Traveling Salesman Problem,”Computers & Operations Research, Vol.21, No.8, pp.867-876, 1994.
Langevin, A., M. Dersorchers, J. Desorsiers, E. G., and F. Soumis, “ A Two-Commodity Flow Formulation for the Traveling Salesman and the Makespan Problems with Time Windows,” Networks, Vol.23, pp.631-640, 1993.
Langevin,A., Soumis, F. and Desrosiers, J., “ Classification of traveling Salesman Problem Formulation,” Operations Research Letters, Vol.9, pp.127-132, 1990.
Laporte, G. and Osman, I.H., “Rouitng Problems︰A Bibliography,” Annals of Operations Research, Vol. 61, pp.227-262, 1995.
Laporte,G., “The Traveling Salesman Problem：An Overview of Exact and Approximate Algorithm,” European Journal of Operational Research, Vol. 59, pp.231-247, 1992.
Laporte,G.,“ The Vehicle Routing Problem：An Overview of Exact and Approximate Algorithm,” European Journal of Operational Research, Vol.59, pp.345~358, 1992.
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., and Shmoys, D. B., The Traveling Salesman Problem-A Guide Tour of Combinatorial Optimization, John Wiley & Sons Press, New York, 1985.
Lenstra,J.K., Rinnoooy Kan. A.H.G., “Some Simple Applications of the Traveling Salesman Problem,” Operational Research Quarterly, Vol. 26, pp.717-733, 1975.
Lucena,A., “Time-Dependent Traveling Salesman Problem-The Deliveryman Case,” Networks, Vol. 20, pp.753-763, 1990.
Malandraki, C. and Daskin, M. S., “ Time Dependent Vehicle Routing Problem: Formulation, Properties and Heuristic algorithms,” Transportation Science, Vol. 26, pp.185-200, 1992.
Malandraki, C., “ Time Dependent Vehicle Routing Problem: Formulation, Solution Algorithm and Computation Experiments,” Ph.D. dissertation, Northwestern University, Evanston, IL, 1989.
Malandraki,C. and Dial, R.B., “ A Restricted Dynamic Programming Heuristic Algorithm for the Time Dependent Traveling Salesman Problem,” European Journal of Operational Research, Vol.90, pp.45-55, 1996.
Martin, S. and Marc, S., “DRIVE︰Dynamic Routing of Independent Vehicles,” Operations Research, Vol. 46, No. 4, pp. 474-490, 1998.
Mladenovic, N. and Hansen, P., “Variable Neighborhood Search,” Computers & Operations Research, Vol. 24, pp.1097-1100, 1997.
Mladenovic, N. and Hansen, P.,“ Variable Neighbor Search,”Computer & Operations Research, Vol.24, No.11, pp.1097-1100, 1997.
Norback,J. and Love, R.,“ Geometric Approach to Solving the Traveling Salesman Problem,” Management Science, Vol. 23, pp.1208-1223, 1977.
Padberg,M. and Sung, T.Y., “ An Analytical Comparison of Different Formulations of the Traveling Salesman problem,” Mathematical Programming, Vol. 52, pp.315-357, 1996.
Pesant, G., Gendreau, M., Potvin, J.Y. and Rousseau, J.M.,“On The Flexibility of Constraint Programming Models︰From Single to Multiple Time Windows for The Traveling Salesman Problem,” European Journal of Operational Research, Vol.117, No.2, pp.253-263, 1999.
Picard, J.C., and Queyranne, M., “ The Time-Dependent Traveling Salesman Problem and its Application to the Tardiness Problem in One Machine Scheduling,” Operations Research, Vol.26, pp.86-110, 1978.
Pick, J.C., and Queyranne, M. “The Time-Dependent Traveling Salesman Problem and its Application to the Tardiness Problem in One Machine Scheduling,” Operations Research, Vol. 26, pp.86-110, 1978.
Prabir, K. B. and Barin, N. N., “Dynamic Vehicle Scheduling︰An Expert Systems Approach,” International Journal of Physical Distribution & Logistics Management, Vol. 21, No. 2, pp.10-18, 1990.
Psaraftis, H.N., “ Dynamic Vehicle Routing Problems,” In Vehicle Routing: Methods and Studies (B. L. Golden and A. A. Assad, eds.), North Holland, Amsterdam, pp.223-248, 1988.
Psaraftis, H.N., “Dynamic vehicle routing︰Status and prospects,” Annals of Operations Research, Vol.61, pp.143-164, 1995.
Psaraftis, H.N.,“ A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-ride Problem,” Transportation Science, Vol.14, pp.130-154, 1980.
Psaraftis, H.N.,“ An Exact Algorithm for the Single Vehicle Many-to-Many Dial-A-Ride Problem with Time Windows,” Transportation Science, Vol.17, pp.351-357, 1983.
Psraftis, H. N., J. B. Orlin, D. Bienstock, and P. M. Thompson, “ Analysis and Solution Algorithm of Sealift Routing and Scheduling Problem︰Final Report. Working paper No. 1700-85, Sloan School of Management, MIT, 1985.
Rego, C.,“ Relaxed Tours and Path Ejections for The Traveling Salesman Problem,”European Journal of Operational Research, Vol.106, No.2, pp.522-538, 1998.
Renaud, J. and Boctor, F. F.,“ An Efficient Composite Heuristic for The Symmetric Generalized Traveling Salesman Problem,”European Journal of Operational Research, Vol.108, No.3, pp.571-584, 1998.
Schmitt, L. J. and Amini, M. M.,“ Performance Characteristics of The Alternative Genetic Algorithmic Approaches to the Traveling Salesman Problem Using Path Representation︰An Empirical Study,”European Journal of Operational Research, Vol.108, No.3, pp.551-570, 1998.
Shi, L., Olafsson, S. and Sun. N.,“ New Parallel Randomized Algorithm for The Traveling Salesman Problem,” Computers & Operations Research, Vol.26, No.4, pp.371-394, 1999.
Shieh, H. M. and May, M. D.,“ On-line Vehicle Routing with Time Windows,” In Transportation Research Record 1617, TRB, National Research Council, Washington, D. C., pp.171-178, 1998.
Strosnider, J. K. and Paul, C. J., “A Structure View of Real-time Problem Solving,” AI Magazine, Vol. 15, No. 2, pp.45-66, 1994.
Stuart,E. D., and Averill, M. L., “ The Art and Theory of Dynamic Programming,” Academic Press, New York, 1977.
Tian, P., Ma, Jian and Zhang, D.M.,“ Application of The Simulated Annealing Algorithm to The Combinatorial Optimisation Problem with Permutation Property︰An Investigation of Generation Mechanism, European Journal of Operational Research, Vol.118, No.1, pp.81-94, 1999.
Tsubakitani, S. and Evans, J.R.,“ An Empirical Study of A New Meta-heuristic for the Traveling Salesman Problem,”European Journal of Operational Research, Vol.104, No.1, pp.113-128, 1998.
Tsubakitani, S. and Evans, J.R.,“ Optimizing Tabu List Size for The Traveling Salesman Problem,”Computers & Operations Research, Vol.25, No.2, pp.91-97, 1998.
Valenzuela, C. L. and Jones, A. J.,“ Estimating the Held-Karp Lower Bound for The Geometric TSP,” European Journal of Operational Research, Vol.102, No.1, pp.157-175, 1997.
Vander Wiei, R.J. and Sahinidis, N.V., “ An Exact Solution Approach for the Time-Dependent Traveling-Salesman Problem,” Navel Research Logistics, Vol. 43, pp. 797-820, 1996.
Vander Wiei, R.J., and Sahinidis, N.V., “Heuristic Bounds and Test Problem Generation fir the Time-Dependent Traveling Salesman Problem,” Transportation Science, Vol. 29, pp.167-183, 1995.
Yagiura, M. and Ibaraki, T.,“ The Use of Dynamic Programming in Genetic Algorithms for Permutation Problems,”European Journal of Operational Research, Vol.92, No.2, pp.387-401, 1996.
Zilberstein, S. and Russell, S. J., “Optimal Composition of Real-time System,” Artificial Intelligence, Vol. 82, No. 1-2, pp.181-213, 1996.

指導教授

謝浩明

審核日期

2009-5-11

推文