本研究探討具時間窗、覆蓋區位與群眾外包之二階車輛途程問題(Two-Echelon Vehicle Routing Problem with Time Windows, Covering Locations and Occasional Drivers; 2E-VRPTW-CO-OD)，為車輛途程問題(Vehicle Routing Problem)之延伸問題。本研究目標為最小化總旅行成本，包含車輛之路徑成本、覆蓋區位的支付成本，以及群眾外包的補償成本。在此問題中，顧客能由兩種類型的車輛提供服務，即配送車與群眾外包(Occasional Driver; OD)，每位顧客可選擇送貨到府服務或替代交付服務。若顧客選擇替代交付服務，則將顧客需求配送至其中一個可用的覆蓋區位(Covering Location; CO)，顧客再親自至覆蓋區位取貨。本研究為此問題建構一數學模型，藉由AMPL/CPLEX對小型題庫進行求解，同時使用適應性大規模鄰域搜尋演算法(Adaptive Large Neighborhood Search; ALNS)求解此問題之小型與大型題庫，並比較兩實驗之求解結果與效率。2E-VRPTW-CO-OD為二階車輛途程問題(Two-Echelon Routing Problem; 2E-VRP)的特殊情況，在此情況下，本研究提出的ALNS演算法可獲得與其他先進演算法相當的結果。實驗結果顯示本研究所提出之ALNS在求解2E-VRPTW-CO-OD上之效率以及2E-VRPTW-CO-OD中之群眾外包和覆蓋區位所帶來的效益。

This research proposes and formulates a new variant of the two-echelon vehicle routing problem called the two-echelon vehicle routing problem with time windows, covering locations and occasional drivers (2E-VRPTW-CO-OD). The goal of 2E-VRPTW-CO-OD is to minimize the total cost which consists of routing cost, connection costs, and compensation paid to occasional drivers. There are two types of fleet available to serve customers, i.e., city freighters and occasional drivers. Two delivery options can be selected by each customer, i.e., home delivery and alternative delivery. If a customer chooses the alternative delivery option, the customer’s demand will be delivered to one of the available covering locations, and the customer will go to the covering location to pick up the demand. In this study, we formulate a mixed-integer programming model for the problem and use AMPL/CPLEX to solve small instances. An adaptive large neighborhood search (ALNS) is also developed and used to solve small and large instances. The results and efficiency of the two experiments are compared. The two-echelon vehicle routing problem (2E-VRP) is a special case of 2E-VRPTW-CO-OD. Our proposed ALNS provides comparable results with those obtained by state-of-the-art algorithms for 2E-VRP. Moreover, we report detailed computational results from solving 2E-VRPTW-CO-OD instances to show the effectiveness of our proposed ALNS, and the benefits of the covering locations and occasional drivers in 2E-VRPTW-CO-OD.

