Sachverhalt:
A.
A._ ist Eigentümer der Parzelle Nr. 1051 im Gebiet B._, Gemeinde Heiden. Am 17. Juni 2008 genehmigte der Regierungsrat von Appenzell Ausserrhoden im südlichen Teil der Parzelle die Deponiezone B._ sowie den Quartierplan B._ mit einem Deponievolumen von 85'000 m3.
Seit dem Jahr 2011 beabsichtigt A._ die Deponiezone zu erweitern, weshalb er mehrere Projektänderungsgesuche einreichen liess. Das kantonale Planungsamt (heute: Abteilung Raumentwicklung) kam in verschiedenen Vorprüfungsberichten zum Ergebnis, dass dem Beschwerdeführer keine positive Beurteilung in Aussicht gestellt werden könne.
B.
Aufgrund einer Strafanzeige des Oberforstamts vom 9. Oktober 2012 wurde eine Deponievermessung durch ein externes Vermessungsbüro angeordnet. Diese ergab, dass in der Deponie B._ anstelle des bewilligten Volumens von 85'000 m3 insgesamt 114'500 m3 Deponiematerial aufgeschüttet worden war. Davon befanden sich 4000 m3 zwischen dem Deponieperimeter und dem Wald und ca. 2000 m3 Schüttmaterial im Wald.
Am 11. Oktober 2012 erliess die Kommission Planung und Baubewilligung einen Zulieferstopp. Anlässlich des Augenscheins vom 21. Mai 2013 wurde beschlossen, dass A._ bis Ende Juni 2013 ein Umgestaltungsprojekt einzureichen habe.
Am 1. Juli 2013 reichte A._ Korrektureingaben zum Teilzonen- und Quartierplan, ein Rodungsgesuch sowie ein modifiziertes Baugesuch ein. Nach der Durchführung eines Mitberichtverfahrens teilte das Planungsamt A._ am 4. Oktober 2013 mit, dass für das Vorhaben keine Genehmigung in Aussicht gestellt werden könne. Auf Antrag von A._ wurden die Unterlagen öffentlich aufgelegt und ein Einspracheverfahren durchgeführt.
Am 19. Januar 2015 verweigerte das Departement Volks- und Landwirtschaft A._ eine Ausnahmebewilligung zur Rodung von Wald für die geplante Erweiterung der Deponiezone auf der Parzelle Nr. 1051 und verfügte, das zweckentfremdete Waldareal sei wiederherzustellen. Mit Entscheid vom 10. Februar 2015 verweigerte das damalige Departement Bau und Umwelt das Gesuch zur Änderung der Deponieplanung. Beide Entscheide erwuchsen unangefochten in Rechtskraft.
C.
Am 8. September 2015 reichte die C._ AG im Auftrag von A._ ein weiteres Projektänderungsgesuch zur Vorprüfung ein.
Mit Entscheid vom 11. Dezember 2015 trat das Departement Bau und Umwelt (heute: Departement für Bau und Volkswirtschaft; nachfolgend: Departement) auf das Vorprüfungsgesuch nicht ein, weil die Planung Komponenten enthalte, auf welche bereits in früheren Stellungnahmen kein Antrag auf Genehmigung habe in Aussicht gestellt werden können; teilweise gehe es sogar über dasjenige hinaus, was in früheren Vorprüfungen bzw. durch das Departement abgelehnt worden sei.
Dagegen erhob A._ am 30. Dezember 2015 Rekurs beim Regierungsrat Appenzell Ausserrhoden. Dieser wies den Rekurs am 13. März 2018 ab, wogegen A._ am 17. April 2018 Beschwerde beim Obergericht Appenzell Ausserrhoden erhob.
Das Obergericht wies die Beschwerde am 24. Januar 2019 ab. Auf Antrag von A._ wurde der Enscheid begründet und am 9. Mai 2019 versandt.
D.
Dagegen hat A._ am 6. Juni 2019 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht erhoben. Er beantragt, der angefochtene Entscheid sei aufzuheben und die Angelegenheit sei zur materiellen Prüfung an das Departement zurückzuweisen.
E.
Das Obergericht und die Kantonskanzlei (namens des Regierungsrats und des Departements) beantragen die Abweisung der Beschwerde. Die Einwohnergemeinde Heiden hat auf eine Stellungnahme verzichtet. Das Bundesamt für Raumentwicklung (ARE) verweist auf die zutreffenden Erwägungen des angefochtenen Entscheids.
Mit Replik vom 3. Oktober 2019 hält der Beschwerdeführer an seinem Antrag und seinen Vorbringen fest.

