A variable neighborhood search heuristic for periodic routing problems

The aim of this paper is to propose a new heuristic for the Periodic Vehicle Routing Problem (PVRP) without time windows. The PVRP extends the classical Vehicle Routing Problem (VRP) to a planning horizon of several days. Each customer requires a certain number of visits within this time horizon whi...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2009-06, Vol.195 (3), p.791-802
Main Authors: Hemmelmayr, Vera C., Doerner, Karl F., Hartl, Richard F.
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
Heuristic
Logistics
Metaheuristics
Operational research and scientific management
Operational research. Management science
Periodic traveling salesman problem
Periodic vehicle routing problem
Periodic vehicle routing problem Periodic traveling salesman problem Metaheuristics Variable neighborhood search
Routing
Studies
Traveling salesman problem
Variable neighborhood search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The aim of this paper is to propose a new heuristic for the Periodic Vehicle Routing Problem (PVRP) without time windows. The PVRP extends the classical Vehicle Routing Problem (VRP) to a planning horizon of several days. Each customer requires a certain number of visits within this time horizon while there is some flexibility on the exact days of the visits. Hence, one has to choose the visit days for each customer and to solve a VRP for each day. Our method is based on Variable Neighborhood Search (VNS). Computational results are presented, that show that our approach is competitive and even outperforms existing solution procedures proposed in the literature. Also considered is the special case of a single vehicle, i.e. the Periodic Traveling Salesman Problem (PTSP). It is shown that slight changes of the proposed VNS procedure is also competitive for the PTSP.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2007.08.048