成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	吳旻哲 Wu, Min-Che
論文名稱：	考量目標卡路里消耗量之自行車騎乘路線規劃問題 Biking Route Planning Based on Target Calorie Comsumption
指導教授：	王逸琳 Wang, I-Lin
學位類別：	碩士 Master
系所名稱：	管理學院 - 資訊管理研究所 Institute of Information Management
論文出版年：	2010
畢業學年度：	98
語文別：	中文
論文頁數：	103
中文關鍵詞：	騎乘路線、卡路里、整數規劃、基因演算法、粒子群演算法
外文關鍵詞：	biking route, calorie, integer programming, Genetic Algorithm, Particle Swarm Optimization
相關次數：	點閱：105 下載：11
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

近來大眾之健康觀念及環保意識提升，騎乘自行車已逐漸成為主流運動之一。本研究將探討兩類騎乘路線（簡單路徑及迴圈路徑）之規劃方式，期能找出可滿足騎乘者設定之目標卡路里消耗量範圍的最安全騎乘路線。

我們首先考量三維的地理資料、風向與風速，配合騎乘者及自行車的重量、速度，提出騎乘各路段之卡路里消耗量估算方式。若將各路段之卡路里消耗量視為其路段長度，則尋找一條符合騎乘者設定的卡路里消耗範圍之騎乘路線，將等同於求解一具有長度限制的路徑規劃問題，為一NP-hard 問題，與文獻中大部分以求解最短路徑問題為主的汽車路徑規劃議題大相逕庭。然而我們發現此兩類路線規劃問題之數學規劃模式，其將受長度下限之影響而產生許多額外的排除子迴圈限制式（subtour elimination constraints），因此本研究針對此兩類路線個別推導其專屬的子迴圈排除限制式，並以Branch-and-Cut（B&C）手法加速其求解效率。此外，我們亦針對有效不等式（valid inequalities）及前處理演算法（preprocessing algorithm）作探討，並比較這兩種方法對於整數規劃模式求解效率的影響性。

由於第一類問題為一尋找長度符合限制範圍的簡單路徑問題，因此可將其轉化為具額外限制的最短路徑（Constrained Shortest Path；CSP）問題來求解。本研究參考相關CSP 文獻，提出改良式的前K短路徑（K-Shortest Path；KSP）演算法及拉氏釋限法（Lagrangian Relaxation；LR）來求解之。然而，測試結果顯示KSP及LR法皆可能耗時甚久，且求解效率隨網路規模變大而變差。為能更快求出品質不錯的路線以增加本研究之實用價值，我們亦針對此簡單路徑與迴圈路徑等兩類路線個別設計數種基因演算法（Genetic Algorithm；GA）及粒子群演算法（Particle Swarm Optimization；PSO）。數值測試結果顯示，GA之求解效率與效能皆劣於PSO，且PSO之求解效能較穩定且求解品質亦表現不錯，因此當時間有限且可接受非最佳騎乘路線時，本研究建議使用PSO當作路線規劃的計算機制。

Cycling becomes more popular recently, because it is not only environmentally friendly, but also a more pleasant way to lose weight. Conventional researches in route planning usually focus on selecting a route of minimum time, distance, or risks. This thesis, on the other hand, aims at methodologies to generate a least risky biking route that satisfies the calorie consumption requirement specified by the cyclist. We first introduce methods to estimate risks associated with nodes or arcs and propose a calorie consumption formula that takes the 3-dimensional geographical data over each route segment, the biking velocity and weight of the cyclist, and the speed and direction of the wind into consideration. Three categories of biking routes: simple paths, eulerian subgraphs, and general circuits are investigated. These are NP-hard integer programming problems. Their IP formulations have to include plenty of subtour elimination constraints due to the lower bound in the calorie consumption.

The problem of seeking an optimal biking route of the first category (i.e. an optimal simple path) can be viewed as a specialized constrained shortest path (CSP). We have exploit variants of conventional CSP methodologies such as K-shortest path (KSP) algorithms and Lagrangian Relaxation (LR), but found they both consume too much time. We then develop variants of Genetic Algorithms (GA) and Particle Swarm Optimization (PSO) heuristics to efficiently calculate an optimal biking route. Moreover, we also derive valid inequalities that generate new cuts in the branch-and- cut scheme and conduct preprocessing to simplify the network, so that the IP solution time is further reduced.

To effciently seek optimal biking routes that are circuits, we also propose a few GA and PSO heuristics that involve different encoding mechanisms. Computational experiments indicate our proposed PSO heuristics are more effcient and effective than the state-of-the-art IP solver and GA, for solving these three categories of biking routes, and thus are suitable for real-world implementation.

摘要 i
Abstract iii
誌謝 v
表目錄 ix
圖目錄 xi
第一章緒論 1
1 研究動機. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 研究目的. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3 研究範圍與限制. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4 論文架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
第二章文獻回顧 5
1 道路危險程度的推估方法. . . . . . . . . . . . . . . . . . . . . . . . . 5
2 卡路里消耗量的推估方法. . . . . . . . . . . . . . . . . . . . . . . . . 7
3 具額外限制的最短路徑問題. . . . . . . . . . . . . . . . . . . . . . . 10
4 前K短路徑演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.1 前K短簡單路徑演算法之相關文獻. . . . . . . . . . . . . . . 12
4.2 前K短可含迴圈路徑演算法之相關文獻. . . . . . . . . . . . . 12
5 車輛途程問題相關文獻. . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.1 具有長度限制的車輛途程問題. . . . . . . . . . . . . . . . . . 13
5.2 具有時窗限制的車輛途程問題. . . . . . . . . . . . . . . . . . 14
6 啟發式演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.1 基因演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.2 粒子群演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
第三章具長度限制之簡單路徑規劃問題 20
1 模式建構與問題限制. . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 求解演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1 拉氏釋限法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 前K短簡單路徑演算法. . . . . . . . . . . . . . . . . . . . . . 25
2.3 基因演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.1 染色體的編碼及解碼方法. . . . . . . . . . . . . . . . 28
2.3.2 染色體的交配、突變及適應函式. . . . . . . . . . . 29
2.4 粒子群演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3 前處理方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 有效不等式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.1 節點優先權不等式. . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2 不等式的加入機制. . . . . . . . . . . . . . . . . . . . . . . . . 35
5 數值測試與比較. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.1 模式求解與演算法之比較. . . . . . . . . . . . . . . . . . . . . 37
5.2 前處理對求解效率之影響. . . . . . . . . . . . . . . . . . . . . 46
5.3 有效不等式對求解效率之影響. . . . . . . . . . . . . . . . . . 49
6 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
第四章具長度限制之迴圈路徑規劃問題 52
1 尤拉子圖問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
1.1 模式建構與問題限制. . . . . . . . . . . . . . . . . . . . . . . 53
1.2 排除獨立子迴圈之討論. . . . . . . . . . . . . . . . . . . . . . 54
1.3 求解演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.3.1 基因演算法一（GA-I） . . . . . . . . . . . . . . . . . 55
1.3.2 基因演算法二（GA-II） . . . . . . . . . . . . . . . . 59
1.3.3 基因演算法三（GA-III） . . . . . . . . . . . . . . . . 61
1.3.4 粒子群演算法. . . . . . . . . . . . . . . . . . . . . . 65
1.4 前處理方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
1.5 數值測試與比較. . . . . . . . . . . . . . . . . . . . . . . . . . 69
1.5.1 求解整數規劃模式之探討. . . . . . . . . . . . . . . . 69
1.5.2 GA-I 與GA-II 之比較. . . . . . . . . . . . . . . . . . 71
1.5.3 演算法綜合比較. . . . . . . . . . . . . . . . . . . . . 71
1.5.4 前處理對求解效率之影響. . . . . . . . . . . . . . . . 77
2 一般迴圈問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.1 模式建構與問題限制. . . . . . . . . . . . . . . . . . . . . . . 80
2.2 粒子群演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
2.3 數值測試與比較. . . . . . . . . . . . . . . . . . . . . . . . . . 84
3 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
第五章結論與未來研究方向 91
1 結論與貢獻. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
1.1 具長度限制之簡單路徑規劃問題. . . . . . . . . . . . . . . . . 91
1.2 具長度限制之迴圈路徑規劃問題. . . . . . . . . . . . . . . . . 92
2 未來研究方向. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
2.1 延伸議題之討論. . . . . . . . . . . . . . . . . . . . . . . . . . 94
2.2 其它可行的求解概念. . . . . . . . . . . . . . . . . . . . . . . 96
參考文獻 99
                                    

