change title page on search result

To change document title use document_title_parts.filter. You want to apply changes only on the search page (as indicated in the title), so you should use is_search() conditional tag (or is_archive() as you suggest in the comment) and your code from php file.

add_filter( 'document_title_parts', 'se333744_site_title' );
function se333744_site_title( $title )
{
    global $wp_query;
    if ( is_archive() )
    {
        // your code here
        if ( isset($_GET['search_region'], $_GET['search_categories']) ) 
        {
            // set variables: $cat, $city
            //
            foreach ($cat as $catid => $categories) {
                foreach ($city as $idRegion => $region) {

                    if ( $catid == $_GET['search_categories'] &&  
                        $idRegion == $_GET['search_region']) 
                    {
                        $title['title'] = sprintf("%s %s", $categories, $region);
                        return $title;
                    }
                }
            }
        }
    }
    return $title;
}

---

I don’t know your code so I may be wrong, but code that determine document name I would move to a function. Being in one place, it will be easier to manage.. Thanks to the static variable, the code will be executed only once, and subsequent function calls will return the previously determined title.
Function se333874_prepare_title you use in se333744_site_title and in PHP file.

functions.php

add_filter( 'document_title_parts', 'se333744_site_title' );
function se333744_site_title( $title )
{
    global $wp_query;
    if ( is_search() )
    {
        if ( isset($_GET['search_region'], $_GET['search_categories']) ) 
            $title['title'] = se333874_prepare_title();
    }
    return $title;
}

function se333874_prepare_title()
{
    static $title = null;
    if ( $title != null)
        return $title;

    $title = false;
    if ( isset($_GET['search_region'], $_GET['search_categories']) ) 
    {
        // set $cat and $city variables here
        //
        foreach ($cat as $catid => $categories) {
            foreach ($city as $idRegion => $region) {

                if ( $catid == $_GET['search_categories'] &&  
                    $idRegion == $_GET['search_region']) 
                {
                    $title = sprintf("%s %s", $categories, $region);
                    return $title;
                }
            }
        }
    }
    return $title;
}

PHP file:

if ( isset($_GET['search_region'], $_GET['search_categories']) ) 
    printf('<h1 class="cat-title">%s %s</h1>', $categories, $region);