小汽車共乘配對最佳化模式暨求解演算法之研究; Optimization Models and Solution Algorithms for the Car Pooling Problems

NCUIR > Engineering College > Graduate Institute of Civil Engineering > Electronic Thesis & Dissertation > Item 987654321/43317

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/43317

Title:	小汽車共乘配對最佳化模式暨求解演算法之研究;Optimization Models and Solution Algorithms for the Car Pooling Problems
Authors:	陳俊穎;Chun-Ying Chen
Contributors:	土木工程研究所
Keywords:	小客車共乘;多重貨物網路流動問題;時空網路;拉氏鬆弛法;time-space network;multiple commodity network flow problem;carpool;Lagrangian relaxation
Date:	2010-07-21
Issue Date:	2010-12-08 13:34:17 (UTC+8)
Publisher:	國立中央大學
Abstract:	由於目前台灣都會區交通量的成長迅速，因此若能實行小客車共乘，則除可以紓解都市的交通擁塞問題外，亦可節約國家的能源。然而，以往探討小客車共乘配對問題的文獻不多，且為簡化問題，所發展的模式大多未考慮實際營運時的限制，僅考量簡單的時窗與容量限制。因此，此等模式難以直接地運用於複雜的實務問題上。至於在問題稍為相似的撥召配對文獻上，雖有較多學者曾嘗試發展數學解析模式及解法，然該問題與本研究所欲解決的小客車共乘問題存有相當的差異，因此其模式與解法亦難直接地應用於求解本研究問題。由於以往鮮有探討多對多起迄之小客車共乘配對問題，另在加入考量先前配對資訊考量的小客車共乘問題更未發現有相關的研究，因此本研究以系統最佳化觀點，針對預約式多對多起迄的旅次發展一小客車共乘配對模式與考量先前資訊之小客車共乘配對模式，期能提供決策者輔助工具，在面對不同的問題，以有效地規劃小客車共乘配對。本研究分為兩個主題。第一主題中，本研究針對每日預約的多對多起迄旅客構建一不考量先前資訊之小客車共乘配對模式；第二主題中，針對每日預約的多對多起迄旅客構建考量先前資訊之小客車共乘配對模式。本研究利用網路流動技巧以構建所有模式。此等模式預期均可定式為特殊之整數多重貨物網路流動問題，屬NP-hard問題，預期在面對實務大型的問題時，難以在合理的時間內求得最佳解。因此，為了有效地求解實際的大型問題，在第一個主題中，我們發展一以拉氏鬆弛法暨次梯度法為基礎之求解演算法以及一個上限啟發解法；第二個主題中，我們發展一以拉氏鬆弛法為基礎之求解演算法以及一個上限啟發解法。最後，為評估各演算法之實際求解績效，本研究進行範例測試，並設計電腦隨機產生器產生多個不同的測試例，以測試各演算法在不同情況下的求解績效，結果甚佳。 Traffic volume has significantly grown in Taiwan. If carpool is performed, it will not only relieve traffic congestion but will also save energy. However, only a little research related with car pooling problems has been studied. Moreover, in order to simplify the studied problems, they only considered simple constraints, such as time-windows or capacity constraints. Consequently, the proposed models or methods cannot be directly applied to the complex and practical carpooling problems. Although many researchers have developed analytical models to solve the dial-a-ride problem which is rather closely related with our research, the difference in between is significant. Therefore, the proposed models and solution algorithms cannot be directly used for solving our problem. Since there has not yet research on many-to-many car pooling problem, particularly with consideration of pre-matching information, in this research, based on the system optimization perspective and a set of given advanced-order passenger trips, we develop a many-to-many car pooling model, and the many-to-many car pooling model with pre-matching information. These models are expected to be useful tools to help the planner effectively and efficiently solve these car pooling problems. This study is divided into two essays. In the first essay, we construct a car pooling model without pre-matching information for the daily advanced-order many-to-many trips. In the second essay, we construct the car pooling model with pre-matching information for the daily advanced-order many-to-many trips. In this study, we strive to make up this lack by employing a time-space network flow technique to develop models for two essays. All the models are formulated as special integer multiple commodity network flow problems, which are characterized as NP-hard and cannot be optimally solved in a reasonable time for large-scale problems. In order to efficiently solve large-scale problems occurring in real world, in the first essay, we develop a solution algorithm based on Lagrangian relaxation, a subgradient method, and a heuristic for the upper bound solution, to solve the model; in the second essays, we develop a solution algorithm based on Lagrangian relaxation, and a heuristic for the upper bound solution, to solve the model. Finally, computerized random generators also are designed to generate different problem instances used for testing the solution algorithms. The results are good, showing that the model and heuristic algorithm could be useful.
Appears in Collections:	[Graduate Institute of Civil Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	704	View/Open

社群 sharing

Loading...