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

    1. Вот 100пудово это НА ГРАФЫ (неор.графы)!
    2. Под оптимальностью, что понимать? Ну, мне кажется, что минимизация пройденного пути грузовиком. (не факт, что я прав)
    3. Как понимаю, грузовик не факт, что управится за 1 рейс. Может быть и 2 и 3 и 23 рейса...
    4. Все товары на складе, т е грузовик стартует с хаба и "дозаправляется" товаром также со склада
    *5. Из условия вроде не гарантируется, что есть ПРЯМОЙ путь от склада до любого магазина (не уверен)

    Это вообще, в сторону чего копать графы нужно?

    Подскажите как быть-то?
    спс за внимание!
      Цитата
      Есть задача, примерно такого содержания

      Все-таки надо уточнить - что на входе, что должно получиться на выходе. Если на входе конкретный список заказов для конкретной поездки (без "дозаправки"), то решение тривиально (тупой перебор небольшого количества вариантов). Если есть очередь заказов, не влезающих в грузовик, тогда все уже сложнее. Если и очереди нет, а есть неупорядоченный набор заказов, и нужно минимизировать общее время доставки, то это уже две сложные задачи.
      Сообщение отредактировано: AVA12 -
        Если предположить, что обеспечение всех заказов является обязательным условием, возможны два критерия. Первый - минимизация времени. Второй - минимизация тонно-километров (в первом приближении - расстояния).

        В принципе обе версии фактически сводятся к одной - к задаче о рюкзаке. Где на первом шаге определяется количество рейсов, которое получится roundup(общий вес / грузоподъёмность), возможно ещё плюс один, если расстояние сильно варьирует. А на втором выполняется деление на рюкзаки (загрузки), для загрузок в несколько точек - минимизация расстояния/времени.

        В общем, по большому счёту, NP или очень близко, так что да, динамика на базе графа.
          Я бы не стал априорно высчитывать количество рейсов. Может получиться так, что для минимизации тонно-километров количество рейсов должно быть в несколько раз больше такого минимума.
            на рис. один из вариантов такой сети дороги-магазины-хаб

            Прикреплённая картинка
            Прикреплённая картинка


            Т е программа запрашивает кол-во магазинов, затем их названия, затем расстояние между магазинами или хабом и магазином (инициализация) - тут все понятно!

            Сразу оговорка: товар однотипный, т е это НЕЧТО, имеющее какой-то вес и все)

            Затем в программе вводится для магазинов, кол-во необходимого им товара, например:
            1 1.1
            3 0.85
            4 3.3
            5 1.7
            ...
            Если кол-во товара для какого-то магазина НЕ ЗАДАЕТСЯ, значит оно равно 0 (логично)

            Грузовик (6тонн) начинает движение с ХАБА (всегда) и заканчивает движение в ХАБЕ (всегда). Его цель: доставить товар во все магазины в нужном кол-ве. Остатка в кузове быть НЕ ДОЛЖНО, т е приезжает на ХАБ пустым. В процессе доставки товаров может многократно проезжать через ХАБ, т е нет цели посещать магазины (вершины графа) ровно по 1 разу.
            Поскольку кол-во магазинов может быть очень большим и большинство из них хотят заполучить этот товар, то обычно за 1 рейс грузовик не управится. Кол-во рейсов НЕ имеет значения (столько, сколько нужно).

            Цель грузовика: намотать мин.километраж (кол-во рейсов НЕ важнО), обслужив все магазины.
            Кол-во товара на складе неограниченно.


            AVA12, не знаю, ответил ли я этим на твои вопросы...

            Цитата Akina @
            В общем, по большому счёту, NP или очень близко,

            т е даже НЕ нужно считать кратчайшие расстояние от ХАБА до каждого магазина (алг.Дейкстры)?

            Добавлено
            также давайте считать, что товар НЕ МОЖЕТ разгружаться частично, т е грузовик приехал в магазинN и отгрузил ВЕСЬ товар, который нужен этому магазину при условии, что в кузове есть необходимое кол-во товара (а если нет необходимого кол-ва товара, тогда спрашивается, зачем он туда приехал) )
            может это важно)
              Ну, вроде, ясно. Получается самый сложный случай, задача коммивояжера плюс задача о рюкзаке. Разве что принцип "один магазин - одна доставка" слегка утешает. Надо думать.
                Цитата FasterHarder @
                а если нет необходимого кол-ва товара, тогда спрашивается, зачем он туда приехал

                Граф - кольцо из хаба и 3 магазинов. Потребность каждого 2, грузоподъёмность 3.

                Добавлено
                Цитата AVA12 @
                Разве что принцип "один магазин - одна доставка" слегка утешает.

                Причём на порядки. Фактически сводя задачу к линейному раскрою (или получится совсем нереальный граф).
                Сообщение отредактировано: Akina -
                  Цитата Akina @
                  Граф - кольцо из хаба и 3 магазинов. Потребность каждого 2, грузоподъёмность 3.

                  понимаю, что имеешь ввиду этим примером
                  тут просто лексически я подразумевал разность слов "приехал" и "проехал(мимо/через)", т е грузовик приехал в городN и отгрузил товар (стоянка какая-то), а если он едет в др.город транзитом через N, то грузовик ПРОЕХАЛ не останавливаясь, как бы)
                  тут все понятно и спорных моментов нет никаких!

                  в общем быстро прочитал/вспомнил задачи о рюкзаке и коммивояжера. Как-то все слишком сложно получается применительно к моей задаче, т к грузовику нужно возвращаться на дозаправку товаром (например, в коммивояжера лишь 1 рейс делается через все города)

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

                  еще: наверняка потребуется применить алгоритм Флойда-Уоршелла для построения матриц кратчайших расстояний между вершинами графа

                  не уверен, еще какой-нибудь мин.остов нужен и пр. пр.
                  и при этом нужны всякие NP-переборы.

                  СЛИШКОМ СЛОЖНО ВСЕ! Слишком большая концентрация графовых алгоритмов в одной задаче (прим.ТС, знать бы еще их хорошо) Надо упрощать, причем значительно!

                  ВОПРОС: как можно значительно упростить данную задачу, введя какие-то допущения, ограничения, но не нарушая базовых требований задачи??

                  т е на данный момент задача имеет сложность 8 из 10, надо ее превратить в сложность 3/4 из 10, т е не максимально упростить до сложности 1 из 10, а до 3/4 из 10.
                  сделать граф полностью связным? да никак это вроде не поможет.
                  вот за счет чего можно упростить?
                    Хотите упростить? Тогда сделайте размер заказа фиксированным 1 или 3 тонны.
                      Гм. А какие тут базовые требования? Что именно нельзя нарушать?

                      Я уже упоминал вариант радикального упрощения задачи: вместо неупорядоченного набора заказов использовать очередь, и грузить заказы в машину строго в порядке их поступления. Тогда действительно сложной проблемой будет только выбор, грузить очередной заказ "прям щас" или оптимальнее будет отложить его для следующей доставки.
                        Цитата AVA12 @
                        Гм. А какие тут базовые требования? Что именно нельзя нарушать?

                        ну, например, грузоподъемность грузовичка (хотя на грузовик не тянет) ) в 6тонн и т.п.

                        Цитата AVA12 @
                        Я уже упоминал вариант радикального упрощения задачи: вместо неупорядоченного набора заказов использовать очередь, и грузить заказы в машину строго в порядке их поступления. Тогда действительно сложной проблемой будет только выбор, грузить очередной заказ "прям щас" или оптимальнее будет отложить его для следующей доставки.

                        ясно, ну, тогда на этом и остановимся, может что-то и получится.

                        всем спс. за участие!

                        г
                        Скрытый текст
                        рафы - опаснейшие химеры, обладающие какой-то бесконечной лютой сложностью на определенном этапе)) а ведь существует миллион графовых задач в разы сложнее, как их решают, хз)...
                        и вообще, мне кажется (возможно, что именно КАЖЕТСЯ), что графы - апофеоз сложности в Computer Science...те же деревья - частный случай графа вроде
                          Цитата AVA12 @
                          Ну, вроде, ясно. Получается самый сложный случай, задача коммивояжера плюс задача о рюкзаке. Разве что принцип "один магазин - одна доставка" слегка утешает. Надо думать.

                          Типичная транспортная задача, решается методом симплекса
                          Сообщение отредактировано: Gonarh -
                            Я почитал про транспортную задачу в Википедии - там нет ничего про транспортную сеть. Есть только стоимости доставки из пункта производства a[i] в пункт потребления b[j]. Но у нас другой случай: если имеется плотный кластер магазинов, к которому от хаба ведет длинная дорога, то минимальная стоимость доставки товаров ко всем магазинам кластера будет меньше, чем сумма стоимостей доставки к каждому из них. Свести имеющуюся задачу к транспортной (назначить некоторые магазины временными "пунктами производства") так просто не получается.
                              Я бы предложил следующий алгоритм:
                              1. Составить все варианты сочетания магазинов (маршрутов), для 8ми магазинов из #5 получится 2^8-1 = 255 маршрутов
                              2. Решить задачу коммивояжера для каждого маршрута (наименьший путь)
                              3. Исходя из требуемых заказов составить все варианты упаковки груза не превышающий грузоподъемность машины
                              4. Составить линейную модель где требуется минимизировать пробег, выполнив все заказы используя варианты упаковки из п.3 с учетом весов полученных в п.2. для каждого маршрута и решить ее целочисленным линейным программированием
                                Ну тут сразу надо отказаться от попыток найти оптимальное решение точным алгоритмом.
                                Что-то эвристическое на здравом смысле.
                                А насколько непредсказуемо магазины делают заказы? Заказывают каждый день? раз в неделю? раз в месяц?

                                Если заказывают более-менее равномерно по времени.
                                Это всё на плоскости происходит, можно сказать, на карте.
                                Разделить карту на квадранты, сгруппировать магазины по квадрантам.
                                Средняя суммарная потребность одной группы не должна превосходить 6 тонн.
                                В идеальной ситуации грузовик объезжает группу - возвращается, загружается и едет в следующую группу.
                                Если что-то пошло не так.
                                В каких-то группах сегодня недогруз, в каких-то - перегруз.
                                Берём список групп-"ближайших соседей" группы с недогрузом, ищем группу с максимальным "перегрузом" и в заключении маршрута из одной группы с недогрузом переезжаем в группу с перегрузом.
                                Если во всех группах одновременно недогруз или перегруз, значит группы неправильно сформированы.

                                Как внутри группы объезжать магазины - водила сам догадается.
                                Остаётся только задача набора заданного веса из заданных слагаемых.
                                Если слагаемых меньше 20, то алгоритмом с возвратом. Больше - динамикой. Сверхбольшой размерности тут, видимо, нет.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0664 ]   [ 18 queries used ]   [ Generated: 19.03.24, 07:03 GMT ]