I believe I need to make a hash of team containing an array of (unique)location containing an array of tools and their number. Or maybe a hash of hashes of hashes? I've been trying just about every permutation I can think of for days.

Pass your required output to an XML parser that uses data structures and see what it produces; and then mimic it:

#! perl -slw
use strict;
use Data::Dump qw[ pp ];
use XML::Simple;

my $xml = XMLin( \*DATA, KeepRoot => 1, NoAttr => 1 );
pp $xml;
print XMLout( $xml, KeepRoot => 1, NoAttr => 1 );

__DATA__
<ToolLocations>
  <ToolLocation>
    <LocationName>location_4</LocationName>
    <ToolList>
      <Tool>
        <ToolName>tool_2</ToolName>
        <ToolNum>5</ToolNum>
      </Tool>
      <Tool>
        <ToolName>tool_5</ToolName>
        <ToolNum>3</ToolNum>
      </Tool>
    </ToolList>
  </ToolLocation>
</ToolLocations>
[download]

Produces:

C:\test>1001808
{
  ToolLocations => {
    ToolLocation => {
      LocationName => "location_4",
      ToolList     => {
                        Tool => [
                          { ToolName => "tool_2", ToolNum => 5 },
                          { ToolName => "tool_5", ToolNum => 3 },
                        ],
                      },
    },
  },
}

<ToolLocations>
  <ToolLocation>
    <LocationName>location_4</LocationName>
    <ToolList>
      <Tool>
        <ToolName>tool_2</ToolName>
        <ToolNum>5</ToolNum>
      </Tool>
      <Tool>
        <ToolName>tool_5</ToolName>
        <ToolNum>3</ToolNum>
      </Tool>
    </ToolList>
  </ToolLocation>
</ToolLocations>
[download]

That takes your required output as input, converts it to a data structure and then converts it back successfully. So now you know what the data structure needs to look like.