以遺傳演算法及蟻拓優化演算法求解具時限及性別限制的計程車共乘問題

Abstract

本研究提出於都會區內的計程車共乘問題。問題承襲自撥召問題並加入同性別限制和容忍多繞行時間限制。目的是在不違反乘客上車時窗限制、車容量限制、同性別限制及多繞行時間限制的情況下，最小化車輛途程產生的行車時間及距離成本。除了定義問題外，並針對限制條件提出此優化問題的混整數線性規劃模型。此外為了取得車輛繞行產生的目標值和違反限制條件的違反量，本研究規劃路徑排程演算程序，根據計程車繞行序列取得繞行途中於各點抵達時間、出發時間和車上乘客等資訊。本研究提出以遺傳演算及蟻拓優化演算為基的求解模式，並實作求解系統以求解計程車共乘問題。本研究取得100個都市區的站點以及點跟點之間的路徑資訊，設計在不同需求區間下不同乘客數的範例問題，並以此範例比較三種求解模式的求解效能：基本遺傳演算模式、排程改良的遺傳演算模式、蟻拓優化演算模式。測試結果顯示三種求解摸式得到的行車成本相較於原始成本都顯著降低。此外，實驗結果顯示兩種遺傳演算模式在大部份的範例中效能皆高於蟻拓模式。

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.