Задача прикрепления поставщиков к потребителю

В литературе описан ряд классических транспортных задач и методов их решения.

Задача о коммивояжере.

Имеются города, пронумерованные числами 1, 2, …, n. Выехав из города 1, коммивояжер должен объехать все остальные города, побывав в каждом из них по одному разу и вернуться в исходный город. Известно расстояние между городами i и j (i, j=1,2,…,n)/

Требуется найти самый короткий маршрут.

(коммивояжер выезжает их каждого пункта только один раз).

Модель классической транспортной задачи.

Однородный продукт, находящийся в К пунктах производства в количестве требуется доставить в L пунктов потребления. Потребность в продукции в этих пунктах равна . Полагаем, что общий объем поставляемой продукции равен объему потребности:

Стоимость транспортных издержек по перевозке единицы продукции из любого пункта производства в любой пункт потребления ( i – номер пункта производства, j – номер пункта потребления).

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

Условие классической транспортной задачи в общем виде можно записать как линейную модель с ограничениями:

;

продукция, отправляемая из пунктов производства

;

продукция, поступающая в пункты потребления

, .

Кроме экономико-математического моделирования существуют и иные подходы, использование которых дает достаточно эффективные решения.

Например.Организация перевозок с маршрутами в виде лепестков маргаритки (подход).

Условия:

-нет пересечения соседних маршрутов;

- величина каждой остановки поглощает лишь незначительную часть возможностей транспортного средства;

- разветвленная сеть дорог.

Такая схема может быть получена с помощью применения следующих правил.

- начинайте с удаленной точки.

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

- повторять шаг 2 до тех пор, пока грузовик не будет использован полностью.

- установить последовательность в форме лепестка.

- найти следующую наиболее удаленную точку, не включенную к данному моменту времени в лепестки, и повторить шаги .

Формирование маршрутов таким образом может дать хорошие результаты, соперничающие с методами математического решения проблемы.

Иногда, для построения маршрутов движения транспортных средств используют последовательно несколько методов и подходов.

Составление кольцевых маршрутов в первом приближении может осуществляться методом известным как алгоритм Свира или алгоритм стеклоочиcтителя.

Суть алгоритма заключается в том, что ось x подобно стеклоочистителю начинает постепенно вращаться против или по часовой стрелке, «стирая» при этом с координатного поля изображенные на нем магазины – потребители материального потока. Как только сумма заказов «стертых» магазинов достигнет вместимости транспортного средства, фиксируется сектор, обслуживаемый одним кольцевым маршрутом. В пределах каждого сектора составление кольцевого маршрута может осуществляться посредством решения задачи коммивояжера.

Вопрос 124. Показатели работы транспорта. Продукция транспорта – перевозки пассажиров и грузов. Определяется в денежном и условно-натуральном выражении. Различают валовую и чистую транспортную продукцию.

Продукция транспорта валовая в денежном выражении – доходы от перевозок пассажиров и грузов.

Продукция транспорта чистая – те же доходы за вычетом эксплуатационных затрат (затрат на топливо, материалы и т. п.).

Качество продукции – комплексный показатель, рассчитываемый по совокупности: соблюдение перевозчиком сроков доставки, отсутствие случаев утраты, повреждения грузов, предоставление грузоотправителю и грузополучателю дополнительных услуг.

Производительность транспортного средства – объем работы в единицу времени (час, сутки и др.).

Для грузовых автомобилей – количество тонно-километров (тонн) в среднем на 1 тонну грузоподъемности в единицу времени.

Для грузового вагона – измеряется в тонно-километрах за одни вагоно-сутки.

Для морского судна – объем работы судна в единицу времени измеряется количеством тонно-миль, приходящихся на 1 т грузоподъемности в среднем за сутки.

Для речного – произведение тонно-км/сутки на единицу грузоподъемности или на единицу мощности.

Коэффициент использования грузовместимости – показатель, отражающий часть полного объема грузовых помещений транспортного средства, используемого для размещения груза. У грузовых вагонов коэффициент использования грузовместимости рассчитывается как частное от деления погрузочного объема на полный объем

Коэффициент использования грузоподъемности (подвижного состава) – степень использования грузоподъемности автомобиля, вагона, судна, самолета. Коэффициент использования грузоподъемности автомобиля характеризует использование номинальной грузоподъемности автомобиля в статике и динамике. Статический коэффициент – отношение загрузки автомобиля в тоннах к его номинальной грузоподъемности в момент окончания погрузки. Определяется за одну ездку – делением количества фактически перевезенного груза на номинальную грузоподъемность автомобилей; за смену – делением объема перевозок на произведение номинальной грузоподъемности и количества выполненных за смену ездок. Динамический коэффициент определяется делением фактических тонно-километров на возможные тонно-километры при полном использовании грузоподъемности. Коэффициент использования грузоподъемности вагона может быть исчислен делением средней статической нагрузки вагона на среднюю его грузоподъемность. Коэффициент использования грузоподъемности судна определяется как частное от деления величины тонно-километров (тонно-миль), фактически выполненных судном за отчетный период, на количество тоннаже-километров (тоннаже-миль) в порожнем и груженом состоянии за этот период. Коэффициент использования коммерческой грузоподъемности самолета характеризует использование его нормативной коммерческой грузоподъемности. Определяется делением приведенных тонно-километров на предельный объем тонно-километров приведенных.

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

Коэффициент использования парка транспортных средств по времени – отношение отработанных машино-часов к числу машино-часов пребывания в парке.

Коэффициент использования парка транспортных средств по выпуску – отношение количества машин (вагонов) в движении (на линии, в рейсе) к числу машин (вагонов) в наличии.

Коэффициент использования пробега (автомобиля) – показатель, характеризующий удельный вес производительного (с грузом) пробега автомобиля в его общем пробеге. На коэффициент использования пробега влияют состав клиентуры и территориальное размещение пунктов погрузки и разгрузки, структура парка подвижного состава по специализации, характер грузовых потоков (односторонний, двусторонний) и т. п.

Коэффициент порожнего пробега (подвижного состава, средства транспорта) – характеризует величину порожнего пробега и зависит от особенностей работы и использования транспортных средств, их специализации, а также размещения пунктов производства и потребления, сырьевых источников и пунктов переработки продукции и др. на железнодорожном транспорте этот показатель исчисляется только для грузовых вагонов как в целом, так и по родам вагонов отношением порожнего пробега к общему и отдельно к груженому пробегу. На автомобильном транспорте определяется как отношение величины пробега автомобиля без груза (пробега автобуса без пассажиров или пробега такси неоплаченного) к величине общего пробега автомобилей (автобусов или такси). На морском транспорте – балластные пробеги(переходы), которые морские транспортные суда проходят без груза. Для флота (группы судов) определяется делением тоннаже-миль балластного пробега на тоннаже-мили общего пробега; для отдельного судна – делением балластного пробега на общий пробег судна.

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