Cooperative versus non-cooperative parallel variable neighborhood search strategies: a case study on the capacitated veh
- PDF / 1,618,539 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 104 Downloads / 192 Views
Cooperative versus non-cooperative parallel variable neighborhood search strategies: a case study on the capacitated vehicle routing problem Panagiotis Kalatzantonakis1
· Angelo Sifaleras1
· Nikolaos Samaras1
Received: 29 March 2019 / Accepted: 3 December 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract The capacitated vehicle routing problem (CVRP) is a well-known NP-hard combinatorial optimization problem with numerous real-world applications in logistics. In this work, we present a literature review with recent successful parallel implementations of variable neighborhood search regarding different variants of vehicle routing problems. We conduct an experimental study for the CVRP using well-known benchmark instances, and we present and investigate three parallelization strategies that coordinate the communication of the multiple processors. We experimentally evaluate a non-cooperative and two novel cooperation models, the managed cooperative and the parameterized cooperative strategies. Our results constitute a first proof-of-concept for the benefits of this new self-adaptive parameterized cooperative approach, especially in computationally hard instances. Keywords Variable neighborhood search · Parallel computing · Vehicle routing problem · Self-adaptive mechanism
1 Introduction Combinatorial or discrete optimization problems have significant importance to many industrial applications, with a vast number of uses and can be described as the effort to find an optimal solution from a finite number of alternative solutions. The vehicle routing problem (VRP) is one of the most well-studied combinatorial optimization problems, and it emerges when one seeks an optimal route for a fleet of vehicles to accommodate a set of clients, given a set of constraints.
B
Angelo Sifaleras [email protected] Panagiotis Kalatzantonakis [email protected] Nikolaos Samaras [email protected]
1
Department of Applied Informatics, School of Information Sciences, University of Macedonia, 156 Egnatias Str., 54636 Thessaloníki, Greece
123
Journal of Global Optimization
The CVRP, which was initially introduced by Dantzig and Ramser in 1959 [14] is a variation of VRP, in which a fleet of homogenous delivery vehicles of limited carrying capacity must service known client demands from a depot, at a minimum transit cost. The CVRP is an NP-hard problem with significant impact on the fields of transportation, distribution, and logistics since transportation is usually a significant component of the cost of a product. One of the major concerns of the industry has always been the minimization of the product cost, essential both for the achievement of a more substantial profit as for the maintenance of a vantage over the competition. In addition, a growing interest in reducing the environmental impact of their products and services is also cultivated among companies, thus creating a trend towards a greener management of the modern supply chain [32]. Finding an optimal solution for the CVRP is generally a compu
Data Loading...
