隨著日益興盛的網路發展，網路購物行為，帶動了簽收送貨服務的成長。簽收送貨服務會確保包裹必須在送達至收貨人時由收貨人簽收，這是一種可靠的送貨形式。然而，一般的簽收送貨的路徑規劃未考慮收貨人的在家資訊，一旦發生當送貨員抵達時，收貨人卻不在家的情形，送貨員就必須安排重新配送該收件人的時間與路徑，這類重新配送的問題會降低送貨員配送的效率，造成鉅額的資源浪費及送貨員的超時工作等問題。在本篇論文裡，我們目標解決避免重新配送的路徑規劃問題，並且提出一種新的互動式規劃框架，我們稱為 COKI，主要是採用不間斷的互動機制來進行有效的路徑規劃，我們的框架目標是規劃不需重新配送的最短路線，使送貨員準確地在第一次送貨給收貨人時，收貨人就會簽收並且成功交貨，最後，應用了真實世界的資料來進行實驗，實驗結果證明在沒有適當考慮避免重新配送的情況下，目前最先進的路徑規劃演算法只能實現次優的結果。此外，我們的 COKI 框架，可以利用互動機制來有效的找到不需重新拜訪的最佳最短路線。

With the progress of technology, the fast development of online shopping has given rise to the growth of signed-for delivery services. Signed-for delivery is a reliable way for driver to get proof of the delivery that the parcel must be signed when it arrives. However, due to the unknown occupancy of the recipient, signed-for delivery is not very effective for delivery drivers. Once the recipients are unavailable when the driver arrives, the driver must rearrange to delivery to the recipient, resulting in waste of resources and driver fatigue. In this thesis, we solve an important problem about revisiting-free itinerary planning, and propose a novel interactive planning framework, called COKI, with a comprehensive strategy to interactively plan the effective delivery itineraries. The proposed method allows the delivery driver to shorten the itinerary without returning to any recipient. With real dataset, our experimental results show that the COKI framework can efficiently find the better revisiting-free itinerary.

