臺灣博碩士論文加值系統

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.

ABSTRACT ................................................................................................................................... ii
ACKNOWLEDGMENT ............................................................................................................. iii
TABLE OF CONTENTS ............................................................................................................ iv
LIST OF FIGURES ..................................................................................................................... vi
LIST OF TABLES ...................................................................................................................... vii
CHAPTER 1 INTRODUCTION ................................................................................................ 1
1.1 Background ...................................................................................................................... 1
1.2 Research Purpose ............................................................................................................. 4
1.3 Research Limitations ........................................................................................................ 4
1.4 Organization of Thesis ..................................................................................................... 5
CHAPTER 2 LITERATURE REVIEW ..................................................................................... 7
2.1 Dial-a-Ride Problem ........................................................................................................ 7
2.2 Share-a-Ride Problem ...................................................................................................... 8
2.3 Multi-compartment and Flexible Compartment Size VRP ............................................ 10
CHAPTER 3 MODEL DEVELOPMENT............................................................................... 12
3.1 Problem Definition ......................................................................................................... 12
3.2 Mathematical Model ...................................................................................................... 13
CHAPTER 4 SOLUTION METHODOLOGY ........................................................................ 19
4.1 Solution Representation ................................................................................................. 19
4.2 Initial Solution ................................................................................................................ 20
4.3 Neighborhood Search Mechanism ................................................................................. 20
4.4 Time Slack Strategy ....................................................................................................... 22
4.5 Simulated Annealing Algorithm .................................................................................... 24
CHAPTER 5 COMPUTATIONAL STUDY ............................................................................ 27
5.1 Benchmark Instances...................................................................................................... 27
5.2 Parameter Settings .......................................................................................................... 28
5.3 Algorithm Verification ................................................................................................... 35
5.4 Comparison Between SARP and SARPAC ................................................................... 38
CHAPTER 6 CONCLUSION AND FUTURE RESEARCH ................................................ 41
6.1 Conclusion ...................................................................................................................... 41
6.2 Future Research .............................................................................................................. 42
REFERENCES ............................................................................................................................ 43

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.