Curious order of events in Josephus Antiquities 18, chapters 2 - 3:
After him came Annius Rufus, under whom died Caesar (Augustus), the second emperor of the Romans, the duration of whose reign was fifty-seven years, besides six months and two days (of which time Antonius ruled together with him fourteen years; but the duration of his life was seventy-seven years); upon whose death Tiberius Nero, his wife Julia's son, succeeded. He (= Tiberius) was now the third emperor; and he sent Valerius Gratus to be procurator of Judea, and to succeed Annius Rufus. This man deprived Ananus of the high priesthood, and appointed Ismael, the son of Phabi, to be high priest. He also deprived him in a little time, and ordained Eleazar, the son of Ananus, who had been high priest before, to be high priest; which office, when he had held for a year, Gratus deprived him of it, and gave the high priesthood to Simon, the son of Camithus; and when he had possessed that dignity no longer than a year, Joseph Caiaphas was made his successor. When Gratus had done those things, he went back to Rome, after he had tarried in Judea eleven years, when Pontius Pilate came as his successor.
And now Herod the tetrarch (= Antipas), who was in great favor with Tiberius, built a city of the same name with him, and called it Tiberias. He built it in the best part of Galilee, at the lake of Gennesareth. There are warm baths at a little distance from it, in a village named Emmaus. Strangers came and inhabited this city; a great number of the inhabitants were Galileans also; and many were necessitated by Herod to come thither out of the country belonging to him, and were by force compelled to be its inhabitants; some of them were persons of condition. He also admitted poor people, such as those that were collected from all parts, to dwell in it. Nay, some of them were not quite free-men, and these he was benefactor to, and made them free in great numbers; but obliged them not to forsake the city, by building them very good houses at his own expenses, and by giving them land also; for he was sensible, that to make this place a habitation was to transgress the Jewish ancient laws, because many sepulchers were to be here taken away, in order to make room for the city Tiberias whereas our laws pronounce that such inhabitants are unclean for seven days.
About this time died Phraates, king of the Parthians, by the treachery of Phraataces his son, upon the occasion following: When Phraates had had legitimate sons of his own, he had also an Italian maid-servant, whose name was Thermusa, who had been formerly sent to him by Julius Caesar, among other presents. He first made her his concubine; but he being a great admirer of her beauty, in process of time having a son by her, whose name was Phraataces, he made her his legitimate wife, and had a great respect for her. Now she was able to persuade him to do any thing that she said, and was earnest in procuring the government of Parthia for her son; but still she saw that her endeavors would not succeed, unless she could contrive how to remove Phraates's legitimate sons [out of the kingdom;] so she persuaded him to send those his sons as pledges of his fidelity to Rome; and they were sent to Rome accordingly, because it was not easy for him to contradict her commands. Now while Phraataces was alone brought up in order to succeed in the government, he thought it very tedious to expect that government by his father's donation [as his successor]; he therefore formed a treacherous design against his father, by his mother's assistance, with whom, as the report went, he had criminal conversation also. So he was hated for both these vices, while his subjects esteemed this [wicked] love of his mother to be no way inferior to his parricide; and he was by them, in a sedition, expelled out of the country before he grew too great, and died. But as the best sort of Parthians agreed together that it was impossible they should be governed without a king, while also it was their constant practice to choose one of the family of Arsaces, [nor did their law allow of any others; and they thought this kingdom had been sufficiently injured already by the marriage with an Italian concubine, and by her issue,] they sent ambassadors, and called Orodes [to take the crown]; for the multitude would not otherwise have borne them; and though he was accused of very great cruelty, and was of an untractable temper, and prone to wrath, yet still he was one of the family of Arsaces. However, they made a conspiracy against him, and slew him, and that, as some say, at a festival, and among their sacrifices; (for it is the universal custom there to carry their swords with them;) but, as the more general report is, they slew him when they had drawn him out a hunting. So they sent ambassadors to Rome, and desired they would send one of those that were there as pledges to be their king. Accordingly, Vonones was preferred before the rest, and sent to them (for he seemed capable of such great fortune, which two of the greatest kingdoms under the sun now offered him, his own and a foreign one). However, the barbarians soon changed their minds, they being naturally of a mutable disposition, upon the supposal that this man was not worthy to be their governor; for they could not think of obeying the commands of one that had been a slave, (for so they called those that had been hostages,) nor could they bear the ignominy of that name; and this was the more intolerable, because then the Parthians must have such a king set over them, not by right of war, but in time of peace. So they presently invited Artabanus, king of Media, to be their king, he being also of the race of Arsaces. Artabanus complied with the offer that was made him, and came to them with an army. So Vonones met him; and at first the multitude of the Parthians stood on this side, and he put his army in array; but Artabanus was beaten, and fled to the mountains of Media. Yet did he a little after gather a great army together, and fought with Vonones, and beat him; whereupon Vonones fled away on horseback, with a few of his attendants about him, to Seleucia [upon Tigris]. So when Artabanus had slain a great number, and this after he had gotten the victory by reason of the very great dismay the barbarians were in, he retired to Ctesiphon with a great number of his people; and so he now reigned over the Parthians. But Vonones fled away to Armenia; and as soon as he came thither, he had an inclination to have the government of the country given him, and sent ambassadors to Rome [for that purpose]. But because Tiberius refused it him, and because he wanted courage, and because the Parthian king threatened him, and sent ambassadors to him to denounce war against him if he proceeded, and because he had no way to take to regain any other kingdom, (for the people of authority among the Armenians about Niphates joined themselves to Artabanus,) he delivered up himself to Silanus, the president of Syria, who, out of regard to his education at Rome, kept him in Syria, while Artabanus gave Armenia to Orodes, one of his own sons.
5. At this time died Antiochus, the king of Commagene; whereupon the multitude contended with the nobility, and both sent ambassadors to [Rome]; for the men of power were desirous that their form of government might be changed into that of a [Roman] province; as were the multitude desirous to be under kings, as their fathers had been. So the senate made a decree that Germanicus should be sent to settle the affairs of the East, fortune hereby taking a proper opportunity for depriving him of his life; for when he had been in the East, and settled all affairs there, his life was taken away by the poison which Piso gave him, as hath been related elsewhere. (7)
1. BUT now Pilate, the procurator of Judea, removed the army from Cesarea to Jerusalem, to take their winter quarters there, in order to abolish the Jewish laws. So he introduced Caesar's effigies, which were upon the ensigns, and brought them into the city; whereas our law forbids us the very making of images; on which account the former procurators were wont to make their entry into the city with such ensigns as had not those ornaments. Pilate was the first who brought those images to Jerusalem, and set them up there; which was done without the knowledge of the people, because it was done in the night time; but as soon as they knew it, they came in multitudes to Cesarea, and interceded with Pilate many days that he would remove the images; and when he would not grant their requests, because it would tend to the injury of Caesar, while yet they persevered in their request, on the sixth day he ordered his soldiers to have their weapons privately, while he came and sat upon his judgment-seat, which seat was so prepared in the open place of the city, that it concealed the army that lay ready to oppress them; and when the Jews petitioned him again, he gave a signal to the soldiers to encompass them routed, and threatened that their punishment should be no less than immediate death, unless they would leave off disturbing him, and go their ways home. But they threw themselves upon the ground, and laid their necks bare, and said they would take their death very willingly, rather than the wisdom of their laws should be transgressed; upon which Pilate was deeply affected with their firm resolution to keep their laws inviolable, and presently commanded the images to be carried back from Jerusalem to Cesarea.
Now compare Tacitus Annals 2 describing events 16 - 19 CE
http://www.unrv.com/government/consul-1-ad.php:
In the consulship of Sisenna Statilius Taurus and Lucius Libo (= 16 CE)there was a commotion in the kingdoms and Roman provinces of the East. It had its origin among the Parthians, who disdained as a foreigner a king whom they had sought and received from Rome, though he was of the family of the Arsacids. This was Vonones, who had been given as an hostage to Augustus by Phraates. For although he had driven before him armies and generals from Rome, Phraates had shown to Augustus every token of reverence and had sent him some of his children, to cement the friendship, not so much from dread of us as from distrust of the loyalty of his countrymen.
After the death of Phraates and the succeeding kings in the bloodshed of civil wars, there came to Rome envoys from the chief men of Parthia, in quest of Vonones, his eldest son. Caesar thought this a great honour to himself, and loaded Vonones with wealth. The barbarians, too, welcomed him with rejoicing, as is usual with new rulers. Soon they felt shame at Parthians having become degenerate, at their having sought a king from another world, one too infected with the training of the enemy, at the throne of the Arsacids now being possessed and given away among the provinces of Rome. "Where," they asked, "was the glory of the men who slew Crassus, who drove out Antonius, if Caesar's drudge, after an endurance of so many years' slavery, were to rule over Parthians." Vonones himself too further provoked their disdain, by his contrast with their ancestral manners, by his rare indulgence in the chase, by his feeble interest in horses, by the litter in which he was carried whenever he made a progress through their cities, and by his contemptuous dislike of their national festivities. They also ridiculed his Greek attendants and his keeping under seal the commonest household articles. But he was easy of approach; his courtesy was open to all, and he had thus virtues with which the Parthians were unfamiliar, and vices new to them. And as his ways were quite alien from theirs they hated alike what was bad and what was good in him.
Accordingly they summoned Artabanus, an Arsacid by blood, who had grown to manhood among the Dahae, and who, though routed in the first encounter, rallied his forces and possessed himself of the kingdom. The conquered Vonones found a refuge in Armenia, then a free country, and exposed to the power of Parthia and Rome, without being trusted by either, in consequence of the crime of Antonius, who, under the guise of friendship, had inveigled Artavasdes, king of the Armenians, then loaded him with chains, and finally murdered him. His son, Artaxias, our bitter foe because of his father's memory, found defence for himself and his kingdom in the might of the Arsacids. When he was slain by the treachery of kinsmen, Caesar gave Tigranes to the Armenians, and he was put in possession of the kingdom under the escort of Tiberius Nero. But neither Tigranes nor his children reigned long, though, in foreign fashion, they were united in marriage and in royal power.
Next, at the bidding of Augustus, Artavasdes was set on the throne, nor was he deposed without disaster to ourselves. Caius Caesar was then appointed to restore order in Armenia. He put over the Armenians Ariobarzanes, a Mede by birth, whom they willingly accepted, because of his singularly handsome person and noble spirit. On the death of Ariobarzanes through a fatal accident, they would not endure his son. Having tried the government of a woman named Erato and having soon afterwards driven her from them, bewildered and disorganised, rather indeed without a ruler than enjoying freedom, they received for their king the fugitive Vonones. When, however, Artabanus began to threaten, and but feeble support could be given by the Armenians, or war with Parthia would have to be undertaken, if Vonones was to be upheld by our arms, the governor of Syria, Creticus Silanus, sent for him and kept him under surveillance, letting him retain his royal pomp and title. How Vonones meditated an escape from this mockery, I will relate in the proper place.
Vonones I was king of Parthia c. 8–12 CE. From the Wikipedia article we read:
But Artabanus II demanded his deposition, and as Augustus did not wish to begin a war with the Parthians he removed Vonones I into Syria, where he was kept in custody, though in a kingly style.[4] Later he was moved to Cilicia,[5] and when he tried to escape in about 19 AD, he was killed by his guards
Now if we suppose that the Antiquities were sloppily pieced together from Tacitus's Annals we find all the elements which make up this reference. The one thing we seem to know for certain is that Tiberias was founded c. 18 - 21 CE. Now let's go to the next historical reference in the section:
During the same time, on the deaths of Antiochus and Philopator, kings respectively of the Commageni and Cilicians, these nations became excited, a majority desiring the Roman rule, some, that of their kings. The provinces too of Syria and Judaea, exhausted by their burdens, implored a reduction of tribute. Tiberius accordingly discussed these matters and the affairs of Armenia, which I have already related, before the Senate. "The commotions in the East," he said, "could be quieted only by the wisdom, of Germanicus; own life was on the decline, and Drusus had not yet reached his maturity." Thereupon, by a decree of the Senate, the provinces beyond sea were entrusted to Germanicus, with greater powers wherever he went than were given to those who obtained their provinces by lot or by the emperor's appointment. [Annals 2:42 - 43]
This sending of Germanicus to Commagne and the making of it into a Roman province is again dated to 18 CE. Germanicus dies in 19 CE. It is immediately following these two reference to 18 CE that Josephus again repeats that Pilate was already in control of Judea:
BUT now Pilate, the procurator of Judea, removed the army from Cesarea to Jerusalem, to take their winter quarters there, in order to abolish the Jewish laws. So he introduced Caesar's effigies, which were upon the ensigns, and brought them into the city; whereas our law forbids us the very making of images; on which account the former procurators were wont to make their entry into the city with such ensigns as had not those ornaments.
So the reference to the beginning of the building of Tiberias in 18 CE generally agrees with the idea that the city may have been completed by 21 CE and thus not fully completed during the period described in the gospel.