I agree much with both posters. Like Tyre, where he built a causeway to defeat an island, he would have likely made a land route. First conquering Arabia, lands west of Egypt were ripe for the plucking, and to the best of my knowledge, past what is now eastern Libya (Tobruk, etc) which was taken by Egypt in past dynasties, the other areas due west were only accessed by sea because of the long distance and difficulties of land based logistics.
Of all people, Alexander proved himself in both distance and logistics by his return from India with the thirst and trials. Bonus points for going in winter, but with this man who knows? I expect Carthage to have at least glimmerings of advance plans of any buildup, as naval powers are especially in tune with intel (the human factor information under deep cover), especially soon after the roll west. Alexander might even try to use Arabia as a feint false campaign, trying it later where it would fall like a bunch of dominoes after the Carthage adventure.
It would only take a couple of months for the whole thing to take place. He might even do it with a large light cavalry (in late winter) and possibly a camel corps plus getting resupply by way of ships some distance from Carthage literally dumping their cargo at night in barrells or bales or amphora just off the coast during wind to shore event, so to miminize risk of attack, like drug smugglers did with canabis in Florida. This is just off the top of my head.
From Carthage, the hive of bees would be sprung, and end battle to the death. Refugees would go to what is now Cartagenia, Spain, Malta, etc. and stir up a storm. The North African route would be the soft underbelly, being the previously protected center of the western colonies (AFAIK), though Berber tribes would be tough past what is mid Tunisia in OTL, knowledge of Arabia being only partial help.
A quick doubling of length of the Empire, and huge kudos from nearly all, even enemies and potential foes. A masterstroke. He would quite possibly make a deal with the Berbers (he paid off the keepers of Khyber pass, did he not?) and settle irrigatable lands like the Romans did later.