Optimization Online


Capacitated ring arborescence problems with profi ts

Alessandro Alessandro (alessandro.hill***at***uai.cl)
Roberto Baldacci (r.baldacci***at***unibo.it)
Edna Ayako Hoshino (eah***at***facom.ufms.br)

Abstract: In this work we introduce profit-oriented capacitated ring arborescence problems and present exact and heuristic algorithms. These combinatorial network design problems ask for optimized bi-level networks taking into account arc costs and node profits. Solutions combine circuits on the inner level with arborescences on the outer level of the networks. We consider the prize-collecting, the budget-constrained and the target-profit models and develop corresponding exact branch and cut algorithms based on mixed integer formulations and valid inequalities. Iterated local search heuristics based on the exploration of problem specific neighborhoods are elaborated to strengthen the upper bounds. For a set of hard literature derived instances with up to 51 nodes, we provide computational results which give evidence for the efficiency of the proposed approaches. Furthermore, we extensively analyze the performance of our methods, the obtained solution networks and the impact of the cutting planes on the obtained lower bounds.

Keywords: ring arborescence problem, vehicle routing problem; prize-collecting Steiner tree problem; network design; mathematical programming

Category 1: Network Optimization

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Applications -- OR and Management Sciences (Transportation )


Download: [PDF]

Entry Submitted: 01/19/2017
Entry Accepted: 01/19/2017
Entry Last Modified: 01/19/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society