Об одном нестационарном варианте обобщенной задачи курьера с внутренними работами

Аннотация

Рассматривается задача последовательного обхода мегаполисов с условиями предшествования и выполнением работ в пределах данных мегаполисов. Предполагается, что стоимости перемещений зависят от параметра, который имеет смысл дискретного времени; упомянутая зависимость может отражать приоритеты клиентов, связанных с обслуживаемыми мегаполисами и частично компенсирующих затраты исполнителей. Построенный метод решения объективно отвечает широко понимаемому динамическому программированию, применяемому для решения задачи маршрутизации с ограничениями. Предложено расширение исходной задачи, использующее эквивалентное преобразование системы ограничений, в результате чего допустимость (маршрутов) по предшествованию заменяется допустимостью "по вычеркиванию", (заданий из списка). Тем самым ограничения на маршрут в целом сводятся к системе ограничений на текущие перемещения, что позволяет получить уравнение Беллмана. Для использования последнего в вычислительной процедуре построения слоев функции Беллмана используется подход, в рамках которого предусматривается построение всего массива значений упомянутой функции; данный подход базируется на использовании только существенных (по предшествованию) списков заданий, чем достигается экономия вычислений.