臺灣博碩士論文加值系統

共享交通模式是共享經濟重要的一環，不但能減緩空氣汙染，也促進智慧城市的發展。隨著人工智慧(AI)、V2X通訊技術發展愈趨成熟，以及5G時代的來臨，自動駕駛車輛在道路提供乘客接送服務指日可待。隨需自動駕駛服務為結合自駕車及隨需行動服務的概念，讓乘客享有最後一哩路的服務。除了解決乘車需求的時空不確定性，也能自主平衡城市中的供需問題，實現共享自駕車的服務理念。
研究指出，實施動態費率是叫車平台平衡供需的有效方法，一方面能增加司機進入市場的誘因，另一方面則減少價格敏感的乘客之搭車需求。在歐美國家，部分民眾考量私人汽車購置及維修成本過高，透過共乘的方式通勤，除了能減少在交通工具上的支出，也幫助城市減緩交通壅塞及降低空氣汙染。
基於上述研究背景，本研究建立了共乘機制的車輛指派模型，並在真實路網中進行數值實驗，比較五種不同因素對模型的影響。基於實驗結果的數據，本研究通過迴歸分析來預測低規模需求和供給下的服務效能與效率，並應用上述迴歸模型，建構共享自動駕駛汽車在 AMoD 系統下的乘車市場之供需模型。該模型使用動態定價策略和共乘機制，其中模型以社會福利最大化為目標，並以近似動態規劃求解每個決策階段的最佳費率。實驗結果發現，共乘模式下能提升乘車服務率，此外，本研究所建構乘車市場供需模型之結果顯示，在共乘機制下，動態費率透過平衡市場上的供需，獲得比固定費率還高的社會福利，也降低乘客的平均等待時間。

Shared transportation is a vital branch of sharing economy, which can lighten the air pollution problem and promote the development of a smart city. Artificial intelligence, V2X communication technologies, and 5G technology have become more and more mature, and using autonomous vehicles to provide pick-up and drop-off services on the road is just around the corner. Autonomous Mobility-on Demand (AMoD) combines self-driving and Mobility-on-Demand (MoD) services, allowing passengers to enjoy the last mile service. AMoD can solve the spatial-temporal uncertainty of ride demands and autonomously balances the supply and demand over time, which implements the concept of shared autonomous vehicle (SAV) service.
Studies point out that the implementation of dynamic pricing is an effective way for ride-hailing platforms to balance supply and demand. On the one hand, it can increase the incentives for drivers to enter the market; on the other hand, it can reduce the demand for rides from price-sensitive passengers. In European and American countries, some people consider that the cost of purchasing and maintaining private cars is too high so they take ridesharing services, which can not only reduce the expenditure on transportation but also help cities decrease traffic congestion and reduce air pollution.
Based on the research background, this research builds a ridesharing and dispatching model and conducts numerical experiments on the real road network to compare the effects of five different factors on the model. Based on the simulation data, this study performs linear regression to predict the average waiting time and meeting rate under small-scale demand and supply. Then, applying the above regression model, this study constructs a supply and demand model in the ridesourcing market with the application of SAV in AMoD systems, which considers dynamic pricing strategy and ridesharing. This model aims at maximizing social welfare and uses approximate dynamic programming to solve the optimal pricing for each stage. The experimental results reveal that ridesharing can improve the service rate of rides. Additionally, the demand and supply model results in the ridesharing market show that the dynamic pricing strategy achieves higher social welfare by balancing the supply and demand compared to fixed pricing under the ridesharing mechanism. It also reduces the average waiting time of passengers.

