臺灣博碩士論文加值系統

智慧型共乘系統（Intelligent Carpool System, ICS），讓司機與乘客能輕鬆地存取共乘服務方便達成使用者間的車輛共乘，現今共乘的相關議題已經發展為共乘服務問題（Carpool Service Problem, CSP）。本論文承續了基礎的共乘服務問題，並更進一步定義高乘載旅途規劃之共乘服務問題(Carpool Services Problem Featuring High-Occupancy-Vehicle Itineraries, CSPHI)，其中高乘載旅途規劃主要是利用多目標問題模型，考量車輛如何在共乘旅途之情況下，所行駛的每一條路徑都能夠使車輛內座位空間具有高效率的使用。因此，本論文是基於第二代非支配排序基因演算法(Non-dominated Sorting Genetic Algorithm II, NSGA-II) 結合專為問題所設計的啟發操作子，提出了多目標最佳化演算法求解高乘載旅途規劃之共乘服務問題(HMO-CSPHI)，其主要由兩個模組所構成：(1)啟發式搜尋操作和(2)多目標個體選擇。在本論文實驗中，我們將沒有加入啟發式操作的NSGA-II與本論文提出的HMO-CSPH演算法作為主要的比較對象，實驗結果證明本論文所提出的HMO-CSPHI演算法，針對多目標的量化評估和二維目標視覺化投影上都有顯著的帕雷托最優結果。

Intelligent carpool system makes both drivers and passengers even convenient to access carpool services to enjoy their ridesharing. The foundation of carpool-related issues has been developed as Carpool Service Problem. This thesis inherits from fundamental problem to further as Carpool Service Problem featuring High-Occupancy-Vehicle Itineraries which takes into consideration the enhancement of the vehicular space occupancy for each edge of ridesharing itinerary while multiple objectives is being involved. As such, the Heuristic Multi-Objective Optimization Algorithm to solve Carpool Service Problem featuring High-Occupancy-Vehicle Itineraries is proposed based on Non-dominated Sorting Genetic Algorithm II and comprised of two modules: Heuristics Search Operation and Multi-objective Individual Selection. In the experimental section, the Non-dominated Sorting Genetic Algorithm II without the heuristics mechanism is taken as an important competitor to the proposed Heuristic Multi-Objective Optimization Algorithm. Experimental results demonstrate that HMO-CSPHI can generate the most outstanding performances in terms of quantitative analysis and visualization comparison on Pareto optimality.

Abstract in Chinese i
Abstract in English ii
Acknowledgements iii
Contents iv
List of Figures vi
List of Tables vii
1 Introduction 1
1.1 Thesis Overview 3
2 Background 4
3 Proposed HMO-CSPHI algorithm 9
3.1 Heuristics Search Operation 9
3.1.1 Route Renewal Function (RRF) 11
3.1.2 Passenger Insertion Heuristics (HS1) 12
3.1.3 Passenger Mixture Heuristics (HS2) 13
3.1.4 Perimeter Exchange Heuristics (HS3) 15
3.1.5 Driver Route Heuristics (HS4) 17
3.2 Multi-objective Individual Selection 18
3.2.1 Non-dominated Sorting 18
3.2.2 Crowding Distance Sorting 20
4 Experimental Results 22
4.1 Performance Metrics in Multi-objective Optimization 23
4.1.1 Inverted Generational Distance (IGD) 24
4.1.2 Spacing Metric (SP) 24
4.1.3 Pareto Spread Metric (OS) 24
4.1.4 Distribution and Spread / Diversity Metric (△*) 25
4.1.5 Coverage Metric (C-metric) 25
4.2 Comparisons of our HMO-CSPHI and NSGA-II-CM 26
4.2.1 Quantitative Analysis on MOO Metrics 26
4.2.2 Visualization Analysis on 2D Projection 28
5 Conclusions 30
Bibliography 31

