×

zbMATH — the first resource for mathematics

A hybrid constraint programming approach to the log-truck scheduling problem. (English) Zbl 1231.90186
Summary: Scheduling problems in the forest industry have received significant attention in the recent years and have contributed many challenging applications for optimization technologies. This paper proposes a solution method based on constraint programming and mathematical programming for a log-truck scheduling problem. The problem consists of scheduling the transportation of logs between forest areas and woodmills, as well as routing the fleet of vehicles to satisfy these transportation requests. The objective is to minimize the total cost of the non-productive activities such as the waiting time of trucks and forest log-loaders and the empty driven distance of vehicles. We propose a constraint programming model to address the combined scheduling and routing problem and an integer programming model to deal with the optimization of deadheads. Both of these models are combined through the exchange of global constraints. Finally the whole approach is validated on real industrial data.

MSC:
90B35 Deterministic scheduling theory in operations research
90C10 Integer programming
Software:
OPL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersson, G., Flisberg, P., Liden, P., & Rönnqvist, M. (2008). RuttOpt–a decision support system for routing of logging trucks. Canadian Journal of Forest Research, 38, 1784–1796. · doi:10.1139/X08-017
[2] Bredström, D., & Rönnqvist, M. (2008). Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. European Journal of Operational Research, 191(1), 19–31. · Zbl 1146.90364 · doi:10.1016/j.ejor.2007.07.033
[3] Baptiste, P., LePape, C., & Nuijten, W. (1995). Constraint-based optimization and approximation for job-shop scheduling. In AAAI-SIGMAN workshop on intelligent manufacturing systems, IJCAI’95 (pp. 5–16). Montreal, Canada.
[4] Baptiste, P., LePape, C., & Nuijten, W. (2001). Constraint-based scheduling. Dordrecht: Kluwer Academic. · Zbl 1094.90002
[5] Fahle, T., & Sellmann, M. (2000). Constraint programming based column generation with knapsack subproblems. In Proceeding of the international workshop on integration of AI and OR techniques in constraint programming for combinatorial optimisation problems (CP-AI-OR’00) (pp. 33–43).
[6] Freling, R., Huisman, D., & Wagelmans, A. P. M. (2003). Models and algorithms for integration of vehicle and crew scheduling. Journal of Scheduling, 6, 63–85. · Zbl 1154.90449 · doi:10.1023/A:1022287504028
[7] Flisberg, P., Liden, B., & Rönnqvist, M. (2010, in press). A hybrid method based on linear programming and tabu search for routing of logging trucks. Computers and Operations Research.
[8] Gronalt, M., & Hirsch, P. (2007). Log-truck scheduling with tabu search strategy. Metaheuristics, 39, 65–88. · Zbl 1172.90400
[9] Haase, K., Desaulniers, G., & Desrosiers, J. (2001). Simultaneous vehicle and crew scheduling in urban mass transit systems. Transportation Science, 35(3), 286–303. · Zbl 1069.90528 · doi:10.1287/trsc.35.3.286.10153
[10] Hooker, J. N. (2005). A hybrid method for the planning and scheduling. Constraints, 10(4), 385–401. · Zbl 1122.90054 · doi:10.1007/s10601-005-2812-2
[11] Linnainmaa, S., Savalo, J., & Jokinen, O. (1995). EPO: A knowledge based system for wood procurement management. Paper presented at the 7th Annual Conference on Artifical Intelligence, Montreal.
[12] Michaelsen, J. (1994). Productivité des chargeuses de bois courts (Communiqué Technique N: Chargement et Camionnage-37 Sommaire de rapport interne de FERIC).
[13] Milano, M. (2004). Constraint and integer programming. Dordrecht: Kluwer Academic. · Zbl 1078.90055
[14] Murphy, G. (2003). Reducing trucks on the road through optimal route scheduling and shared log transport services. Southern Journal of Applied Forestry, 27(3), 198–205.
[15] Palmgren, M., Rönnqvist, M., & Värbrand, P. (2003). A solution approach for log truck scheduling based on composite pricing and branch and bound. International Transactions in Operational Research, 10, 433–447. · Zbl 1106.90316 · doi:10.1111/1475-3995.00420
[16] Palmgren, M., Rönnqvist, M., & Värbrand, P. (2004). A near-exact method for solving the log-truck scheduling problem. International Transactions in Operational Research, 11, 447–464. · Zbl 1131.90362 · doi:10.1111/j.1475-3995.2004.00469.x
[17] Régin, J.-C. (1996). Generalized arc consistency for global cardinality constraint. In Proceedings of AAAI/IAAI (Vol. 1, pp. 209–215). Menlo Park: AAAI Press/The MIT Press.
[18] Rönnqvist, M. (2003). Optimization in forestry. Mathematics Programming, 97, 267–284. · Zbl 1053.90143
[19] Rönnqvist, M., & Ryan, D. (1995). Solving truck dispatch problem in real time. In Proceedings of the 31st annual conference of the Operational Research Society of New Zealand (pp. 165–172). Wellington, New Zealand, 31 August–1 September 1995. Auckland: The Operational Research Society of New Zealand.
[20] Rönnqvist, M., Sahlin, H., & Carlsson, D. (1998). Operative planning and dispatching of forestry transportation (Report LiTH-MAT-R-1998-18). Linköping, Sweden.
[21] Ropke, S., Cordeau, J.-F., & Laporte, G. (2007). Models and branch-and-cut algorithm for pick-up and delivery problems with time windows. Networks, 4(49), 258–272. · Zbl 1141.90340 · doi:10.1002/net.20177
[22] Rousseau, L.-M., Gendreau, M., & Pesant, G. (2002). Solving small VRPTWs with constraint programming based column generation. In Proceeding of the fourth international workshop on integration of AI and OR techniques in constraint programming for combinatorial optimisation problems (CP-AI-OR’02) (pp. 333–344).
[23] Sakkout, H. E., & Wallace, M. (2000). Probe backtrack search for minimal perturbation in dynamic scheduling. Constraints, 5(4), 359–388. · Zbl 0970.68014 · doi:10.1023/A:1009856210543
[24] Sellmann, M., Zervoudakis, K., Stamatopoulos, P., & Fahle, T. (2002). Crew assignment via constraint programming: integrating column generation and heuristic tree search. Annals of Operations Research, 115, 207–225. · Zbl 1013.90091 · doi:10.1023/A:1021105422248
[25] Simonis, H., Charlier, P., & Kay, P. (2000). Constraint handling in an integrated transportation problem. IEEE Intelligent Systems, 15(1), 26–32.
[26] Van Hentenryck, P. (1989). Constraint satisfaction in logic programming. Cambridge: MIT Press. · Zbl 0707.68101
[27] Van Hentenryck, P. (1999). The OPL optimization programming language. Cambridge: MIT Press.
[28] Van Hentenryck, P., Perron, L., & Puget, J.-F. (2000). Search and strategies in OPL. ACM Transactions on Computational Logic, 2(1), 285–320. · Zbl 1365.90281
[29] Weintraub, A., Epstein, R., Morales R, Seron J., & Traverso, P. (1996). A truck scheduling system improves efficiency in the forest industries. Interfaces, 4(26), 1–12. · doi:10.1287/inte.26.4.1
[30] Zweben, M., & Fox, M. (1994). Intelligent scheduling. San Mateo: Morgan Kaufman.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.