Reorganizing inventory items into a data structure
The first thing to note is that Java no longer requires the generic types to be specified in the declaration of the collections you have, so, for example, the code 


Map&lt;String, ArrayList&lt;TreeMap&lt;String, String&gt;&gt;&gt; map = new TreeMap&lt;String, ArrayList&lt;TreeMap&lt;String, String&gt;&gt;&gt;();



can be replaced with:

Map&lt;String, ArrayList&lt;TreeMap&lt;String, String&gt;&gt;&gt; map = new TreeMap&lt;&gt;();


That simplifies your line-lengths in a few places.

This is how I would simplify the code cosmetically:

Map&lt;String, ArrayList&lt;TreeMap&lt;String, String&gt;&gt;&gt; map = new TreeMap&lt;&gt;();
String charsToFilter = "[" + Pattern.quote("_-") + "]";
ArrayList&lt;String&gt; productNameArray = new ArrayList&lt;&gt;();

for (Map&lt;String, String&gt; baseDataItem : baseDataArray) {
    productNameArray.add(baseDataItem.get("product_name")
                    .replaceAll(charsToFilter, " ")
                    .toLowerCase());
}

for (Map&lt;String, String&gt; inventoryItem : inventoryArray) {
    //moving this to the for loop below increase execution time by 100%
    String processedInventoryItem = inventoryItem.get("title")
          .replaceAll(charsToFilter, " ")
          .toLowerCase();     

    for (String productName : productNameArray) {
        if (processedInventoryItem.contains(productName)) {
            ArrayList&lt;TreeMap&lt;String, String&gt;&gt; currentListingArray = new ArrayList&lt;&gt;();
            TreeMap&lt;String, String&gt; currentListingMap = new TreeMap&lt;&gt;();
            for (Map.Entry&lt;String, String&gt; keyValue :  inventoryItem.entrySet()) {
                currentListingMap.put(keyValue.getKey(),  keyValue.getValue());
            }

            currentListingArray.add(currentListingMap); 
            if (map.get(productName) == null) {                     
                map.put(productName, currentListingArray);
            } else {
                map.get(productName).add(currentListingMap);
            }

            break;
        }
    }
}
return map;


OK, that fits on a single screen, and is almost narrow-enough for StackExchange code blocks.

Right, now, what are you doing? You're iterating over the inventoryArray, and, for each inventoryItem, you check to see whether there's a baseDataArray member who's filtered name is part of the filtered inventoryItem's name.

You extract the processing of the baseDataArray names to a separate loop to prevent recalculating it often. That's a good idea. It would be better if you reused a single compiled Pattern:

Pattern charfilter = Pattern.compile("[" + Pattern.quote("_-") + "]");


Then, use that pattern in the loop, replacing the following


for (Map&lt;String, String&gt; baseDataItem : baseDataArray) {
    productNameArray.add(baseDataItem.get("product_name")
      .replaceAll(charsToFilter, " ").toLowerCase());
}



with:

for (Map&lt;String, String&gt; baseDataItem : baseDataArray) {
    productNameArray.add(charfilter.matcher(baseDataItem.get("product_name"))
      .replaceAll(" ").toLowerCase());
}


Similarly, inside the inventory loop, you can also do:

String processedInventoryItem = charfilter.matcher(inventoryItem.get("title")).replaceAll(" ").toLowerCase();


That should reuse the pattern more efficiently, and improve the replaceall time (though Java probably does a good job of detecting that misuse, and compiling it efficiently anyway.

There is a potential bug in your code, though, and it possibly accounts for the speed-up too.

In the original code, you check every inventory item against every product.

In the second code, you check each product against only the first inventory. You "break" the inner loop.

As a result, your "faster" code does not do a full join between the data sets, but only a partial one. This may or may not impact your results, but it will impact the performance.

As an aside, this code would look great in Java 8 with streams... do you have Java 8 available?