Checkbox options to filter search

I have 1 custom post type and multiple post categories.

Currently I am displaying all of the category names in a list in a sidebar but as this is a job site then I have 3 different lists so list 1 is full time, part time etc., list 2 is location etc. so my code is below.

<?php
	$customPostTaxonomies = get_object_taxonomies('jobs');

if(count($customPostTaxonomies) > 0)
{
     foreach($customPostTaxonomies as $tax)
     {
	     $args = array(
         	  'orderby' => 'name',
	          'show_count' => 1,
        	  'pad_counts' => 0,
	          'hierarchical' => 1,
        	  'taxonomy' => $tax,
	          'exclude' => '15,17,18,12,16,14,13',
        	  'title_li' => ''
        	);

	     wp_list_categories( $args );
  }
}
?>

    <div class="sbar-sub-title2">Location</div>
     <?php
	$customPostTaxonomies = get_object_taxonomies('jobs');

if(count($customPostTaxonomies) > 0)
{
     foreach($customPostTaxonomies as $tax)
     {
	     $args = array(
         	  'orderby' => 'name',
	          'show_count' => 1,
        	  'pad_counts' => 0,
	          'hierarchical' => 1,
        	  'taxonomy' => $tax,
		  'exclude' => '15,17,9,18,1,16,18,11,8',
        	  'title_li' => ''
        	);

	     wp_list_categories( $args );
  }
}

?>

    <div class="sbar-sub-title2">Job Position</div>
     <?php
	$customPostTaxonomies = get_object_taxonomies('jobs');

if(count($customPostTaxonomies) > 0)
{
     foreach($customPostTaxonomies as $tax)
     {
	     $args = array(
         	  'orderby' => 'name',
	          'show_count' => 1,
        	  'pad_counts' => 0,
	          'hierarchical' => 1,
        	  'taxonomy' => $tax,
		  'exclude' => '9,1,12,14,13,8,11',
        	  'title_li' => ''
        	);

	     wp_list_categories( $args );
  }
}

?>

When clicking any of the links, all jobs in that category only are displayed on the page.

What I want to do now though in addition to the above (so I would have a list of links as I have but also what i want as described below) is to go further and make it more complete so I want each category to be a checkbox and when a user checks multiple boxes the results are whatever matches the boxes they’ve checked.

So if a user wants to see all full time jobs in Blackpool for example, they would check ‘full time’ and ‘blackpool’ but how would I do this?

I tried the search and filter plugin but this doesn’t quite too what i want. With the plugin if you check ‘full time’ and ‘blackpool’, it gives any job that is in either category and not only jobs that are in both categories.

Ultimately I wan the user to be able to drill the results down to match exactly what they want.

Any advice is greatly appreciated.