A heuristic to solve the synchronized log-truck scheduling problem

被引:54
作者
El Hachemi, Nizar [1 ]
Gendreau, Michel [1 ]
Rousseau, Louis-Martin [1 ]
机构
[1] Interuniv Res Ctr Enterprise Networks Logist & Tr, Montreal, PQ H3C 3J7, Canada
关键词
Synchronized routing; Scheduling; Forestry; Local search; Constraint-based local search and constraint programming; VEHICLE-ROUTING PROBLEM; SEARCH; OPTIMIZATION; SYSTEM; PICKUP;
D O I
10.1016/j.cor.2011.02.002
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
We present a synchronized routing and scheduling problem that arises in the forest industry, as a variation of the log-truck scheduling problem. It combines routing and scheduling of trucks with specific constraints related to the Canadian forestry context. This problem includes aspects such as pick-up and delivery, multiple products, inventory stock, multiple supply points and multiple demand points. We developed a decomposition approach to solve the weekly problem in two phases. In the first phase we use a MIP solver to solve a tactical model that determines the destinations of full truckloads from forest areas to woodmills. In the second phase, we make use of two different methods to route and schedule the daily transportation of logs: the first one consists in using a constraint-based local search approach while the second one is a hybrid approach involving a constraint programming based model and a constraint-based local search model. These approaches have been implemented using COMET2.0. The method, was tested on two industrial cases from forest companies in Canada. (c) 2011 Elsevier Ltd. All rights reserved.
引用
收藏
页码:666 / 673
页数:8
相关论文
共 37 条
[1]   RuttOpt - a decision support system for routing of logging trucks [J].
Andersson, Gert ;
Flisberg, Patrik ;
Liden, Bertil ;
Ronnqvist, Mikael .
CANADIAN JOURNAL OF FOREST RESEARCH, 2008, 38 (07) :1784-1796
[2]  
[Anonymous], 1989, Constraint Satisfaction in Logic Programming
[3]  
Baptiste P., 1995, Proceedings of AAAI-SIGMAN Workshop on Intelligent Manufacturing Systems, P5
[4]  
Baptiste P., 2001, Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems
[5]   A reactive variable neighborhood search for the vehicle-routing problem with time windows [J].
Bräysy, O .
INFORMS JOURNAL ON COMPUTING, 2003, 15 (04) :347-368
[6]   Combined vehicle routing and scheduling with temporal precedence and synchronization constraints [J].
Bredstrom, David ;
Ronnqvist, Mikael .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 191 (01) :19-31
[7]  
Cordeau JF, 2002, SIAM MONOG DISCR MAT, P157
[8]   THE PICKUP AND DELIVERY PROBLEM WITH TIME WINDOWS [J].
DUMAS, Y ;
DESROSIERS, J ;
SOUMIS, F .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1991, 54 (01) :7-22
[9]   A hybrid constraint programming approach to the log-truck scheduling problem [J].
El Hachemi, Nizar ;
Gendreau, Michel ;
Rousseau, Louis-Martin .
ANNALS OF OPERATIONS RESEARCH, 2011, 184 (01) :163-178
[10]   LAPS CARE -: an operational system for staff planning of home care [J].
Eveborn, P ;
Flisberg, P ;
Rönnqvist, M .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 171 (03) :962-976