Non-unique term slugs, or anything else I can use to build specific pages and permalinks?

My project is a directory of business listings.

Individual listing URL looks as simple as domain.com/five-star-cars – something that WordPress handles out of the box.

But I have a problem drilling into region-based archives. We need a specific URL structure for those. For example, if we want to show all listings in Ohio, we need domain.com/ohio – also simple.

However, if we want to show all listings in Cleveland, Ohio and Cleveland, Nevada – we want to do this:

• domain.com/cleveland/oh
• domain.com/cleveland/nd

So I created a CPT “Listings” and a custom taxonomy “Location”. I added Ohio and Nevada as parent terms and Cleveland as children to both.

Here’s the issue: the slug of the 1st Cleveland is domain.com/location/ohio/cleveland/ but the 2nd one became domain.com/location/nevada/cleveland-nevada/

I found out that term slugs must be unique, so that’s a problem – I can’t use term slugs to build URLs.

What I did next is saving state and city as custom field values in each listing. Now I can use these values (which, unlike term slugs, don’t have to be unique) as global variables via something like this:

function loc_global_vars() {
 global $wp_query;
 $postid = $wp_query->post->ID;
 global $loc_vars;
 $loc_vars = array(
    'state'     => get_post_meta($postid, 'state', true),
    'city'      => get_post_meta($postid, 'city', true),
);
}
add_action( 'parse_query', 'loc_global_vars' );

But now I’m stuck: what are my next steps?

Q1: How do I build archive pages and permalinks using these variables?

Q2: How do I build templates so that I’m able to customize them for every archive type?

Or is there anything obvious that I’ve missed and I’m simply looking into a wrong direction?
So, generally:

Q3: Is there a better way to approach this?