研究生: |
Putu Agus Yudisuda Indrakarna Putu Agus Yudisuda Indrakarna |
---|---|
論文名稱: |
Share-a-Ride Problem with Adjustable Compartment Share-a-Ride Problem with Adjustable Compartment |
指導教授: |
喻奉天
Vincent F. Yu |
口試委員: |
郭伯勳
Po-Hsun Kuo Chun-Cheng Lin Chun-Cheng Lin |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2019 |
畢業學年度: | 107 |
語文別: | 英文 |
論文頁數: | 44 |
中文關鍵詞: | Share-a-Ride Problem with Adjustable Compartment 、Share-a-Ride Problem 、Adjustable compartment 、Simulated annealing 、Slack time |
外文關鍵詞: | Share-a-Ride Problem with Adjustable Compartment, Share-a-Ride Problem, Adjustable compartment, Simulated annealing, Slack time |
相關次數: | 點閱:363 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
The Share-a-Ride Problem with Adjustable Compartment (SARPAC) is a study conducted with an aim to reduce traffic congestion and taxi wasted space when servicing a passenger. It is an extension of the Share-a-ride Problem (SARP) where both passenger and freight transport is handled by a single taxi network. SARPAC allows a taxi to adjust its compartment size within its lower and upper bounds while maintaining the same total capacity, allowing it to service more packages while also service one passenger at the same time. This will allow taxies to fully utilize their space to maximize profit. We propose a Simulated Annealing (SA) algorithm to solve SARPAC. Furthermore, we study the effect of delaying slack time mechanism on our algorithm’s computational time and solution quality by activating mutation neighbourhood at a later stage of temperature reduction. The performance of our algorithm is benchmarked against CPLEX for small instances and the SARP instances for large instances. The objective function of SARPAC is to maximize total profit obtained from serving passenger and parcel requests simultaneously. The proposed algorithm obtains optimal solutions for small instances with reasonable computational time. When compared to SARP result on large instances, SARPAC model obtains an average of 61.80% more profit.
The Share-a-Ride Problem with Adjustable Compartment (SARPAC) is a study conducted with an aim to reduce traffic congestion and taxi wasted space when servicing a passenger. It is an extension of the Share-a-ride Problem (SARP) where both passenger and freight transport is handled by a single taxi network. SARPAC allows a taxi to adjust its compartment size within its lower and upper bounds while maintaining the same total capacity, allowing it to service more packages while also service one passenger at the same time. This will allow taxies to fully utilize their space to maximize profit. We propose a Simulated Annealing (SA) algorithm to solve SARPAC. Furthermore, we study the effect of delaying slack time mechanism on our algorithm’s computational time and solution quality by activating mutation neighbourhood at a later stage of temperature reduction. The performance of our algorithm is benchmarked against CPLEX for small instances and the SARP instances for large instances. The objective function of SARPAC is to maximize total profit obtained from serving passenger and parcel requests simultaneously. The proposed algorithm obtains optimal solutions for small instances with reasonable computational time. When compared to SARP result on large instances, SARPAC model obtains an average of 61.80% more profit.
Chen, W., Mes, M., Schutten, M., & Quint, J. (2019). A ride-sharing problem with meeting points and return restrictions. Transportation science.
Cordeau, J.-F., & Laporte, G. (2003). A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B: Methodological, 37(6), 579-594.
Cordeau, J.-F., & Laporte, G. (2007). The dial-a-ride problem: models and algorithms. Annals of operations research, 153(1), 29-46.
El Fallahi, A., Prins, C., & Calvo, R. W. (2008). A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Computers & Operations Research, 35(5), 1725-1741.
Furuhata, M., Dessouky, M., Ordóñez, F., Brunet, M.-E., Wang, X., & Koenig, S. (2013). Ridesharing: The state-of-the-art and future directions. Transportation Research Part B: Methodological, 57, 28-46.
Henke, T., Speranza, M. G., & Wäscher, G. (2015). The multi-compartment vehicle routing problem with flexible compartment sizes. European Journal of Operational Research, 246(3), 730-743.
Jaw, J.-J., Odoni, A. R., Psaraftis, H. N., & Wilson, N. H. (1986). A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transportation Research Part B: Methodological, 20(3), 243-257.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
Li, B., Krushinsky, D., Reijers, H. A., & Van Woensel, T. (2014). The share-a-ride problem: People and parcels sharing taxis. European Journal of Operational Research, 238(1), 31-40.
Li, B., Krushinsky, D., Van Woensel, T., & Reijers, H. A. (2016a). An adaptive large neighborhood search heuristic for the share-a-ride problem. Computers & Operations Research, 66, 170-180.
Li, B., Krushinsky, D., Van Woensel, T., & Reijers, H. A. (2016b). The Share-a-Ride problem with stochastic travel times and stochastic delivery locations. Transportation Research Part C: Emerging Technologies, 67, 95-108.
44
Lokhandwala, M., & Cai, H. (2018). Dynamic ride sharing using traditional taxis and shared autonomous taxis: A case study of NYC. Transportation Research Part C: Emerging Technologies, 97, 45-60.
Masmoudi, M. A., Hosny, M., Demir, E., Genikomsakis, K. N., & Cheikhrouhou, N. (2018). The dial-a-ride problem with electric vehicles and battery swapping stations. Transportation Research Part E: Logistics and Transportation Review, 118, 392-420.
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2010). Variable neighborhood search for the dial-a-ride problem. Computers & Operations Research, 37(6), 1129-1138.
Psaraftis, H. 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.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
Stiglic, M., Agatz, N., Savelsbergh, M., & Gradisar, M. (2018). Enhancing urban mobility: Integrating ride-sharing and public transit. Computers & Operations Research, 90, 12-21.
Tellez, O., Vercraene, S., Lehuédé, F., Péton, O., & Monteiro, T. (2018). The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity. Transportation Research Part C: Emerging Technologies, 91, 99-123.
Yu, V. F., Redi, A. P., Hidayat, Y. A., & Wibowo, O. J. (2017). A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing, 53, 119-132.
Yu, V. F., Purwanti, S. S., Redi, A. P., Lu, C.-C., Suprayogi, S., & Jewpanya, P. (2018). Simulated annealing heuristic for the general share-a-ride problem. Engineering Optimization, 50(7), 1178-1197.