ABSTRACT i
摘要 iii
誌謝 iv
TABLE OF CONTENTS v
LIST OF TABLES viii
LIST OF FIGURES ix
CHAPTER 1 INTRODUCTION 1
1.1 Research Background and Motivation 1
1.2 Research Objectives 4
1.3 Research Flow Chart 4
CHAPTER 2 LITERATURE REVIEW 7
2.1 The Era of Autonomous Vehicles 7
2.1.1 Features of AMoD 7
2.1.2 Shared Autonomous Vehicle 9
2.2 Ridesourcing System 11
2.2.1 Demand-Supply Equilibrium 11
2.2.2 Dynamic Pricing 13
2.3 Vehicle Routing Problem 15
2.3.1 Categories of Vehicle Routing Problem 15
2.3.2 Solution Methods for Dynamic Vehicle Routing Problems (D-VRP) 17
2.3.3 Ridesharing Service 19
2.4 Approximate Dynamic Programming 20
2.5 Summary 21
CHAPTER 3 RESEARCH METHODOLOGY 23
3.1 Problem Statement and Research Assumptions 23
3.2 Research Framework 25
3.3 Ridesharing and Dispatching Model 28
3.3.1 Definition of Variables and Parameters 29
3.3.2 Mathematical Model 31
3.4 Approximate Dynamic Programming 35
3.4.1 Definition of the Variables and Parameters 36
3.4.2 Demand and Supply Function 40
3.4.3 Optimization Problem Formulation 42
3.4.4 State 44
3.4.5 Action 45
3.4.6 Exogenous Information 46
3.4.7 Bellman’s Optimality Equation 46
3.4.8 Value Function Approximation Updating Rule 47
3.4.9 Solution Algorithm 48
3.5 Regression Analysis 52
3.5.1 Linear Regression 52
3.5.2 Transformation 53
3.5.3 The Meeting Rate, Waiting Time, and Idle Time Model 54
3.6 Summary 55
CHAPTER 4 EXPERIMENTS ON RIDESHARING AND DISPATCHING MODELS 56
4.1 Experiment Setup 56
4.1.1 Test Network 56
4.1.2 Experimental Design 57
4.1.3 Code for Ridesharing and Dispatching Model 58
4.2 Results Analysis 60
4.2.1 Ridesharing / Non-ridesharing 60
4.2.2 Maximum Acceptable Waiting Time 62
4.2.3 Update Time Interval 63
4.2.4 Demand Levels 64
4.2.5 Fleet Sizes 66
4.3 Summary 68
CHAPTER 5 EXPERIMENTS OF DYNAMIC PRICING 69
5.1 Regression Analysis 69
5.1.1 Input Data of Regression Model 70
5.1.2 Results of Regression Analysis 71
5.2 Experiment of ADP 75
5.2.1 Data Processing 75
5.2.2 Input Data 75
5.2.3 Parameter Setting 78
5.2.4 Code of ADP algorithm 79
5.2.5 Results Analysis 81
5.3 Summary 84
CHAPTER 6 CONCLUSIONS AND SUGGESTIONS 85
6.1 Conclusions 85
6.2 Suggestions 86
REFERENCES 87

Agatz, N., Erera, A., Savelsbergh, M., & Wang, X. (2012). Optimization for dynamic ride-sharing: A review. European Journal of Operational Research, 223(2), 295–303. https://doi.org/10.1016/j.ejor.2012.05.028

Aghazadeh, D., & Ertogral, K. (2022). An Improved Approximate Dynamic Programming Method for The Integrated Fleet Sizing and Replenishment Planning Problem with Predetermined Delivery Frequencies. IFAC-PapersOnLine, 55(10), 3034–3039. https://doi.org/10.1016/j.ifacol.2022.10.194

Alonso-Mora, J., Samaranayake, S., Wallar, A., Frazzoli, E., & Rus, D. (2017). On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proceedings of the National Academy of Sciences, 114(3), 462–467. https://doi.org/10.1073/pnas.1611675114

An, S., Nam, D., & Jayakrishnan, R. (2019). Impacts of integrating shared autonomous vehicles into a Peer-to-Peer ridesharing system. Procedia Computer Science, 151, 511–518. https://doi.org/10.1016/j.procs.2019.04.069

Bent, R., & van Hentenryck, P. (2004). The Value of Consensus in Online Stochastic Scheduling. In Proceedings of the 14th International Conference on Automated Planning and Scheduling, ICAPS 2004.

Bent, R. W., & van Hentenryck, P. (2004). Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers. Operations Research, 52(6), 977–987. https://doi.org/10.1287/opre.1040.0124