王逸琳、賴致豪、尹珮瑜、劉家瑜及李翌瑄，(2009)，考慮目標熱量之自行車騎乘路線規劃問題，中國工業工程學術研討會。

交通部運輸研究所，(1997)，道路潛在危險性評估指標之研究

Ahn, C. W., Member, S., & Ramakrishna, R. S. (2002). A genetic algorithm for shortest path routing problem and the sizing of populations. IEEE Transactions on Evolutionary omputation, 6, 566 - 579.

Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Networkflows: theory, algorithms, and applications. Englewood Cliffs, NJ: Prentice Hall.

Ai, T. J., & Kachitvichyanukul, V. (2007). A particle swarm optimization for the capacitated vehicle routing problem. International Journal of Logistics and SCM Systems, 2, 50 - 55.

Ai, T. J., & Kachitvichyanukul, V. (2009a). A particle swarm optimisation for vehicle routing problem with time windows. International Journal of Operational Research, 6(4), 519 - 537.

Ai, T. J., & Kachitvichyanukul, V. (2009b). A particle swarm optimisation for vehicle routing problem with simultaneous pickup and delivery. Computers and Operations Research, 36, 1693 - 1702.

Bodin, L., Golden, B., Assad, A., & Ball, M. (1983). Routing and scheduling of vehicles and crews: The state of the art. Computers and Operations Research, 10(2), 63 - 211.

Brander, A. W., & Sinclair, M. C. (1995). A comparative study of k-shortest path algorithms. In Proc. 11th UK Performance Engineering Workshop for Computer and Telecommunications Systems.

Carlyle, W. M., Royset, J. O., & Wood, R. K. (2008). Lagrangian relaxation and enumeration for solving constrained shortest-path problems. Networks, 52(4), 256 - 270.

Chang, Y., & Chen, L. (2007). Solve the vehicle routing problem with time windows via a genetic algorithm. Discrete and continuous dynamical systems supplement, 240 - 249.

Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568 - 581.

Cordeau, J.-F., & Laporte., G. (2001). A tabu search algorithm for the site dependent vehicle routing problem with time windows. Scheduling in Distributed and Cellular Systems, 39(3), 292 - 298.

Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80 - 91.

Desrochers, M., Desrosiers, J., & Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2), 342 - 354.

Eppstein, D. (1999). Finding the k shortest paths. SIAM J. Comput., 28(2), 652 - 673.

Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109 - 124.

Fox, B. L. (1975). K-th shortest paths and applications to the probabilistic networks.ORSA/TIMS Joint National Mtg., 23, B263.

Garey, M. R., & Johnson, D. S. (1990). Computers and intractability: A guide to the theory of np-completeness. New York, NY, USA: W. H. Freeman & Co.

Garica, R. (2009). Resource constrained shortest paths and extensions. Unpublished doctoral dissertation, Georgia Institute of Technology, Atlanta, Georgia.

Gen, M., Cheng, R., & Wang, D. (1997). Genetic algorithms for solving shortest path problems. In Proc. of IEEE Interational Conference on Evolutionary Computation, 401 - 406.

Handler, G. Y., & Zang, I. (1980). A dual algorithm for the constrained shortest path problem. Networks, 10(4), 293 - 309.

Hassin, R. (1992). Approximation schemes for the restricted shortest path problem. Mathematics of Operations Research, 17(1), 36 - 42.

