本研究提出考慮同時收送貨與群眾外包之車輛途程問題(Vehicle Routing Problem with Simultaneous Pick-up and Delivery and Occasional Drivers; VRPSPDOD)，VRPSPDOD為結合同時收送貨之車輛途程問題(Vehicle Routing Problem with Simultaneous Pick-up and Delivery; VRPSPD)與考慮群眾外包之車輛途程問題(Vehicle Routing Problem with Occasional Drivers; VRPOD)概念之延伸問題。本研究為此問題建構一數學模型，其目標為最小化總車輛成本，其中包含一般車輛之路徑成本以及群眾外包(Occasional Driver; OD)的補償成本。本研究並提出一基於模擬退火法之數學啟發式演算法來求解此問題。由於VRPSPDOD為一個新的問題，因此沒有此問題的測試題庫。本研究以Nagy and Salhi之VRPSPD題庫為基礎，建立一個VRPSPDOD的測試題庫，以驗證演算法之效能。最後，本研究分析不同的OD參數對於應用OD的效益所帶來之影響。

This research proposes and formulates a new variant of the vehicle routing problem with simultaneous pick-up and delivery (VRPSPD) called the vehicle routing problem with simultaneous pick-up and delivery and occasional drivers (VRPSPDOD). It extends the VRPSPD by considering occasional drivers (ODs). The goal of VRPSPDOD is to minimize the total cost which consists of traveling cost of regular vehicles and compensation cost paid to occasional drivers. This study proposes a simulated annealing based matheuristic for solving VRPSPDOD. Since this problem has not been study in the literature yet, there are no benchmark instances for this problem. Thus, a VRPSPDOD benchmark dataset adapted from VRPSPD benchmark instances of Nagy and Salhi is generated in the study to test the performance of the proposed algorithm. The impacts of different OD parameters on benefits of using ODs are also analyzed.

Ai, T. J., & Kachitvichyanukul, V. (2009). A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 36(5), 1693-1702.
Archetti, C., Bianchessi, N., & Speranza, M. G. (2011). A column generation approach for the split delivery vehicle routing problem. Networks, 58(4), 241-254.
Archetti, C., Doerner, K. F., & Tricoire, F. (2013). A heuristic algorithm for the free newspaper delivery problem. European Journal of Operational Research, 230(2), 245-257.
Archetti, C., Guastaroba, G., & Speranza, M. G. (2014). An ILP-refined tabu search for the directed profitable rural postman problem. Discrete Applied Mathematics, 163, 3-16.
Archetti, C., Savelsbergh, M., & Speranza, M. G. (2016). The vehicle routing problem with occasional drivers. European Journal of Operational Research, 254(2), 472-480.
Arslan, A. M., Agatz, N., Kroon, L., & Zuidwijk, R. (2019). Crowdsourced delivery—A dynamic pickup and delivery problem with ad hoc drivers. Transportation Science, 53(1), 222-235.
Barr, A., & Wohl, J. (2013). Exclusive: Walmart may get customers to deliver packages to online buyers. REUTERS–Business Week.
Bianchessi, N., & Righini, G. (2007). Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Computers & Operations Research, 34(2), 578-594.
Boschetti, M. A., Maniezzo, V., Roffilli, M., & Röhler, A. B. (2009). Matheuristics: Optimization, simulation and control. Paper presented at the International Workshop on Hybrid Metaheuristics.
Çatay, B. (2010). A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert Systems with Applications, 37(10), 6809-6817.
Chen, C., & Pan, S. (2016). Using the Crowd of Taxis to Last Mile Delivery in E-Commerce: a methodological research. In Service Orientation in Holonic and Multi-Agent Manufacturing (pp. 61-70): Springer.
Chen, J. F., & Wu, T. H. (2006). Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society, 57(5), 579-587.
Chen, S., Golden, B., & Wasil, E. (2007). The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results. Networks, 49(4), 318-329.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581.
Cordeau, J.-F., Stojković, G., Soumis, F., & Desrosiers, J. (2001). Benders decomposition for simultaneous aircraft routing and crew scheduling. Transportation Science, 35(4), 375-388.
Crispim, J., & Brandão, J. (2005). Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls. Journal of the Operational Research Society, 56(11), 1296-1302.
Dahle, L., Andersson, H., & Christiansen, M. (2017). The vehicle routing problem with dynamic occasional drivers. Paper presented at the International Conference on Computational Logistics.
Dahle, L., Andersson, H., Christiansen, M., & Speranza, M. G. (2019). The pickup and delivery problem with time windows and occasional drivers. Computers & Operations Research, 109, 122-133.
Danna, E., & Le Pape, C. (2005). Branch-and-price heuristics: A case study on the vehicle routing problem with time windows. In Column Generation (pp. 99-129): Springer.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91.
Dell’Amico, M., Righini, G., & Salani, M. (2006). A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transportation Science, 40(2), 235-247.
Demir, E., Bektaş, T., & Laporte, G. (2012). An adaptive large neighborhood search heuristic for the pollution-routing problem. European Journal of Operational Research, 223(2), 346-359.
Dethloff, J. (2001). Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR Spektrum, 23(1), 79-96.
Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
Flisberg, P., Lidén, B., & Rönnqvist, M. (2009). A hybrid method based on linear programming and tabu search for routing of logging trucks. Computers & Operations Research, 36(4), 1122-1144.
Foster, B. A., & Ryan, D. M. (1976). An integer programming approach to the vehicle scheduling problem. Journal of the Operational Research Society, 27(2), 367-384.
Gajpal, Y., & Abad, P. (2009). An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup. Computers & Operations Research, 36(12), 3215-3223.
Goksal, F. P., Karaoglan, I., & Altiparmak, F. (2013). A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering, 65(1), 39-53.
Guerrero, W. J., Prodhon, C., Velasco, N., & Amaya, C. A. (2013). Hybrid heuristic for the inventory location-routing problem with deterministic demand. International Journal of Production Economics, 146(1), 359-370.
Jeong, C.-S., & Kim, M.-H. (1991). Fast parallel simulated annealing for traveling salesman problem on SIMD machines with linear interconnections. Parallel Computing, 17(2-3), 221-228.
Jin, M., Liu, K., & Eksioglu, B. (2008). A column generation approach for the split delivery vehicle routing problem. Operations Research Letters, 36(2), 265-270.
Jun, Y., & Kim, B.-I. (2012). New best solutions to VRPSPD benchmark problems by a perturbation based algorithm. Expert Systems with Applications, 39(5), 5641-5648.

