Lagrangian Relaxation in Iterated Local Search for the Workforce Scheduling and Routing Problem
- Publication Type:
- Conference Proceeding
- 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:
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 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: