Описание

pCouriers - незавершенный проект по оптимальному распределению заказов между несколькими курьерами.

Есть множество фирм и интернет-магазинов, продающих небольшие товары с доставкой их заказчикам. Однако, когда число курьеров больше двух, становится трудно правильно распределить заказы между курьерами так, чтобы каждый из них потратил возможно меньшее время на доставку, и чтобы при этом все клиенты остались довольны. В настоящее время мной написана программа, в некоторой степени реализующая данную идею.

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

В настоящее время в программе реализовано следующее:

• Ввод и вывод данных - через текстовые файлы.
• Количество курьеров и заказов неограничено.
• Курьеры указывают не только время своей работы (а оно может быть разным), но и место жительства. Программа попытается учесть это обстоятельство, чтобы курьер закончил работу поближе к дому.
• Для расчета программа пользуется генетическим алгоритмом. На практике это означает, что, запустив программу несколько раз, Вы получите разные результаты. Но можно быть уверенным, что по оптимальности они будут более или менее одинаковыми (в тестовом примере, см. ниже, разброс времени составлял около 10 минут).

• Всего курьеров в этом примере - пять.
• У четырех курьеров задано время работы с 8-30 до 23-59, у последнего - 10-30 - 12-30
• Один из заказчиков указал время получения 18-00, невыгодное ни одному из курьеров. В решении это обстоятельство учтено, и курьер "Сидоров" отрабатывает из-за этого несколько меньшее время.
• Время данного расчета на P4-2500 - порядка 1 минуты.

• При запуске программа считывает все задания из файла Zakazy.ini, распределяет их в первый момент по курьерам так: 1-я линия метро - первому курьеру, и т.д. по кругу (см. первый рисунок). Также при запуске программа автоматически начинает расчет.
  
• Первая кнопка (Загрузить) очищает заказы, потом заново считывает задания из того же файла.
  
• Вторая кнопка (Рассчитать) запускает или останавливает процесс поиска оптимального распределения заказов.
  
• Кнопка "сохранить" сохраняет результирующий вариант в текстовый файл, указанный в настройках (по-умолчанию Result.txt), в следующем виде:
  
  --------------
  Курьер: Иванов
  --
  Заказчик: Заказчик10
  Станция: Беляево
  Расчетное время прибытия: 9:30
  Товар: Товар10
  --
  Заказчик: Заказчик32
  ...
  
• Каждый столбец - это курьер. Формальное время работы данного курьера обозначено голубым прямоугольником.
  
• Каждый прямоугольник - это заказ вместе со временем, которое он затратит на дорогу с момента предыдущего заказа.
  
• Время от одного заказа до другого (это же время является высотой прямоугольников) рассчитывается следующим образом: Берется время на метро от предыдущей станции до следующей, прибавляется время от метро до заказчика, прибавляется время у заказчика, прибавляется время от заказчика до метро.
  
• Если вес всех заказов (физический вес, в граммах) превышает лимит курьера, то курьеру придется вернуться за частью заказов в офис. Нормой по-умолчанию считается 7кг, ее можно изменить в настройках каждого курьера.
  
• Если курьер опаздывает с заказом, или ему поручается отвезти после окончания его рабочего дня, то такой заказ считается просроченным и помечается красным крестом по белому прямоугольнику. Программа стремится, чтобы таких прямоугольников было как можно меньше.
  
• Если курьер приедет раньше положенного (например, в заказе указано после 18-00, а курьер закончил все предыдущие дела в 16-00), то считается, что курьер в метро не спускается, пока не придет время ехать к этому заказчику. На диаграмме в этом месте просто пусто.
  
• Если у курьера два заказа на одной и той же станции, то считается, что курьер экономит около 4 минут за счет входа и выхода из метро.
  
• Курьер может указать, где его дом, т.е. куда он поедет, когда все закончит. В этом случае программа попробует подобрать пути с учетом этого.
  
• Критерий оптимальности в данной версии - минимизировать максимальное из "средневзвешенных времен" курьеров. "Средневзвешенное время" курьера рассчитывается так:
  
  время от офиса до ближайшего метро
  + (плюс) чистое время на заказы (высота всех прямоугольников), включая время по превышению веса.
  - минус 4 минуты на каждой паре заказов, если они на одной станции
  + время простоя, деленное на 3 (цифра эмпирическая)
  + время до желательной конечной станции деленное на 2 (цифра эмпирическая)
  + "штраф" за каждую просрочку товара 1 час (цифра эмпирическая)
  + "штраф" за внеурочную работу 8 часов (цифра эмпирическая)
  
  "Штрафы" нужны для того, чтобы программа могла сделать расчет даже тогда, когда бесштрафного решения просто не существует.
  
• В процессе расчета программа как бы запускается одновременно 5 раз (можно изменить в настройках, параметр "Количество вариантов"), отображая в каждый момент лучший из результатов. При каждом шаге из каждого варианта делается 100 вариаций (можно изменить в настройках, параметр "Количество подвариантов"), из них выбираются лучшие. Процесс расчета останавливается, когда после 100 итераций не было ни одного улучшения ни в одном из вариантов.
  

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