×

Data mining-based dispatching system for solving the local pickup and delivery problem. (English) Zbl 1269.90008

Summary: 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.

MSC:

90B06 Transportation, logistics and supply chain management
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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. · doi:10.1287/trsc.1030.0056
[2] Bräsy, O., & Gendreau, M. (2005b). Vehicle routing problem with time windows, part II: metaheuristics. Transportation Science, 39(1), 119–139. · doi:10.1287/trsc.1030.0057
[3] Breiman, L., Friedman, J., Stone, C. J., & Olshen, R. (1984). Classification and regression trees. Belmont: Wadsworth. · Zbl 0541.62042
[4] Campbell, A. M., & Savelsbergh, M. (2004). Efficient insertion heuristics for vehicle routing and scheduling problems. Transportation Science, 38(3), 369–378. · doi:10.1287/trsc.1030.0046
[5] 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. · doi:10.1198/106186004X13064
[6] 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. · Zbl 0579.90095 · doi:10.1016/0377-2217(86)90243-2
[7] Dumas, Y., Desrosiers, J., & Soumis, F. (1991). The pickup and delivery problem with time windows. European Journal of Operational Research, 54(1), 7–22. · Zbl 0736.90028 · doi:10.1016/0377-2217(91)90319-Q
[8] Ekins, S., Shimada, J., & Chang, C. (2006). Application of data mining approaches to drug delivery. Advanced Drug Delivery Reviews, 58, 1409–1430. · doi:10.1016/j.addr.2006.09.005
[9] 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. · doi:10.1111/j.1475-3995.2000.tb00196.x
[10] 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. · Zbl 1122.90400 · doi:10.1007/s10732-005-1997-2
[11] Holsapple, C. W., Lee, A., & Otto, J. (1997). A machine learning method for multi-expert decision support. Annals of Operations Research, 75, 171–188. · Zbl 0895.90127 · doi:10.1023/A:1018955328719
[12] Li, X., & Ólafsson, S. (2005). Discovering dispatching rules using data mining. Journal of Scheduling, 8, 515–527. · Zbl 1123.90031 · doi:10.1007/s10951-005-4781-0
[13] 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. · doi:10.1109/TASE.2005.853472
[14] Lim, A., Wang, F., & Xu, Z. (2006). A transportation problem with minimum quantity commitment. Transportation Science, 40(1), 117–129. · doi:10.1287/trsc.1050.0123
[15] Liu, H., & Motoda, H. (1998). Feature extraction, construction and selection: a data mining perspective. Norwell: Kluwer Academic. · Zbl 0912.00012
[16] 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. · doi:10.1006/cbmr.1993.1005
[17] 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. · doi:10.1142/S1469026803000835
[18] 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. · doi:10.1016/S0191-2615(99)00016-8
[19] 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. · doi:10.1109/TASE.2008.916761
[20] 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. · Zbl 0899.90113 · doi:10.1023/A:1018902200919
[21] Powell, W. B., & Carvalho, T. (1998). Dynamic control of logistics queueing networks for large scale fleet management. Transportation Science, 32(2), 90–109. · Zbl 0987.90016 · doi:10.1287/trsc.32.2.90
[22] 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. · Zbl 1134.90528 · doi:10.1287/trsc.36.2.231.561
[23] Quinlan, J. R. (1986). Induction of decision tree. Machine Learning, 1(1), 81–106.
[24] 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. · doi:10.1080/07408179208964213
[25] Shi, L., & Ólafsson, S. (2000). Nested partitions method for global optimization. Operations Research, 48(3), 390–407. · Zbl 1106.90368 · doi:10.1287/opre.48.3.390.12436
[26] Wang, X., & Regan, A. C. (2002). Local truckload pickup and delivery with hard time window constraints. Transportation Research. Part B, 36, 78–94. · doi:10.1016/S0965-8564(00)00037-9
[27] Witten, I. H., & Frank, E. (2005). Data mining: practical machine learning tools and techniques (second ed.). San Mateo: Morgan Kaufmann. · Zbl 1076.68555
[28] Xu, H., Chen, Z. L., Rajagopal, S., & Arunapuram, S. (2001). Solving a practical pickup and delivery problem. Transportation Science, 37(3), 347–364. · doi:10.1287/trsc.37.3.347.16044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.