Single vehicle routing problems with a predefined customer sequence, compartmentalized load and stochastic demands

D.G. Pandelis, E.G. Kyriakidis and T.D. Dimitrakos

European Journal of Operational Research, 2012, vol. 217, issue 2, 324-332

Abstract: We consider the problem of finding the optimal routing of a single vehicle that delivers K different products to N customers according to a particular customer order. The demands of the customers for each product are assumed to be random variables with known distributions. Each product type is stored in its dedicated compartment in the vehicle. Using a suitable dynamic programming algorithm we find the policy that satisfies the demands of the customers with the minimum total expected cost. We also prove that this policy has a specific threshold-type structure. Furthermore, we investigate a corresponding infinite-time horizon problem in which the service of the customers does not stop when the last customer has been serviced but it continues indefinitely with the same customer order. It is assumed that the demands of the customers at different tours have the same distributions. It is shown that the discounted-cost optimal policy and the average-cost optimal policy have the same threshold-type structure as the optimal policy in the original problem. The theoretical results are illustrated by numerical examples.

Keywords: Logistics; Dynamic programming; Stochastic demands; Multiple-product delivery (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221711008551
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:217:y:2012:i:2:p:324-332

DOI: 10.1016/j.ejor.2011.09.027

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().