Методы построения оптимальных маршрутов доставки грузов, Рамиз Гиндуллин und Ефим Бронштейн

В работе рассматривается разновидность задачи маршрутизации транспортных средств при перевозке грузов – VRP (Vehicle Routing Problem) – SVRPPD – задача транспортной маршрутизации с вывозом и доставкой одним транспортным средством. Особенностями рассматриваемой задачи являются наличие множественных пунктов-производителей, из которых производится вывоз груза. Поставленная задача может быть сформулирована как целочисленная линейная оптимизационная задача, и является обобщением двух известных задач: задачи коммивояжера и задачи о загрузке рюкзака. Рассмотрены три разных варианта задачи: все пункты посещаются только один раз, пункты могут быть посещены более одного раза и пункты могут быть посещены более одного раза с возможностью оставить и забирать грузы. В результате, исследованы свойства поставленных задач, построены точные и эвристические методы решения, а также проведены численные эксперименты с целью исследования эффективности разработанных методов.