2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 оптимальные маршруты перевозок при огранич пропускн способн
Сообщение17.11.2017, 21:16 


12/06/15
11
Задача такая: дана транспортная сеть, для каждого ребра задана стоимость перевозки и пропускная способность. Также задана
матрица корреспонденций для всех вершин, т.е. для каждой пары вершин (v,u) задан объем груза, который нужно перевезти
из вершины u в вершину v. Нужно перевезти грузы в соответствии с заданной матрицей корреспонденций по таким маршрутам, чтобы общая стоимость всех перевозок была минимальной.
Понятно, что при неограниченных пропускных способностях задача становится тривиальной (перевозки нужно осуществлять по путям с наименьшей стоимостью), но вот что делать если пропускные способности ограниченные?
Если кто-то знает где можно найти информацию по такой задаче, то буду очень признателен.

 Профиль  
                  
 
 Re: оптимальные маршруты перевозок при огранич пропускн способн
Сообщение17.11.2017, 22:58 
Заслуженный участник


20/08/14
12027
Россия, Москва
Можно решать последовательным приближением: сначала по путям наименьшей стоимости до исчерпания пропускной способности в каком-то месте, удаляем это место из графа (назначаем бесконечную стоимость), пытаемся развести оставшийся груз.

 Профиль  
                  
 
 Re: оптимальные маршруты перевозок при огранич пропускн способн
Сообщение18.11.2017, 10:25 


12/06/15
11
Dmitriy40 в сообщении #1266218 писал(а):
Можно решать последовательным приближением: сначала по путям наименьшей стоимости до исчерпания пропускной способности в каком-то месте, удаляем это место из графа (назначаем бесконечную стоимость), пытаемся развести оставшийся груз.

Такой подход не дает (гарантировано) оптимальное решение. Может быть так: пропускная способность некоторого ребра e уже исчерпана грузами $q_1$,$q_2$,...,$q_n$, и груз q, для которого путь наименьшей стоимости содержит ребро e, пускаем по маршруту без ребра e. Однако, может оказаться, что если бы мы пустили груз q по маршруту, содержащему ребро e, а какой-то из грузов $q_1$,$q_2$,...,$q_n$ по маршруту, не содержащему ребро e, то мы бы получили более оптимальный план перевозок.

 Профиль  
                  
 
 Re: оптимальные маршруты перевозок при огранич пропускн способн
Сообщение18.11.2017, 10:36 
Заслуженный участник
Аватара пользователя


09/09/14
6328
xelAlex
Я правильно понимаю, что в Вашей постановке задачи любой груз может быть перемещён одной и только одной транзакцией? То есть, грузы не приходится делить на части и маршруты с несколькими точками выгрузки / дозагрузки запрещены.

 Профиль  
                  
 
 Re: оптимальные маршруты перевозок при огранич пропускн способн
Сообщение18.11.2017, 12:46 


12/06/15
11
grizzly в сообщении #1266356 писал(а):
xelAlex
Я правильно понимаю, что в Вашей постановке задачи любой груз может быть перемещён одной и только одной транзакцией? То есть, грузы не приходится делить на части и маршруты с несколькими точками выгрузки / дозагрузки запрещены.

Давайте уточним. У меня задана матрица корреспонденций, т.е. для каждой упорядоченной пары вершин u и v задан объем груза, который необходимо перевезти из u в v. Этот объем груза можно разбить на любое количество частей и провозить по разным маршрутам. Подчеркну, что этот груз должен быть доставлен именно в вершину v, т.е. удовлетворить потребности вершины v в этом грузе за счет перевозок из других вершин нельзя. Наверное можно сказать, что мы имеем дело с многопродуктовой задачей и каждой корреспонденции соответствует свой уникальный продукт.

 Профиль  
                  
 
 Re: оптимальные маршруты перевозок при огранич пропускн способн
Сообщение18.11.2017, 12:58 
Заслуженный участник
Аватара пользователя


09/09/14
6328
xelAlex в сообщении #1266372 писал(а):
Давайте уточним.
Пока не совсем получилось. Я понял, что груз можно разбивать. А можно не разбивать? Утрируя: в одном пункте есть миллион единиц груза объёмом 1 м.куб. каждая. Весь этот груз нужно доставить в (один) другой пункт. Разрешается это сделать одной транзакцией? Я просто хочу понять, зачем заданы объёмы.

-- 18.11.2017, 13:19 --

А, наверное, пропускная способность рёбер выражается в объёмах, а не в количествах транзакций?

 Профиль  
                  
 
 Re: оптимальные маршруты перевозок при огранич пропускн способн
Сообщение18.11.2017, 13:23 


01/11/14
195
Задача сводится к задаче линейного программирования.
Пользуюсь обозначениями из недавно вышедшей статьи http://rts-md.com/index.php/jornalRTS/article/view/25/18.
Там же есть ссылки, на работы, которые могут быть полезными.
Пусть $ \mathcal M, \mathcal M<i,j> \subseteq \mathcal M, \mathcal M(k,l) \subseteq \mathcal M  $ - соответственно множество всех маршрутов, множество маршрутов из $i $ в $ j $, множество маршрутов, проходящих по дуге $ (k,l) $;
$\lambda (\mu) $– интенсивность потока на маршруте $\mu \in  \mathcal M,  \lambda = (\lambda (\mu) )_{\mu \in  \mathcal M }  $ - поток (функция распределения потоков, система потоков, или вектор-поток, или вектор интенсивностей потоков – как угодно) в сети;
$\Lambda = \{\lambda | 0 \le \lambda (\mu) \land \sum_{\mu \in  \mathcal M(k,l) } \le c(k,l) \}$- множество допустимых потоков (ограничено линейными неравенствами).

Задача формулируется в виде:
$S(\lambda) \Rightarrow \max_{\lambda \in \Lambda} $,
где $S()$– стоимость потока (линейный функционал).

Другой вариант задания системы потоков $\lambda $ посмотрите в книге Шварца (см. ссылку выше).

 Профиль  
                  
 
 Re: оптимальные маршруты перевозок при огранич пропускн способн
Сообщение18.11.2017, 16:05 


12/06/15
11
grizzly
Да, пропускная способность ребер выражается в объемах, а не в количестве транзакций

-- 18.11.2017, 18:06 --

Iam
По-моему это то, что нужно. Спасибо огромное!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: STR


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group