Benyahia, I., & Potvin, J.-Y. (1998). Decision support for vehicle dispatching using genetic programming. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 28(3), 306–314. https://doi.org/10.1109/3468.668962

Bösch, P. M., Becker, F., Becker, H., & Axhausen, K. W. (2018). Cost-based analysis of autonomous mobility services. Transport Policy, 64, 76–91. https://doi.org/10.1016/J.TRANPOL.2017.09.005

Buchholz, N., Doval, L., Kastl, J., Matějka, F., & Salz, T. (2020). The Value of Time: Evidence from Auctioned Cab Rides. https://doi.org/10.3386/w27087

Cachon, G. P., Daniels, K. M., & Lobel, R. (2017). The Role of Surge Pricing on a Service Platform with Self-Scheduling Capacity. Manufacturing & Service Operations Management, 19(3), 368–384. https://doi.org/10.1287/msom.2017.0618

Chen, L., Mislove, A., & Wilson, C. (2015). Peeking Beneath the Hood of Uber. Proceedings of the 2015 Internet Measurement Conference, 495–508. https://doi.org/10.1145/2815675.2815681

Chen, X, Zheng, H., Ke, J., & Yang, H. (2020). Dynamic optimization strategies for on-demand ride services platform: Surge pricing, commission rate, and incentives. Transportation Research Part B: Methodological, 138, 23–45. https://doi.org/https://doi.org/10.1016/j.trb.2020.05.005

Chen, Z.-L., & Xu, H. (2006). Dynamic Column Generation for Dynamic Vehicle Routing with Time Windows. Transportation Science, 40(1), 74–88. https://doi.org/10.1287/trsc.1050.0133

Cohen, P., Hahn, R., Hall, J., Levitt, S., & Metcalfe, R. (2016). Using Big Data to Estimate Consumer Surplus: The Case of Uber. https://doi.org/10.3386/w22627

Coşgun, Ö., Ekinci, Y., & Yanık, S. (2014). Fuzzy rule-based demand forecasting for dynamic pricing of a maritime company. Knowledge-Based Systems, 70, 88–96. https://doi.org/10.1016/j.knosys.2014.04.015

Ferrero, F., Perboli, G., Rosano, M., & Vesco, A. (2018). Car-sharing services: An annotated review. Sustainable Cities and Society, 37, 501–518. https://doi.org/10.1016/j.scs.2017.09.020

Gendreau, M., Guertin, F., Potvin, J.-Y., & Taillard, É. (1999). Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching. Transportation Science, 33(4), 381–390. https://doi.org/10.1287/trsc.33.4.381

George A. F. Seber, & C. J. Wild. (2003). Nonlinear_Regression. Wiley.
Hillier, F. S., & Lieberman, G. J. (2001). Introduction to operations research. McGraw hill Companies, Inc.

Hvattum, L. M., Løkketangen, A., & Laporte, G. (2006). Solving a Dynamic and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic. Transportation Science, 40(4), 421–438. https://doi.org/10.1287/trsc.1060.0166

Hyland, M. F., & Mahmassani, H. S. (2017). Taxonomy of Shared Autonomous Vehicle Fleet Management Problems to Inform Future Transportation Mobility. Transportation Research Record: Journal of the Transportation Research Board, 2653(1), 26–34. https://doi.org/10.3141/2653-04

Hyland, M., & Mahmassani, H. S. (2018). Dynamic autonomous vehicle fleet operations: Optimization-based strategies to assign AVs to immediate traveler demand requests. Transportation Research Part C: Emerging Technologies, 92, 278–297. https://doi.org/10.1016/j.trc.2018.05.003

Katzev, R. (2003). Car Sharing: A New Approach to Urban Transportation Problems. Analyses of Social Issues and Public Policy, 3(1), 65–86. https://doi.org/10.1111/j.1530-2415.2003.00015.x

Kim, S., Chang, J. J. E., Park, H. H., Song, S. U., Cha, C. B., Kim, J. W., & Kang, N. (2020). Autonomous Taxi Service Design and User Experience. International Journal of Human–Computer Interaction, 36(5), 429–448. https://doi.org/10.1080/10447318.2019.1653556

