近年來，隨著行動裝置與網際網路的普及，改變消費者的購物行為，特別是在節日以及後疫情時代，根據經濟部的統計2021年電子商務的營收達到4303億元，大量的包裹運送需求提升；除此之外，Uber Eats, Foodpanda, Lalamove等餐飲快遞外送平台服務也受到消費者青睞，帶動了群眾外包(crowdsourcing)的工作機會，透過網路平台公開地將工作交由一群不特定的人們完成，快遞公司藉由臨時性、季節性的人力資源協助運送大量的包裹並節省成本。
本研究旨在探討多工司機助手配送包裹之車輛途程問題 (Hybrid Helper Dispatching Problem)，透過司機助手在路途中的可轉移性與多工的角色，協助司機減少包裹配送的時間，此模型的目標為最小化交付成本，成本來源包含車隊的燃油成本、司機的薪水與司機助手的薪水，為了更貼近實務情況考慮了司機助手的最低工資與司機的加班費。
在研究中使用了Google OR-Tools軟體來求解大型實例題目，並採用爬山演算法優化卡車與司機助手搭配後的路線。實驗中使用電腦模擬的資料集，考慮五個變數，包含客戶數量、服務區域大小、多客戶點比例、司機薪水及燃油成本，搭配出不同情境，將本研究的模型與無司機助手(no-helper)、獨立司機助手(independent-helper)與依賴司機助手(dependent-helper)方法進行四者間的總成本與總時間的比較。
實驗結果顯示多工司機助手的模型相較其他三種方法可節省總花費時間，在總成本的節省上也優於無司機助手與依賴司機助手方法，此外，本研究的模型在服務區域相對小、適中的多客戶點數量、較高的司機薪水及低燃油成本的情境下可以有效地節省成本。

In recent years, with the popularity of mobile devices and the Internet, consumers' shopping behavior have changed, especially on the holidays and post-epidemic era. According to the statistic of Ministry of Economic Affairs, in 2021, the revenue of e-commerce has reached to 430.3 billion NTD, leads to the demand for large number of parcels delivery. In addition, Uber Eats, Foodpanda, Lalamove and other express delivery platform services are favored by customers also has increased the opportunities of crowdsourcing which can hand over the work to a group of unspecified people through online platform openly. Delivery companies can deal with large number of packages and save the cost by using the temporary or seasonal human resources.
The purpose of this study is to investigate the Hybrid Helper Dispatching Problem (HHDP), the driver helper is transferable and can be assigned as different characteristics, it helps driver to reduce the service time at customer nodes. The objective of the model is to minimize the total cost, including fuel cost, driver’s cost and helper’s cost. To be more practical, the minimum working hours of driver helper and the overtime pay of drivers are considered.
In this study, Google OR-Tools software suite is used to solve the large-scale examples, and adopting the hill climbing algorithm to optimize the route of driver coordinate with helper. This study using computational simulation data set and considering five variables, including number of customer nodes, service area, percentage of multiple customer node, driver’s wage and fuel cost. To compare the total cost and return time between hybrid helper, no-helper, independent-helper and dependent-helper solutions in various scenarios.
The result shows that HHDP model has better time saving potential than others and outperform than no-helper solution and dependent-helper solution on cost saving. Besides, our model works well in relatively small area, moderate percentage of multiple customer node, high driver’s wage and low fuel cost scenario.

