If you're staying in central Sandakan, you'll be there within moments after landing at SDK. The terminal is only 10 kilometers from downtown.