Back to search

University of the Aegean

The multi-period vehicle routing problem and its applications

Abstract

dc:description

In this dissertation we investigate the Multi-Period Vehicle Routing Problem with Time Windows (MPVRPTW), in which orders are related to a period window (a set of service periods). Routing costs are minimized over a planning horizon, respecting period window, time window, and capacity constraints. We present a general model and an exact approach to solve this problem based on the column generation method. We also propose two novel, efficient techniques to speed up the column generation method for obtaining lower bounds. The proposed techniques exploit the multi-period setting in order to identify similarities within the subproblems and avoid solving all subproblems at each iteration. We evaluated the performance of the proposed methods systematically for various parameters, such as customer geographical distribution and period window patterns. In most cases, the new methods improve significantly the efficiency of convergence to the optimal solution of the relaxed problem, especially in the computationally expensive test cases with wide period windows. Integer optimal solutions to the MPVRPTW are provided through a branch-and-price implementation. We propose two strategies that consider the multi-period characteristics of the problem, in addition to a simple pruning heuristic that speeds up the solution procedure and provides efficient results. For solving the MPVRPTW in long-term horizons, we propose a rolling horizon framework. Initially, we discuss three theoretical statements that provide insights on the effects of the planning and implementation horizons in the final solutions. Subsequently, in order to apply rolling horizon routing, we propose significant modifications to the model and the solution approach for the MPVRP; these modifications concern the ability to postpone serving customers for later periods. We investigate two rolling horizon settings (quasi-static and dynamic) and we establish the recommended values for the planning and implementation horizons, under a wide range of parameters, such as customer geographical distribution and time window width. Finally, we address a practical variation, which regards a hybrid service policy that includes (a) inflexible (pre-assigned to specific vehicles) and (b) flexible customer orders. For this case, we propose the necessary modifications to the MPVRP model and solution approach. Extensive experiments show that significant cost savings can be achieved by considering longer planning horizons in the planning process.

Degree

thesis:*
Grantor dc:publisher
University of the Aegean
Year dc:date
2011

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Αθανασόπουλος, Θεόδωρος
  • Athanasopoulos, Theodore

Subjects

dc:subject × 12

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/25190

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Αθανασόπουλος, Θεόδωρος; Athanasopoulos, Theodore. The multi-period vehicle routing problem and its applications. University of the Aegean, 2011. http://hdl.handle.net/10442/hedi/25190