臺灣博碩士論文加值系統

People and goods are transported independently in city logistics. New approaches to city logistics are needed to ensure efficient urban mobility for both people and goods. To solve this issue, the share-a-ride problem was developed, in which the same taxi network managed both people and goods in a coordinated way. This system can reduce pollution and urban congestion from a city perspective. The parcel delivery service offers new advantages from the perspective of a taxi company. This research introduces the share-a-ride problem with transfers (SARP-T), which is an extension of the share-a-ride problem (SARP) that allows passengers and parcels to transfer from one taxi to another at the transfer nodes. The goal of the share-a-ride problem with transfers (SARP-T) is to maximize the profit from serving parcel and passenger requests with taxis that depart from a depot. We developed a mixed integer linear program for SARP-T and proposed the simulated annealing with mutation strategy (SAMS) algorithm to solve the problem. Computational findings indicate that for small SARP-T benchmark instances, both the commercial solver CPLEX and our proposed SAMS algorithm attain optimal solutions. Furthermore, for large SARP-T benchmark instances, comparison results demonstrate that the proposed SAMS algorithm achieves better solution values than the basic SA heuristic. Our analysis also shows that SARP-T solutions are better than the share-a-ride problem (SARP), the general share-a-ride problem (G-SARP), and the share-a-ride problem with flexible compartments (SARPFC) solutions.

TABLE OF CONTENTS
ABSTRACT ii
ACKNOWLEDGMENT iii
TABLE OF CONTENTS iv
LIST OF TABLES vii
LIST OF FIGURES viii
CHAPTER 1 1
INTRODUCTION 1
1.1. Background 1
1.2. Research objective and contribution 2
1.3. Scope and limitations 3
1.4. Research procedures 3
1.5. Organization of thesis 4
CHAPTER 2 6
LITERATURE REVIEW 6
2.1. The Dial-a-Ride Problem 6
2.2. The Share-a-Ride Problem 8
2.3. Transfers of requests 10
2.4. Benefits of transfers 12
CHAPTER 3 15
MODEL DEVELOPMENT 15
3.1. Problem Definition 15
3.2. Model development 16
CHAPTER 4 21
SOLUTION METHODOLOGY 21
4.1. Simulated Annealing Heuristic 21
4.2. Solution representation 22
4.3. The initial solution 25
4.4. Neighborhood moves 27
4.4.1. Swap move 27
4.4.2. Insertion move 27
4.4.3. Reverse move 28
4.4.4. Mutation move 28
4.5. Time slack strategy and penalty mechanism 28
4.5.1. Penalty mechanism 28
4.5.2. Time slack strategy 29
4.6. The general outline of SAMS 30
CHAPTER 5 33
COMPUTATIONAL RESULTS 33
5.1. Description of the benchmark instances 33
5.1.1. Generating small instances 33
5.1.2. Generating large instances 33
5.2. Parameter setting 34
5.3. Performance of SAMS algorithm for solving SARP-T benchmark instances 37
5.3.1. Comparison of CPLEX, basic SA and the proposed SAMS algorithm on small instances …………………………………………………………………………………..38
5.3.2. Comparison of the basic SA and the proposed SAMS for large SARP-T instances…………. 38
5.3.3. Comparison of SARP-T model with SARP, G-SARP and SARPFC models 40
CHAPTER 6 46
CONCLUSION AND FUTURE RESEARCH 46
6.1. Conclusion 46
6.2. Future Research 46
REFERENCES 48

