Эта модель является типичной моделью логистики. Она не сводится к классическим задачам составления расписаний. Этот факт и стохастичность основного параметра — времени движения между двумя портами — приводят к мысли об использовании имитационного моделирования для решения задачи.
Постановка задачи
Компания обеспечивает доставку нефти танкерами из портов загрузки 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.
Имитационная модель
