Taxi Carpooling Problem Solved by Genetic Algorithm and Ant Colony Optimization Method
Date Issued
2014
Date
2014
Author(s)
Sheng, Tsung-Hao
Abstract
This work presents a taxi carpooling problem for people traveling in a metropolitan area. The problem is augmented from a dial-and-ride problem by adding same-sex restrictions and tolerable exceeding time constrains to the passengers onboard. The goal is to minimize the traveling time and distance of the dispatched taxies to serve all of the passengers carpooled without violating boarding time window constraints, capacity constraints, same-sex restrictions, and exceeding time limit constraints. In addition to the problem definition, a mix-integer linear programming model is presented to depict the optimization problem subject to a variety of constraints. In addition, a scheduling procedure is developed to decode a routing plan of the dispatched taxies to obtain boarding, traveling, and unboarding details, in order to calculate the amounts of constraint violation and objective values as well. Moreover, a Genetic Algorithm based and an Ant Colony Optimization-based solving method is proposed. Additionally, a prototype solving system implementing the proposed methods is developed for solving the carpooling problem. Sampling problems of different numbers of customers within different sizes of time periods are constructed based on 100 boding/exiting points picked from a metro city. Numerical tests are conducted to compare the performance of three computation modes: the GA, GA with schedule refinement, and ACO. Results show that all the proposed modes have significantly reduced the traveling time and cost comparing to the original cost. The carpooled results also show that the number of taxies dispatched is lowered than the half of the number of passengers. Among the tested modes the GA methods generally outperform the ACO method for most of the tested samples.
Subjects
遺傳演算法
蟻拓優化演算法
撥召問題
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-103-R01546040-1.pdf
Size
23.54 KB
Format
Adobe PDF
Checksum
(MD5):0672c4a812cd70162661558f4923ac40