時間Voronoi Diagram與運輸網定價

本論文主要有兩章，探討兩個不同的問題。這兩個問題都是與直線公路有關。第二章我們考慮一個 Voronoi diagram 的變形，稱為「時間 Voronoi diagram」。在平面上有一組點 (site) 和一組直線公路，在公路上移動速度較快。兩點之間的「最短時間距離」則是從一點到另一點，所需要的最少時間。每條公路的速度亦不盡相同。我們將探討，在有公路的考量下，Voronoi diagram 會如何改變。第三章我們考慮一個 Stackelberg game 的問題。一家運輸公司，擁有平面上一組直線公路，並按里程收費。現有一組顧客，每位顧客有一個目的地，他們可以選擇使用或不使用公路，而他們的目標是用盡量少的成本到達目的地。我們將從這家公路公司的角度，尋找一個好的公路使用費率，盡可能地將利潤最佳化。

關鍵字

Voronoi diagram

並列摘要

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.

並列關鍵字

Voronoi diagram ； price

參考文獻

[1] M. J. Osborne and A. Rubinstein, A Course in Game Theory. The MIT Press, 1994.

“Skew Voronoi diagram,” Int’l J. Comput. Geometry and Applications, vol. 9,

[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–

國際替代計量

時間Voronoi Diagram與運輸網定價

全文下載

主題瀏覽