Hembecker, F., Lopes, H. S., & Godoy, W. (2007). Particle swarm optimization for the multidimensional knapsack problem. Lecture Notes in Computer Science, 4431,
358 - 365.

Hoffman, W., & Pavley, R. (1959). A method for the solution of the nth best path problem. J. ACM, 6(4), 506 - 514.

Hwang, H.-S. (2002). An improved model for vehicle routing problem with time constraint based on genetic algorithm. Computers and Industrial Engineering, 42(2-4), 361 - 369.

Katoh, N., Ibaraki, T., & Mine, H. (1982). An e±cient algorithm for k shortest simple paths. Networks, 12(4), 411 - 427.

Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In Proc. of IEEE International Conference on Neural Networks, 4, 1942 - 1948.

Kong, M., & Tian, P. (2006). Apply the particle swarm optimization to the multidimensional knapsack problem. In Proc. 8th Int. Conf. Artif. Intell. Soft Comput. (ICAISC), 4029, 1140 - 1149.

Koskosidis, Y. A., Powell, W. B., & Solomon, M. M. (1992). An optimization-based heuristic for vehicle routing and scheduling with soft time window constraints. Transportation Science, 26(2), 69 - 85.

Kumar, N., & Ghosh., R. K. (1994). Parallel algorithm for finding first k shortest paths. computer. Computer Science and Informatics, 24(3), 21 - 28.

Laporte, G., Desrochers, M., & Nobert, Y. (1984). Two exact algorithms for the distance-constrained vehicle routing problem. Networks, 14(1), 161 - 172.

Laporte, G., Nobert, Y., & Desrochers, M. (1985). Optimal routing under capacity and distance restrictions. Operations Research, 33(5), 1050 - 1073.

Lawler, E. L. (1972). A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18(7), 401 - 405.

Li, C.-L., Simchi-Levi, D., & Desrochers, M. (1992). On the distance constrained vehicle routing problem. Operations Research, 40(4), 790 - 799.

Lin, L., & Gen, M. (2009). Priority-based genetic algorithm for shortest path routing problem in ospf. Intelligent and Evolutionary Systems, 187, 91 - 103.

Lorenz, D. H., & Raz, D. (2001). A simple e±cient approximation scheme for the restricted shortest path problem. Operations Research Letters, 28(5), 213 - 219.

Mohemmed, A. W., Sahoo, N. C., & Geok, T. K. (2008). Solving shortest path problem using particle swarm optimization. Applied Soft Computing, 8(4), 1643 - 1653.

Padberg, M., & Rinaldi, G. (1991). A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev., 33(1), 60 - 100.

Pape, U. (1974). Implementation and effciency of moore-algorithms for the shortest route problem. Mathematical Programming, 7(1), 212 - 222.

Ribero, C., & Minoux, M. (1985). A heuristic approach to hard constrained shortest path prorblems. Discrete Applied Mathematics, 10, 125 - 137.

Ruppert, E. (2000). Finding the k shortest paths in parallel. Algorithmica, 28(2), 242 - 254.

Shier, D. R. (1979). On algorithms for finding the k shortest paths in a network. Networks, 9(3), 195 - 214.

Solomon, M. M., & Desrosiers, J. (1988). Survey paper - time window constrained routing and scheduling problems. Transportation Science, 22(1), 1 - 13.

Warburton, A. (1987). Approximation of pareto optima in multiple-objective, shortest-path problem. Operations Research, 35, 70 - 79.

Xiao, Y., Thulasiraman, K., Xue, G., & Juttner, A. (2005). The constrained shortest path problem: algorithmic approaches and an algebraic study with generalization.
AKCE International Journal of Graphs and Combinatorics, 2(2), 63 - 86.

Yen, J. Y. (1971). Finding the k shortest loopless paths in a network. Management Science, 17(11), 712 - 716.

校內：2013-08-18公開
校外：2013-08-18公開

簡易檢索 / 詳目顯示

相關論文