[1] F.-Y. Wang, S. Tang, Y. Sui, and X. Wang, “Toward intelligent transportation systems for the 2008
olympics,” IEEE Intelligent Systems, vol. 18, pp. 8–11, Nov 2003.
[2] R. Barrero, J. V. Mierlo, and X. Tackoen, “Energy savings in public transport,” IEEE Vehicular Technology
Magazine, vol. 3, pp. 26–36, Sept 2008.
[3] S. Tsugawa and S. Kato, “Energy its: another application of vehicular communications,” IEEE Communications
Magazine, vol. 48, pp. 120–126, November 2010.
[4] O. Dakroub, C. M. Boukhater, F. Lahoud, M. Awad, and H. Artail, “An intelligent carpooling app for
a green social solution to traffic and parking congestions,” in 16th International IEEE Conference on
Intelligent Transportation Systems (ITSC 2013), pp. 2401–2408, Oct 2013.
[5] J.-F. Cordeau, G. Laporte, J.-Y. Potvin, and M. W. Savelsbergh, “Chapter 7 transportation on demand,”
in Transportation (C. Barnhart and G. Laporte, eds.), vol. 14 of Handbooks in Operations Research
and Management Science, pp. 429 – 466, Elsevier, 2007.
[6] A. Santos, N. McGuckin, H. Y. Nakamoto, D. Gray, and S. Liss, “Summary of travel trends: 2009 national
household travel survey,” Technical Report, US Department of Transportation Federal Highway
Administration, 2011.
[7] N. D. Chan and S. A. Shaheen, “Ridesharing in north america: Past, present, and future.,” Transport
Reviews, vol. 32, no. 1, pp. 93–112, 2012.
[8] “Lyft’s Home.” https://www.lyft.com/.
[9] “Uber’s Home.” https://www.uber.com/.
[10] “Flinc’s Home.” https://flinc.org/.
[11] “Carma’s Home.” https://www.gocarma.com/.
[12] “Zimride’s Home.” http://www.zimride.com/.
[13] “BlueNet-Ride.” https://www.bluenet-ride.com/.
[14] S. C. Huang, M. K. Jiau, and C. H. Lin, “A genetic-algorithm-based approach to solve carpool service
problems in cloud computing,” IEEE Transactions on Intelligent Transportation Systems, vol. 16,
pp. 352–364, Feb 2015.
[15] R. Baldacci, V. Maniezzo, and A. Mingozzi, “An exact method for the car pooling problem based on
lagrangean column generation,” Oper. Res., vol. 52, pp. 422–439, June 2004.
[16] N. A. Agatz, A. L. Erera, M. W. Savelsbergh, and X. Wang, “Dynamic ride-sharing: A simulation
study in metro atlanta,” Transportation Research Part B: Methodological, vol. 45, no. 9, pp. 1450 –
1464, 2011. Select Papers from the 19th {ISTTT}.
[17] M. K. Jiau, S. C. Huang, and C. H. Lin, “Optimizing the carpool service problem with genetic algorithm
in service-based computing,” in Services Computing (SCC), 2013 IEEE International Conference on,
pp. 478–485, June 2013.
[18] S. C. Huang, M. K. Jiau, and C. H. Lin, “Optimization of the carpool service problem via a fuzzycontrolled
genetic algorithm,” IEEE Transactions on Fuzzy Systems, vol. 23, pp. 1698–1712, Oct
2015.
[19] R. Baldacci, A. Mingozzi, and R. Roberti, “Recent exact algorithms for solving the vehicle routing
problem under capacity and time window constraints,” European Journal of Operational Research,
vol. 218, no. 1, pp. 1 – 6, 2012.
[20] H. C. Brandão de Oliveira and G. C. Vasconcelos, “A hybrid search method for the vehicle routing
problem with time windows,” Annals of Operations Research, vol. 180, no. 1, pp. 125–144, 2010.
[21] Z. Ursani, D. Essam, D. Cornforth, and R. Stocker, “Localized genetic algorithm for vehicle routing
problem with time windows,” Applied Soft Computing, vol. 11, no. 8, pp. 5375 – 5390, 2011.
[22] Y. J. Gong, J. Zhang, O. Liu, R. Z. Huang, H. S. H. Chung, and Y. H. Shi, “Optimizing the vehicle
routing problem with time windows: A discrete particle swarm optimization approach,” IEEE Transactions
on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 42, pp. 254–267,
March 2012.
[23] M. K. Jiau and S. C. Huang, “Services-oriented computing using the compact genetic algorithm
for solving the carpool services problem,” IEEE Transactions on Intelligent Transportation Systems,
vol. 16, pp. 2711–2722, Oct 2015.
[24] W. M. Herbawi and M. Weber, “A genetic and insertion heuristic algorithm for solving the dynamic
ridematching problem with time windows,” in Proceedings of the 14th Annual Conference on Genetic
and Evolutionary Computation, GECCO ’12, (New York, NY, USA), pp. 385–392, ACM, 2012.
[25] K. Ghoseiri, A. Haghani, M. Hamedi, M.-A. U. T. Center, P. D. of Transportation, U. S. D. of Transportation.
Research, and I. T. Administration, Real-time Rideshare Matching Problem. Mid-Atlantic
Universities Transportation Center, 2011.
[26] J. Castro-Gutierrez, D. Landa-Silva, and J. M. Pérez, “Nature of real-world multi-objective vehicle
routing with evolutionary algorithms,” in Systems, Man, and Cybernetics (SMC), 2011 IEEE International
Conference on, pp. 257–264, Oct 2011.
[27] J. O. Yang, Q. R. Yuan, F. Yang, H. J. Zhou, Z. P. Nie, and Z. Q. Zhao, “Synthesis of conformal phased
array with improved nsga-ii algorithm,” IEEE Transactions on Antennas and Propagation, vol. 57,
pp. 4006–4009, Dec 2009.
[28] M. Shaygan, A. Alimohammadi, A. Mansourian, Z. S. Govara, and S. M. Kalami, “Spatial multiobjective
optimization approach for land use allocation using nsga-ii,” IEEE Journal of Selected Topics
in Applied Earth Observations and Remote Sensing, vol. 7, pp. 906–916, March 2014.
[29] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm:
Nsga-ii,” IEEE Transactions on Evolutionary Computation, vol. 6, pp. 182–197, Apr 2002.
[30] N. Agatz, A. Erera, M. Savelsbergh, and X. Wang, “Optimization for dynamic ride-sharing: A review,”
European Journal of Operational Research, vol. 223, no. 2, pp. 295 – 303, 2012.
[31] B. Meng, L. Zheng, H. Yu, and G. Me, “Spatial characteristics of the residents’ commuting behavior
in beijing,” in Geoinformatics, 2011 19th International Conference on, pp. 1–5, June 2011.
[32] M. O. Asikhia and N. F. Nkeki, “Polycentric employment growth and the commuting behaviour in
benin metropolitan region, nigeria,” Journal of Geography and Geology, vol. 5, no. 2, p. 1, 2013.
[33] “Google cloud platform.” https://cloud.google.com/.
[34] S. Jiang, Y. S. Ong, J. Zhang, and L. Feng, “Consistencies and contradictions of performance metrics in
multiobjective optimization,” IEEE Transactions on Cybernetics, vol. 44, pp. 2391–2404, Dec 2014.
[35] Y. Zhou and J. Wang, “A local search-based multiobjective optimization algorithm for multiobjective
vehicle routing problem with time windows,” IEEE Systems Journal, vol. 9, pp. 1100–1113, Sept 2015.
[36] Z. He and G. G. Yen, “Visualization and performance metric in many-objective optimization,” IEEE
Transactions on Evolutionary Computation, vol. 20, pp. 386–402, June 2016.
[37] D. A. van Veldhuizen and G. B. Lamont, “Multiobjective evolutionary algorithm test suites,” in Proceedings
of the 1999 ACM Symposium on Applied Computing, SAC ’99, (New York, NY, USA),
pp. 351–357, ACM, 1999.
[38] E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G. da Fonseca, “Performance assessment of
multiobjective optimizers: an analysis and review,” IEEE Transactions on Evolutionary Computation,
vol. 7, pp. 117–132, April 2003.
[39] Q. Zhang and H. Li, “Moea/d: A multiobjective evolutionary algorithm based on decomposition,”
IEEE Transactions on Evolutionary Computation, vol. 11, pp. 712–731, Dec 2007.
[40] H. Li and Q. Zhang, “Multiobjective optimization problems with complicated pareto sets, moea/d and
nsga-ii,” IEEE Transactions on Evolutionary Computation, vol. 13, pp. 284–302, April 2009.
[41] J. Schott, Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. Massachusetts
Institute of Technology, Department of Aeronautics and Astronautics, 1995.
[42] J. Wu and S. Azarm, “Metrics for Quality Assessment of a Multiobjective Design Optimization Solution
Set,” Journal of Mechanical Design, vol. 123, 2001.
[43] A. Zhou, Y. Jin, Q. Zhang, B. Sendhoff, and E. Tsang, “Combining model-based and genetics-based
offspring generation for multi-objective optimization using a convergence criterion,” in 2006 IEEE
International Conference on Evolutionary Computation, pp. 892–899, 2006.
[44] E. Zitzler and L. Thiele, Multiobjective optimization using evolutionary algorithms — A comparative
case study, pp. 292–301. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998.
[45] E. Zitzler and L. Thiele, “Multiobjective evolutionary algorithms: a comparative case study and the
strength pareto approach,” IEEE Transactions on Evolutionary Computation, vol. 3, pp. 257–271, Nov
1999.