運輸效率低下會導致經濟和環境問題，嚴重的交通阻塞會增加資源浪費和污染。為了解決這個問題，共乘問題（SARP）被提出。在SARP中，計程車可以同時服務乘客和包裹。然而，SARP具有某些限制，例如計程車不可同時服務多位乘客，並且不能超過可以插入在乘客上、下車點之間的包裹數量上限。因此，本研究提出了一般化的SARP問題，稱為一般共乘問題（General Share-A-Ride Problem；G-SARP），其允許計程車同時服務多位乘客，且可以在乘客的上、下車點之間服務的包裹數量方面沒有限制。此外，在本研究中還提出了G-SARP的延伸問題，稱為具可調式載具之一般共乘問題（General Share-A-Ride Problem with Adjustable Compartment；G-SARPAC）。在此問題中，乘客和包裹的最大車廂容量可以根據需求進行調整。G-SARP和G-SARPAC的目標是在極大化服務乘客和包裹所獲得的總利潤。在本研究中，我們提出了這兩個問題數學模型，以CPLEX求解小型測試問題，並發展模擬退火法以求解大型測試問題。

Inefficiencies in transportation have resulted in economic and environmental problems. High levels of traffic congestion increase waste of resources and pollution. To address this issue, the Share-A-Ride Problem (SARP) has been introduced. In SARP, a taxi could serve passengers and parcel requests at the same time. However, SARP has certain limitations, such as assuming that a taxi should not serve more than one passenger at the same time and should observe the maximum number of parcel requests that can be inserted between the pickup and drop-off points of a passenger. Therefore, this study introduces a generalized model of SARP, called the General Share-A-Ride Problem (G-SARP), which allows the taxi to serve more than one passenger request at the same time and has no restriction in terms of the number of parcel requests that can be served between the pickup and drop-off points of a passenger. Moreover, this study also develops an extended model of G-SARP, called the general shared a ride problem with adjustable compartment (G-SARPAC). In this model the maximum compartment size both for passengers and parcels can be adjusted based on the demand. The objective of G-SARP and G-SARPAC are to maximize total profit obtained from serving people and parcel requests. In this study, we formulate mathematical models for the two problems, perform a numerical study using CPLEX to solve small benchmark instances and develop simulated annealing algorithms for solving large benchmark instances.

Agatz, N., Erera, A., Savelsbergh, M., & Wang, X. (2012). Optimization for dynamic ride-sharing: A review. European Journal of Operational Research, 295-303.
Akpinar, S. (2016). Hybrid large neighborhood search algorithm for capacitated vehicle routing problem. Expert System with Applications, 61, 28-38.
Barnes, J. W., & Nanry, W. P. (2000). Solving the pickup and delivery problem with time windows using reactive tabu search. Transportation Research Part B: Methodological, 34(2), 107-121.
Cherkesly, M., Desaulniers, G., & Laporte, G. (2015). A population-based metaheuristic for the pickup and delivery problem with time windows and LIFO loading. Computers & Operations Research, 62, 23-25.
Cordeau, J., & Laporte, G. (2007). The dial-a-ride problem: models and algorithms. Annals of Operations Research, 153(1), 29-46.
Coredeau, J. F., & Laporte, G. (2003). A tabu heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B: Methodological, 579-594.
Deng, A.-M., Mao, C., & Zhou, Y.-t. (2009). Optimizing research of an improved simulated annealing algorithm to soft time windows vehicle routing problem with pick-up adn delivery. System Engineering: Theory & Practice, 29, 186-192.
Errico, F., Desaulniers, G., Gendreau, M., Rei, W., & Rosseau, L. M. (2016). A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times. European Journal of Operational Research, 249, 55-66.
Fallahi, A. E., Prins, C., & Calvo, R. W. (2008). A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Computers & Operations Research, 35, 1725-1741.
Furuhata, M., Dessouky, M., Ordonez, F., & Brunet, M.-E. (2013). Ridesharing: The state-of-the-art and future directions. Transportation Research Part B, 57, 28-46.
Henke, T., Sperenza, M. G., & Wascher, G. (2015). The multi-compartment vehicle routing problem with flexible compartment sizes. European Journal of Operational Research, 246, 730-743.
Hosni, H., Sawaya, J., & Artail, H. (2014). The shared-taxi problem: Formulation and solution methods. Transportation Research Part B: Methodological, 303-318.
Janqueira, L., & Morabito, R. (2015). Heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem in a carrier. Computers & Industrial Engineering, 88, 110-130.
Li, B., Krunshinsky, D., Woensel, T. V., & Reijers, H. A. (2014). The share-a-ride problem: people and parcels sharing taxis. European Journal of Operational Research, 31-40.
Li, B., Krunshinsky, D., Woensel, T. V., & Reijers, H. A. (2016). An adaptive large neighborhood search heuristic for the share-a-ride problem. Computers & Operations Research, 66, 170-180.
Lin, S.-W., Yu, V. F., & Lu, C.-C. (2011). A simulated annealing heuristic for the truck and trailer routing problem with time windows. Expert System with Applications, 38, 15244-15252.
Liu, R., Xie, X., Augusto, V., & Rodriguez, C. (2013). Heuristic algorithm for vehicle routing problem with simulaneous delivery and pickup adn time windows in home health care. European Journal of Operational Research, 230, 475-486.
Nagy, G., & Salhi, S. (2005). Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research, 162(1), 126-141.
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2010). Variable neighborhood search for dial-a-ride problem. Computers & Operations Research, 1129-1138.
Reisabadi, E. Z., & Mirmohammadi, S. H. (2015). Site dependent vehicle routing problem with soft time window: Modeling and solution approach. Computers & Industrial Engineering, 90, 177-185.
Stiglic, M., Agatz, N., Savelsbergh, M., & Gradisar, M. (2016). Making dynamic ride-sharing work: The impact of driver and rider flexibility. Transporttaion Research Part E: Logistics and Transportation Review, 190-207.
Wei, L., Zhang, Z., Zhang, D., & Lim, A. (2015). A variable neighborhood search for the capacitated vehicle routing problem with two-dimesional loading constraints. European Journal of Operational Research, 243, 798-814.
Xiao, Y., & Konak, A. (2015). A simulated annealing algorithm to solve the green vehicle routing & scheduling problem with hierarchical objectives and weighted tardiness. Applied Soft Computing, 34, 372-388.
Yu, V. F., & Lin, S.-Y. (2015). A simulated annealing heuristic for open location-routing problem. Computers & Operations Research, 62, 184 - 196.
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, 1121-1131.