№6(59) декабрь 2013 ТРАНСПОРТИРОВКА В ЛОГИСТИКЕ Об одной целочисленной задаче маршрутизации БРОНШТЕЙН Е. М. доктор физ.-мат наук, профессор кафедры вычислительной математики и кибернетики История задач маршрутизации насчитывает более полувека. <...> Рамсера [4], в которой была сформулирована задача, впоследствии названная VRP – Vehicle Routing Problem. <...> За эти годы было сформулировано множество задач маршрутизации с различными условиями, разработаны различные алгоритмы решения (обзоры см. <...> ). ГИНДУЛЛИН Р. В. аспирант кафедры вычислительной математики и кибернетики Уфимский государственный авиационный технический университет В работе авторов [2] рассмотрен класс монономенклатурных задач маршрутизации, когда одним транспортным средством (ТС) груз следует доставить от некоторых поставщиков потребителям за один рейс. <...> При этом ТС в начальный момент выезжает из депо и в конце должно в депо вернуться. <...> В настоящей статье рассматривается одна из этих задач, в которой предусмотрено, что ТС может посещать каждый пункт многократно. <...> Требуется организовать доставку грузов так, чтобы длина маршрута была минимальной. <...> Эта задача в отличие от некоторых других, рассмотренных в [2], разрешима при любой вместимости ТС. <...> Через a(i) обозначим вес груза в пункте производства (в этом случае a(i)>0) или потребность в пункте потребления (тогда a(i)<0). <...> Допускается, что депо совпадает с пунктом производства, в противном случае a(0)=0. <...> Заданы также матрица C расстояний между пунктами: Cij (i,j=0,1,…,n) – расстояние от i-го пункта до j-го (считаем, что все расстояния конечные, причем матрица не обязательно симметрическая) и S – вместимость ТС. <...> Необходимо найти план перевозок – последовательность пар (u(0), v(0)), (u(1), v(1)),…, (u(N), v(N)) (число Nаприори неизвестно, т.е. тоже является неизвестным, подлежащим определению), первый элемент каждой из которых это номер пункта, т.е. u(i){0,1,…,n}, а модуль второго – вес вывозимого (при v(i)>0) или доставляемого (при v(i <...>