Задача последовательного перебора

Впервые этот метод был описан Алирезой Ардаланом в 1984 году в статье «Эвристический подход к эффективному размещению объектов сервиса». Термин «эвристика» означает «эмпирическое правило, позволяющее ограничить доступный набор решений в некоторой сложной предметной области».

Задача последовательного перебора применяется в случае, когда нужно выбрать определенное число мест размещения из большого количества вариантов. Трудность заключается в том, что принятие решения по размещению распределительного центра в какой-либо точке изменяет исходную задачу. Если мы не будем применять метод Ардалана, при наличии большого числа альтернативных мест размещения нам придется решать практически бесконечное количество частных задач.

Предположим, что наша компания планирует открытие двух автосервисов и центров продажи автозапчастей в городах Свердловской области. К рассмотрению принимаются помещения, расположенные в городах: Алапаевске (А), Богдановиче (В), Серове (С) и Ирбите (D). Жители каждого города могут обращаться в автосервисы других городов. Сравнительное удобство такого обращения отражает расстояние между городами. В табл. 4.2 приведенырасстояния между городами, численность населения и относительная важность расположения в них пункта сервисного обслуживания автомобилей.

Относительная важность расположения в городе автосервиса и магазина запасных частей – это комплексный показатель, определяющийся экспертным путем. В данном случае он должен учитывать покупательную способность населения, средний уровень дохода, состояние дорожного покрытия в городе и окрестностях, распределение населения по полу и возрасту, наличие или отсутствие сервисов-конкурентов и т.д.

Прежде всего необходимо рассчитать приведенные расстояния для каждого маршрута движения, умножая расстояние между городами на численность населения и на относительную важность размещения автосервиса именно в этом городе. Так, например, чтобы узнать приведенное расстояние между Алапаевском (А) и Богдановичем (В), необходимо умножить 260 км на 43 тысячи человек и на коэффициент 0,8. Получившееся значение 8944 показывает относительное неудобство для жителей Алапаевска, связанное с обращением в автосервис, расположенный в Богдановиче. Чем больше получившееся значение, тем большее неудобство испытывают наши потребители.

Приведенные расстояния, учитывающиеся на первом этапе рассуждений, представлены в табл. 4.3.

В табл. 4.3 наименьшая сумма наблюдается в столбце С. Следовательно, при размещении автосервиса в городе Серове жители прочих городов будут испытывать наименьшие неудобства. Если бы нам было нужно разместить только один сервисный пункт, наши рассуждения на этом можно было бы окончить. Необходимость выбора места для ещё одного автосервиса несколько усложняет задачу.

В табл. 4.4 представлены приведенные расстояния с учетом того, что один сервисный центр уже размещен в городе Серове. Очевидно, что жители Серова не будут регулярно обращаться в автосервис, расположенный в другом городе. Следовательно, ожидаемое неудобство для жителей Серова от расположения автосервисов в других городах будет равно нулю.

Сравним ячейки АВ и АС табл. 4.3. Приведенное расстояние, которое должны преодолеть жители Алапаевска, чтобы обратиться в автосервис, расположенный в Богдановиче, меньше, чем в случае обращения в уже размещенный автосервис в Серове. Следовательно, если в Богдановиче будет присутствовать автосервис, жители Алапаевска будут преодолевать не более 8944 приведенных километров. Записываем значение 8944 в ячейку АВ табл. 4.4. Аналогично заполняем остальные ячейки.

В случае если бы приведенное расстояние АВ оказалось больше, чем расстояние АС, мы были бы должны записать значение АС в ячейку АВ на следующем шаге рассуждений. Мы исходим из того, что жители изучаемых городов разумно предпочтут преодолеть меньшее расстояние и не станут обращаться в автосервис, расположенный на большем удалении. В табл. 4.4 после уточнения приведенных расстояний выяснилось, что наименьшая сумма – в столбце D. Сумма по столбцу С в этом случае не учитывается, так как в городе

С уже расположен один сервисный центр. Таким образом, второй автосервис мы должны будем расположить в Ирбите (D), так как этот вариант наименее неудобен для жителей прочих городов.

Предположим, что у нас появились свободные средства, достаточные для открытия ещё одного сервисного центра. Изучим ячейку АВ табл. 4.4. Жители Алапаевска (А) в случае нахождения третьего автосервиса в Богдановиче (В) могут обратиться в города B, C или D. Наименьшее приведенное расстояние соответствует автосервису, расположенному в городе D.

Следовательно, жители города Алапаевска из всех сервисных центров выберут именно его, и приведенное расстояние составит 3922. Записываем это значение в ячейку АВ. Аналогично изучаем ячейку ВА. Результаты этих рассуждений приведены в табл. 4.5.

Таким образом, очередной сервисный центр должен быть расположен в городе В (Богданович).
Основная сложность при использовании этого метода – подбор анализируемых параметров и определение значений относительной важности размещения распределительного или сервисного центра в том или ином городе.

Скажем, в рассмотренном выше примере вместо параметра «численность населения» мы могли бы учитывать параметры «количество автомобилей, зарегистрированных в данном городе» или «количество автомобилей определенной марки, принадлежащих жителям этого города». При подборе параметров следует исходить из доступности той или иной информации. Так, если численность населения городов России доступна на сайте Госкомстата (www.gks.ru), то узнать, например, количество автомобилей «Хонда», зарегистрированных в Нижнем Тагиле, значительно сложнее.