کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4959356 1445946 2017 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Dynamic penalization of fractional directions in the integral simplex using decomposition: Application to aircrew scheduling
ترجمه فارسی عنوان
جریمه دینامیکی جهت های کسری در ساده سازی انتگرال با استفاده از تجزیه: برنامه ریزی برای برنامه ریزی هواپیما
کلمات کلیدی
برنامه ریزی عدد صحیح الگوریتم های اولیه، یکپارچه ساده عادی سازی، برنامه ریزی هواپیما،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
To solve integer linear programs, primal algorithms follow an augmenting sequence of integer solutions leading to an optimal solution. In this work, we focus on a particular primal algorithm, the integral simplex using decomposition (ISUD). To find the next point, one solves a linear program to select an augmenting direction for the current point from a cone of feasible directions. To ensure that this linear program is bounded, a normalization constraint is added and the optimization is performed on a section of the cone. The solution of the linear program, i.e., the direction proposed by the algorithm, strongly depends on the chosen normalization weights, and so does the likelihood that the next solution is integer. We modify ISUD so that the normalization is dynamically updated whenever the direction leads to a fractional solution, to penalize that direction. We propose update strategies, based on new theoretical and experimental results. To prove the efficiency of our strategies, we show that our version of the algorithm yields better results than the former version and than classical branch-and-bound techniques on a benchmark of industrial aircrew scheduling instances. The benchmark that we propose here is, to the best of our knowledge, comparable to no other from the literature. It provides large-scale instances with up to 1700 flights and 115,000 pairings, hence as many constraints and variables, and the instances are given in a set-partitioning form together with initial solutions that accurately mimic those of industrial applications. Our work shows the strong potential of primal algorithms for the crew scheduling problem, which is a key challenge for large airlines.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 263, Issue 3, 16 December 2017, Pages 1007-1018
نویسندگان
, , , ,