Para uma solução mais limpa, você pode utilizar a função FIND_IN_SET
para buscar algo em uma lista, sem necessidade de altera-la:
select
nm_linha
from
linhas
where
find_in_set($cod_cidades, replace(cidades_origem, ' ', ''))
and find_in_set($cod_bairros, replace(ida, ' ', ''))
and find_in_set($cod_cidades2, replace(cidades_destino, ' ', ''))
and find_in_set($cod_bairros2, replace(ida, ' ', ''))
Baseado no seu exemplo de lista, utilizei o REPLACE
somente para remover os espaços, mas se tiver a possibilidade de já guardar esses valores sem espaços já elimina esta função da sua query.
Aqui está um SQL Fiddle para você testar a solução.