Follow us on
Eco-friendly Vehicle Routing via Balanced and Compact Clustering
Submitted by gkortsilas on Tue, 2014-11-04 17:45
Publication Date:
September, 2014
Abstract:
We investigate the Vehicle Routing Problem with Time Windows (VRPTW)
under an eco-friendly framework that demands the delivery of balanced and compact
customer clusters. We present a new approach consisting of three major phases:
(i) a first clustering of customers with compatible time windows;
(ii) a second clustering of customers with close geographic
proximity based on various methods (natural cuts, KaHIP, quad trees);
(iii) a refinement phase that either splits a cluster into smaller
ones, or merges clusters to form a bigger compact cluster.
Our approach turns out to be beneficial when used in an on-line
environment, where changes to the initial tour are requested (add a
new customer to the tour or drop some customers). The new method
serves as a warm starting point for re-evaluating and further
optimizing the solution of VRPTW. Experiments with real data sets
demonstrate that our approach compares favorably with
standard approaches that start from a basic (cold) solution.
File:
Work Packages:
