| dc.description.abstract | 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.
| en_US |