 The vehicle‐routing problem with delivery and back‐haul optionsShoshana Anily Naval Research Logistics (NRL), 1996, vol. 43, issue 3, 415-434 Abstract: In this article we consider a version of the vehicle‐routing problem (VRP): A fleet of identical capacitated vehicles serves a system of one warehouse and N customers of two types dispersed in the plane. Customers may require deliveries from the warehouse, back hauls to the warehouse, or both. The objective is to design a set of routes of minimum total length to serve all customers, without violating the capacity restriction of the vehicles along the routes. The capacity restriction here, in contrast to the VRP without back hauls is complicated because amount of capacity used depends on the order the customers are visited along the routes. The problem is NP‐hard. We develop a lower bound on the optimal total cost and a heuristic solution for the problem. The routes generated by the heuristic are such that the back‐haul customers are served only after terminating service to the delivery customers. However, the heuristic is shown to converge to the optimal solution, under mild probabilistic conditions, as fast as N−0.5. The complexity of the heuristic, as well as the computation of the lower bound, is O(N3) if all customers have unit demand size and O(N3 log N) otherwise, independently of the demand sizes. © 1996 John Wiley & Sons, Inc. Date: 1996 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:43:y:1996:i:3:p:415-434 Access Statistics for this article More articles in Naval Research Logistics (NRL) from John Wiley & Sons |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.