Stochastic single vehicle routing problem with ordered customers and partial fulfilment of demands

ABSTRACT

We consider the problem of finding the optimal routing of a single vehicle that starts its route from a depot and delivers a product to N customers that are served according to a particular order. The vehicle during its route can return to the depot for replenishment. It is assumed a stochastic demand for each customer. The actual demand of each customer becomes known upon the vehicle's arrival at the customer's site. It is permissible to satisfy fully or to satisfy partially or not to satisfy the demand of a customer. The cost structure includes travel costs between consecutive customers, travel costs between the customers and the depot and penalty costs if a customer's demand is not satisfied or if it is satisfied partially. A dynamic programming algorithm is developed for the determination of the optimal routing policy. It is shown that the optimal routing policy has a specific threshold-type structure. Furthermore, if we consider the same problem without the assumption that the customers are ordered, numerical experiments indicate that the optimal routing strategy can be computed for N smaller or equal to nine.

KEYWORDS:

• Routing problem
• dynamic programming
• partial service
• stochastic demands

Acknowledgments

The authors would like to thank two anonymous referees for useful suggestions that improved the presentation of the paper. The author Epaminondas G. Kyriakidis has been financed by the research program EP-2718-01 (RC/AUEB).

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

Epaminondas G. Kyriakidis: research program EP-2718-01 (RC/AUEB).

Notes on contributors

Epaminondas G. Kyriakidis

Epaminondas G. Kyriakidisis Professor in Applied Probability and in Stochastic Operational Research in Department of Statistics in Athens University of Economics and Business. His research interests are, among others, Markov decision processes, Control of Queues and Logistics. His work had been published, among others journals, in Journal of Applied Probability, in Statistics and Probability Letters and in Probabilty in the Engineering and Informational Science.

Theodosis D. Dimitrakos

Theodosis D. Dimitrakosis Assistant Professor in Probability-Statistics in Department of Mathematics in University of the Aegean. His research interests are, among others, Stochastic Dynamic Programming, Optimal control of Biological Population Models and Machine Replacement Models. His work had been published, among others journals, in European Journal of Operational Research, in Methodolgy and Computing in Applied Probability and in International Journal of Production Economics.