Bongiovanni, C., Kaspi, M., & Geroliminis, N. (2019). The electric autonomous dial-a-ride problem. Transportation Research Part B: Methodological, 122, 436-456. https://doi.org/10.1016/j.trb.2019.03.004
Braekers, K., Caris, A., & Janssens, G. K. (2014). Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots. Transportation Research Part B: Methodological, 67, 166-186. https://doi.org/10.1016/j.trb.2014.05.007
Cavagnini, R., & Morandi, V. (2021). Implementing Horizontal Cooperation in Public Transport and Parcel Deliveries: The Cooperative Share-A-Ride Problem. Sustainability, 13(8). https://doi.org/10.3390/su13084362
Cordeau, J.-F., & Laporte, G. (2003a). The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 1(2). https://doi.org/10.1007/s10288-002-0009-8
Cordeau, J.-F., & Laporte, G. (2003b). A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B: Methodological, 37(6), 579-594. https://doi.org/10.1016/s0191-2615(02)00045-0
Cordeau, J.-F., & Laporte, G. (2007). The dial-a-ride problem: models and algorithms. Annals of Operations Research, 153(1), 29-46. https://doi.org/10.1007/s10479-007-0170-8
Detti, P., Papalini, F., & Lara, G. Z. M. d. (2017). A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare. Omega, 70, 1-14. https://doi.org/10.1016/j.omega.2016.08.008
Fu, Z., & Chow, J. Y. J. (2022). The pickup and delivery problem with synchronized en-route transfers for microtransit planning. Transportation Research Part E: Logistics and Transportation Review, 157. https://doi.org/10.1016/j.tre.2021.102562
Ho, S. C., Szeto, W. Y., Kuo, Y.-H., Leung, J. M. Y., Petering, M., & Tou, T. W. H. (2018). A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B: Methodological, 111, 395-421. https://doi.org/10.1016/j.trb.2018.02.001
Hosni, H., Naoum-Sawaya, J., & Artail, H. (2014). The shared-taxi problem: Formulation and solution methods. Transportation Research Part B: Methodological, 70, 303-318. https://doi.org/10.1016/j.trb.2014.09.011
Kirkpatrick, S., Gelatt, C. D., Jr., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680. https://doi.org/10.1126/science.220.4598.671
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. https://doi.org/10.1016/j.ejor.2014.03.003
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. https://doi.org/10.1016/j.cor.2015.08.008
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. https://doi.org/http://dx.doi.org/10.1016/j.trc.2016.01.014
Maalouf, M., MacKenzie, C. A., Radakrishnan, S., & Court, M. (2014). A new fuzzy logic approach to capacitated dynamic Dial-a-Ride problem. Fuzzy Sets and Systems, 255, 30-40. https://doi.org/10.1016/j.fss.2014.03.010
Masmoudi, M. A., Hosny, M., Braekers, K., & Dammak, A. (2016). Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem. Transportation Research Part E: Logistics and Transportation Review, 96, 60-80. https://doi.org/10.1016/j.tre.2016.10.002
Masson, R., Lehuédé, F., & Péton, O. (2014). The Dial-A-Ride Problem with Transfers. Computers & Operations Research, 41, 12-23. https://doi.org/10.1016/j.cor.2013.07.020
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21(6), 1087-1092. https://doi.org/10.1063/1.1699114
Paquette, J., Cordeau, J.-F., Laporte, G., & Pascoal, M. M. B. (2013). Combining multicriteria analysis and tabu search for dial-a-ride problems. Transportation Research Part B: Methodological, 52, 1-16. https://doi.org/10.1016/j.trb.2013.02.007
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. https://doi.org/10.1016/j.cor.2009.10.003
Peng, Z., Al Chami, Z., Manier, H., & Manier, M.-A. (2019). A hybrid particle swarm optimization for the selective pickup and delivery problem with transfers. Engineering Applications of Artificial Intelligence, 85, 99-111. https://doi.org/10.1016/j.engappai.2019.06.006
Rais, A., Alvelos, F., & Carvalho, M. S. (2014). New mixed integer-programming model for the pickup-and-delivery problem with transshipment. European Journal of Operational Research, 235(3), 530-539. https://doi.org/10.1016/j.ejor.2013.10.038
Santos, D. O., & Xavier, E. C. (2015). Taxi and Ride Sharing: A Dynamic Dial-a-Ride Problem with Money as an Incentive. Expert Systems with Applications, 42(19), 6728-6737. https://doi.org/10.1016/j.eswa.2015.04.060
Vallee, S., Oulamara, A., & Cherif-Khettaf, W. R. (2020). New online reinsertion approaches for a dynamic Dial-a-Ride Problem. Journal of Computational Science, 47. https://doi.org/10.1016/j.jocs.2020.101199
Wolfinger, D., & Salazar-González, J.-J. (2021). The Pickup and Delivery Problem with Split Loads and Transshipments: A Branch-and-Cut Solution Approach. European Journal of Operational Research, 289(2), 470-484. https://doi.org/10.1016/j.ejor.2020.07.032
Yu, V. F., Indrakarna, P. A. Y., Redi, A. A. N. P., & Lin, S.-W. (2021). Simulated Annealing with Mutation Strategy for the Share-a-Ride Problem with Flexible Compartments. Mathematics, 9(18). https://doi.org/10.3390/math9182320
Yu, V. F., Jewpanya, P., & Redi, A. A. N. P. (2016). Open vehicle routing problem with cross-docking. Computers & Industrial Engineering, 94, 6-17. https://doi.org/10.1016/j.cie.2016.01.018
Yu, V. F., Jodiawan, P., Ho, Y.-H., & Lin, S.-W. (2019). Location-Routing Problem With Demand Range. IEEE Access, 7, 149142-149155. https://doi.org/10.1109/access.2019.2946219
Yu, V. F., & Lin, S.-W. (2014). Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery. Applied Soft Computing, 24, 284-290. https://doi.org/10.1016/j.asoc.2014.06.024
Yu, V. F., & Lin, S.-Y. (2015a). A simulated annealing heuristic for the open location-routing problem. Computers & Operations Research, 62, 184-196. https://doi.org/10.1016/j.cor.2014.10.009
Yu, V. F., & Lin, S.-Y. (2015b). Solving the location-routing problem with simultaneous pickup and delivery by simulated annealing. International Journal of Production Research, 54(2), 526-549. https://doi.org/10.1080/00207543.2015.1085655
Yu, V. F., Marye Zegeye, M., Geremew Gebeyehu, S., Indrakarna, P. A. Y., & Jodiawan, P. (2023a). A matheuristic algorithm for the share-a-ride problem. Expert Systems with Applications. https://doi.org/10.1016/j.eswa.2023.120569
Yu, V. F., Marye Zegeye, M., Geremew Gebeyehu, S., Indrakarna, P. A. Y., & Jodiawan, P. (2023b). The multi-depot general share-a-ride problem. Expert Systems with Applications, 213. https://doi.org/10.1016/j.eswa.2022.119044
Yu, V. F., Purwanti, S. S., Redi, A. A. N. 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. https://doi.org/10.1080/0305215x.2018.1437153
Yu, V. F., Redi, A. A. N. P., Hidayat, Y. A., & Wibowo, O. J. (2017). A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing, 53, 119-132. https://doi.org/10.1016/j.asoc.2016.12.027
Zidi, I., Mesghouni, K., Zidi, K., & Ghedira, K. (2012). A multi-objective simulated annealing for the multi-criteria dial a ride problem. Engineering Applications of Artificial Intelligence, 25(6), 1121-1131. https://doi.org/10.3182/20100831-4-fr-2021.00047