Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 127 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

129
эстафетного метода как одного из важных этапов решения задач
коммивояжера.
Выдвигается предположение: решение задачи коммивояжера –
это
некоторое соединение участков кратчайших маршрутов,
удовлетворяющих заданному требованию
. Когда это требование
заключается в минимизации
длины цикла или величины энергозатрат,
существуют достаточно эффективные методы.
Практический интерес может представлять случай, когда задача
состоит в построении гамильтонова цикла, обеспечивающего
минимальное время доставки грузов, при условии, что скорость
передвижения транспортного средства меняется по некоторому закону в
зависимости от степени его загрузки
α
(0<
α
<1). Решение такой задачи
пока неизвестно и для случая линейной зависимости скорости движения по
участку
ji, от степени загрузки
α
,)()(
min
ijijijij
VVVV +−=
αα
где
min
ij
V – скорость на участке ji, при полной загрузке )1( =
α
;
ij
V –
скорость без загрузки )0( =
α
.
Рассмотренные методы позволяют предложить различные подходы
при дополнительных условиях: наличие двух и более коммивояжеров;
ограничения по грузоподъемности транспортного средства и т.п.

Страницы