Lagrangian Relaxation in Iterated Local Search for the Workforce Scheduling and Routing Problem

Publication Type:
Conference Proceeding
Citation:
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2019, 11544 LNCS pp. 527 - 540
Issue Date:
2019-01-01
Filename Description Size
Lagrangian_In_WSRP.pdfAccepted Manuscript version440.32 kB
Adobe PDF
Full metadata record
© 2019, Springer Nature Switzerland AG. The efficiency of local search algorithms for vehicle routing problems often increases if certain constraints can be violated during the search. The penalty for such violation is included as part of the objective function. Each constraint, which can be violated, has the associated parameters that specify the corresponding penalty. The values of these parameters and the method of their modification are usually a result of computational experiments with no guarantee that the obtained values and methods are equally suitable for other instances. In order to make the optimisation procedure more robust, the paper suggests to view the penalties as Lagrange multipliers and modify them as they are modified in Lagrangian relaxation. It is shown that such modification of the Xie-Potts-Bektaş Algorithm for the Workforce Scheduling and Routing Problem permits to achieve without extra tuning the performance comparable with that of the original Xie-Potts-Bektaş Algorithm.
Please use this identifier to cite or link to this item: