Naslov
A Two-Phase Vehicle based Decomposition Algorithm for Large-Scale Capacitated Vehicle Routing with Time Windows

Autori
Gulić, Matija ; Lučanin, Dražen ; Skorin-Kapov, Nina

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
Proceeding of Mipro 2012 / - , 2012, 1285-1289

Skup
Mipro 2012

Mjesto i datum
Opatija, Hrvatska, 21.05.2012. - 25.05.2012

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
vehicle routing problem ; time windows ; largescale ; greedy search ; decomposition ; scalability ; optimization

Sažetak
With significant advances in computing power during recent years, increasingly complex variants of the vehicle routing problem (VRP) with added constraints are coming into focus. VRP is a combination of the classical traveling salesman and bin packing problems, with many real world applications in various fields – from physical resource manipulation planning to virtual resource management in the ever more popular cloud computing domain. In this paper, we consider large-scale VRP problem instances with time window constraints. Due to their complexity, we propose a solution approach based on the divide and conquer paradigm, decomposing problem instances into smaller, mutually independent sub-problems which can be solved using traditional algorithms and integrated into a global solution of reasonably good quality. Numerical results indicate the efficiency and scalability of the proposed approach, making it highly applicable to large- scale realistic VRP problem instances.

Izvorni jezik
Engleski

POVEZANOST RADA