На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) 1 [2]  все  ( Перейти к последнему сообщению )  
> Грузовик доставляет товары по сетке магазинов (оптимальный маршрут) , нужен графовый алгоритм, не пойму какой
    swf,
    Предложенный мной алгоритм не исключает упрощения и эвристики
    Если "магазинов" много, и значение 2^n (где n - количество магазинов) большое, становится не рационально генерировать все комбинации маршрутов
    На этапе 1-2 исключаем варианты, в которых расстояние больше определенного, либо, как предложили Вы группируем магазины, в качестве группировки можно использовать алгоритм k-means
    Этап 1-2 делается один раз для заданной логистической схемы, поэтому на него можно потрать определенное время

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

    Думаю, что для небольшой сетки (пару десятков магазинов) можно найти оптимальное решение через линейное программирование, для большего количества, используя эвристики, достаточно близкое к оптимальному за разумное время.
      Есть вот какое предложение ...

      Допустим у нас не 10 магазинов, а стопицот миллионов (пусть это размер N). Полный перебор сразу можно делегировать правнукам. Но задачу же все равно нужно решать. А что если произвести предварительную "подготовку"?

      1) Матрицу NxN разделить на крупные области, ну как в картографии - "квадраты"
      2) Если квадраты получаются тоже большого размера, каждый квадрат так же разделить на "под-квадраты"
      3) Итерация п.2 до разумных размеров полученных "под-квадратов"
      4) Построить матрицы стоимостей путей между квадратами, под-квадратами, под-под- квадратами, но только на своих уровнях

      И теперь получается следующее. Пусть грузовик находится в квадрате A1, и есть варианты куда доставить груз - это квадраты M122, N3, Z14. По предварительно рассчитанным данным мы сразу выбираем нужный квадрат, в нем подквадрат и т.д.

      Предложение мое конечно "сыровато", но оно призвано уменьшить объемы пересчетов путем отсечения ненужных областей для пересчетов.
        to m-ch
        Приветствуем нового рыцаря участника Алгоритмов!
        Давно уже к нам специалисты не заглядывали.

        Задача массовая, много раз возникала на моём жизненном пути (то газовые баллоны по частным домам развозят, то хлебобулочные изделия по магазинам несколькими транспортными средствами различной ёмкости).
        Не бралась за неё. И сейчас не возьмусь. Просто не удержалась и вставила свои 3 коп.
        Нет входных данных.
        Все эвристические алгоритмы доводятся до рабочего состояния на входных данных.
        То есть вначале надо получить данные хотя бы за полгода (данные - это расписания, которые составлял человек-диспетчер), лучше за год, ещё лучше побеседовать с диспетчером и выяснить, какие ограничения можно нарушать, а чего нарушать крайне нежелательно, потом обязательно писать код и смотреть как это работает на реальных данных, менять алгоритмы.

        Но могу сказать одно, по опыту решения других задач.
        Если для подобной, весьма сложной реальной задачи с элементами коммивояжера, для большой размерности сделать эвристический алгоритм, который будет прекрасно (и быстро!) работать, то работать он будет не по науке и статью про это не напишешь.
        А вот если делать чем-то модным (неважно чем, лишь бы мейнстрим), например, генетическими алгоритмами, то работать оно будет плохо, зато с публикациями будет полный порядок.
        Либо шашечки, либо ехать. Вот такая моя т.н.т.з. :D
        Сообщение отредактировано: swf -
          Цитата JoeUser @
          стопицот миллионов

          Один грузовик не осилит :lol:

          Есть "главный" вопрос: это теоретическая задача или это будет практическое применение?

          На практике. За достоверность не ручаюсь.
          Заказы надо получать утром, это если это продуктовые магазины. Хозяйственные, строительные и т.д. в течении дня или недели.
          Один грузовик не будет возить продукты и не продукты (даже по очереди), сан.нормы.
          Продукты развозятся или с местных заводов или с центрального склада. В первом случае получается узко специализированная поездка, например, развозка из теплицы огурцов и помидоров, что одним грузовиком можно охватить много магазинов. Хлебобулочные сразу же с пекарни отгружаются в магазины, молочка тоже. У каждого может быть свой грузовик, а возможно общий.
          Не продукты так же возможно отгрузка не с центрального склада, а с фабрики/завода и так же будет тематической.

          Мне кажется, что задача, приближенная к реальности, будет решаться проще, с разбивкой на частные случаи или подзадачи.

          Добавлено
          Если чисто теоретически, что за товар не известно, т.е. не делим продукты и не продуты и один склад.

          На вскидку вижу два стартовых шага/направления с повторением цикла:
          1) Берем тот продукт, масса которого самая большая, строим для него оптимальный маршрут(ы), может быть с несколькими поездками, в последнем случае с не полной загрузкой, докидываем потребность этих же магазинов другим товаром.
          2) Берем такой товар, для которого самый длинный маршрут по длине пути или по количеству магазинов. В случае недогруза, докидываем товарами из объезжаемых магазинов.
            Если рассуждать логически из физического смысла задачи, грузовик имеет грузоподъемность (это не почтальон который может носить 100 писем)
            поэтому число посещаемых магазинов будет варьироваться от 1 до 7 (6/3.2)...(6/0.8).
            Теперь можно составить списки (цепочки) посещений магазинов которые удовлетворяют условию: Сумма отвозимых товаров не более грузоподъемности.
            пример
            вариант 1
            A(3.0) - B(2.5) - C(0.5)
            D(2.5) - E(1.5) - F(1.0) - G(0.5)
            H(1.0) - I(1.0) - J(1.0)
            вариант 2
            A(3.0) - D(2.5) - C(0.5)
            B(2.5) - E(1.5) - F(1.0) - G(0.5)
            H(1.0) - I(1.0) - J(1.0)
            и т.д.
            Простой перебор (вариантов цепочек + перебор внутри цепочек) решает задачу. Критерий для сравнения вариантов суммарный путь грузовика.
              Что такое оперативное планирование производства при горизонте планирования сутки.
              Утром появляется суточный портфель заказов.
              Эти данные загружаются в программу, нажимают кнопку, через 5(пять) минут должен выйти план.
              Поэтому линейное программирование сразу идёт в топку.

              Далее, предположим, мы написали программу для 20 магазинов. А 20 магазинов ещё можно перебрать.
              А через некоторое время появляются ещё 5 магазинов, уже программа идёт в топку.
              Магазины, конечно, надо агрегировать и для понижения размерности задачи, и на случай увеличения размерности входных данных.
              Новые магазины добавляются в группы. а там можно увеличивать количество "ходок" при увеличении объёма товара.

              Далее, фирма прикупила ещё два транспортных средства, разной ёмкости.
              Программа для одного грузовика идёт в топку.
              С другой стороны, для разработчика это хорошо, без дела не сидит :D
                Цитата
                Эти данные загружаются в программу, нажимают кнопку, через 5(пять) минут должен выйти план.
                Поэтому линейное программирование сразу идёт в топку

                А можно пояснить что значит через 5 минут должен выйти план.
                Компьютер считает исключительно быстро, (при малом числе вариантов например менее 1000 магазинов) слабым звеном здесь является оператор(диспетчер) который вводит данные тут и 5 и 30 мин может быть ... но при удобном интерфейсе программы и при правильном планировании рабочего времени проблем не вижу.
                Цитата
                Далее, предположим, мы написали программу для 20 магазинов

                Цитата
                Далее, фирма прикупила ещё два транспортных средства, разной ёмкости

                Могу написать программу для N магазинов и K грузовиков, каждый из которых M(K) грузоподъемности, руководствуясь вышеизложенным принципом построения цепочек по грузоподъемности. Но оставлю этот алгоритм для автора, дабы не лишать его удовольствия от создания интересной и полезной программы.
                  5 минут прописывается в техзадании, это требование заказчика.
                  Если задача включает в себя коммивояжера и размерность задачи 250 (с точки зрения заказчика, это совсем немного), то размерность пространства решений равна 250!, это больше чем число атомов в видимой нами части вселенной.
                  Впрочем, заказчика атомы в видимой нами части вселенной не волнуют, он точно знает, что он нажал кнопку и не более чем через 5 минут должен выйти суточный план.
                    Цитата
                    Могу написать программу для N магазинов и K грузовиков, каждый из которых M(K) грузоподъемности

                    Но пока занят другим проектом, и кроме того коммерческого предложения на разработку этой программы у меня нет. В области реального количества вариантов которые останутся если сначала отбраковать все невозможные, решение не будет занимать много компьютерного времени. В этом я и вижу смысл "не искать лучший математический алгоритм" а "отбраковать все нереальные на ранней стадии"
                      Цитата swf @
                      Если задача включает в себя коммивояжера и размерность задачи 250 (с точки зрения заказчика, это совсем немного), то размерность пространства решений равна 250!, это больше чем число атомов в видимой нами части вселенной.

                      Ну это именно теоретический подход с прицелом "на статью".

                      А практически из 31 с хвостом тысячи межмагазинных линков после отсеивания заведомо идиотских останется тыща, ну может две, да и те распадаются на десяток-другой кластеров. То есть в реальности, как и сказал Маршал,
                      Цитата Маршал @
                      число посещаемых магазинов будет варьироваться от 1 до 7

                      То есть программно практически без итераций формируется 99% плана разъездов. И лишь остаток закрывается с использованием всех существующих связей - да и его проще закрыть "ближними перетасовками", чем одним покрывающим маршрутом. Даже жадный алгоритм, начинающий с дальних узлов, я думаю, отлично справится с задачей - нам же нужно получить план развоза, а не доказательство, что он оптимален...
                        Цитата Akina @
                        Цитата swf @
                        Если задача включает в себя коммивояжера и размерность задачи 250 (с точки зрения заказчика, это совсем немного), то размерность пространства решений равна 250!, это больше чем число атомов в видимой нами части вселенной.

                        Ну это именно теоретический подход с прицелом "на статью".

                        С этого начинается работа математика-постановщика. Вначале определяется класс задачи.
                        Затем у заказчика запрашивается максимальный размер входных данных и определяется размерность пространства решений.
                        И после этого сразу отбрасываются те методы, которые не укладываются в 5 минут в оперативное планирование.
                          0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                          0 пользователей:


                          Рейтинг@Mail.ru
                          [ Script execution time: 0,0363 ]   [ 15 queries used ]   [ Generated: 19.03.24, 09:36 GMT ]