機械学習と最適化技術の統合による需要不確実性下でのshared e-scooterの短期オペレーション

• Material Type: 博士論文
• Title: 機械学習と最適化技術の統合による需要不確実性下でのshared e-scooterの短期オペレーション
• Author/Editor: Saum, Narith
• Author Heading: Saum, Narith
• Publication, Distribution, etc.: Hokkaido University
• Publication Date: 2023-09-25
• Publication Date (W3CDTF): 2023-09-25
• Alternative Title: Integrating Machine Learning and Optimization Techniques for Short-Term Management of Shared E-Scooters under Demand Uncertainty
• Contributor: 杉浦, 聡志; 萩原, 亨; 内田, 賢悦; 髙橋, 翔
• Degree Grantor: 北海道大学
• Date Granted: 2023-09-25
• Date Granted (W3CDTF): 2023-09-25
• Dissertation Number: 甲第15624号
• Degree Type: 博士(工学)
• Text Language Code: eng
• Subject Heading: Autoregressive Conditional Heteroskedasticity; Deep Learning; Demand Uncertainty; Heuristic Optimization Algorithm; Hybrid Optimization Algorithm; Hyperparameter Optimization; Integer Linear Programming; Machine Learning; Shared Electric Scooters; Shared Service Rebalancing
• NDC: 500
• Target Audience: 一般
• Note (General): (主査) 准教授 杉浦 聡志, 教授 萩原 亨, 教授 内田 賢悦, 准教授 髙橋 翔; 工学院（北方圏環境政策工学専攻）
• DOI: 10.14943/doctoral.k15624; https://doi.org/10.14943/doctoral.k15624
• Persistent ID (NDL): info:ndljp/pid/13122856; https://dl.ndl.go.jp/pid/13122856
• Collection: 障害者向け資料
• Collection (Materials For Handicapped People:1): テキストデータ
• Collection (particular): 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文; https://dl.ndl.go.jp/collections/A00014
• Acquisition Basis: 博士論文（自動収集）
• Date Accepted (W3CDTF): 2023-12-15T22:13:26+09:00
• Format (IMT): application/pdf
• Access Restrictions: 国立国会図書館内限定公開
• Service for the Digitized Contents Transmission Service: 図書館・個人送信対象外
• Availability of remote photoduplication service: 可
• Periodical Title (URI): https://doi.org/10.14943/doctoral.k15624; http://hdl.handle.net/2115/90860
• Is Referenced By (URI): http://hdl.handle.net/2115/90858
• Data Provider (Database): 国立国会図書館 : 国立国会図書館デジタルコレクション; https://dl.ndl.go.jp

• Summary, etc.: Shared mobility has proliferated in global cities as an innovative transportation mode enhancing urban mobility and as a potential solution to address first- and last-mile problems. Recently, a new emerging shared transportation, dockless electric scooters (e-scooters), has gained popularity worldwide for their specific advantages, including environmentally friendly, time and cost-saving mode, congestion, parking constraint, and satisfied riding experience. Besides these advantages, this shared mode has several disadvantages, including volatile demand, excessive or starving stations, short service life, costly maintenance, battery recharging, and distribution regulations. As a new transportation mode, there are limited studies about shared e-scooters, especially related to daily operations. Therefore, this study aims to develop an efficient framework for better managing this dockless shared service by taking advantage of open-source historical ridership data, machine learning, and deep learning methods. This study thus is separated into three main sections as follows. From the literature review, shared e-scooters are mainly used for recreational or tourism activities, which differs from shared bikes. These trip purposes with dockless policy led to high demand volatility while requiring a higher service level. To deal with the heteroscedasticity (i.e., non-constant variation) of the demand, both demand and variance prediction models are developed using deep learning (Recurrent Neural Networks) and Autoregressive Conditional Heteroskedasticity (ARCH), respectively. Moreover, Box Cox transformation was also employed to remove the heteroscedasticity. Based on numerical results from three real-world datasets (Austin TX, Minneapolis MN, and Thammasat TH), machine learning and deep learning achieved higher prediction accuracy than conventional regression models, SARIMAX. Box Cox transformation can improve the prediction accuracy, especially MAE by around 5.36%, while the supply planning with this transformation is very efficient for lower service levels. Nevertheless, the application of this transformation technique in supply planning for higher service levels exhibits decreased efficiency due to its exponential conversion characteristic, thereby revealing a weakness of Box Cox transformation. In this case, the supply planning model with original data and predicted variance by SGARCH achieves lower oversupply. At 95% served demand, accounting for heteroscedasticity in supply planning could reduce the oversupply by 26.22%. Even machine learning and deep learning models can outperform conventional statistical models; their performance strongly depends on the choice of hyperparameters, while optimizing these hyperparameters is usually computationally expensive. To deal with this problem (i.e., Hyperparameter Optimization or HPO), this study proposed a novel algorithm, Iterative Decision Tree (IDT), which employs a Decision Tree regressor based on the Classification and Regression Tree (CART) algorithm as the surrogate function. Our algorithm suggests several new candidates per iteration as random or extreme points from a few bestperformed leaves. This characteristic allows IDT to be trained in parallel, which solves the main disadvantage of previous sequential model-based algorithms (ex., Bayesian Optimization). To evaluate the performance of IDT, it was employed to optimize several benchmark problems, including nonconvex functions and HPO of machine learning and deep learning models. As a result, IDT showed very effective performance for both computational time and objective value compared to benchmark algorithms. Based on the above results, a new framework for short-term rebalancing planning was proposed for the unique characteristic of shared e-scooters, including volatile and heteroscedastic demand, recharging the battery, and faulty e-scooters. Monte Carlo simulation based on the predicted trip gaps and standard deviations was employed to generate the stochastic demand scenarios. The framework was examined based on e-scooter data from Minneapolis MN, while k-means clustering algorithm was employed to aggregate the trip generation and attraction for the total clusters of 15, 30, and 60. For this data-driven stochastic optimization problem, two separated formulations were constructed and solved by the Integer Linear Programming (ILP) and the Hybrid of Ant Colony Optimization with ILP (ACO-ILP). Under limited computational time, ILP solver is efficient for solving small-size problems (15 and 30-cluster problems), but the Hybrid approach is more efficient for large-size problems (60- cluster problems). Based on the numerical result of the most practical case (60-cluster problems), our data-driven framework for rebalancing planning for shared e-scooters could reduce the expected objective value by around 13.27% and 16.68% compared to historical weekly and daily data. In summary, dockless shared e-scooters require proper operational planning to minimize their negative impacts, so that this shared mode can become a potential solution for compacted urban mobility. This objective can be achieved through the proposed data-driven framework, which integrates machine learning and optimization techniques to minimize the demand uncertainty and driving distance for the rebalancing vehicle. For instance, start-of-art prediction models with hyperparameter optimization can effectively handle the volatile demand of shared e-scooters, while rebalancing optimization planning can be addressed through the exact approach (ILP solver) or the heuristic algorithm (ACO-ILP).
• DOI: 10.14943/doctoral.k15624; https://doi.org/10.14943/doctoral.k15624
• Format (IMT): application/pdf
• Source: Narith_Saum.pdf （fulltext）; https://eprints.lib.hokudai.ac.jp/repo/huscap/all/90860/Narith_Saum.pdf
• Access Restrictions: インターネット公開
• Is Referenced By (URI): HDL; https://hdl.handle.net/2115/90858
• Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）; https://irdb.nii.ac.jp
• Original Data Provider (Database): 北海道大学 : 北海道大学学術成果コレクション