[1] Y.-P. Chiu, S.-K. Lo, A.-Y. Hsieh, and Y. Hwang, “Exploring why people spend more time shopping online than in offline stores,” Computers in Human Behavior, vol. 95, pp. 24–30, 2019.
[2] R. Huang, “Ecommerce in rural areas and environmental sustainability: The last-mile delivery,” in Proc. of Wuhan International Conference on E-Business, 2017, p. 50.
[3] S. Ohsugi and N. Koshizuka, “Delivery route optimization through occupancy prediction from electricity usage,” in Proc. of Annual Computer Software and Applications Conference, vol. 1, 2018, pp. 842–849.
[4] M. of Economy Trade and Industry, Social loss caused from parcel redelivery. Agency for Natural Resources and Energy, 2015.
[5] C. Alabas-Uslu and B. Dengiz, “A self-adaptive local search algorithm for the classical vehicle routing problem,” Expert Systems with Applications, vol. 38, no. 7, pp. 8990–8998, 2011.
[6] F. Semet, P. Toth, and D. Vigo, “Classical exact algorithms for the capacitated vehicle routing problem,” in Vehicle Routing, 2014, pp. 37–57.
[7] S.-Y. Teng, S.-C. Wu, and K.-T. Chuang, “Optimal delivery routing in road network with occupancy detection,” in Proc. of International Conference on Mobile Data Management (MDM), 2019, pp. 575–580.
[8] W. Kleiminger, C. Beckel, T. Staake, and S. Santini, “Occupancy detection from electricity consumption data,” in Proc. of ACM Workshop on Embedded Systems For Energy-Efficient Buildings, 2013, pp. 1–8.
[9] S. Arora, “Polynomial time approximation schemes for euclidean tsp and other geometric problems,” in Proc. of Conference on Foundations of Computer Science, 1996, pp. 2–11.
[10] J. J. Bentley, “Fast algorithms for geometric traveling salesman problems,” ORSA Journal on computing, vol. 4, no. 4, pp. 387–411, 1992.
[11] S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Operations Research, vol. 21, no. 2, pp. 498–516, 1973.
[12] E. L. Lawler, J. K. Lenstra, A. R. Kan, D. B. Shmoys et al., The traveling salesman problem: a guided tour of combinatorial optimization, 1985.
[13] B. Soylu, “A general variable neighborhood search heuristic for multiple traveling salesmen problem,” Computers & Industrial Engineering, vol. 90, pp. 390–401, 2015.
[14] Z. Xu and B. Rodrigues, “An extension of the christofides heuristic for the generalized multiple depot multiple traveling salesmen problem,” European Journal of Operational Research, vol. 257, no. 3, pp. 735–745, 2017.
[15] D. Cattaruzza, N. Absi, and D. Feillet, “Vehicle routing problems with multiple trips,” 4OR, vol. 14, no. 3, pp. 223–259, 2016.
[16] P. Toth and D. Vigo, Vehicle routing: problems, methods, and applications, 2014.
[17] G. Laporte and S. Martello, “The selective travelling salesman problem,” Discrete Applied Mathematics, vol. 26, no. 2-3, pp. 193–207, 1990.
[18] G. Desaulniers and Q. Groupe d’´etudes et de recherche en analyse des d´ecisions (Montr´eal, The VRP with pickup and delivery, 2002.
[19] G. Gutin and A. Yeo, “The greedy algorithm for the symmetric tsp,” Algorithmic Operations Research, vol. 2, no. 1, 2007.
[20] O. Chebbi and J. Chaouachi, “Multi-objective iterated greedy variable neighborhood search algorithm for solving a full-load automated guided vehicle routing problem with battery constraints,” Electronic Notes in Discrete Mathematics, vol. 47, pp. 165–172, 2015.
[21] T. Mosharraf, J. Wu, and H. Zheng, “Poster: Vehicle routing with pickup and delivery: A greedy approach,” in Proc. of Workshop on Challenged Networks, 2017, pp. 43–45.
[22] D. Xu, T. Weise, Y. Wu, J. L¨assig, and R. Chiong, “An investigation of hybrid tabu search for the traveling salesman problem,” in Proc. of International on Bio-Inspired ComputingTheories and Applications. Springer, 2015, pp. 523–537.
[23] M. Battarra, G. Erdoˇgan, G. Laporte, and D. Vigo, “The traveling salesman problem with pickups, deliveries, and handling costs,” Transportation Science, vol. 44, no. 3, pp. 383–399, 2010.
[24] C. Wang, M. Lin, Y. Zhong, and H. Zhang, “Solving travelling salesman problem using multiagent simulated annealing algorithm with instance-based sampling,” International Journal of Computing Science and Mathematics, vol. 6, no. 4, pp. 336–353, 2015.
[25] L. Wei, Z. Zhang, D. Zhang, and S. C. Leung, “A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints,” European Journal of Operational Research, vol. 265, no. 3, pp. 843–859, 2018.
[26] S. Afifi, D.-C. Dang, and A. Moukrim, “A simulated annealing algorithm for the vehicle routing problem with time windows and synchronization constraints,” in Proc. of International Conference on Learning and Intelligent Optimization, 2013, pp. 259–265.
[27] Google or-tools. [Online]. Available: https://developers.google.com/optimization
[28] J. Fiosina and M. Fiosins, “Selecting the shortest itinerary in a cloud-based distributed mobility network,” in Proc. of International Conference Distributed Computing and Artificial Intelligence, 2013, pp. 103–110.
[29] Y. Deng, Y. Chen, Y. Zhang, and S. Mahadevan, “Fuzzy dijkstra algorithm for shortest path problem under uncertain environment,” Applied Soft Computing, vol. 12, no. 3, pp. 1231–1237, 2012.
[30] I. Kiselev, A. Glaschenko, A. Chevelev, and P. Skobelev, “Towards an adaptive approach for distributed resource allocation in a multi-agent system for solving dynamic vehicle routing problems,” in Proc. of AAAI Conference on Artificial Intelligence, 2007, pp. 1874–1875.
[31] H. Hern´andez-P´erez and J.-J. Salazar-Gonz´alez, “The multi-commodity one-to-one pickupand-delivery traveling salesman problem,” European Journal of Operational Research, vol. 196, no. 3, pp. 987–995, 2009.
[32] J.-r. Su, “Improved particle swarm optimization for multi-object traveling salesman problems,” in Proc. of International Conference on Natural Computation, 2011, pp. 1175–1179.
[33] G. Karypis and V. Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,” SIAM Journal on scientific Computing, vol. 20, no. 1, pp. 359–392, 1998.
[34] B. W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell system technical journal, vol. 49, no. 2, pp. 291–307, 1970.
[35] B. Abdulhai and L. Kattan, “Reinforcement learning: Introduction to theory and potential for transport applications,” Canadian Journal of Civil Engineering, vol. 30, no. 6, pp. 981–991, 2003.
[36] J. Li, J. Du, and L. Li, “Optimization of vehicle routing problem with fatigue driving based on genetic algorithm,” in Proc. of Conference on Research in Adaptive and Convergent Systems, 2018, pp. 37–42.