Задачи по определению кратчайшего пути доставки пассажиров и грузов

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

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

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

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

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

А). Исходные данные

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

Пусть задана транспортная сеть (рис. 4.1), состоящая из станций А₀, А₁ и т.д. и коммуникаций, соединяющих некоторые из этих станций.

Рис. 4.1. Принципиальная схема транспортной сети.

Длины коммуникаций предполагаются известными и равными Cij (на рисунке это цифры над стрелками). Если станции Аi и Аj непосредственно не соединены друг с другом, предполагаем что Сij равна бесконечности. Из начальной станции А0 (на рисунке эта станция обозначена кругом с цифрой 1) на конечную станцию Аn+1 (круг с цифрой 7) можно попасть через большое количество путей, проходящих через разные промежуточные станции. Требуется выделить из всех путей путь наименьшей длины. Поясним, что длины коммуникаций могут означать время движения, стоимость перевозок от станции до станции, вероятности своевременной перевозки груза от станции до станции и др.

Б). Экономико-математическая модель решения задачи

Приведем в соответствии каждой паре пунктов Аi и Аj величины Хij.

Если участок АiАj принадлежит кратчайшему пути Хij=1 и, Хij =0 в противном случае. Задача о кратчайшем пути в таком случае может быть сведена к выбору чисел Хij, для которых сумма произведений длины дуг на искомые переменные Хij стремится к минимуму при условиях:

(1)

(2)

(3)

(4)

(5)

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

Условие 3 означает, что количество коммуникаций из исходного пункта А0 превышает на единицу число коммуникаций входящих в исходный пункт.

Аналогичным образом условие 4 свидетельствует о том, что в конечный пункт Аn+1 входит на одну коммуникацию больше, чем выходит.

Вместе с условием 2 и требованием минимизации целевой функции 1 условия 3 и 4 означают, что на каждую станцию Аi приходит ровно одна коммуникация и из каждой станции Аi исходит ровно одна коммуникация.

Условие 5 в задаче эквивалентно требованию, согласно которому все значения Хij равны нулю или единице.

Таким образом, соотношения 1-5 определяют кратчайший путь в сети. Необходимо еще раз отметить, что в качестве длин дуг могут быть не только километры, но и другие показатели, например стоимости, время и т.д.

Методика решения этой задачи с использованием общедоступного и широко используемого программного продукта Microsoft Excel приведена автором в [4].

Задачи по определению оптимального плана перевозок пассажиров и грузов

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

Рассмотрим задачу по определению оптимального плана перевозок грузов от поставщиков в организации туристского комплекса (например, гостиницы).

А). Исходные данные

Крупная туристская компания имеет в собственности пять гостиниц. В каждой из них организовано питание клиентов. Для приготовления пищи требуется исходные продукты, которые могут доставляться с трех баз. Требуется найти оптимальный план перевозок исходных продуктов. На базах имеются следующие запасы исходных продуктов: №1 - 1 тыс. кг, №2 - 2 тыс. кг, №3 - 4 тыс. кг. Потребности гостиниц во фруктах составляют: №1 – 0, 4 тыс. кг, №2 – 0, 5 тыс. кг, №3 – 0, 7 тыс. кг, №4 – 0, 9 тыс. кг, №5 – 0, 9 тыс. кг. Стоимость перевозок 1 кг фруктов приведена в таблице 4.1.

Таблица 4.1.

Стоимость транспортировки 1 кг исходных продуктов от баз

до гостиниц (руб. за 1 кг)

Б). Экономико-математическая модель решения задачи

Пусть - количество исходных продуктов (груза), перевозимого от поставщика (из исходного пункта) -му потребителю (в пункт назначения, гостиницу) (рис. 4.2). Количество груза, имеющегося у -го поставщика обозначим через , а количество груза, необходимого -му потребителю через . Стоимость перевозки (или стоимость перевозки и закупки) одной единицы груза от -го поставщика -му потребителю равна . Тогда задача определения оптимального плана перевозок грузов от поставщиков потребителям по критерию минимума затрат на перевозки в общем виде формулируется следующим образом:

Рис. 4.2. Транспортная модель.

, (6)

, (7)

, (8)

. (9)

Целевая функция и ограничения задачи интерпретируются следующим образом:

целевая функция (6) минимизирует затраты на закупку и доставку грузов (исходных продуктов);

условия (7) требует удовлетворения потребностей каждого потребителя в грузах (исходных продуктах);

условие (8) указывает, что суммарный объем перевозок грузов (материальных средств) от каждого производителя не может превысить его возможностей по производству этих грузов (исходных продуктов);

условие (9) учитывает пропускную способность транспортных коммуникаций и требование неотрицательности переменных .

Как и для задачи на определение кратчайшего пути, методика разработки оптимального плана перевозок с использованием общедоступного и широко используемого программного продукта Microsoft Excel приведена автором в [4].