The Prize Collecting Connected Subgraph Problem - A New NP-Hard Problem arising in Snow Removal Routing

P. O. Lindberg and Gholamreza Razmara
Additional contact information
P. O. Lindberg: Linköping University
Gholamreza Razmara: Linköping University

A chapter in Operations Research Proceedings 2004, 2005, pp 360-367 from Springer

Abstract: Abstract We consider a new NP-hard optimization problem, the Prize Collecting Connected Subgraph Problem, which appears as a subproblem in routing of snow plows during snow fall. In this problem we have a set of edges in an undirected network, with edge costs and edge times. Moreover there is a time budget. The problem is to find a connected subset (corresponding to a snowplow tour) of minimal cost subject to the budget constraint. This problem can be modeled using flow constraints or introducing valid inequalities. We exemplify computations for the classical Sioux Falls Network

Keywords: Road Segment; Valid Inequality; Undirected Network; Edge Cost; Snow Removal (search for similar items in EconPapers)
Date: 2005
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-540-27679-1_45

Ordering information: This item can be ordered from
http://www.springer.com/9783540276791

DOI: 10.1007/3-540-27679-3_45

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().