/service_locations/city-name/

/serivce_locations/city-name/service-type/

add_action( 'init', 'service_locations' );
function service_locations() {
    register_post_type('service_locations', array(
        'label' => 'Service Areas',
        'description' => '',
        'public' => true,
        'show_ui' => true,
        'show_in_menu' => true,
        'capability_type' => 'post',
        'hierarchical' => true,
        'rewrite' => true,
        'query_var' => true,
        'exclude_from_search ' => true,
        'has_archive' => true,
        'supports' => array(
            'title',
            'page-attributes'
            ),
        )
    );
}

/city-name/

/city-name/service-type/

// Remove the slug from published post permalinks. Only affect our CPT though.
function vipx_remove_cpt_slug( $post_link, $post, $leavename ) {
    if ( ! in_array( $post->post_type, array( 'service_locations' ) ) || 'publish' != $post->post_status )
        return $post_link;
    $post_link = str_replace( '/' . $post->post_type . '/', '/', $post_link );
    return $post_link;
}
add_filter( 'post_type_link', 'vipx_remove_cpt_slug', 10, 3 );

function vipx_parse_request_tricksy( $query ) {
    if ( ! $query->is_main_query() )
        return;

    if ( 2 != count( $query->query )
        || ! isset( $query->query['page'] ) )
        return;

    if ( ! empty( $query->query['name'] ) )
        $query->set( 'post_type', array( 'post', 'service_locations', 'page' ) );
}
add_action( 'pre_get_posts', 'vipx_parse_request_tricksy' );