Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
International Journal of Data Science and Analytics
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

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
previous article PARAS: a parameter space-driven approach for complete association rule mining
next article Correction to: Online information disorder: fake news, bots and trolls

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
Literature
1.
2.
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.
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.
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.
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
6.
7.
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.
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.
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.
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.
Ezhilarasi, G.A., Swarup, K.: Network decomposition using Kernighan-Lin strategy aided harmony search algorithm. Swarm Evol. Comput. 7, 1–6 (2012)CrossRef
12.
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.
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.
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.
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.
Gutin, G., Yeo, A.: The greedy algorithm for the symmetric tsp. Algorithmic Oper. Res. 2(1), 1 (2007)MathSciNetMATH
17.
Hasselt, H. V.: Double q-learning. In: Proceedings of Advances in Neural Information Processing Systems, pp. 2613–2621 (2010)
18.
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.
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.
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.
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.
Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(2), 291–307 (1970)MATHCrossRef
23.
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.
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.
Kool, W., van Hoof, H., Welling, M.: Attention, learn to solve routing problems! In: ICLR (2019)
26.
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.
Kröse, B.J.A.: Learning from delayed rewards. Robot. Auton. Syst. 15(4), 233–235 (1995)CrossRef
28.
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.
Laporte, G., Toth, P., Vigo, D.: Vehicle Routing: Historical Perspective and Recent Contributions (2013)
31.
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.
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.
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.
Liaw, A., Wiener, M., et al.: Classification and regression by randomforest. R News 2(3), 18–22 (2002)
35.
36.
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.
M. of Economy Trade and Industry. Social loss caused from parcel redelivery. Agency for Natural Resources and Energy (2015)
38.
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.
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.
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.
Probst, P.: Hyperparameters, tuning and meta-learning for random forest and other machine learning algorithms. PhD thesis (2019)
42.
Semet, F., Toth, P., Vigo, D.: Classical exact algorithms for the capacitated vehicle routing problem. In: Vehicle Routing, pp. 37–57 (2014)
43.
Soylu, B.: A general variable neighborhood search heuristic for multiple traveling salesmen problem. Comput. Ind. Eng. 90, 390–401 (2015)CrossRef
44.
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.
Sutton, R. S., Barto, A. G.: Reinforcement learning: An introduction. Adaptive computation and machine learning. (1998)
46.
Suykens, J.A., Vandewalle, J.: Least squares support vector machine classifiers. Neural Process. Lett. 9(3), 293–300 (1999)CrossRef
47.
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.
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.
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.
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.
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.
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.
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

Correction

Correction to: Online information disorder: fake news, bots and trolls

Regular Paper

Bounding open space risk with decoupling autoencoders in open set recognition

Review

A survey on event and subevent detection from microblog data towards crisis management

Regular Paper

PARAS: a parameter space-driven approach for complete association rule mining

Regular Paper

Multilingual hope speech detection in English and Dravidian languages

Regular Paper

Sample-selection-adjusted random forests

Premium Partner

    Image Credits