A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups. (September 2017)

• Record Type: Journal Article
• Authors: Polat, Olcay
• Is Part Of: Computers & operations research. Volume 85(2017)
• Page Start: 71
• Page End: 86
• Publication Date: 2017-09
• Subjects: Vehicle routing problem -- Divisible deliveries and pickups -- Parallel computing -- Variable neighborhood search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.03.009
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: The vehicle routing problem with divisible delivery and pickup is considered. A parallel approach based on variable neighborhood search is proposed. A number of well-known benchmark problems are solved and compared. Proposed parallel approach outperforms the existing methods. New best solutions for 179 of 220 benchmark instances are found. Abstract: A well-known variant of the vehicle routing problem involves backhauls, where vehicles deliver goods from a depot to linehaul customers and pick up goods from backhaul customers to the depot. The vehicle routing problem with divisible deliveries and pickups (VRPDDP) allows vehicles to visit each client once or twice for deliveries or pickups. In this study, a very efficient parallel approach based on variable neighborhood search (VNS) is proposed to solve VRPDDP. In this approach, asynchronous cooperation with a centralized information exchange strategy is used for parallelization of the VNS approach, called cooperative VNS (CVNS). All available problem sets of VRPDDP have been successfully solved with the CVNS, and the best solutions available in the literature have been significantly improved.