Alexander the Great’s army solved its logistical problems through diplomacy:
It would send scouts or messengers ahead, seeking out availability of food and water.* Local chieftans or government officials presented themselves at the camp as word got around about an approaching army. Typically they would surrender to the conqueror, whereupon he would usually confirm them in their positions, enlisting them as allies. This meant they were obligated to help his army pass through their territory. Diplomacy on the whole meant generosity and persuasion. Alexander didn’t have to conquer everybody; leveling one resisting city and selling the population into slavery would be enough to bring the others around. In places where there was distrust, the invaders would leave a garrison, or demand hostages. It was a mild form of conquest, which left everything locally as it had been.
*We see the same thing in the Bible, when Jesus and a growing crowd of followers travel from Galilee in northern Israel to Jerusalem, a distance of 100 miles. Jesus sends out 70 forerunners to find towns to host them. It is not a military expedition, but Jesus calls down religious sanctions on the villages that refuse to receive them. “Woe to you, Chorazin! Woe to you, Bethsaida! … And you, Capernaum, will you be lifted to heaven? No, you will go down to Hades.” [Luke 10: 1-16] Logistical issues recur throughout Jesus’ career, since big crowds overstress local resources: hence the need for miracles of multiplying loaves and fishes, and turning water into wine.
The essential thing was that new allies or friendly natives were obligated to provide stores of food and fodder along the route; pack animals to replace those lost by malnourishment, or to marshal their own local pack trains.
For Alexander’s army, the method worked well. It also explains why it took 10 years to conquer the empire. Conquering the eastern part meant more marches through deserts and mountains, careful planning of when harvests were available, and more advance diplomacy.
Alexander fought relatively few battles. After each one, he would stay in a well-provided location, receive visits of capitulation, and arrange logistics for the way ahead. His father, building a mini-empire on the barbarian fringes of Greece, was ruthless when he needed to be, but on the whole Philip expanded by diplomacy. It all meshed together: his fast-moving army, his combined-arms victories, and his diplomatic agreements that solved problems of logistics. His son operated the same way.