This is not for everybody but since QF nuked PER-MEL for me (after SYD-PER) I usually fly PER-CBR and then drive, either CBR-MEL or CBR-ADL-MEL. Beautiful country (Barossa Valley, Pacific Coast Highway, etc.) and a welcome change from all those airports, that get to me after a while.