Erwägungen:
1.
Gegen den kantonal letztinstanzlichen Endentscheid des Obergerichts steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht offen (Art. 82 lit. a, 86 Abs. 1 lit. d und 90 BGG). Der Beschwerdeführer ist als Gesuchsteller befugt, mit Beschwerde überprüfen zu lassen, ob das Departement auf sein Vorprüfungsgesuch vom 8. September 2015 hätte eintreten müssen (<ref-law>). Auf die rechtzeitig erhobene Beschwerde (<ref-law>) ist daher grundsätzlich einzutreten.
Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann insbesondere die Verletzung von Bundesrecht gerügt werden (<ref-law>). Das Bundesgericht wendet dieses grundsätzlich von Amtes wegen an (<ref-law>). Die Verletzung von Grundrechten (einschliesslich die willkürliche Anwendung von kantonalem Recht) prüft es dagegen nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und genügend begründet worden ist (<ref-law>). Dafür gelten qualifizierte Begründungsanforderungen (<ref-ruling> E. 1.4.2 S. 254 mit Hinweisen). Ob diese erfüllt sind, ist im Zusammenhang mit den jeweiligen Rügen zu prüfen.
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat, sofern dieser nicht offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Art. 105 und Art. 97 Abs. 1 BGG). Neue Tatsachen und Beweismittel können nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>). Echte Noven, d.h. Tatsachen, die erst nach dem angefochtenen Urteil eingetreten sind, bleiben im bundesgerichtlichen Verfahren unberücksichtigt (<ref-ruling> E. 3.1.2 S. 123; <ref-ruling> E. 5.2.4 S. 229; <ref-ruling> E. 2.1 S. 343 f.). Soweit sich der Beschwerdeführer daher auf ein Schreiben der kantonalen Abteilung Raumenwicklung zum Deponiebedarf vom 13. Mai 2019 beruft, ist darauf nicht weiter einzugehen.
2.
2.1. Die Vorinstanz erwog, dass es sich beim Teilzonenplan und dem Quartierplan B._ um kantonale Nutzungspläne handle. Nutzungspläne seien gemäss Art. 21 Abs. 2 RPG zu überprüfen und allenfalls anzupassen, wenn sich die Verhältnisse erheblich geändert hätten. Dabei sei zu berücksichtigen, dass die Abfallplanung den Kantonen obliege (<ref-law>). Da das Gebiet B._ weder im Richtplan 2002 noch im nachgeführten Richtplan 2019 als Standort für eine Inertstoffdeponie aufgeführt sei, sei kein neues öffentliches Interesse an einer Überprüfung und Erweiterung dieser Deponiezone ersichtlich. Der Beschwerdeführer substanziiere auch nicht, dass neu ein Engpass in der regionalen Deponieversorgung vorliege und im Vorderland keine anderweitige Verwertung der Inertstoffe gewährleistet sei. Dem stehe bereits die Eröffnung der Deponie D._ mit einem Gesamtvolumen von ca. 200'000 m3 klar entgegen, welche sich in nur rund 2 km Entfernung befinde. Die z.T. illegalen Schüttungen in der Deponie B._ seien vom Beschwerdeführer verursacht und könnten keine neuen Bedürfnisse des Gemeinwesens begründen. Insofern seien die Voraussetzungen für eine Überprüfung der Deponieplanung nicht erfüllt.
2.2. Der Beschwerdeführer macht dagegen geltend, die kantonale Abfall- und Richtplanung müsse aufgrund des im Kanton herrschenden "Deponienotstands" überprüft werden. Dieser rechtfertige es, auch in der Deponie B._ nachträglich zusätzliches Schüttvolumen zu bewilligen, wie dies auch in der Deponie E._ in Heiden geschehen sei.
In diesem Zusammenhang sei zu berücksichtigen, dass die bundesgerichtliche Rechtsprechung zwei Stufen der Prüfung unterscheide. Bei der Frage, ob überhaupt eine Überprüfung der Grundordnung geboten sei, genüge es bereits, wenn eine Anpassung der Zonenplanung im fraglichen Gebiet in Betracht falle und die entgegenstehenden Interessen der Rechtssicherheit und des Vertrauens in die Planbeständigkeit nicht so gewichtig seien, dass eine Plananpassung von vornherein ausscheide (<ref-ruling> E. 3.2 mit Hinweisen). Dies habe das Obergericht verkannt.
2.3. Die Abfallplanung ist Aufgabe der Kantone (<ref-law>; Art. 4 der Verordnung über die Vermeidung und die Entsorgung von Abfällen vom 4. Dezember 2015 [Abfallverordnung, VVEA; SR 814.600]). Sie umfasst insbesondere den Bedarf an Deponievolumen und die Standorte von Deponien (Deponieplanung; <ref-law>). Die Kantone überprüfen die Abfallplanung alle fünf Jahre und passen sie wenn nötig an (<ref-law>). Sie weisen die in der Deponieplanung vorgesehenen Standorte von Deponien in ihren Richtplänen aus und sorgen für die Ausscheidung der erforderlichen Nutzungszonen (<ref-law>).
Der Standort B._ ist in der kantonalen Abfallplanung nicht als Deponiestandort vorgesehen; er ist weder im Richtplan 2002 noch im nachgeführten Richtplan 2019 als solcher aufgeführt. Dies steht - wie die Vorinstanz zutreffend dargelegt hat - der Errichtung oder Erweiterung einer Deponie an diesem Standort entgegen.
2.4. Der Beschwerdeführer bestreitet, dass in der Region genügend Inertstoffdeponien bestünden, um den Bedarf zu decken. Der Planungsbericht vom 21. August 2015, auf den er sich beruft, wurde jedoch von ihm selbst in Auftrag gegeben und stellt daher eine Parteibehauptung dar. Näher zu prüfen ist daher in erster Linie der von ihm angerufene Vorprüfungsbericht des Planungsamts vom 29. Mai 2012, in welchem angeblich ein zusätzlicher Bedarf an Deponien im Appenzeller Vorderland bejaht worden sei.
Dort wurde die Nichtaufnahme des Standorts B._ als Deponiestandort im kantonalen Richtplan jedoch vor allem mit der Ungeeignetheit des Standorts begründet: Die Landschaftskammer liege in einem Landschaftsschutzgebiet und einem Gefahrengebiet "permanente Rutschungen"; letzteres stelle einen Ausschlussgrund dar. Im Übrigen sei in rund 1400 m Distanz die Deponie "D._" mit einem Volumen von 200'000 m3 geplant, und es widerspreche dem dezentralen Konzept der kantonalen Abfallplanung, mehrere Deponien auf engem Raum zu konzentrieren.
Der Beschwerdeführer setzt sich mit dieser Argumentation nicht auseinander und legt nicht dar, dass sich insoweit die Verhältnisse geändert hätten. Dies ist auch nicht ersichtlich; vielmehr wurde die Deponie D._ zwischenzeitlich eröffnet. Es liegen somit keine neuen Elemente vor, welche für eine Aufnahme des Standorts B._ als Deponiestandort in die kantonale Richt- und Zonenplanung sprechen würden. Es besteht daher - schon auf der ersten Stufe gemäss Art. 21 Abs. 2 RPG - kein Anspruch auf eine grundsätzliche Überprüfung der Deponieplanung in dieser Hinsicht.
3.
3.1. Nach dem Gesagten durfte das Departement auf Gesuche um Erweiterung der bestehenden Inertstoffdeponie B._, welche einen Bedarfsnachweis bzw. einen Standort im kantonalen Richtplan voraussetzen, nicht eintreten, ohne eine Rechtsverweigerung zu begehen. Anders ist die Situation dagegen möglicherweise zu beurteilen, wenn die Planänderung lediglich die Endgestaltung der bestehenden Deponie betrifft, d.h. die Geländegestaltung optimieren soll, ohne neues Deponiematerial zuzulassen.
3.2. Die zuständigen Behörden haben mehrfach signalisiert, dass eine Änderung des Quartierplans B._ in Bezug auf die Geländegestaltung möglich und - zur Gewährleistung der Deponiestabilität - sogar erforderlich sei. Mit Schreiben vom 10. August 2012 skizzierte das Planungsamt eine angepasste Geländegestaltung und maximale Schütthöhen für eine mögliche Anpassung des Quartierplans. Am Rekursaugenschein vom 21. Mai 2013 wurde der Beschwerdeführer verpflichtet, ein Umgestaltungsprojekt einzureichen. Im Vorprüfungsbericht vom 4. Oktober 2013 regte das Planungsamt an, das Gesuch vom 1. Juli 2013 so zu überarbeiten, wie mit Schreiben vom 10. August 2012 aufgezeigt worden sei. Auch im vorliegend angefochtenen Nichteintretensentscheid vom 11. Dezember 2015 (E. 7) lehnte das Departement eine Überarbeitung des geltenden Quartierplans nicht grundsätzlich ab, betonte aber, dass der Vorschlag vom 10. August 2012 nach wie vor die maximal mögliche Anpassung darstelle.
Insofern ist davon auszugehen, dass grundsätzlich ein Anspruch auf Prüfung von Änderungsprojekten gemäss Art. 21 Abs. 2 RPG besteht, die lediglich die Endgestaltung der Deponie zum Gegenstand haben, nicht aber deren Erweiterung.
3.3. Der Beschwerdeführer macht geltend, das Gesuch vom 8. September 2015 betreffe ausschliesslich die Endgestaltung der Deponie: Im Gegensatz zu früheren Gesuchen werde der Deponieperimeter nicht vergrössert und es solle weder neues Material zu- noch abgeführt werden.
Das Departement und, ihm folgend, Regierungsrat und Obergericht, hielten dagegen fest, dass das Schüttvolumen gegenüber dem Quartierplan aus dem Jahr 2008 um 48'700 m3erhöht werde, d.h. von 85'000 m3 auf 133'700 m3. Dies gehe über die bei der Deponievermessung vom 27. November 2012 festgestellte Überschüttung von 37'000 m3 hinaus und bedeute, dass zusätzlich zur bereits vorhandenen Schüttmenge von 114'500 m3 weitere 19'200 m3 Material zugeführt werden könnten.
Diese Zahlen entsprechen den Gesuchsunterlagen (vgl. insbesondere Planungsbericht vom 21. August 2015, Ziff. 3.4) und werden vom Beschwerdeführer nicht substanziiert bestritten. Insofern wird mit dem neuen Gesuch nicht nur eine Umlagerung des schon vorhandenen Materials, sondern auch eine Erweiterung der Deponie angestrebt.
3.4. Das Obergericht hat einen Anspruch auf Überprüfung der geltenden Deponieplanung zu Recht verneint.
4.
Ist die Beschwerde schon aus diesem Grund abzuweisen, braucht nicht mehr geprüft zu werden, ob das Gesuch vom 8. September 2015 im Wesentlichen mit dem rechtskräftig abgelehnten Gesuch vom 1. Juli 2013 identisch ist und das Departement schon aus diesem Grund darauf nicht eintreten musste, wie die Vorinstanzen angenommen haben.
Auf die Rüge der Verletzung des Gleichbehandlungsgebots (<ref-law>) ist schon mangels genügender Begründung nicht einzutreten, legt der Beschwerdeführer doch nicht dar, inwiefern die Verhältnisse am Standort B._ mit denjenigen der Deponie E._ vergleichbar sind.
5.
Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kostenpflichtig (<ref-law>) und es sind keine Parteientschädigungen zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 4'000.-- werden dem Beschwerdeführer auferlegt.
3.
Es werden keine Parteientschädigungen zugesprochen.
4.
Dieses Urteil wird dem Beschwerdeführer, dem Departement Bau und Volkswirtschaft, dem Regierungsrat und dem Obergericht des Kantons Appenzell Ausserrhoden, 4. Abteilung, der Gemeinde Heiden sowie dem Bundesamt für Raumentwicklung (ARE) schriftlich mitgeteilt.
Lausanne, 17. Februar 2020
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Die Gerichtsschreiberin: Gerber