Sachverhalt:
A.
A._ ist im Besitz einer Taxihalterbewilligung A sowie einer Taxichauffeurbewilligung im Kanton Basel-Stadt. Aufgrund wiederholter Verstösse gegen das Gesetz des Kantons Basel-Stadt vom 17. Januar 1996 über den Betrieb von Taxis (Taxigesetz; SG 563.200) stellte ihm das Taxibüro der Kantonspolizei Basel-Stadt am 28. April 2008 den Entzug der Taxihalterbewilligung in Aussicht. Das Verfahren wurde am 30. September 2008 bis zum Vorliegen eines rechtskräftigen Strafurteils sistiert.
Nachdem weitere Vorkommnisse hinzugetreten waren, verfügte das Taxibüro am 3. August 2011 nach Gewährung des rechtlichen Gehörs den Entzug der Taxihalterbewilligung und drohte A._ den Entzug der Taxichauffeurbewilligung an, für den Fall, dass sein Verhalten in den nächsten zwei Jahren (bis 1. September 2013) erneut Anlass zu Klagen geben sollte. Das Taxibüro begründete seine Verfügung mit einem offenen Verfahren bei der Kantonspolizei wegen manipulierter Fahrtschreiber, einer Verurteilung durch das Polizeigericht U._/F, Widerhandlungen gegen das Taxigesetz (unzulässige Kundenanwerbung am Flughafen Basel/Mulhouse) sowie drei Verurteilungen durch das Strafgericht Basel-Stadt. Die dagegen erhobenen kantonalen Rechtsmittel sind erfolglos geblieben (Entscheid des Justiz- und Sicherheitsdepartements des Kantons Basel-Stadt vom 18. September 2014; Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 16. November 2015).
B.
Am 4. Januar 2016 erhebt A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht und beantragt die Aufhebung des Urteils des Appellationsgerichts.
Das Appellationsgericht beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Justiz- und Sicherheitsdepartement schliesst auf Abweisung sowohl der Beschwerde als auch des Gesuchs um Erteilung der aufschiebenden Wirkung. Das Taxibüro hat sich nicht vernehmen lassen.
Mit Verfügung vom 22. März 2016 wurde das Gesuch um aufschiebende Wirkung abgewiesen.

