A Fast Randomized Algorithm for the Heterogeneous Vehicle Routing Problem with Simultaneous Pickup and Delivery
| Autor: | Ricardo Barboza Saboia, Plácido Rogério Pinheiro, Napoleão Nepomuceno |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Mathematical optimization
lcsh:T55.4-60.8 Computer science 0211 other engineering and technologies 02 engineering and technology lcsh:QA75.5-76.95 Theoretical Computer Science k-nearest neighbors algorithm greedy algorithms Vehicle routing problem 0202 electrical engineering electronic engineering information engineering Single vehicle lcsh:Industrial engineering. Management engineering Pickup Greedy algorithm Numerical Analysis 021103 operations research randomized algorithms Extension (predicate logic) Randomized algorithm Computational Mathematics Computational Theory and Mathematics Benchmark (computing) vehicle routing problem 020201 artificial intelligence & image processing lcsh:Electronic computers. Computer science |
| Zdroj: | Algorithms, Vol 12, Iss 8, p 158 (2019) Algorithms Volume 12 Issue 8 |
| ISSN: | 1999-4893 |
| Popis: | In the vehicle routing problem with simultaneous pickup and delivery (VRPSPD), customers demanding both delivery and pickup operations have to be visited once by a single vehicle. In this work, we propose a fast randomized algorithm using a nearest neighbor strategy to tackle an extension of the VRPSPD in which the fleet of vehicles is heterogeneous. This variant is an NP-hard problem, which in practice makes it impossible to be solved to proven optimality for large instances. To evaluate the proposal, we use benchmark instances from the literature and compare our results to those obtained by a state-of-the-art algorithm. Our approach presents very competitive results, not only improving several of the known solutions, but also running in a shorter time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
| Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |