Some exact and heuristics algorithms for single vehicle routing problem with pickups and deliveries

Abstract

A problem for constructing the shortest cyclic route that ensures homogeneous cargo is delivered from producers to consumers by a transport vehicle of limited capacity is considered. Formalizations in the form of quadratic Boolean programming, linear integer and linear Boolean programming problems are given. Comparative analysis of the efficiency of four exact algorithms is performed. The problem of finding the min-imal admissible capacity of the transport vehicle is considered as an auxiliary problem. Dependence of the length of the optimal route on the capacity of the transport vehicle is studied experimentally.