Alnaggar, A., Gzara, F., & Bookbinder, J. H. (2021). Crowdsourced delivery: A review of platforms and academic literature. Omega, 98, 102139.
Alvarez-Palau, E. J., Calvet-Liñán, L., Viu-Roig, M., Gandouz, M., & Juan, A. A. (2021). Economic profitability of last-mile food delivery services: Lessons from Barcelona. Research in Transportation Business & Management, 100659.
Archetti, C., Savelsbergh, M., & Speranza, M. G. (2016). The vehicle routing problem with occasional drivers. European Journal of Operational Research, 254(2), 472-480.
Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787-800.
Bektaş, T., & Laporte, G. (2011). The pollution-routing problem. Transportation Research Part B: Methodological, 45(8), 1232-1250.
Baldacci, R., Mingozzi, A., & Roberti, R. (2012). Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218(1), 1-6.
Deng, P., Amirjamshidi, G., & Roorda, M. (2020). A vehicle routing problem with movement synchronization of drones, sidewalk robots, or foot-walkers. Transportation research procedia, 46, 29-36.
Dordaie, N., & Navimipour, N. J. (2018). A hybrid particle swarm optimization and hill climbing algorithm for task scheduling in the cloud environments. ICT Express, 4(4), 199-202.
Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the travelling salesman problem. biosystems, 43(2), 73-81.
Dorling, K., Heinrichs, J., Messier, G. G., & Magierowski, S. (2016). Vehicle routing problems for drone delivery. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47(1), 70-85.
Drexl, M. (2012). Synchronization in vehicle routing—a survey of VRPs with multiple synchronization constraints. Transportation Science, 46(3), 297-316.
Drexl, M. (2013). Applications of the vehicle routing problem with trailers and transshipments. European Journal of Operational Research, 227(2), 275-283.
Euchi, Jalel., Zidi, Salah., Laouamer Lamri. (2020). A Hybrid Approach to Solve the Vehicle Routing Problem with Time Windows and Synchronized Visits In-Home Health Care. Arbian Journal for Science and Engineering 45, 10637-10652.
Gambardella, L. M., Taillard, É., & Agazzi, G. (1999). Macs-vrptw: A multiple colony system for vehicle routing problems with time windows. In New ideas in optimization.
Garzon Castro, K. A., & Mondragón García, S. (2020). A vehicle routing application for retail delivery with open source tools.
García-Martínez, C., & Lozano, M. (2007). Local search based on genetic algorithms. In Advances in metaheuristics for hard optimization (pp. 199-221). Springer, Berlin, Heidelberg.
Gendreau, M. (2003). An introduction to tabu search. In Handbook of metaheuristics (pp. 37-54). Springer, Boston, MA.
Gerdessen, J. C. (1996). Vehicle routing problem with trailers. European Journal of Operational Research, 93(1), 135-147.
Ghaziri, Hassan & Osman, Ibrahim (2003), “A neural network algorithm for the traveling salesman problem with backhauls,” Computers & Industrial Engineering, 44, 267-281.
Ghoseiri, K., & Ghannadpour, S. F. (2010). Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm. Applied Soft Computing, 10(4), 1096-1107.
Glover, F., & Laguna, M. (1998). Tabu search. In Handbook of combinatorial optimization (pp. 2093-2229). Springer, Boston, MA.
Google OR-Tools. Retrieved from https://developers.google.com/optimization
Gupta, D. K. (2002). Tabu search for vehicle routing problems (VRPs). International journal of computer mathematics, 79(6), 693-701.
Helsgaun, K. (2000). An effective implementation of the Lin–Kernighan traveling salesman heuristic. European journal of operational research, 126(1), 106-130.
Ho, W., Ho, G. T., Ji, P., & Lau, H. C. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering applications of artificial intelligence, 21(4), 548-557.
Katayama, K., Sakamoto, H., & Narihisa, H. (2000). The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem. Mathematical and Computer Modelling, 31(10-12), 197-203.
Kek, A. G., Cheu, R. L., & Meng, Q. (2008). Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots. Mathematical and Computer Modelling, 47(1-2), 140-152.
Knox, J. (1994). Tabu search performance on the symmetric traveling salesman problem. Computers & Operations Research, 21(8), 867-876.
Kirkpatrick, S., Gelatt Jr, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
Lenstra, J. K., & Kan, A. R. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), 221-227.
Li, J.M., Li, A.H., Varbanov, P.S., and Liu, Z.Y. (2017). Distance potential concept and its applications to the design of regional biomass supply chains and solving vehicle routing problems. Journal of Cleaner Production, 144, 426-436.
Lin, C. K. Y. (2008). Resources requirement and routing in courier service. Vehicle routing problem, 125-42.
Lin, S. W., Vincent, F. Y., & Chou, S. Y. (2010). A note on the truck and trailer routing problem. Expert Systems with Applications, 37(1), 899-903.
Lu, S.H., Suzuki, Y., and Clottey, T. (2020). The Last Mile: Managing Driver Helper Dispatching for Package Delivery Services. Journal of Business Logistics, 41(3), 206- 221.
Lu, S. H., Suzuki, Y., & Clottey, T. (2022). Improving the efficiency of last‐mile package deliveries using hybrid driver helpers. Decision Sciences, 1-23.
Marinakis, Y., Marinaki, M., and Dounias, G. (2010). A hybrid particle swarm optimization algorithm for the vehicle routing problem. Engineering Applications of Artificial Intelligence, 23(4), 463-472.
Mangiaracina, R., Perego, A., Seghezzi, A., & Tumino, A. (2019). Innovative solutions to increase last-mile delivery efficiency in B2C e-commerce: a literature review. International Journal of Physical Distribution & Logistics Management.
Miranda, D.M., and Conceição, S.V (2016), “The vehicle routing problem with hard time windows and stochastic travel and service time,” Expert System with Applications, 64, 104-116.
Montané, F. A. T., & Galvao, R. D. (2006). A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research, 33(3), 595-619.
Murray, C. C., & Chu, A. G. (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 54, 86-109.
Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of operations research, 41(4), 421-451.
Palmer, A. (2007). The development of an integrated routing and carbon dioxide emissions model for goods vehicles.
Paulo Roberto de Oliveira da Costa., Stefano, M., Paula, C., Fabiano, P (2018), “A Genetic Algorithm for a Green Vehicle Routing Problem,” Electronic Notes in Discrete Mathematics, 64, 65-74.
Purnamasari, C. D., & Santoso, A. (2018). Vehicle Routing Problem (VRP) for courier service: A review. In MATEC Web of Conferences (Vol. 204, p. 07007). EDP Sciences.
Rhodes, K., Nehring, R., Wilk, B., and Patel, N. (2007). UPS Helper Dispatch Analysis. In Systems and Information Engineering Design Symposium, 2007. SIEDS 2007. IEEE. 1-6.
Savelsbergh, M (1985), “Local search in routing problems with time windows,” Annals of Operations Research, 4, 285-305.
Savuran, H., & Karakaya, M. (2016). Efficient route planning for an unmanned air vehicle deployed on a moving carrier. Soft Computing, 20(7), 2905-2920.
Sazaki, Y., Satria, H., Primanita, A., & Apriliansyah, R. (2018, July). Application of the Steepest Ascent Hill Climbing Algorithm in the Preparation of the Crossword Puzzle Board. In 2018 4th International Conference on Wireless and Telematics (ICWT)(pp. 1-6). IEEE.
Shen, Y., Liu, M., Yang, J., Shi, Y., & Middendorf, M. (2020). A hybrid swarm intelligence algorithm for vehicle routing problem with time windows. Ieee Access, 8, 93882-93893.
Shi, X. H., Liang, Y. C., Lee, H. P., Lu, C., & Wang, Q. X. (2007). Particle swarm optimization-based algorithms for TSP and generalized TSP. Information processing letters, 103(5), 169-176.
Skiscim, C. C., & Golden, B. L. (1983). Optimization by simulated annealing: A preliminary computational study for the tsp. Institute of Electrical and Electronics Engineers (IEEE).
Solomon, M.M (1983), “Vehicle routing and scheduling with time windows constraints: Models and algorithms,” Ph.D. Dissertation, Department of Decision Sciences, University of Pennsylvania.
Surana, P. (2019). Benchmarking Optimization Algorithms for Capacitated Vehicle Routing Problems.
Tan, K. C., Chew, Y. H., & Lee, L. H. (2006). A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems. European Journal of Operational Research, 172(3), 855-885.
Toth, P., & Vigo, D. (2002). The vehicle routing problem. Society for Industrial and Applied Mathematics.
Toth, P., & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics, 123(1-3), 487-512.
Verhoeven, M. G. A., Aarts, E. H., & Swinkels, P. C. J. (1995). A parallel 2-opt algorithm for the traveling salesman problem. Future Generation Computer Systems, 11(2), 175-182.
Villegas, J. G., Prins, C., Prodhon, C., Medaglia, A. L., & Velasco, N. (2013). A matheuristic for the truck and trailer routing problem. European Journal of Operational Research, 230(2), 231-244.
Wang, Y. (2014). The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem. Computers & Industrial Engineering, 70, 124-133.
Wester, V. D. (1993). A genetic algorithm for the vehicle routing problem.