Ali, O., Côté, J.-F., & Coelho, L. C. (2021). Models and algorithms for the delivery and installation routing problem. European Journal of Operational Research, 291(1), 162-177.
Anderluh, A., Hemmelmayr, V. C., & Nolz, P. C. (2017). Synchronizing vans and cargo bikes in a city distribution network. Central European Journal of Operations Research, 25(2), 345-376.
Archetti, C., Savelsbergh, M., & Speranza, M. G. (2016). The vehicle routing problem with occasional drivers. European Journal of Operational Research, 254(2), 472-480.
Arnold, F., Cardenas, I., Sörensen, K., & Dewulf, W. (2018). Simulation of B2C e-commerce distribution in Antwerp using cargo bikes and delivery points. European Transport Research Review, 10(1), 1-13.
Boysen, N., Fedtke, S., & Schwerdfeger, S. (2020). Last-mile delivery concepts: a survey from an operational research perspective. OR Spectrum, 1-58.
Breunig, U., Schmid, V., Hartl, R. F., & Vidal, T. (2016). A large neighbourhood based heuristic for two-echelon routing problems. Computers & Operations Research, 76, 208-225.
Clement, J. (2019). E-commerce share of total global retail sales from 2015 to 2023. Retrieved from https://www.statista.com/statistics/534123/e-commerce-share-of-retail-sales-worldwide/
Dellaert, N., Dashty Saridarq, F., Van Woensel, T., & Crainic, T. G. (2019). Branch-and-price–based algorithms for the two-echelon vehicle routing problem with time windows. Transportation Science, 53(2), 463-479.
Deutsch, Y., & Golany, B. (2018). A parcel locker network as a solution to the logistics last mile problem. International Journal of Production Research, 56(1-2), 251-261.
Enthoven, D. L., Jargalsaikhan, B., Roodbergen, K. J., uit het Broek, M. A., & Schrotenboer, A. H. (2020). The two-echelon vehicle routing problem with covering options: City logistics with cargo bikes and parcel lockers. Computers & Operations Research, 118, 104919.
Grangier, P., Gendreau, M., Lehuédé, F., & Rousseau, L.-M. (2016). An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization. European Journal of Operational Research, 254(1), 80-91.
Gunawan, A., Widjaja, A. T., Vansteenwegen, P., & Yu, V. F. (19-24 July, 2020). Adaptive large neighborhood search for vehicle routing problem with cross-docking. Paper presented at the 2020 IEEE Congress on Evolutionary Computation (CEC), Glasgow, UK.
Hemmelmayr, V. C., Cordeau, J.-F., & Crainic, T. G. (2012). An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Computers & Operations Research, 39(12), 3215-3228.
Huang, K., & Ardiansyah, M. N. (2019). A decision model for last-mile delivery planning with crowdsourcing integration. Computers Industrial Engineering, 135, 898-912.
Jiang, L., Dhiaf, M., Dong, J., Liang, C., & Zhao, S. (2020). A traveling salesman problem with time windows for the last mile delivery in online shopping. International Journal of Production Research, 58(16), 5077-5088.
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.
Li, H., Wang, H., Chen, J., & Bai, M. (2020). Two-echelon vehicle routing problem with time windows and mobile satellites. Transportation Research Part B: Methodological, 138, 179-201.
Li, H., Zhang, L., Lv, T., & Chang, X. (2016). The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems. Transportation Research Part B: Methodological, 94, 169-188.
Liu, T., Luo, Z., Qin, H., & Lim, A. (2018). A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints. European Journal of Operational Research, 266(2), 487-497.
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, Sorrento, Italy.
Macrina, G., Pugliese, L. D. P., Guerriero, F., & Laporte, G. (2020). Crowd-shipping with time windows and transshipment nodes. Computers & Operations Research, 113, 104806.
Orenstein, I., Raviv, T., & Sadan, E. (2019). Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis. EURO Journal on Transportation Logistics, 8(5), 683-711.
Perboli, G., Tadei, R., & Vigo, D. (2011). The two-echelon capacitated vehicle routing problem: Models and math-based heuristics. Transportation Science, 45(3), 364-380.
Rai, H. B., Verlinde, S., Merckx, J., & Macharis, C. (2017). Crowd logistics: an opportunity for more sustainable urban freight transport. European Transport Research Review, 9(3), 1-13.
Rohmer, S., & Gendron, B. (2020). A Guide to Parcel Lockers in Last Mile Distribution: Highlighting Challenges and Opportunities from an OR Perspective: CIRRELT.
Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4), 455-472.
Sampaio, A., Savelsbergh, M., Veelenturf, L., & Van Woensel, T. (2019). Crowd-based city logistics. In J. Faulin, A. A. Juan, S. E. Grasman, & P. Hirsch (Eds.), Sustainable Transportation and Smart Logistics (pp. 381-400): Elsevier.
Sampaio, A., Savelsbergh, M., Veelenturf, L. P., & Van Woensel, T. (2020). Delivery systems with crowd‐sourced drivers: A pickup and delivery problem with transfers. Networks, 2020, 76(2), 232-255.
Savelsbergh, M., & Van Woensel, T. (2016). 50th anniversary invited article—city logistics: Challenges and opportunities. Transportation Science, 50(2), 579-590.
Schliwa, G., Armitage, R., Aziz, S., Evans, J., & Rhoades, J. (2015). Sustainable city logistics—Making cargo cycles viable for urban freight transport. Research in Transportation Business Management, 15, 50-57.
Shaw, P. (1999). Using constraint programming and local search methods to solve vehicle routing problems. Paper presented at the International conference on principles and practice of constraint programming, Pisa, Italy.
Simoni, M. D., Marcucci, E., Gatta, V., & Claudel, C. G. (2019). Potential last-mile impacts of crowdshipping services: a simulation-based evaluation. Transportation, 1-22.
Soysal, M., Bloemhof-Ruwaard, J. M., & Bektaş, T. (2015). The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations. International Journal of Production Economics, 164, 366-378.
Sun, P., Veelenturf, L. P., Hewitt, M., & Van Woensel, T. (2020). Adaptive large neighborhood search for the time-dependent profitable pickup and delivery problem with time windows. Transportation Research Part E: Logistics Transportation Review, 138, 101942.
Van Duin, J., Wiegmans, B., van Arem, B., & van Amstel, Y. (2020). From home delivery to parcel lockers: A case study in Amsterdam. Transportation Research Procedia, 46, 37-44.
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013). Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. European Journal of Operational Research, 231(1), 1-21.
Wang, K., Shao, Y., & Zhou, W. (2017). Matheuristic for a two-echelon capacitated vehicle routing problem with environmental considerations in city logistics service. Transportation Research Part D: Transport Environment, 57, 262-276.
Yu, V. F., Jewpanya, P., Redi, A. P., & Tsao, Y.-C. (2021). Adaptive neighborhood simulated annealing for the heterogeneous fleet vehicle routing problem with multiple cross-docks. Computers & Operations Research, 129, 105205.
Yu, V. F., Redi, A. P., Halim, C., & Jewpanya, P. (2020). The path cover problem: Formulation and a hybrid metaheuristic. Expert Systems with Applications, 146, 113107.
Zhou, L., Baldacci, R., Vigo, D., & Wang, X. (2018). A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution. European Journal of Operational Research, 265(2), 765-778.