臺灣人文及社會科學引文索引資料庫系統

:::

詳目顯示

回上一頁
第 1 筆 / 總合 1 筆   第一頁 上一頁 下一頁 最後一頁
/1頁
題名：時間窗口網路之時間分析
作者：蕭立人
作者(外文)：Li-Jen Hsiao
校院名稱：國立中央大學
系所名稱：資訊管理研究所
指導教授：陳彥良
學位類別：博士
出版日期：2004
主題關鍵詞：時間窗口；網路分析；生理時鐘；時間分析；最晚路徑；彈性路徑；運送；繞徑；Time Window；Network Analysis；Body Clock；Time Analysis；Latest Path；Flexible Path；Shipping；Vehicle Routing
原始連結：連回原系統網址new window
相關次數：
  • 被引用次數被引用次數:期刊(0) 博士論文(0) 專書(0) 專書論文(0)
  • 排除自我引用排除自我引用:0
  • 共同引用共同引用:0
  • 點閱點閱:35
由相關領域之各大期刊蒐集得到的許多研究文獻中，都曾經提出一些時間窗口(Time Window)網路的模型及相關的研究，這一類的研究大多著重以在時間窗口網路的基礎上，解決找尋最短路徑或交通工具繞徑等問題。在此模型之下，有些狀況未曾被考慮過，本文將找出這些因素並加以研究，研究結果大致可以歸納如下：第一、根據此類問題的實際狀況，提出生理時鐘(Body Clock)的時間條件，以彌補網路模型的不足，並提出解決貨運排程問題的演算方法。第二、研究旅行者在時間窗口網路上，所循路徑之彈性問題，並提出演算方法以找出最有時間彈性之路徑。第三、在時間網路模型中，加入生理時鐘之條件，並研究其彈性之相關議題。
Time window has been a common form of time constraint extensively considered in the literature. Basically, a time window is a time period, defined by the earliest and latest times, when a node is ready for traveling through. Although many variants of transportation problem in time-window networks have been proposed, none of them considers the possibility that time windows may be associated with the moving travelers or vehicles who travel only in these time periods.
In this dissertation, a new variant of time-window constraint, we call it body clock constraint, is proposed at first. We assume that each vehicle has its own body clock and a capacity limitation on carrying goods, and we are trying to determine a minimal time schedule for sending a certain amount of goods from source to destination in a time-window network. The problem is studied by two cases, the first case considers single vehicle scheduling while the second one discusses multiple vehicles. Two different algorithms are presented to find the optimum schedule for each of the two cases.
Secondly, to plan and select a path under a constraint on the latest entering time at the destination node, we propose a systematic method to generate time information of the paths and nodes on a time-window network. Algorithms are proposed to generate various time characteristics of the nodes, including the earliest and latest times of arriving at, entering, and departing from each node on the network. Using the basic time characteristics, we identify inaccessible nodes that cannot be included in a feasible path. Concurrently, we evaluate the flexibilities of accessible nodes in the waiting time and staying time. We also propose a method to measure adverse effects when including an arc. Based on the time characteristics and the proposed analysis schemes, we develop an algorithm for finding the most flexible path in a time-window network.
We then extend the time window network to include body clock with traveler. Time characteristics of nodes and arcs are generated similarly. The flexibility and inaccessibility analyses of nodes and arcs are also discussed. Similarly, we provide an algorithm to find the most flexible path in this time-window network with traveler’s body clock.
[1] Ahn BH and Shin JY. Vehicle-routing with time windows and time-varying congestion. Journal of the Operational Research Society 1990;42:393-400.new window
[2] Atkinson JB. A vehicle-scheduling system for delivering school meals. Journal of the Operational Research Society 1990;41:703-11.
[3] Baker E. Vehicle routing with time window constraints. Logistics & Transportation Review 1982;18:385-401.
[4] Baker EK. An exact algorithm for the time-constrained traveling salesman problem. Operations Research 1983;31:938-45.
[5] Balakrishnan N. Simple heuristics for the vehicle routing problem with soft time windows. Journal of the Operational Research Society 1993;44:279-87.
[6] Bodin LD, Golden BL, Assad AA and Ball MO. Routing and scheduling of vehicles and crews: the state of the art. Computers & Operations Research 1982;10:63-211.
[7] Bramel J and Simchi-Levi D. Probabilistic analyses and practical algorithms for the vehicle routing problem with time windows. Operations Research 1996;44:501-9.
[8] Chen YL, Rinks D and Tang K. Critical path in an activity network with time constraints. European Journal of Operational Research 1997;100:122-33.
[9] Chen YL and Tang K. Minimal time paths in a network with mixed time constraints. Comp Opns Res 1998;25: 793-805.
[10] Chen YL and Yang HH. Shortest paths in traffic-light networks. Trans Res:B 2000;34: 241-253.
[11] Desaulniters G and Villeneuve D. The shortest path problem with time windows and linear waiting costs. Transp. Sci. 2000;34: 312-319.
[12] Desrochers M, Desrosiers J and Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research 1992;40:342-54.
[13] Desrochers M and Soumis F. A reoptimization algorithm for the shortest path problem with time windows. European Journal of Operational Research 1988;35:242-54.
[14]Desrosiers J, Sauve M and Soumis F. Lagrangian relaxation methods for solving the minimum Oeet size multiple traveling salesman problem with time windows. Management Science 1988;34:1005-22.
[15] Dijkstra EW. A note on two problems in connexion with graphs. Numerische Mathematik 1959;1: 269-271.new window
[16] Dumas Y, Desrosiers J, Gelinas E and Solomon M. An optimal algorithm for the traveling salesman problem with time windows. Operations Research 1995;43:367-71.
[17] Dumas Y, Desrosiers J and Soumis F. The pickup and delivery problem with time windows. European Journal of Operational Research 1991;54:7-22.
[18] Eppstein D. Finding the k shortest paths. 35th Annual Symposium on Foundations of Computer Science 1994: 154-165.
[19] Floyd RW. Algorithm 97:shortest path. Comm. ACM 1962;5:6:345.
[20] Fox BL. Data structures and computer science techniques in operations research. Opns Res 1978;26: 686-717.
[21] Fredman ML and Tarjan RE. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of ACM 1987;34:596-615.
[22]Horowits E and Sahni S. Fundamentals of data structure in pascal. Computer Science Press 1990; 345-355.
[23] Kohl N and Madsen O. An optimization al
gorithm for the vehicle routing problem with time windows based on lagrangian relaxation. Operations Research 1997;45:395-406.
[24] Kolen A, Rinnooy KA and Trienekens H. Vehicle routing with time windows. Operations Research 1987;35:266-73.
[25]Martello S, Laporte G, Minoux M and Ribeiro C. Surveys in Combinatorial Optimization. Ann. Discr. Math. 31, North-Holland, Amsterdam, 147-184.
[26] Mingozzi A, Bianco L and Ricciardelli S. Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints. Operations Research 1997;45:365-77.
[27] Ree S and Yoon BS. A two-stage heuristic approach for the newspaper delivery problem. Computers & Industrial Engineering 1996;30:501-9.
[28] Shang JS and CuG CK. Multicriteria pickup and delivery problem with transfer opportunity. Computers & Industrial Engineering 1996;30:631-45.
[29] Solomon M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 1987;35:254-65.
[30]Warshall S. A theorem on Boolean matrices. J. ACM 1962;9:11-12.
 
 
 
 
第一頁 上一頁 下一頁 最後一頁 top
QR Code
QRCODE

臺灣人文及社會科學引文索引資料庫

目前上線人數：852（臺灣：838，外國：14） ／ 本年度總使用人次：2602775 ／ 訪客人次（自102年09月）：68396746
國家圖書館著作權聲明 Copyright © 2013 All rights reserved.
本館地址: 100201臺北市中山南路20號． 本館地圖及交通資訊．
總機：(02)23619132．最佳瀏覽解析度為1024x768以上