Sachverhalt: A. A.a. Gestützt auf die Vorschriften über die Strassenprostitution des Stadtrats Zürich vom 17. Juli 1991 war die Strassenprostitution im Gebiet Niederdorf, begrenzt durch Seilergraben, Neumarkt, Rindermarkt, Marktgasse und Limmatquai, von 19.00 bis 05.00 Uhr gestattet. A.b. Am 7. März 2012 erliess der Gemeinderat der Stadt Zürich eine Prostitutionsgewerbeverordnung (PGVO), in deren Art. 8 und 11 er die Nutzung des öffentlichen Grundes zur Ausübung der Strassenprostitution sowie die Salonprostitution neu einer Bewilligungspflicht unterstellt. Art. 7 PGVO ermächtigt den Stadtrat, unter Beachtung der Zweckumschreibung von Art. 1 PGVO Gebiete und Zeiten zu bezeichnen, in denen die örtlichen Verhältnisse die Strassen- oder Fensterprostitution zulassen. Art. 17 PGVO stellt die Ausübung der Strassen- und Fensterprostitution ausserhalb der zugelassenen Gebiete und Zeiten ohne Bewilligung unter Sanktion. Die PGVO trat am 1. Juli 2012 in Kraft. A.c. Mit Beschluss vom 13. März 2013 gestattete der Stadtrat die Strassenprostitution im Gebiet Niederdorf, begrenzt durch Seilergraben, Neumarkt, Rindermarkt, Marktgasse und Limmatquai von 22.00 bis 02.00 Uhr. Gleichzeitig gestattete er die Fensterprostitution an der Häringstrasse von 19.00 bis 05.00 Uhr, sofern die dazugehörigen Räumlichkeiten über eine entsprechende Bewilligung zur sexgewerblichen Nutzung verfügen. Die Anpassung der Strichzone setzte er per 1. September 2013 in Kraft. B. Gegen den Stadtratsbeschluss vom 13. März 2013 erhoben A._, B._, C._, D._ und E._ Rekurs an den Bezirksrat, der die Sache zuständigkeitshalber an den Statthalter überwies. Dieser wies den Rekurs mit Entscheid vom 14. Februar 2014 ab, soweit er darauf eintrat. C. Dagegen erhoben die Rekurrentinnen Beschwerde an das Verwaltungsgericht des Kantons Zürich. Dieses wies mit Urteil vom 20. November 2014 die Beschwerde im Sinne der Erwägungen ab. D. A._, B._, C._, D._ und E._ erheben mit gemeinsamer Eingabe vom 30. Januar 2015 Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, das Urteil des Verwaltungsgerichts sei aufzuheben und an die Vorinstanz zurückzuweisen. Zudem beantragen sie Erteilung der aufschiebenden Wirkung. Das Verwaltungsgericht und der Stadtrat Zürich beantragen, die Beschwerde abzuweisen. Die Beschwerdeführerinnen replizieren.