CREATE TABLE `routes`
  ( `route_id` int(11) NOT NULL,
    `p1` int(11) NOT NULL,
    `p1` int(11) NOT NULL,
    `ordr` int(11) NOT NULL,
    KEY `p1p2` (`p1`,`p2`) )
  ENGINE=InnoDB;

select route_id, count(route_id) weight
  from routes
  where p1 IN (x1, x2, ...)
    AND p2 IN (x2, x3, ...)
  group by route_id
  order by weight DESC;

> CREATE TABLE `routes`
>   ( `route_id` int(11) NOT NULL,
>     `p1` int(11) NOT NULL,
>     `p1` int(11) NOT NULL,
тут p2 ты имел ввиду наверное...

>     `ordr` int(11) NOT NULL,
>     KEY `p1p2` (`p1`,`p2`) )
>   ENGINE=InnoDB;
> 

> select route_id, count(route_id) weight
>   from routes
>   where p1 IN (x1, x2, ...)
>     AND p2 IN (x2, x3, ...)

это не правильное услвие! Либо паре присваивай ИД и тогда IN (список ИД) или связывай таблицу саму с собой... как в моем первом селекте. Твое условие работает быстрее, но не правильно

>   group by route_id
>   order by weight DESC;
> 

select route_id, count(route_id) weight
       from routes
            where 
            (p1 = x1) AND (p2=x2) OR
            (p1 = x2) AND (p2=x3) OR
             .....
       group by route_id;