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

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

0.00 Avg rating0 Votes
Article ID: iaor201111029
Volume: 217
Issue: 2
Start Page Number: 324
End Page Number: 332
Publication Date: Mar 2012
Journal: European Journal of Operational Research
Authors: , ,
Keywords: combinatorial optimization, programming: dynamic
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.

Reviews

Required fields are marked *. Your email address will not be published.