کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
476236 699432 2008 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem
چکیده انگلیسی

In the integrated vehicle and crew scheduling problem (VCSP) one has to simultaneously assign vehicles to timetabled trips and drivers to vehicles. In this paper, the VCSP is described by an integer linear programming formulation combining a multicommodity network flow model with a set partitioning/covering model.We propose an algorithm that starts with a pre-processing phase to define the set of tasks and to obtain an initial set of duties. In a second phase, we solve the linear programming relaxation of the models using a column generation scheme. Whenever the resulting solution is not integer, branch-and-bound techniques are used over the set of feasible crew duties generated while solving the linear programming relaxation in order to obtain a feasible solution for the VCSP. We show that, under some conditions, just one subset of the decision variables is required to be integer.Computational experience, with randomly generated data publicly available for benchmarking on the WEB is reported, and the results show the effectiveness of our approach concerning both, the quality of the solutions and the CPU time needed to obtain them. Moreover, the approach can be applied to large instances.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 35, Issue 5, May 2008, Pages 1562–1575
نویسندگان
, ,