Single vehicle routing with a predefined customer sequence and multiple depot returns

The optimal routing of a single vehicle with limited capacity that delivers one product to n clients according to a predefined client sequence can be determined using dynamic programming. In the present paper we propose and investigate three practical variations of this problem: (i) the case of multiple-product deliveries when each product is stored in its own compartment in the vehicle, (ii) the case of multiple-product deliveries when all products are stored together in the vehicle’s single compartment, and (iii) the case in which the vehicle picks up from and delivers a single product to each customer. Suitable dynamic programming algorithms that find the optimal routing of the vehicle are developed for each case. The efficiency of the algorithms is studied by solving large problem sets.