Back to first pageBack to first page Centre for Artificial Intelligence of UNL
Browse our site
You are here:

Publication details

Go back
Publication details
Main information
A Clustering Approach for Vehicle Routing Problems with Hard Time Windows
July 2014
Puga14
Vehicle Routing Problem with hard Time Windows (VRPTW) is probably the most studied variant of the VRP problem and the presence of time windows requires complex techniques to handle it. In fact, … the VRPTW problem is NP-Hard. Therefore, … the literature is full with inexact methods that use metaheuristics, local search and hybrid approaches which are capable of producing high quality solutions within practical time limits. In this work we are interested in applying clustering techniques to VRPTW problem and present a novel approach, that any VRPTW solver can adapt, by running a preprocessing stage before attempting to solve the problem. Our proposed method, tested with a state of the art solver (Indigo), enables the solver to find solutions much faster (up to an order of magnitude speed-up). In general this comes with at slightly reduced solution quality, but in somes types of problems, Indigo is able to obtain better solutions than those obtained with no clustering.
M. Sc. dissertation
Sergejs Pugacs
Pedro Barahona
Universidade Nova de Lisboa
-
-
Publication files
- click here to download - pdf 581 KB
Export formats
Sergejs Pugacs, A Clustering Approach for Vehicle Routing Problems with Hard Time Windows, Pedro Barahona (superv.), Universidade Nova de Lisboa, July 2014.
<b>Sergejs Pugacs</b>, <u>A Clustering Approach for Vehicle Routing Problems with Hard Time Windows</u>, <a href="/people/members/view.php?code=7e27bc13fad97e99cd21ea6914d55659" class="supervisor">Pedro Barahona</a> (superv.), Universidade Nova de Lisboa, July 2014.
@mastersthesis {Puga14, author = {Sergejs Pugacs}, title = {A Clustering Approach for Vehicle Routing Problems with Hard Time Windows}, school = {Universidade Nova de Lisboa}, note = {Pedro Barahona (superv.); }, abstract = {Vehicle Routing Problem with hard Time Windows (VRPTW) is probably the most studied variant of the VRP problem and the presence of time windows requires complex techniques to handle it. In fact, … the VRPTW problem is NP-Hard. Therefore, … the literature is full with inexact methods that use metaheuristics, local search and hybrid approaches which are capable of producing high quality solutions within practical time limits. In this work we are interested in applying clustering techniques to VRPTW problem and present a novel approach, that any VRPTW solver can adapt, by running a preprocessing stage before attempting to solve the problem. Our proposed method, tested with a state of the art solver (Indigo), enables the solver to find solutions much faster (up to an order of magnitude speed-up). In general this comes with at slightly reduced solution quality, but in somes types of problems, Indigo is able to obtain better solutions than those obtained with no clustering.}, month = {July}, year = {2014}, }
Publication's urls
/publications/view.php?code=97eb353ce5fae9f0bf72222066e03597
/publications/view.php?code=Puga14
Go back
Centre for Artificial Intelligence of UNL
Departamento de Informática, FCT/UNL
Quinta da Torre 2829-516 CAPARICA - Portugal
Tel. (+351) 21 294 8536 FAX (+351) 21 294 8541

Fundacao_FCT