Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Data mining-based dispatching system for solving the local pickup and delivery problem

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The Local Pickup and Delivery Problem (LPDP) has drawn much attention, and optimization models and algorithms have been developed to address this problem. However, for real world applications, the large-scale and dynamic nature of the problem causes difficulties in getting good solutions within acceptable time through standard optimization approaches. Meanwhile, actual dispatching solutions made by field experts in transportation companies contain embedded dispatching rules. This paper introduces a Data Mining-based Dispatching System (DMDS) to first learn dispatching rules from historical data and then generate dispatch solutions, which are shown to be as good as those generated by expert dispatchers in the intermodal freight industry. Three additional benefits of DMDS are: (1) it provides a simulation platform for strategic decision making and analysis; (2) the learned dispatching rules are valuable to combine with an optimization algorithm to improve the solution quality for LPDPs; (3) by adding optimized solutions to the training data, DMDS is capable to generate better-than-actuals solutions very quickly.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Algorithm 1
Fig. 4
Algorithm 2
Algorithm 3

Similar content being viewed by others

References

  • Bräsy, O., & Gendreau, M. (2005a). Vehicle routing problem with time windows, part I: route construction and local search algorithms.Transportation Science,39(1), 104–118.

    Article  Google Scholar 

  • Bräsy, O., & Gendreau, M. (2005b). Vehicle routing problem with time windows, part II: metaheuristics.Transportation Science,39(1), 119–139.

    Article  Google Scholar 

  • Breiman, L., Friedman, J., Stone, C. J., & Olshen, R. (1984).Classification and regression trees. Belmont: Wadsworth.

    Google Scholar 

  • Campbell, A. M., & Savelsbergh, M. (2004). Efficient insertion heuristics for vehicle routing and scheduling problems.Transportation Science,38(3), 369–378.

    Article  Google Scholar 

  • Chan, K. Y., & Loh, W. Y. (2004). Lotus: an algorithm for building accurate and comprehensible logistic regression trees.Journal of Computational and Graphical Statistics,13(4), 826–852.

    Article  Google Scholar 

  • Desrosiers, J., Soumis, F., Desrochers, M., & SauvéGerad, M. (1986). Methods for routing with time windows.European Journal of Operational Research,23(2), 236–245.

    Article  Google Scholar 

  • Dumas, Y., Desrosiers, J., & Soumis, F. (1991). The pickup and delivery problem with time windows.European Journal of Operational Research,54(1), 7–22.

    Article  Google Scholar 

  • Ekins, S., Shimada, J., & Chang, C. (2006). Application of data mining approaches to drug delivery.Advanced Drug Delivery Reviews,58, 1409–1430.

    Article  Google Scholar 

  • Fagerholt, K., & Christiansen, M. (2000). A travelling salesman problem with allocation, time window and precedence constraints—an application to ship scheduling.International Transactions in Operational Research,7(3), 231–244.

    Article  Google Scholar 

  • Funke, B., Grunert, T., & Irnich, S. (2005). Local search for vehicle routing and scheduling problems: review and conceptual integration.Journal of Heuristics,11(4), 267–306.

    Article  Google Scholar 

  • Holsapple, C. W., Lee, A., & Otto, J. (1997). A machine learning method for multi-expert decision support.Annals of Operations Research,75, 171–188.

    Article  Google Scholar 

  • Li, X., & Ólafsson, S. (2005). Discovering dispatching rules using data mining.Journal of Scheduling,8, 515–527.

    Article  Google Scholar 

  • Lim, A., & Wang, F. (2005). Multi-depot vehicle routing problem: a one-stage approach.IEEE Transactions on Automation Science and Engineering,2(4), 397–402.

    Article  Google Scholar 

  • Lim, A., Wang, F., & Xu, Z. (2006). A transportation problem with minimum quantity commitment.Transportation Science,40(1), 117–129.

    Article  Google Scholar 

  • Liu, H., & Motoda, H. (1998).Feature extraction, construction and selection: a data mining perspective. Norwell: Kluwer Academic.

    Book  Google Scholar 

  • Long, W. J., Griffith, J. L., & Selker, H. P. (1993). A comparison of logistic regression to decision-tree induction in a medical domain.Computers and Biomedical Research,26, 74–97.

    Article  Google Scholar 

  • Mourkousis, G., Protonotarios, M., & Varvarigou, T. (2003). Application of genetic algorithms to a large-scale multiple-constraint vehicle routing problem.International Journal of Computational Intelligence and Applications,3(1), 1–21.

    Article  Google Scholar 

  • Nanry, W. P., & Barnes, J. W. (2000). Solving the pickup and delivery problem with time windows using reactive tabu search.Transportation Research. Part B,34(2), 107–121.

    Article  Google Scholar 

  • Pi, L., Pan, Y., & Shi, L. (2008). Hybrid nested partitions and mathematical programming approach and its applications.IEEE Transactions on Automation Science and Engineering,5(4), 573–586.

    Article  Google Scholar 

  • Piramuthu, S., Raman, N., & Shaw, M. J. (1998). Decision support system for scheduling a flexible flow system: incorporation of feature construction.Annals of Operations Research,78, 219–234.

    Article  Google Scholar 

  • Powell, W. B., & Carvalho, T. (1998). Dynamic control of logistics queueing networks for large scale fleet management.Transportation Science,32(2), 90–109.

    Article  Google Scholar 

  • Powell, W. B., Shapiro, J., & Simao, H. P. (2002). An adaptive, dynamic programming algorithm for the heterogeneous resource allocation problem.Transportation Science,36(2), 231–249.

    Article  Google Scholar 

  • Quinlan, J. R. (1986). Induction of decision tree.Machine Learning,1(1), 81–106.

    Google Scholar 

  • Shaw, M. J., Park, S. C., & Raman, N. (1992). Intelligent scheduling with machine learning capabilities: the induction of scheduling knowledge.IIE Transactions,24(2), 156–168.

    Article  Google Scholar 

  • Shi, L., & Ólafsson, S. (2000). Nested partitions method for global optimization.Operations Research,48(3), 390–407.

    Article  Google Scholar 

  • Wang, X., & Regan, A. C. (2002). Local truckload pickup and delivery with hard time window constraints.Transportation Research. Part B,36, 78–94.

    Article  Google Scholar 

  • Witten, I. H., & Frank, E. (2005).Data mining: practical machine learning tools and techniques (second ed.). San Mateo: Morgan Kaufmann.

    Google Scholar 

  • Xu, H., Chen, Z. L., Rajagopal, S., & Arunapuram, S. (2001). Solving a practical pickup and delivery problem.Transportation Science,37(3), 347–364.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Industrial and Systems Engineering, University of Wisconsin-Madison, Madison, WI, 53706, USA

    Weiwei Chen, Leyuan Shi & Liang Pi

  2. Dept. of Industrial Engineering and Management, Peking University, Beijing, 100871, China

    Jie Song

  3. Schneider National Inc., Green Bay, WI, 54306, USA

    Peter Sun

Authors
  1. Weiwei Chen

    You can also search for this author inPubMed Google Scholar

  2. Jie Song

    You can also search for this author inPubMed Google Scholar

  3. Leyuan Shi

    You can also search for this author inPubMed Google Scholar

  4. Liang Pi

    You can also search for this author inPubMed Google Scholar

  5. Peter Sun

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toWeiwei Chen.

Rights and permissions

About this article

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp