Abstract
After giving an introduction to ring tree models and existing solution approaches, we study three new customer profit oriented problems in extended capacitated network design. Two types of customer nodes as well as Steiner nodes can be used in a directed bi-level network.
Type two customers have to be in circuits that intersect in a depot. Type one customers may also be used in arborescences that extend this ring core.
Additional capacity constraints on the number of subnetworks attached to the depot and the number of customers in each of them have to be respected.
Objectives take into account the asymmetric arc costs, customer-dependent profits or both, leading to price-collecting, budget-constrained and target profit problem variants. These network optimization problems generalize prominent problems such as the price-collecting travelling salesman problem and the prize-collecting Steiner Tree problem. We develop problem specific metaheuristic algorithms based on iterated local search to optimize given networks that we obtain from corresponding construction procedures. To compute optimal solutions, we formulate the problem as a cut-set based mixed-integer program and develop various valid inequalities. The results obtained on a set of hard test instances by the corresponding branch and cut method are compared against the heuristic bounds. We also study the impact of our cutting planes from a computational point of view. This presentation is based on joint work with Roberto Baldacci and Edna Hoshino.
Affiliation
School of Business, Universidad Adolfo Ibáñez, Santiago, Chile