Location Routing Problems on Simple Graphs

This paper addresses combined location/routing problems defined on trees. Several problems are studied, which consider service demand both at the vertices and the edges of the input tree. Greedy type optimal heuristics are presented for the cases when all vertices have to be visited and facilities have no set-up costs. Facilities set-up costs can also … Read more

The Facility Location Problem with Bernoulli Demands

In this paper we address a discrete capacitated facility location problem in which customers have Bernoulli demands. The problem is formulated as a two-stage stochastic program. The goal is to define an a priori solution for the location of the facilities and for the allocation of customers to the operating facilities that minimize the expected … Read more

Solving the Prize-collecting Rural Postman Problem

In this work we present an algorithm for solving the Prize-collecting Rural Postman Problem. This problem was recently defined and is a generalization of other arc routing problems like, for instance, the Rural Postman Problem. The main difference is that there are no required edges. Instead, there is a profit function on the edges that … Read more

A simple exact separation algorithm for 2-matching inequalities.

In this work we present an exact separation algorithm for the so called co-circuit inequalities, otherwise known as parity or 2-matching inequalities. The algorithm is quite simple since it operates on the tree of min-cuts of the support graph of the solution to separate, relative to an ad hoc capacity vector. The order of our … Read more