Kafle, N., Zou, B., & Lin, J. (2017). Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery. Transportation Research Part B: Methodological, 99, 62-82.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680.
Macrina, G., & Guerriero, F. (2018). The green vehicle routing problem with occasional drivers. In New Trends in Emerging Complex Real Life Problems (pp. 357-366): Springer.
Macrina, G., Pugliese, L. D. P., Guerriero, F., & Laganà, D. (2017). The vehicle routing problem with occasional drivers and time windows. Paper presented at the International Conference on Optimization and Decision Science.
Macrina, G., Pugliese, L. D. P., Guerriero, F., & Laporte, G. (2020). Crowd-shipping with time windows and transshipment nodes. Computers & Operations Research, 113, 104806.
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.
MIC. (2019). 【網購調查系列一】網購消費占比達16.5% 愛用電商平台大排名. Retrieved from https://mic.iii.org.tw/news.aspx?id=516
Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5), 377-386.
Mu, D., Wang, C., Zhao, F., & Sutherland, J. W. (2016). Solving vehicle routing problem with simultaneous pickup and delivery using parallel simulated annealing algorithm. International Journal of Shipping and Transport Logistics, 8(1), 81-106.
Nagy, G., & Salhi, S. d. (2005). Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research, 162(1), 126-141.
Paloheimo, H., Lettenmeier, M., & Waris, H. (2016). Transport reduction by crowdsourced deliveries–a library case in Finland. Journal of Cleaner Production, 132, 240-251.
Parragh, S. N., & Schmid, V. (2013). Hybrid column generation and large neighborhood search for the dial-a-ride problem. Computers & Operations Research, 40(1), 490-497.
Pillac, V., Gueret, C., & Medaglia, A. L. (2013). A parallel matheuristic for the technician routing and scheduling problem. Optimization Letters, 7(7), 1525-1535.
Rakke, J. G., Stålhane, M., Moe, C. R., Christiansen, M., Andersson, H., Fagerholt, K., & Norstad, I. (2011). A rolling horizon heuristic for creating a liquefied natural gas annual delivery program. Transportation Research Part C: Emerging Technologies, 19(5), 896-911.
Rodríguez-Martín, I., & Salazar-González, J. J. (2012). A hybrid heuristic approach for the multi-commodity one-to-one pickup-and-delivery traveling salesman problem. Journal of Heuristics, 18(6), 849-867.
Salhi, S., & Nagy, G. (1999). A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. Journal of the Operational Research Society, 50(10), 1034-1042.
Savelsbergh, M., & Song, J.-H. (2008). An optimization algorithm for the inventory routing problem with continuous moves. Computers & Operations Research, 35(7), 2266-2282.
Schmid, V., Doerner, K. F., Hartl, R. F., Savelsbergh, M. W., & Stoecher, W. (2009). A hybrid solution approach for ready-mixed concrete delivery. Transportation Science, 43(1), 70-85.
Seçkiner, S. U., & Kurt, M. (2007). A simulated annealing approach to the solution of job rotation scheduling problems. Applied Mathematics and Computation, 188(1), 31-45.
Sherali, H. D., Al-Yakoob, S. M., & Hassan, M. M. (1999). Fleet management models and algorithms for an oil-tanker routing and scheduling problem. IIE Transactions, 31(5), 395-406.
Sierksma, G., & Tijssen, G. A. (1998). Routing helicopters for crew exchanges on off-shore locations. Annals of Operations Research, 76, 261-286.
Sofianopoulou, S. (1992). Simulated annealing applied to the process allocation problem. European Journal of Operational Research, 60(3), 327-334.
Statista. (2020). Retail e-commerce sales worldwide from 2014 to 2023. Retrieved from https://www.statista.com/statistics/379046/worldwide-retail-e-commerce-sales/
Subramanian, A., Uchoa, E., Pessoa, A. A., & Ochi, L. S. (2011). Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery. Operations Research Letters, 39(5), 338-341.
Subramanian, A., Uchoa, E., Pessoa, A. A., & Ochi, L. S. (2013). Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery. Optimization Letters, 7(7), 1569-1581.
Wang, C., Mu, D., Zhao, F., & Sutherland, J. W. (2015). A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. Computers & Industrial Engineering, 83, 111-122.
Wassan, N. A., Wassan, A. H., & Nagy, G. (2008). A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries. Journal of Combinatorial Optimization, 15(4), 368-386.
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.
Yu, V. F., Lin, S.-W., Lee, W., & Ting, C.-J. (2010). A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering, 58(2), 288-299.
Yu, V. F., & Lin, S.-Y. (2016). Solving the location-routing problem with simultaneous pickup and delivery by simulated annealing. International Journal of Production Research, 54(2), 526-549.