За последние 20 лет большое число и разнообразие задач по составлению маршрутов и графиков транспортных средств были успешно проанализированы с помощью моделей оптимизации.' Маршрутизация представляет собой физический путь и последовательность пунктов, проходимых транспортным средством. Составление расписания предполагает определение времени погрузок и разгрузок транспорта в распределительных центрах, заводах пли портах, а также расписание доставок в пункты потребителей.

Транспортное средство может быть грузовиком, поездом, баржей, кораблем или самолетом. Горизонты планирования варьируется от 1 дня для местной развозки грузовиками до нескольких недель — для нефтеналивных танкеров и судов-контейнеровозов. Оперативное планирование только лишь грузовиков включает в себя огромное разнообразие задач, связанных с маршрутами и графиками. Назовем следующие примеры:
• местная развозка розничной продукции по магазинам из распределительных центров, причем некоторые магазины сами устанавливают временные окна доставки;
• местная развозка и установка газовых баллонов местным жителям;
• авторазвозка танков с жидким азотом и кислородом на фабриках производства газовых продуктов с целью доставки на малые и средние расстояния промышленным потребителям;
• доставка грузовиками па дальнее расстояние с распределением груза и местной развозкой в обоих концах поездки.
Задачи, подобные перечисленным, могут быть смоделированы и оптимизированы с помощью сочетания смешанного целочисленного программирования и эвристических методов.
Задачи местной доставки. Задачи местной доставки касаются развозки почты и посылок почтовой службой или фирмами по курьерской доставке, бакалеи и других потребительских продуктов из распределительных центров к соответствующим магазинам, потребителям и т. д. Эти задачи могут быть смоделированы как задачи выбора маршрутов для отдельного автомобиля, который вышел из гаража, посетил множество потребителей (стоянок), а затем вернулся в гараж. При выборе маршрута нельзя нарушать вместимость транспортного средства. Часто налагается максимальная продолжительность маршрута. Обычно временное окно доставки конкретизировано для каждого потребителя, которого можно посетить только один раз. Реальный маршрут — это маршрут, который отвечает различным ограничениям по вместимости и времени.