Shortest paths with exclusive-disjunction arc pairs conflicts. (April 2023)

• Record Type: Journal Article
• Authors: Cerulli, Raffaele; Guerriero, Francesca; Scalzo, Edoardo; Sorgente, Carmine
• Is Part Of: Computers & operations research. Volume 152(2023)
• Publication Date: 2023-04
• Subjects: Shortest path -- Arc conflicts -- Matheuristics -- Web applications; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2023.106158
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: In this paper, a NP -hard variant of the shortest path problem, involving exclusive-disjunction arc pairs conflicts, is introduced. In this framework, a conflict is violated and a penalty has to be paid if either both the arcs in a pair or none of them are selected. The aim is to find a path for which the overall cost, defined as the sum of the costs of the traversed arcs and the penalties of the violated conflicts, is minimized. The proposed variant is used to model web applications test planning scenarios, where a path represents a sequence of web pages and hyperlinks. A proof of the NP -hardness is provided and two mathematical programming formulations are proposed for the problem. The former is an integer linear program relying on auxiliary variables to model conflict violations, while the latter is characterized by a nonlinear objective function, that uses only the arc variables to derive the penalties associated to the violated conflicts. To solve the problem, a two-stage matheuristic algorithm is also presented and its performances are compared with those provided by the best formulation solved by CPLEX. Highlights: We introduce a variant of the shortest path problem yielding effective test paths. We formally prove the NP-hardness of the problem. We provide two mathematical formulations for the problem. We devise a two-stage matheuristic to efficiently solve the problem. We conduct a computational study to evaluate the proposed methods' performances.