Finite and infinite-horizon single vehicle routing problems with a predefined customer sequence and pickup and delivery

D.G. Pandelis, C.C. Karamatsoukis and E.G. Kyriakidis

European Journal of Operational Research, 2013, vol. 231, issue 3, 577-586

Abstract: We consider the problem of finding the optimal routing of a single vehicle that starts its route from a depot and picks up from and delivers K different products to N customers that are served according to a predefined customer sequence. The vehicle is allowed during its route to return to the depot to unload returned products and restock with new products. The items of all products are of the same size. For each customer the demands for the products that are delivered by the vehicle and the quantity of the products that is returned to the vehicle are discrete random variables with known joint distribution. Under a suitable cost structure, it is shown that the optimal policy that serves all customers has a specific threshold-type structure. We also study a corresponding infinite-time horizon problem in which the service of the customers is not completed when the last customer has been serviced but it continues indefinitely with the same customer order. For each customer, the joint distribution of the quantities that are delivered and the quantity that is picked up is the same at each cycle. The discounted-cost optimal policy and the average-cost optimal policy have the same structure as the optimal policy in the finite-horizon problem. Numerical results are given that illustrate the structural results.

Keywords: Logistics; Dynamic programming; Routing with pick up and delivery (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221713004694
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:231:y:2013:i:3:p:577-586

DOI: 10.1016/j.ejor.2013.05.050

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 ().