Program > By author > Sanchis José Maria

We study a variant of the Directed Rural Postman Problem (DRPP) where profits are associated with arcs to be served, and incompatibility constraints may exist between nodes and profitable arcs leaving them. If convenient, some of the incompatibilities can be removed provided that penalties are paid. The problem looks for a tour starting and ending at the depot that maximizes the difference between collected profits and total cost as sum of traveling costs and paid penalties, while satisfying remaining incompatibilities. The problem, called Directed Profitable Rural Postman Problem with Incompatibility Constraints (DPRPP-IC), originates in the domain of the transportation service procurement where a company (typically a shipper or a carrier) needs to decide which customer transportation requests to serve in a tour while satisfying constraints that may exclude the joint selection of some requests. We propose two problem formulations involving a different number of variables and constraints, and introduce a matheuristic procedure exploiting the presence of the Generalized Independent Set Problem (GISP) and of the Directed Rural Postman Problem (DRPP) as subproblems. Computational results on a large set of instances show how the matheuristic is extremely effective outperforming the result obtained in one hour computing time by a straightforward branch-and-cut approach implemented with IBM CPLEX 12.6.2 on instances with up to 500 nodes, 1535 arcs, 1132 profitable arcs, and 10743 incompatibilities.