Erwägungen:
1.
1.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist zulässig (vgl. Art. 81 lit. a, Art. 86 Abs. 1 lit. d und Abs. 2 sowie Art. 90 BGG). Auf die form- und fristgerecht eingereichte Beschwerde (vgl. Art. 42 und 100 Abs. 1 BGG) des nach <ref-law> legitimierten Beschwerdeführers ist einzutreten.
1.2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann eine Rechtsverletzung nach Art. 95 und Art. 96 BGG gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist daher weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden (<ref-ruling> E. 3 S. 415). Die Verletzung von kantonalem Gesetzesrecht wird nur unter dem Gesichtswinkel der Willkür geprüft (<ref-ruling> E. 2.2.1 S. 318 mit Hinweisen). In Bezug auf die Verletzung verfassungsmässiger Rechte (einschliesslich der willkürlichen Anwendung von kantonalem Recht) gilt eine qualifizierte Rüge- und Substanziierungspflicht (<ref-law>; <ref-ruling> E. 2.2 S. 232; <ref-ruling> E. 2.5 S. 314).
1.3. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 2 S. 116 f.). Die beschwerdeführende Partei kann die Feststellung des Sachverhalts unter den gleichen Voraussetzungen beanstanden, wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Eine entsprechende Rüge ist substanziiert vorzubringen; auf rein appellatorische Kritik an der Sachverhaltsfeststellung geht das Bundesgericht nicht ein (<ref-ruling> E. 10.1 S. 444 f.; <ref-ruling> E. 5.1 S. 356).
2.
Gemäss § 4 Abs. 1 Taxigesetz bedarf der Betrieb von Taxis auf dem Gebiet des Kantons Basel-Stadt einer Taxihalterbewilligung der zuständigen Behörde. Die allgemeinen Voraussetzungen einer Taxihalterbewilligung werden in § 6 Taxigesetz umschrieben. Danach wird u.a. verlangt, dass sich der Taxihalter über einen guten Leumund ausweist (Abs. 1 lit. b) und über eines oder mehrere technisch einwandfreie und vorschriftsgemäss ausgerüstete Fahrzeuge verfügt (Abs. 1 lit. f). Nach § 9 Abs. 1 Taxigesetz sind Taxihalterbewilligungen zu entziehen, wenn festgestellt wird, dass die gesetzlichen Voraussetzungen zur Erteilung nicht oder nicht mehr bestehen. Sie können auch entzogen werden, wenn die Taxihalterin oder der Taxihalter in schwerer Weise oder wiederholt gegen Verkehrsvorschriften oder gegen Bestimmungen über den Betrieb von Taxis verstossen hat, zu solchen Widerhandlungen angestiftet oder solche mehrmals geduldet hat. In leichten Fällen können der Bewilligungsentzug angedroht und die Belassung der Bewilligung mit Auflagen verbunden werden (§ 9 Abs. 2 Taxigesetz). Wer ein Taxi führen will, bedarf nach § 11 Abs. 1 Taxigesetz einer kantonalen Bewilligung als Taxichauffeuse oder als Taxichauffeur. Bei schwerer oder wiederholter Verletzung von Verkehrsvorschriften sowie von Bestimmungen des Taxigesetzes und seiner Verordnung kann die Bewilligungsbehörde die Taxichauffeurbewilligung entziehen. In leichten Fällen kann der Bewilligungsentzug angedroht und die Belassung der Bewilligung mit Auflagen verbunden werden (vgl. § 12 Abs. 3 Taxigesetz).
3.
3.1. Der Beschwerdeführer rügt zunächst eine offensichtlich unrichtige Sachverhaltsfeststellung. Die Manipulation des Fahrtschreibers sei nicht erwiesen; er habe diese stets bestritten. Durch die Einstellung des Strafverfahrens sei es ihm verunmöglicht worden, seine Sicht der Dinge darzulegen. Damit entfiele die Grundlage für den Entzug der Taxihalterbewilligung. Auch die ihm vorgeworfenen fortgesetzten unerlaubten Kundenanwerbungen am EuroAirport hätten keinerlei Grundlage. Diese basierten auf Beobachtungen konkurrierender Taxiunternehmen, die ihn in ein schlechtes Licht rücken wollten, und den Aussagen einer englischen Kundin. Diese habe sich aber nicht über unerlaubte Kundenanwerbung, sondern über den Preis der Taxifahrt beklagt. Es sei daher aktenwidrig zu behaupten, diese Angelegenheit hätte etwas mit der Kundenanwerbung zu tun.
3.2. Das Justiz- und Sicherheitsdepartement hat in seinem Entscheid detailliert beschrieben, wie in beiden Taxifahrzeugen des Beschwerdeführers Schalter eingebaut waren, mit welchen der Fahrtschreiber manipuliert werden konnte. Laut einer im Auftrag der Kantonspolizei Basel-Stadt durchgeführten Expertise vom 23. Juni 2010 dienten diese zur Unterbrechung des Geschwindigkeitssignals des Fahrtschreibers, so dass bei deren Betätigung die Geschwindigkeit und die Wegstrecke der Fahrzeuge nicht aufgezeichnet wurden. Der Tachograph interpretierte dadurch die Situation so, wie wenn das Fahrzeug gestanden hätte. Die Einlageblätter der Fahrtschreiber wiesen gegenüber den Servicerechnungen eine erhebliche Diskrepanz auf (bei einem der Fahrzeuge über 50'000 km). Aufgrund der hohen Anzahl nicht aufgezeichneter Kilometer und des hohen Aufwands der Installation, die sich offenbar unzweifelhaft dem Beschwerdeführer anlasten liess, ging das Justiz- und Sicherheitsdepartement nicht mehr von einer einmaligen Kleinigkeit aus Versehen, sondern von einer systematisch geplanten Wiederholung bei unzähligen Fahrten aus. Der Beschwerdeführer unterliess es, diese Feststellungen im Rahmen des vorinstanzlichen Verfahrens - unabhängig vom Strafverfahren, das infolge Verjährung eingestellt wurde - konkret zu beanstanden. Der Beschwerdeführer hat seine Mitwirkungspflicht somit nur unzureichend erfüllt. Die Vorinstanz hatte demnach keinerlei Anlass, sich in ihrem Urteil näher damit auseinanderzusetzen. Eine entsprechende Rüge im vorliegenden Verfahren erweist sich damit als verspätet. Im Übrigen legt der Beschwerdeführer auch vor Bundesgericht nicht dar, inwiefern die Vorwürfe betreffend die Manipulation der Fahrtschreiber unzutreffend sein sollten. Es erscheint fraglich, kann letztlich aber offen bleiben, ob er damit der Begründungspflicht (vgl. <ref-law>) genügend nachkommt.
3.3. Hinsichtlich des Vorwurfs der unerlaubten Kundenanwerbung hatte sich die fragliche Kundin des Beschwerdeführers wegen des Preises der Taxifahrt beim Taxibüro beschwert. In dieser Angelegenheit äusserte sich der Beschwerdeführer dahingehend, "[...] da habe ich halt in der Schalterhalle die Frau gefragt, ob sie ein Taxi braucht." (vgl. Aktennotiz des Taxibüros vom 18. Juni 2009). Es ist nicht ersichtlich, inwiefern die Vorinstanz zu Unrecht davon ausgegangen sein soll, dass der Beschwerdeführer in der Schalterhalle des Ankunftsbereichs Personen angesprochen und seine Taxidienste angeboten habe. Im Übrigen hat die Vorinstanz in diesem Zusammenhang nicht nur auf diesen einen Vorfall (mit der englischen Kundin) abgestellt, sondern auch auf Beschwerden anderer Taxiunternehmen sowie Feststellungen der Flughafenleitung (vom Beschwerdeführer im Kurzzeitparkhaus des EuroAirport gelöste Tickets, Bildaufnahmen des Beschwerdeführers mit Gästen). Sie durfte daher, ohne dass ihr eine offensichtlich unrichtige Sachverhaltsfeststellung vorgeworfen werden könnte, annehmen, der Beschwerdeführer habe über einen längeren Zeitraum Kunden am EuroAirport auf unzulässige Weise angelockt. Die Rüge des Beschwerdeführers geht somit fehl.
4.
4.1. Weiter macht der Beschwerdeführer sinngemäss einen unverhältnismässigen Eingriff in die Wirtschaftsfreiheit (<ref-law>) geltend. Da ihm einzig eine Busse von EUR 400.-- vorgehalten werden könne, die er in Frankreich habe bezahlen müssen, sei es weder verhältnismässig noch stehe es im öffentlichen Interesse, ihm als 60-jährigem Familienvater die Taxihalterbewilligung zu entziehen. In fast 30 Jahren sei seine Taxihalterbewilligung nie zur Diskussion gestanden. Dass ihm die Taxichauffeurbewilligung belassen werde, sei kein adäquater Ersatz, sei doch die Möglichkeit, auf eigene Rechnung und aufgrund eigener Zeiteinteilung arbeiten zu können, essentiell.
4.2. Entgegen seinem Vorbringen sind dem Beschwerdeführer nicht nur die tätliche Auseinandersetzung mit einem anderen Taxichauffeur in Frankreich, die zu einer Geldstrafe führte, vorzuwerfen, sondern hat er sich auch Manipulationen am Fahrtschreiber und unzulässige Kundenanwerbung am EuroAirport vorhalten zu lassen (vgl. ausführlich das angefochtene Urteil E. 3.4 f.). Die Vorinstanz hat eine umfassende Verhältnismässigkeitsprüfung durchgeführt (vgl. das angefochtene Urteil E. 4 ff.). Sie hat dargelegt, dass der Beschwerdeführer in schwerer und wiederholter Weise gegen taxi- und arbeitsrechtliche Bestimmungen, strassenverkehrsrechtliche Normen sowie Vorschriften zum Schutz der körperlichen Integrität Dritter verstossen und damit § 9 Abs. 2 Taxigesetz erfüllt hat. An sich hätte ihm gestützt auf § 12 Abs. 3 Taxigesetz auch die Taxichauffeurbewilligung entzogen werden können. Aus Verhältnismässigkeitsüberlegungen wurde ihm diese aber belassen, so dass er nach wie vor ein Taxi fahren und damit ein Einkommen erzielen kann. Die Taxichauffeurbewilligung wurde ihm im Sinne einer letzten Chance nicht entzogen, sondern lediglich deren Entzug angedroht für den Fall, dass sein Verhalten in den nächsten zwei Jahren (bis 1. September 2013) zu Klagen Anlass geben sollte. Die Existenzgrundlage sollte ihm nicht entzogen werden. Er vermag somit nicht darzulegen, inwiefern sich die angeordneten Massnahmen als unverhältnismässig erweisen sollen. Es bleibt ihm im Übrigen unbenommen, für die Erteilung einer neuen Taxihalterbewilligung ein ordentliches Gesuch an das Justiz- und Sicherheitsdepartement zu stellen (vgl. schon die Verfügung des Taxibüros vom 3. August 2011 Ziff. 3).
4.3. Nach dem Gesagten ist nicht zu beanstanden, dass die Taxihalterbewilligung entzogen und der Entzug der Taxichauffeurbewilligung angedroht worden ist.
5.
Die Beschwerde erweist sich damit als unbegründet und ist abzuweisen. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (Art. 65, Art. 66 Abs. 1 BGG). Eine Parteientschädigung ist nicht auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Verfahrensbeteiligten und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht schriftlich mitgeteilt.
Lausanne, 22. April 2016
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Die Gerichtsschreiberin: Fuchs