跳到主要內容

臺灣博碩士論文加值系統

(44.222.64.76) 您好!臺灣時間:2024/06/16 04:36
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:王維邦
研究生(外文):Wei-Bung Wang
論文名稱:時間VoronoiDiagram與運輸網定價
論文名稱(外文):Time-based Voronoi Diagram and Transportation Network Pricing
指導教授:李德財李德財引用關係
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:34
中文關鍵詞:Voronoi diagram
外文關鍵詞:Voronoi diagramprice
相關次數:
  • 被引用被引用:0
  • 點閱點閱:149
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文主要有兩章,探討兩個不同的問題。這兩個問題都是與直線公路有關。

第二章我們考慮一個 Voronoi diagram 的變形,稱為「時間 Voronoi diagram」。在平面上有一組點 (site) 和一組直線公路,在公路上移動速度較快。兩點之間的「最短時間距離」則是從一點到另一點,所需要的最少時間。每條公路的速度亦不盡相同。我們將探討,在有公路的考量下,Voronoi diagram 會如何改變。

第三章我們考慮一個 Stackelberg game 的問題。一家運輸公司,擁有平面上一組直線公路,並按里程收費。現有一組顧客,每位顧客有一個目的地,他們可以選擇使用或不使用公路,而他們的目標是用盡量少的成本到達目的地。我們將從這家公路公司的角度,尋找一個好的公路使用費率,盡可能地將利潤最佳化。
We have two main topics in this thesis. These topics are concerned with a model that involves straight-line highways.

In chapter 2 we consider a variation of Voronoi diagram, or time-based Voronoi diagram, for a set S of sites in the presence of transportation lines or highways in the plane. A shortest time-distance path from a query point to any given sites in S is a path that takes the least travelling time. The travelling speeds and hence travelling times of the subpaths along the highways and in the plane are different. Using different distance metrics will change the characteristics of the Voronoi diagram.

In chapter 3 we consider a game model called Stackelberg game [1]. With a set of source-destination pairs in the presence of transportation network in the plane, the owner of the network can decide a fare charge on the usage of the transportation network. We assume that each customer at a source will try to minimize his cost when travelling to the destination, with or without using the network. Under this assumption we play the role of the transportation network owner and try to maximize our profit by deciding a good fare.
書名頁 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Chinese Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
English Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Time-Based Voronoi Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Good Angle Condition for Two-Highway Model . . . . . . . . . . . . . . 6
2.3 Good Angle Condition for Multiple-Highway Model . . . . . . . . . . . 11
2.4 General Condition for Two-Highway and Multiple-Highway Model . . . 19
3 Network Pricing Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Two-Highway Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 A Good Multiple-Highway Model . . . . . . . . . . . . . . . . . . . . . 27
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
[1] M. J. Osborne and A. Rubinstein, A Course in Game Theory. The MIT Press, 1994.
[2] O. Aichholzer, F. Aurenhammer, D. Z. Chen, D. T. Lee, and E. Papadopoulou,
“Skew Voronoi diagram,” Int’l J. Comput. Geometry and Applications, vol. 9,
pp. 235–248, June 1999.
[3] H. Edelsbrunner, Algorithms in Combinatorial Geometry. New York, NY: Springer-
Verlag New York, Inc., 1987.
[4] D. T. Lee, “Two dimensional Voronoi diagram in the Lp-metric,” J. ACM, pp. 604–
618, October 1980.
[5] D. T. Lee and R. L. Drysdale, “Generalization of Voronoi diagram in the plane,”
SIAM J. Comput., pp. 73–87, February 1981.
[6] E. Papadopoulou and D. T. Lee, “A new approach for the geodesic Voronoi diagram
of points in a simple polygon and other restricted polygonal domains,” Algorithmica,
vol. 20, pp. 319–352, April 1998.
[7] F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction. New
York, NY: Springer-Verlag New York, Inc., 1985.
[8] C. K. Yap, “An O(n log n) algorithm for the Voronoi diagram of a set of simple
curve segments,” Discrete and Computational Geometry, vol. 2, pp. 365–393, 1987.
[9] M. Abellanas, F. Hurtado, V. Sacrist´an, C. Icking, L. Ma, R. Klein, E. Langetepe,
and B. Palop, “Voronoi diagram for services neighboring a highway,” in Information
Processing Letters 86, pp. 283–288, 2003.
[10] J. Cardinal, M. Labb´e, S. Langerman, and B. Palop, “Pricing geometric transportation
networks,” Canadian Conference CG, 2005.
[11] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms. Cambridge,
Massachusetts 02142: The MIT Press, 1990.
[12] S. W. Bae and K.-Y. Chwa, “Voronoi diagram with a transportation network,” in International
Symposium on Voronoi Diagrams in Science and Engineering, pp. 213-
227, September 2004.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top