Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: International Journal of Data Science and Analytics 4/2022

26-05-2022 | Regular Paper

Interactive planning of revisiting-free itinerary for signed-for delivery

Authors: Lo Pang-Yun Ting, Shan-Yun Teng, Szu-Chan Wu, Kun-Ta Chuang

Published in: International Journal of Data Science and Analytics | Issue 4/2022

Login to get access
share
SHARE

Abstract

The trend of online shopping has given rise to the growth of signed-for delivery services. Signed-for delivery is a reliable way of getting proof of delivery that ensures your parcel must be signed for upon its arrival with the recipient. However, due to the unknown of recipient occupancy, general signed-for delivery is not very effective for delivery drivers. Once the recipients are not available upon drivers’ arrival, drivers have to arrange revisiting the recipients, causing the resource waste and being overworked. In this paper, we address an important issue on the revisiting-free itinerary planning and propose a novel interactive planning system, called COKI, to interactively plan the effective delivery itineraries with a round-by-round strategy. The flow enables delivery drivers to take a shorter itinerary without revisiting any recipient. Our experimental studies on real data show that, without properly considering the issues in revisiting-free paradigm, the extension of state-of-the-art routing algorithms can only achieve sub-optimal results. Furthermore, the COKI framework can efficiently discover better revisiting-free itinerary for signed-for delivery in an interactive fashion.
Literature
2.
go back to reference Abou-Rjeili, A., Karypis, G.: Multilevel algorithms for partitioning power-law graphs. In: Proceedings of the IEEE International Parallel and Distributed Processing Symposium (2006) Abou-Rjeili, A., Karypis, G.: Multilevel algorithms for partitioning power-law graphs. In: Proceedings of the IEEE International Parallel and Distributed Processing Symposium (2006)
3.
go back to reference Alabas-Uslu, C., Dengiz, B.: A self-adaptive local search algorithm for the classical vehicle routing problem. Expert Syst. Appl. 38(7), 8990–8998 (2011) CrossRef Alabas-Uslu, C., Dengiz, B.: A self-adaptive local search algorithm for the classical vehicle routing problem. Expert Syst. Appl. 38(7), 8990–8998 (2011) CrossRef
4.
go back to reference Arora, S.: Polynomial time approximation schemes for euclidean tsp and other geometric problems. In: Proceedings of Conference on Foundations of Computer Science, pp. 2–11 (1996) Arora, S.: Polynomial time approximation schemes for euclidean tsp and other geometric problems. In: Proceedings of Conference on Foundations of Computer Science, pp. 2–11 (1996)
5.
go back to reference Battarra, M., Erdoǧan, G., Laporte, G., Vigo, D.: The traveling salesman problem with pickups, deliveries, and handling costs. Transp. Sci. 44(3), 383–399 (2010) MATHCrossRef Battarra, M., Erdoǧan, G., Laporte, G., Vigo, D.: The traveling salesman problem with pickups, deliveries, and handling costs. Transp. Sci. 44(3), 383–399 (2010) MATHCrossRef
7.
go back to reference Chiu, Y.-P., Lo, S.-K., Hsieh, A.-Y., Hwang, Y.: Exploring why people spend more time shopping online than in offline stores. Comput. Hum. Behav. 95, 24–30 (2019) CrossRef Chiu, Y.-P., Lo, S.-K., Hsieh, A.-Y., Hwang, Y.: Exploring why people spend more time shopping online than in offline stores. Comput. Hum. Behav. 95, 24–30 (2019) CrossRef
8.
go back to reference Deng, Y., Chen, Y., Zhang, Y., Mahadevan, S.: Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment. Appl. Soft Comput. 12(3), 1231–1237 (2012) CrossRef Deng, Y., Chen, Y., Zhang, Y., Mahadevan, S.: Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment. Appl. Soft Comput. 12(3), 1231–1237 (2012) CrossRef
9.
go back to reference Dong, X., Cai, Y.: A novel genetic algorithm for large scale colored balanced traveling salesman problem. Fut. Gen. Comput. Syst. 95, 727–742 (2019) CrossRef Dong, X., Cai, Y.: A novel genetic algorithm for large scale colored balanced traveling salesman problem. Fut. Gen. Comput. Syst. 95, 727–742 (2019) CrossRef
10.
go back to reference Efthymiadis, K., Kudenko, D.: Knowledge revision for reinforcement learning with abstract mdps. In: Proceedings of International Conference on Autonomous Agents and Multiagent Systems, pp. 763–770 (2015) Efthymiadis, K., Kudenko, D.: Knowledge revision for reinforcement learning with abstract mdps. In: Proceedings of International Conference on Autonomous Agents and Multiagent Systems, pp. 763–770 (2015)
11.
go back to reference Ezhilarasi, G.A., Swarup, K.: Network decomposition using Kernighan-Lin strategy aided harmony search algorithm. Swarm Evol. Comput. 7, 1–6 (2012) CrossRef Ezhilarasi, G.A., Swarup, K.: Network decomposition using Kernighan-Lin strategy aided harmony search algorithm. Swarm Evol. Comput. 7, 1–6 (2012) CrossRef
12.
go back to reference Fiosina, J., Fiosins, M.: Selecting the shortest itinerary in a cloud-based distributed mobility network. In: Proceedings of International Conference Distributed Computing and Artificial Intelligence, pp. 103–110 (2013) Fiosina, J., Fiosins, M.: Selecting the shortest itinerary in a cloud-based distributed mobility network. In: Proceedings of International Conference Distributed Computing and Artificial Intelligence, pp. 103–110 (2013)
13.
go back to reference Freund, Y., Mason, L.: The alternating decision tree learning algorithm. In: Proceedings of International Conference on Machine Learning, volume 99, pp. 124–133 (1999) Freund, Y., Mason, L.: The alternating decision tree learning algorithm. In: Proceedings of International Conference on Machine Learning, volume 99, pp. 124–133 (1999)
14.
go back to reference Garcia, F. M., Thomas, P. S.: A meta-mdp approach to exploration for lifelong reinforcement learning. In: Proceedings of International Conference on Autonomous Agents and MultiAgent Systems, pp. 1976–1978 (2019) Garcia, F. M., Thomas, P. S.: A meta-mdp approach to exploration for lifelong reinforcement learning. In: Proceedings of International Conference on Autonomous Agents and MultiAgent Systems, pp. 1976–1978 (2019)
15.
go back to reference Glover, F., Gutin, G., Yeo, A., Zverovich, A.: Construction heuristics for the asymmetric tsp. Eur. J. Oper. Res. 129(3), 555–568 (2001) MathSciNetMATHCrossRef Glover, F., Gutin, G., Yeo, A., Zverovich, A.: Construction heuristics for the asymmetric tsp. Eur. J. Oper. Res. 129(3), 555–568 (2001) MathSciNetMATHCrossRef
16.
go back to reference Gutin, G., Yeo, A.: The greedy algorithm for the symmetric tsp. Algorithmic Oper. Res. 2(1), 1 (2007) MathSciNetMATH Gutin, G., Yeo, A.: The greedy algorithm for the symmetric tsp. Algorithmic Oper. Res. 2(1), 1 (2007) MathSciNetMATH
17.
go back to reference Hasselt, H. V.: Double q-learning. In: Proceedings of Advances in Neural Information Processing Systems, pp. 2613–2621 (2010) Hasselt, H. V.: Double q-learning. In: Proceedings of Advances in Neural Information Processing Systems, pp. 2613–2621 (2010)
18.
go back to reference Hernández-Pérez, H., Salazar-González, J.-J.: The multi-commodity one-to-one pickup-and-delivery traveling salesman problem. Eur. J. Oper. Res. 196(3), 987–995 (2009) MathSciNetMATHCrossRef Hernández-Pérez, H., Salazar-González, J.-J.: The multi-commodity one-to-one pickup-and-delivery traveling salesman problem. Eur. J. Oper. Res. 196(3), 987–995 (2009) MathSciNetMATHCrossRef
19.
go back to reference Huang, R.: Ecommerce in rural areas and environmental sustainability: The last-mile delivery. In: Proceedings of Wuhan International Conference on E-Business, pp. 50 (2017) Huang, R.: Ecommerce in rural areas and environmental sustainability: The last-mile delivery. In: Proceedings of Wuhan International Conference on E-Business, pp. 50 (2017)
20.
go back to reference Johannsen, F., Leist, S., Konadl, D., Basche, M., de Hesselle, B.: Comparison of commercial chatbot solutions for supporting customer interaction. In: Proceedings of European Conference on Information Systems: Beyond Digitization—Facets of Socio-Technical Change, pp. 158–174 (2018) Johannsen, F., Leist, S., Konadl, D., Basche, M., de Hesselle, B.: Comparison of commercial chatbot solutions for supporting customer interaction. In: Proceedings of European Conference on Information Systems: Beyond Digitization—Facets of Socio-Technical Change, pp. 158–174 (2018)
21.
go back to reference Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359–392 (1998) MathSciNetMATHCrossRef Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359–392 (1998) MathSciNetMATHCrossRef
22.
go back to reference Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(2), 291–307 (1970) MATHCrossRef Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(2), 291–307 (1970) MATHCrossRef
23.
go back to reference Kiselev, I., Glaschenko, A., Chevelev, A., Skobelev, P.: Towards an adaptive approach for distributed resource allocation in a multi-agent system for solving dynamic vehicle routing problems. In: Proceedings of AAAI Conference on Artificial Intelligence, pp. 1874–1875 (2007) Kiselev, I., Glaschenko, A., Chevelev, A., Skobelev, P.: Towards an adaptive approach for distributed resource allocation in a multi-agent system for solving dynamic vehicle routing problems. In: Proceedings of AAAI Conference on Artificial Intelligence, pp. 1874–1875 (2007)
24.
go back to reference Kleiminger, W., Beckel, C., Staake, T., Santini, S.: Occupancy detection from electricity consumption data. In: Proceedings of ACM Workshop on Embedded Systems For Energy-Efficient Buildings, pp. 1–8 (2013) Kleiminger, W., Beckel, C., Staake, T., Santini, S.: Occupancy detection from electricity consumption data. In: Proceedings of ACM Workshop on Embedded Systems For Energy-Efficient Buildings, pp. 1–8 (2013)
25.
go back to reference Kool, W., van Hoof, H., Welling, M.: Attention, learn to solve routing problems! In: ICLR (2019) Kool, W., van Hoof, H., Welling, M.: Attention, learn to solve routing problems! In: ICLR (2019)
26.
go back to reference Krening, S., Feigh, K. M.: Effect of interaction design on the human experience with interactive reinforcement learning. In: Proceedings of Conference on Designing Interactive Systems, pp. 1089–1100. ACM (2019) Krening, S., Feigh, K. M.: Effect of interaction design on the human experience with interactive reinforcement learning. In: Proceedings of Conference on Designing Interactive Systems, pp. 1089–1100. ACM (2019)
27.
go back to reference Kröse, B.J.A.: Learning from delayed rewards. Robot. Auton. Syst. 15(4), 233–235 (1995) CrossRef Kröse, B.J.A.: Learning from delayed rewards. Robot. Auton. Syst. 15(4), 233–235 (1995) CrossRef
28.
go back to reference Kuan, C.-P., Young, K.-Y.: Reinforcement learning and robust control for robot compliance tasks. J. Intell. Robot. Syst. 23(2–4), 165–182 (1998) MATHCrossRef Kuan, C.-P., Young, K.-Y.: Reinforcement learning and robust control for robot compliance tasks. J. Intell. Robot. Syst. 23(2–4), 165–182 (1998) MATHCrossRef
29.
30.
go back to reference Laporte, G., Toth, P., Vigo, D.: Vehicle Routing: Historical Perspective and Recent Contributions (2013) Laporte, G., Toth, P., Vigo, D.: Vehicle Routing: Historical Perspective and Recent Contributions (2013)
31.
go back to reference Lawler, E. L., Lenstra, J. K., Kan, A. R., Shmoys, D. B. et al.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985) Lawler, E. L., Lenstra, J. K., Kan, A. R., Shmoys, D. B. et al.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985)
32.
go back to reference Lee, K. C., Lee, W.-C., Zheng, B.: Fast object search on road networks. In: Proceedings of International Conference on Extending Database Technology: Advances in Database Technology, pp. 1018–1029 (2009) Lee, K. C., Lee, W.-C., Zheng, B.: Fast object search on road networks. In: Proceedings of International Conference on Extending Database Technology: Advances in Database Technology, pp. 1018–1029 (2009)
33.
go back to reference Li, J., Du, J., Li, L.: Optimization of vehicle routing problem with fatigue driving based on genetic algorithm. In: Proceedings of Conference on Research in Adaptive and Convergent Systems, pp. 37–42 (2018) Li, J., Du, J., Li, L.: Optimization of vehicle routing problem with fatigue driving based on genetic algorithm. In: Proceedings of Conference on Research in Adaptive and Convergent Systems, pp. 37–42 (2018)
34.
go back to reference Liaw, A., Wiener, M., et al.: Classification and regression by randomforest. R News 2(3), 18–22 (2002) Liaw, A., Wiener, M., et al.: Classification and regression by randomforest. R News 2(3), 18–22 (2002)
35.
36.
go back to reference Lo, K.M., Yi, W., Wong, P.-K., Leung, K.-S., Leung, Y., Mak, T.S.T.: A genetic algorithm with new local operators for multiple traveling salesman problems. Int. J. Comput. Intell. Syst. 11, 692–705 (2018) CrossRef Lo, K.M., Yi, W., Wong, P.-K., Leung, K.-S., Leung, Y., Mak, T.S.T.: A genetic algorithm with new local operators for multiple traveling salesman problems. Int. J. Comput. Intell. Syst. 11, 692–705 (2018) CrossRef
37.
go back to reference M. of Economy Trade and Industry. Social loss caused from parcel redelivery. Agency for Natural Resources and Energy (2015) M. of Economy Trade and Industry. Social loss caused from parcel redelivery. Agency for Natural Resources and Energy (2015)
38.
go back to reference Ohsugi, S., Koshizuka, N.: Delivery route optimization through occupancy prediction from electricity usage. In: Proceedings of Annual Computer Software and Applications Conference, Vol. 1, pp. 842–849 (2018) Ohsugi, S., Koshizuka, N.: Delivery route optimization through occupancy prediction from electricity usage. In: Proceedings of Annual Computer Software and Applications Conference, Vol. 1, pp. 842–849 (2018)
39.
go back to reference Pan, G., Li, K., Ouyang, A., Li, K.: Hybrid immune algorithm based on greedy algorithm and delete-cross operator for solving tsp. Soft Comput. 20, 555–566 (2016) CrossRef Pan, G., Li, K., Ouyang, A., Li, K.: Hybrid immune algorithm based on greedy algorithm and delete-cross operator for solving tsp. Soft Comput. 20, 555–566 (2016) CrossRef
40.
go back to reference Paul, P.V., Ganeshkumar, C., Ponnurangam, D., Baskaran, R.: A novel odv crossover operator-based genetic algorithms for traveling salesman problem. Soft Comput. 1, 1–31 (2020) Paul, P.V., Ganeshkumar, C., Ponnurangam, D., Baskaran, R.: A novel odv crossover operator-based genetic algorithms for traveling salesman problem. Soft Comput. 1, 1–31 (2020)
41.
go back to reference Probst, P.: Hyperparameters, tuning and meta-learning for random forest and other machine learning algorithms. PhD thesis (2019) Probst, P.: Hyperparameters, tuning and meta-learning for random forest and other machine learning algorithms. PhD thesis (2019)
42.
go back to reference Semet, F., Toth, P., Vigo, D.: Classical exact algorithms for the capacitated vehicle routing problem. In: Vehicle Routing, pp. 37–57 (2014) Semet, F., Toth, P., Vigo, D.: Classical exact algorithms for the capacitated vehicle routing problem. In: Vehicle Routing, pp. 37–57 (2014)
43.
go back to reference Soylu, B.: A general variable neighborhood search heuristic for multiple traveling salesmen problem. Comput. Ind. Eng. 90, 390–401 (2015) CrossRef Soylu, B.: A general variable neighborhood search heuristic for multiple traveling salesmen problem. Comput. Ind. Eng. 90, 390–401 (2015) CrossRef
44.
go back to reference Su, J.-r.: Improved particle swarm optimization for multi-object traveling salesman problems. In: Proceedings of International Conference on Natural Computation, pp. 1175–1179 (2011) Su, J.-r.: Improved particle swarm optimization for multi-object traveling salesman problems. In: Proceedings of International Conference on Natural Computation, pp. 1175–1179 (2011)
45.
go back to reference Sutton, R. S., Barto, A. G.: Reinforcement learning: An introduction. Adaptive computation and machine learning. (1998) Sutton, R. S., Barto, A. G.: Reinforcement learning: An introduction. Adaptive computation and machine learning. (1998)
46.
go back to reference Suykens, J.A., Vandewalle, J.: Least squares support vector machine classifiers. Neural Process. Lett. 9(3), 293–300 (1999) CrossRef Suykens, J.A., Vandewalle, J.: Least squares support vector machine classifiers. Neural Process. Lett. 9(3), 293–300 (1999) CrossRef
47.
go back to reference Teng, S.-Y., Wu, S.-C., Chuang, K.-T.: Optimal delivery routing in road network with occupancy detection. In: Proceedings of International Conference on Mobile Data Management (MDM), pp. 575–580 (2019) Teng, S.-Y., Wu, S.-C., Chuang, K.-T.: Optimal delivery routing in road network with occupancy detection. In: Proceedings of International Conference on Mobile Data Management (MDM), pp. 575–580 (2019)
48.
go back to reference Van Hasselt, H., Guez, A., Silver, D.: Deep reinforcement learning with double q-learning. In Proceedings of of AAAI Conference on Artificial Intelligence, pp. 2094–2100 (2016) Van Hasselt, H., Guez, A., Silver, D.: Deep reinforcement learning with double q-learning. In Proceedings of of AAAI Conference on Artificial Intelligence, pp. 2094–2100 (2016)
49.
go back to reference Wang, C., Lin, M., Zhong, Y., Zhang, H.: Solving travelling salesman problem using multiagent simulated annealing algorithm with instance-based sampling. Int. J. Comput. Sci. Math. 6(4), 336–353 (2015) MathSciNetMATHCrossRef Wang, C., Lin, M., Zhong, Y., Zhang, H.: Solving travelling salesman problem using multiagent simulated annealing algorithm with instance-based sampling. Int. J. Comput. Sci. Math. 6(4), 336–353 (2015) MathSciNetMATHCrossRef
50.
go back to reference Wang, C., Lin, M., Zhong, Y., Zhang, H.: Swarm simulated annealing algorithm with knowledge-based sampling for travelling salesman problem. Int. J. Intell. Syst. Technol. Appl. 15, 74–94 (2016) Wang, C., Lin, M., Zhong, Y., Zhang, H.: Swarm simulated annealing algorithm with knowledge-based sampling for travelling salesman problem. Int. J. Intell. Syst. Technol. Appl. 15, 74–94 (2016)
51.
go back to reference Wei, L., Zhang, Z., Zhang, D., Leung, S.C.: A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints. Eur. J. Oper. Res. 265(3), 843–859 (2018) MathSciNetMATHCrossRef Wei, L., Zhang, Z., Zhang, D., Leung, S.C.: A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints. Eur. J. Oper. Res. 265(3), 843–859 (2018) MathSciNetMATHCrossRef
52.
go back to reference Xu, D., Weise, T., Wu, Y., Lässig, J., Chiong, R.: An investigation of hybrid tabu search for the traveling salesman problem. In: Proceedings of International on Bio-Inspired Computing-Theories and Applications, pp. 523–537. Springer (2015) Xu, D., Weise, T., Wu, Y., Lässig, J., Chiong, R.: An investigation of hybrid tabu search for the traveling salesman problem. In: Proceedings of International on Bio-Inspired Computing-Theories and Applications, pp. 523–537. Springer (2015)
53.
go back to reference Xu, Z., Rodrigues, B.: An extension of the christofides heuristic for the generalized multiple depot multiple traveling salesmen problem. Eur. J. Oper. Res. 257(3), 735–745 (2017) MathSciNetMATHCrossRef Xu, Z., Rodrigues, B.: An extension of the christofides heuristic for the generalized multiple depot multiple traveling salesmen problem. Eur. J. Oper. Res. 257(3), 735–745 (2017) MathSciNetMATHCrossRef
Metadata
Title
Interactive planning of revisiting-free itinerary for signed-for delivery
Authors
Lo Pang-Yun Ting
Shan-Yun Teng
Szu-Chan Wu
Kun-Ta Chuang
Publication date
26-05-2022
Publisher
Springer International Publishing
Published in
International Journal of Data Science and Analytics / Issue 4/2022
Print ISSN: 2364-415X
Electronic ISSN: 2364-4168
DOI
https://doi.org/10.1007/s41060-022-00333-0

Other articles of this Issue 4/2022

International Journal of Data Science and Analytics 4/2022 Go to the issue

Premium Partner