Modeling and solving the non-smooth arc routing problem with realistic soft constraints. (15th May 2018)

• Record Type: Journal Article
• Authors: de Armas, Jesica; Ferrer, Albert; Juan, Angel A.; Lalla-Ruiz, Eduardo
• Is Part Of: Expert systems with applications. Volume 98(2018)
• Page Start: 205
• Page End: 220
• Publication Date: 2018-05-15
• Subjects: Arc routing problem -- Soft constraints -- Non-smooth optimization -- Biased-randomization -- Metaheuristics; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2018.01.020
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A realistic version of the arc routing problem with soft constraints is analyzed. Soft constraints might cause non-smooth objective functions challenging to optimize. A novel mathematical model for the non-smooth arc routing problem is introduced. A heuristic combining biased randomization with iterated local search is proposed. We improve previous works, a linearized version of the problem is solved with CPLEX. Abstract: This paper considers the non-smooth arc routing problem (NS-ARP) with soft constraints in order to capture in more perceptive way realistic constraints violations arising in transportation and logistics. To appropriately solve this problem, a biased-randomized procedure with iterated local search (BRILS) and a mathematical model for this ARP variant is proposed. An extensive computational study is conducted on rich and diverse problem instances. The results highlight the competitiveness of BRILS in terms of quality and time, where it provides high-quality solutions within reasonable computational times. In the context of real-world environments, the performance exhibited by BRILS motivates its incorporation in intelligent and integrative systems where frequent and fast solutions are required.