Skip to main content

MODELOS Y ALGORITMOS PARA RUTAS INTELIGENTES

MTM2015-63680-R

•
Funding agency name Ministerio de Economía y Competitividad
Funding agency acronym MINECO
Program Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Call Proyectos I+D+i Retos de Investigación
Call year 2015
State Plan 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Management unit Dirección General de Investigación Científica y Técnica
Beneficiary centre UNIVERSIDAD DE LA LAGUNA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 1
Encontrada(s) 1 página(s)

Docta Complutense
Publication Artículo científico (JournalArticle)

The Probabilistic Pickup-and-Delivery Travelling Salesman Problem

  • Benavent, Enrique
  • Landete, Mercedes
  • Salazar González, Juan José
  • Tirado Domínguez, Gregorio
Transportation problems are essential in commercial logistics and have been widely studied in the litera- ture during the last decades. Many of them consist in designing routes for vehicles to move commodities between locations. This article approaches a pickup-and-delivery single-vehicle routing problem where there is susceptibility to uncertainty in customer requests. The probability distributions of the requests are assumed to be known, and the objective is to design an a priori route with minimum expected length. The problem has already been approached in the literature, but through a heuristic method. This article proposes the first exact approach to the problem. Two mathematical formulations are proposed: one is a compact model (i.e. defined by a polynomial number of variables and constraints); the other one contains an exponential number of inequalities and is solved within a branch-and-cut framework. Computational results show the upsides as well as the breakdowns of both formulations.