Computing Publications

Publications Home » Single vehicle routing with a pre...

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

Polyvios Tsirimpas, Antonios Tatarakis, Ioannis Minis, Epaminondas Kyriakidis

Journal Article
University of Aegean
European Journal of Operational Research
Volume 187
Issue 2
April, 2007
ISSN 0377-2217
DOI 10.1016/j.ejor.2007.03.017

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.

BibTEX file for the publication
Copyright notice

2007 Elsevier B.V. All rights reserved. built & maintained by Ashok Argent-Katwala.