Lam, S.-W., Lee, L.-H., & Tang, L.-C. (2007). An approximate dynamic programming approach for the empty container allocation problem. Transportation Research Part C: Emerging Technologies, 15(4), 265–277. https://doi.org/10.1016/j.trc.2007.04.005

Lau, S. T., & Susilawati, S. (2021). Shared autonomous vehicles implementation for the first and last-mile services. Transportation Research Interdisciplinary Perspectives, 11, 100440. https://doi.org/10.1016/j.trip.2021.100440

Lee, S., & Boomsma, T. K. (2022). An approximate dynamic programming algorithm for short-term electric vehicle fleet operation under uncertainty. Applied Energy, 325, 119793. https://doi.org/10.1016/j.apenergy.2022.119793

Lei, C., & Ouyang, Y. (2017). Dynamic pricing and reservation for intelligent urban parking management. Transportation Research Part C: Emerging Technologies, 77, 226–244. https://doi.org/10.1016/j.trc.2017.01.016

Manski, C. F., & Wright, J. D. (1967). Nature of equilibrium in the market for taxi services.

MAYOR OF LONDON LONDONASSEMBLY. (2022, January 11). Cost of congestion in capital revealed as car use remains high. https://www.london.gov.uk/press-releases/mayoral/cost-of-congestion-in-capital-revealed

Montemanni, R., Gambardella, L. M., Rizzoli, A. E., & Donati, A. v. (2005). Ant Colony System for a Dynamic Vehicle Routing Problem. Journal of Combinatorial Optimization, 10(4), 327–343. https://doi.org/10.1007/s10878-005-4922-6

Narayanan, S., Chaniotakis, E., & Antoniou, C. (2020). Shared autonomous vehicle services: A comprehensive review. Transportation Research Part C: Emerging Technologies, 111, 255–293. https://doi.org/10.1016/j.trc.2019.12.008

Novoa, C., & Storer, R. (2009). An approximate dynamic programming approach for the vehicle routing problem with stochastic demands. European Journal of Operational Research, 196(2), 509–515. https://doi.org/10.1016/j.ejor.2008.03.023

Pavone, M. (2016). Autonomous Mobility-on-Demand Systems for Future Urban Mobility. In Autonomous Driving (pp. 387–404). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-662-48847-8_19

Peren, F. W. (2021). Statistics for Business and Economics. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-662-64276-4

Pillac, V., Gendreau, M., Guéret, C., & Medaglia, A. L. (2013). A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1), 1–11. https://doi.org/10.1016/j.ejor.2012.08.015

Powell, W. B. (2011). Approximate Dynamic Programming: Solving the curses of dimensionality (Vol. 703). John Wiley & Sons.

Qian, X., & Ukkusuri, S. v. (2017). Taxi market equilibrium with third-party hailing service. Transportation Research Part B: Methodological, 100, 43–63. https://doi.org/10.1016/j.trb.2017.01.012

Qu, B., Mao, L., Xu, Z., Feng, J., & Wang, X. (2022). How Many Vehicles Do We Need? Fleet Sizing for Shared Autonomous Vehicles With Ridesharing. IEEE Transactions on Intelligent Transportation Systems, 23(9), 14594–14607. https://doi.org/10.1109/TITS.2021.3130749

Rayle, L., Dai, D., Chan, N., Cervero, R., & Shaheen, S. (2016). Just a better taxi? A survey-based comparison of taxis, transit, and ridesourcing services in San Francisco. Transport Policy, 45, 168–178. https://doi.org/10.1016/J.TRANPOL.2015.10.004

Saharan, S., Bawa, S., & Kumar, N. (2020). Dynamic pricing techniques for Intelligent Transportation System in smart cities: A systematic review. Computer Communications, 150, 603–625. https://doi.org/10.1016/j.comcom.2019.12.003

Sayarshad, H. R., & Oliver Gao, H. (2018). A scalable non-myopic dynamic dial-a-ride and pricing problem for competitive on-demand mobility systems. Transportation Research Part C: Emerging Technologies, 91, 192–208. https://doi.org/10.1016/j.trc.2018.04.007

