Оптимизация использования танкерного флота компании

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

Постановка задачи

Компания обеспечивает доставку нефти танкерами из портов загрузки Ai в порты выгрузки Bj (рис. 22.1). В каждом порту Ai составлен график, в соответствии с которым для танкеров компании выделены терминалы за­грузки в определенные, заранее известные дни в течение всего года. Анало­гично этому, в портах Bj танкерам компании выделены терминалы выгрузки

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

Необходимо составить график движения танкеров между портами, т. е. оп­ределить количество танкеров и для каждого из них составить расписание, включающее дату отправления и порт назначения для каждого рейса. Задача в общем случае является недетерминированной: время каждого рейса между каждой парой портов зависит от погодных условий. Мы рассмотрим детер­минированный случай, но поскольку для решения задачи будет использо­ваться имитационная модель, обобщение на недетерминированный случай не будет представлять проблем. Экономии в рамках проекта предполагается • достичь за счет минимизации необходимого числа танкеров для перевозки нефти.

Оценка необходимого числа танкеров

Несложно построить грубые оценки числа необходимых танкеров. Оценим сначала максимальное число танкеров. Это число потребуется при худшем из возможных правил принятия решения, когда каждый день в порту по­грузки на рейде стоит новый танкер. Пусть Tmах — максимальное время в пути между портами Ai и Bj туда и обратно. Ясно, что через Tmах дней

танкеры будут возвращаться из портов разгрузки обратно в порты погрузки. В итоге максимальное число нужных танкеров ограничено числом п*Tmах, где n — число портов погрузки. С другой стороны, нет смысла иметь танке­ров больше, чем суммарное число дней d, выделенных компании для по­грузки танкеров в течение года. Таким образом, шах = min(D, п*Tmах).

Теперь оценим минимальное количество требуемых танкеров. Пусть Tmin — минимальное время в пути из порта погрузки в порт выгрузки и обратно. Тогда любой танкер совершит не больше, чем 3 65/Tmin перегонов. Исполь­зуя непростаивающие танкеры, которые следуют по кратчайшим путям, мы будем использовать не менее, чем D*Tmin/365 танкеров. Эта величина и яв­ляется оценкой снизу числа необходимых компании танкеров.

Подход к решению задачи

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

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

Выделим два типа событий, при наступлении которых нужно принимать решение о дальнейшем пути каждого танкера. Первое событие — окончание погрузки танкера в порту Ai. При наступлении этого события необходимо выбрать для этого танкера порт назначения Bj и день разгрузки в этом пор­ту. Будем выбирать порт с учетом некоторых соображений.

□ Не будем отправлять танкер в дальний порт. В этом случае танкер осво­бодится раньше и им можно перевезти больше груза. Таким образом, "выгодность" порта назначения Bj после загрузки танкера в порту Ai должна зависеть от времени движения Tij из порта Ai в порт Bj. Чем это время меньше, тем более "выгоден" порт Bj в момент принятия решения о направлении в него танкера из порта Ai.

□ Оценим, насколько близко от дня вероятного прибытия танкера в порт назначения находится день разгрузки, чтобы танкеру не пришлось слиш­ком долго ожидать разгрузки. Таким образом, "выгодность" порта назна­чения зависит и от интервала р между моментом прибытия танкера и за­планированным днем разгрузки.

□ Оценим, насколько позже после определенного в расписании дня раз­грузки прибывает танкер в порт назначения. "Выгодность" порта Bj будет зависеть также от интервала q времени между запланированным днем разгрузки и вероятным днем прибытия танкера.

Итак, для принятия решения сформулированы три частных критерия, и ка­ждый из них выражается численным показателем "выгодности" конкретного направления танкера после события окончания его загрузки. Для получения единственного скалярного критерия принятия решения, выберем аддитив­ный критерий, сложив все частные критерии с некоторыми весовыми ко­эффициентами. Критерий к выбора порта назначения можно записать так:

К = wl*Tij + w2*P + w3*Q

при дополнительном условии:

Величина wi определяет важность соответствующего частного критерия оп­тимальности и количественно задает относительное предпочтение одного критерия над другими. Теперь при наступлении события "танкер закончил погрузку в порту Ai", выбор порта назначения в j для него может быть про­изведен на основе сравнения значений критерия "выгодности" к для всех портов назначения Bj и выбора среди этих значений минимального.

Аналогичные правила можно применить после наступления события "тан­ кер закончил разгрузку в порту Bj " при выборе порта назначения Ai.

Имитационная модель