An integration of Lagrangian split and VNS: The case of the capacitated vehicle routing problem

详细信息    查看全文

• 作者：Mouaouia Cherif Bouzid^a ; ^b ; ^{cherifmouaouia.bouzid@gmail.com} ; Hacene Aï ; t Haddadene^b ; Said Salhi^c
• 关键词：Routing problems ; Route-first cluster-second ; Lagrangian relaxation ; Subgradient method ; Variable neighbourhood search ; Hybridisation
• 刊名：Computers & Operations Research
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：78
• 期：Complete
• 页码：513-525
• 全文大小：1210 K
• 卷排序：78

文摘

An ILP formulation for the partitioning of a giant tour denoted Split(T) is proposed. Split(T) is tackled using a Lagrangian relaxation method called Lagrangian split (Ls). Ls relies on a repair mechanism mathematically validated. Ls is integrated into a Variable Neighborhood Search (VNS). When tested on benchmark data, Ls and its integration into VNS provide good results.