本研究提出於都會區內的計程車共乘問題。問題承襲自撥召問題並加入同性別限制和容忍多繞行時間限制。目的是在不違反乘客上車時窗限制、車容量限制、同性別限制及多繞行時間限制的情況下，最小化車輛途程產生的行車時間及距離成本。除了定義問題外，並針對限制條件提出此優化問題的混整數線性規劃模型。此外為了取得車輛繞行產生的目標值和違反限制條件的違反量，本研究規劃路徑排程演算程序，根據計程車繞行序列取得繞行途中於各點抵達時間、出發時間和車上乘客等資訊。本研究提出以遺傳演算及蟻拓優化演算為基的求解模式，並實作求解系統以求解計程車共乘問題。本研究取得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.

謝誌 i
摘要 ii
Abstract iii
圖目錄 vi
表目錄 vii
1. 緒論 1
1.1. 研究背景 1
1.2. 研究目的 2
1.3. 研究方法 2
2. 文獻探討 4
2.1. 多車輛取卸貨問題數學模式 4
2.2. 多車輛取卸貨問題 6
2.2.1. 載貨返航之車輛途程問題(VRPB) 6
2.2.2. 取卸貨之車輛途程問題(VRPPD) 7
2.2.3. 問題複雜度比較 9
2.3. 求解方法 9
2.3.1. 遺傳演算法 10
2.3.2. 蟻拓優化演算法 10
3. 具時限及性別限制的計程車共乘問題之遺傳及蟻拓優化演算法 12
3.1. 具時限及性別限制的計程車共乘問題定義 12
3.1.1. 問題背景 12
3.1.2. 問題定義 13
3.1.3. MILP模式 20
3.2. 具時限及性別限制的計程車共乘問題的遺傳演算法 24
3.2.1. 染色體編碼、解碼法 24
3.2.2. 染色體適應值 26
3.2.3. 貪婪插入法 26
3.2.4. 遺傳演算法的初始解產生 27
3.2.5. 遺傳演算法的交配演算 29
3.2.6. 遺傳演算法的突變演算 32
3.2.7. 遺傳演算法的篩選演算 32
3.2.8. 小結 32
3.3. 具時限及性別限制的計程車共乘問題的蟻拓優化演算法 33
3.3.1. 蟻拓優化演算法的費洛蒙表設計 33
3.3.2. 蟻拓優化演算法的求解模式 33
3.3.3. 蟻拓優化演算法之啟發項設計 34
3.3.4. 蟻拓優化演算法解建構的演算流程 34
3.3.5. 蟻拓優化演算法的費洛蒙更新 39
3.3.6. 小結 39
4. 遺傳及蟻拓優化演算求解系統及範例驗證 40
4.1. 測試範例題庫 40
4.2. 遺傳及蟻拓優化演算法求解系統 42
4.3. 範例測試及效能驗證 45
5. 結論與未來研究建議 54
5.1. 結論 54
5.2. 未來研究建議 54
參考文獻 56

B, Golden, Baker E, Alfaro J, &; J, Schaffer. (1985). The vehicle routing problem with backhauling: Two approaches. Paper presented at the Hammesfahr RD (ed) Proceedings of the Twenty-First Annual Meeting of S. E. TIMS.
Chisman, James A. (1975). The clustered traveling salesman problem. Computers &; Operations Research, 2(2), 115-119.
Cordeau, Jean-Francois, &; Laporte, Gilbert. (2003). A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B: Methodological, 37(6), 579-594.
Cordeau, Jean-Francois, &; Laporte, Gilbert. (2007). The dial-a-ride problem: models and algorithms. Annals of Operations Research, 153(1), 29-46.
Cordeau, Jean-Francois, Desaulniers, Guy, Desrosiers, Jacques, Solomon, Marius M, &; Soumis, Francois. (2001). VRP with time windows. The vehicle routing problem, 9, 157-193.
Deif, I, &; Bodin, L. (1984). Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling. Paper presented at the Proceedings of the Babson conference on software uses in transportation and logistics management.
Dorigo, Marco, Maniezzo, Vittorio, &; Colorni, Alberto. (1996). Ant system: optimization by a colony of cooperating agents. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 26(1), 29-41.
Holland, John H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence: U Michigan Press.
Jorgensen, RM, Larsen, Jesper, &; Bergvinsdottir, Kristin Berg. (2007). Solving the dial-a-ride problem using genetic algorithms. Journal of the Operational Research Society, 58(10), 1321-1331.
Kalantari, Bahman, Hill, Arthur V, &; Arora, Sant R. (1985). An algorithm for the traveling salesman problem with pickup and delivery customers. European Journal of Operational Research, 22(3), 377-386.
Min, Hokey. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5), 377-386.
Parragh, Sophie N, Doerner, Karl F, &; Hartl, Richard F. (2008). A survey on pickup and delivery problems. Journal fur Betriebswirtschaft, 58(1), 21-51.
Parragh, Sophie N, Doerner, Karl F, &; Hartl, Richard F. (2010). Variable neighborhood search for the dial-a-ride problem. Computers &; Operations Research, 37(6), 1129-1138.
Psaraftis, Harilaos N. (1980). A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transportation Science, 14(2), 130-154.