در یک مسئله مکان­ یابی میانه روی شبکه ­ها (گراف­ ها)، هدف پیدا کردن یک مجموعه از بهترین مکان­ ها روی یک گراف معین جهت تاسیس یا استقرار تسهیلات می­ باشد به طوری که مجموع فواصل مشتریان موجود از نزدیک­ترین سرویس­ دهنده کمینه شود. در این مقاله، یک مدل مکان­ یابی میانه نیمه ناخوشایند روی شبکه­ ها  در نظر گرفته می­ شود که در آن تمامی مشتریان به شکل زیرگراف تعریف می­ گردند. یک الگوریتم رقابت استعماری دودویی جدید برای یافتن جواب­های مدل تحت مطالعه پیشنهاد می­ گردد. نتایج محاسباتی ما نشان می ­دهند که این الگوریتم از سرعت و دقت بالایی برخوردار می­ باشد.