Здравствуйте. Поставили следующую задачу: Есть два динамических списка, первый это список курьеров, второй список заказов за последние сутки. Необходимо эффективно распределить заказы по курьерам. А именно: каждый курьер имеет время работы (со скольки - до скольки), грузоподъемность его автомобиля, и максимальный объем груза за одну перевозку. Заказы имеют соответствующие поля. Так собственно вопрос, как эффективно распределить? Проблема в том, если есть, например, несколько мелких заказов, подходящих по времени, то распределить их соответственно курьеру с небольшим объемом и грузоподъемностью автомобиля, а крупные заказы по другим курьерам. Но может случится так, что последний из распределяемых курьеров не может взять крупный заказ, т.к. не работает в это время, но работает в то время, когда нужно доставить, к примеру, 2 мелких, которые уже распределены. Тогда нужно каким-то образом перераспределить мелкие заказы на последнего, а крупный запилить к "мелкому" курьеру. Собственно, помогите советом :)
-
Все еще актуально...– Eugene ShilinCommented 5 апр. 2014 в 11:34
-
1@Евгений Шилин, пока критерий эффективности (да, похоже и еще некоторые ограничения) у Вас определен чисто интуитивно. Вообще же задача непростая. Что-то из серии динамического программирования.– avpCommented 5 апр. 2014 в 16:44
-
Похоже на линейное программирование, попробуйте покопать в сторону симплекс-метода.– VladDCommented 5 апр. 2014 в 19:12
-
avp, Ну как я понимаю эффективность здесь носит достаточно абстрактный характер, т.к на практике использовать эту систему распределения по-моему не получится. VladD, спасибо.– Eugene ShilinCommented 6 апр. 2014 в 13:25
-
@VladD, а разве симплекс-метод годится для дискретной оптимизации?– avpCommented 6 апр. 2014 в 14:09
1 ответ
Можно выбрать несколько подходов. Первый. Это задача о рюкзаке. Её придётся чуть-чуть модифицировать. Об обычной задаче о рюкзаке можно прочитать тут:
Я бы советовал взглянуть на Информатикс. Мало того, что Вы можете прочитать годную теорию там с примерами. Помимо этого вы можете попробовать написать задачу и сдать её в тестирующую систему. На этом же сайте можно найти в примерах задач разборы решений, опубликованные кем-либо. Здесь можно найти как что-нибудь дельное, так и не очень. Но сюда тоже стоит заглянуть. . Разбор открывается при нажатии на синюю надпись "разбор", расположенную под названием задачи.
Codeforces.ru и timus.ru -- здесь можно найти задачи на различную тематику ДП. В том числе и рюкзак.
Что касается метода Гомори. То в интернете полно онлайн-решателей, с помощью которых можно разобраться с ходом действий. Более подробно можно прогуглить в интернете книгу Пантелеева И Летовой. Есть два издания. В одном написано чуть подробнее, в другом -- чуть менее. Здесь и Здесь. Метод Гомори позволяет решить Вашу задачу в целых числах. Это тот же самый симлекс-метод, который перебирает вершины многомерного многоугольника. После этого в окрестностях полученных точек ищет наилучшее целочисленное решение путём решения неравенств в целых числах. Это несложно. Почитайте.
Метод Гомори довольно универсальная штука. Но кодить её будет проблемно. Я бы советовал разобраться с задачей о рюкзаке, так как решение выйдет компактнее. Но здесь не будет универсального решения. Придётся изобретать небольшой велосипед.
Что касается критерия эффективности, то в качестве критерия можно минимизировать время, затрачивающееся на перевозку, либо объём груза. Либо и то, и другое. Но я бы не советовал брать и то, и другое. По крайней мере по-началу. В таком случае у Вас возникнет несколько целевых функций. А с этим работать сложнее. Кроме того, можно объединить это в нелинейный функционал. Например, минимизировать скалярное произведение векторов
(X, T) = x1 * t1 + x2 * t2 + ... + xn * tn, где X -- объём перевезённого груза, T -- время. Но в таком случае задача точного решения не будет иметь. По крайней мере, при решении методом Гомори. В такой постановке она нелинейна.
В любом случае здесь всё зависит от ваших требований. Для чего решает Ваша задача? Кому она нужна?
Как только разберётесь с этими методами. Выберете то, чего Вы хотите, а самое главное, зачем Вы это хотите, пишите сюда. Попробуем разобраться, если у Вас будут вопросы.