The flexible periodic vehicle routing problemmodeling alternatives and solution techniques

  1. HUERTA MUÑOZ, DIANA LUCIA
Dirigida por:
  1. Elena Fernández Aréizaga Directora
  2. Claudia Archetti Director/a

Universidad de defensa: Universitat Politècnica de Catalunya (UPC)

Fecha de defensa: 16 de marzo de 2018

Tribunal:
  1. Demetrio Laganà Presidente/a
  2. María Albareda Sambola Secretario/a
  3. Federico Perea Rojas-Marcos Vocal

Tipo: Tesis

Teseo: 147819 DIALNET lock_openTDX editor

Resumen

In this thesis the Flexible Periodic Vehicle Routing Problem is introduced and studied. In this problem a carrier must establish a distribution plan to serve a given set of customers over a planning horizon using a fleet of homogeneous capacitated vehicles. The total demand of each customer is known for the time horizon and it can be satisfied by visiting the customer in several time periods. There is, however, a limit on the maximum quantity that can be delivered at each visit. The aim is to minimize the total routing cost. This problem can be seen as a generalization of the Periodic Vehicle Routing Problem which, instead, has fixed service schedules and fixed delivered quantities per visit. On the other hand, the Flexible Periodic Routing Problem shares some characteristics with the Inventory Routing Problem in which inventory levels are considered at each time period, the delivery of product is a decision of the problem and, typically, an inventory cost is involved in the objective function. The relation among these periodic routing problems is discussed and a worst-case analysis, which shows the advantages of the studied problem with respect to the problems with periodicity mentioned above, is presented. Furthermore, alternative mixed-integer programming formulations are described and computationally tested. Given the difficulty to optimally solve the studied problem for small size instances, a matheuristic is developed, which is able to solve large size instances efficiently. Extensive computational experiments illustrate the characteristics of the solutions of the problem and show that, also in practice, allowing flexible policies may produce substantial savings in the routing costs in comparison with both the Periodic Vehicle Routing Problem and the Inventory Routing Problem.