An integrated CPU--GPU heuristic inspired on variable neighbourhood search for the single vehicle routing problem with deliveries and selective pickups

I.M. Coelho, P.L.A. Munhoz, L.S. Ochi, M.J.F. Souza, C. Bentes and R. Farias

International Journal of Production Research, 2016, vol. 54, issue 4, 945-962

Abstract: Environmental issues have become increasingly important to industry and business in recent days. This trend forces the companies to take responsibility for product recovery, and proper recycling and disposal, moving towards the design of sustainable green supply chains. This paper addresses the backward stream in transportation of products, by means of reverse logistics applied to vehicle routing. This problem, called single vehicle routing problem with deliveries and selective pickups, consists in finding a route that starts from the depot and visits all delivery customers. Some pickup customers may also be visited, since the capacity of the truck is not exceeded, and there is also a revenue associated with each pickup. We develop an algorithm inspired on the variable neighbourhood search metaheuristic that explores the power of modern graphics processing unit (GPU) to provide routes in reasonable computational time. The proposed algorithm called four-neighbourhood variable neighbourhood search (FN-VNS) includes a novel high-quality initial solution generator, a CPU--GPU integrated perturbation strategy and four different neighbourhood searches implemented purely in GPU for the local search phase. Our experimental results show that FN-VNS is able to improve the quality of the solution for 51 instances out of 68 instances taken from the literature. Finally, we obtained speedups up to 14.49 times, varying from 17.42 up to 76.84 for each local search, measured over a set of new large-size instances.

Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2015.1035811 (text/html)
Access to full text is restricted to subscribers.

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:taf:tprsxx:v:54:y:2016:i:4:p:945-962

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2015.1035811

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().