I'd just create one new properly sorted array containing [sortkey] => reference_to_existing_array_element.
$free = $location = [];
foreach ($all as $k => &$arr) {
$free[$arr['@attributes']['free']][] = $arr;
$location[$arr['@attributes']['location']][] = $arr;
}
# Sort on keys
ksort($free);
ksort($location);
Where "free" wouldd have 3 top level elements (49, 54 (two entries) and 84) while location would contain 4 top level elements (Edinburg, London, Manchester, York).
Sorting on both keys at the same time would still require row-to-column transformations which can then be passed to array_multisort. See example 3 of [man]array_multisort[/man]