Scott Corwin, Joe Vitale, Eamonn Kelly, & Elizabeth Cathles. (2015). The future of mobility: What’s next?

Shen, W., & Lopes, C. v. (2015). Managing Autonomous Mobility on Demand Systems for Better Passenger Experience. PRIMA.

Simão, H. P., Day, J., George, A. P., Gifford, T., Nienow, J., & Powell, W. B. (2009). An Approximate Dynamic Programming Algorithm for Large-Scale Fleet Management: A Case Application. Transportation Science, 43(2), 178–197. https://doi.org/10.1287/trsc.1080.0238

Spivey, M. Z., & Powell, W. B. (2004). The Dynamic Assignment Problem. Transportation Science, 38(4), 399–419. https://doi.org/10.1287/trsc.1030.0073

Susan Shaheen, P., & Nelson Chan. (2015). Mobility and the Sharing Economy: Impacts Synopsis – Spring 2015.
The New York City Taxi and Limousine Commission. (2022). Taxi and Ridehailing Usage in New York City. The New York City Taxi and Limousine Commission.

Thomas, B. W. (2007). Waiting Strategies for Anticipating Service Requests from Known Customer Locations. Transportation Science, 41(3), 319–331. https://doi.org/10.1287/trsc.1060.0183

Thomas, M., & Deepti, T. (2018). Reinventing carsharing as a modern and profitable service. The Intelligent Transportation Society of America, Annual Meeting White Paper.

Ulusan, A., & Ergun, Ö. (2021). Approximate dynamic programming for network recovery problems with stochastic demand. Transportation Research Part E: Logistics and Transportation Review, 151, 102358. https://doi.org/10.1016/j.tre.2021.102358

Wang, H., & Yang, H. (2019). Ridesourcing systems: A framework and review. Transportation Research Part B: Methodological, 129, 122–155. https://doi.org/10.1016/j.trb.2019.07.009

Wang, X., He, F., Yang, H., & Oliver Gao, H. (2016). Pricing strategies for a taxi-hailing platform. Transportation Research Part E: Logistics and Transportation Review, 93, 212–231. https://doi.org/10.1016/j.tre.2016.05.011

Wen, J., Nassir, N., & Zhao, J. (2019). Value of demand information in autonomous mobility-on-demand systems. Transportation Research Part A: Policy and Practice, 121, 346–359. https://doi.org/10.1016/j.tra.2019.01.018

Yang, H., Wong, S. C., & Wong, K. I. (2002). Demand–supply equilibrium of taxi services in a network under competition and regulation. Transportation Research Part B: Methodological, 36(9), 799–819. https://doi.org/10.1016/S0191-2615(01)00031-5

Yang, J., Jaillet, P., & Mahmassani, H. (2004). Real-Time Multivehicle Truckload Pickup and Delivery Problems. Transportation Science, 38(2), 135–148. https://doi.org/10.1287/trsc.1030.0068

Yin, J., Tang, T., Yang, L., Gao, Z., & Ran, B. (2016). Energy-efficient metro train rescheduling with uncertain time-variant passenger demands: An approximate dynamic programming approach. Transportation Research Part B: Methodological, 91, 178–210. https://doi.org/10.1016/j.trb.2016.05.009

Zardini, G., Lanzetti, N., Pavone, M., & Frazzoli, E. (2022). Analysis and Control of Autonomous Mobility-on-Demand Systems. Annual Review of Control, Robotics, and Autonomous Systems, 5(1), 633–658. https://doi.org/10.1146/annurev-control-042920-012811

Zhang, R., Rossi, F., & Pavone, M. (2016). Model predictive control of autonomous mobility-on-demand systems. 2016 IEEE International Conference on Robotics and Automation (ICRA), 1382–1389. https://doi.org/10.1109/ICRA.2016.7487272

Zhang, R., Spieser, K., Frazzoli, E., & Pavone, M. (2015). Models, algorithms, and evaluation for autonomous mobility-on-demand systems. 2015 American Control Conference (ACC), 2573–2587. https://doi.org/10.1109/ACC.2015.7171122