A dynamic-pricing label-setting algorithm for solving the elementary resource constrained shortest path problem

The resource constrained elementary shortest-path problem is a problem used for solving vehicle-routing, production-scheduling and crew-scheduling applications. It occurs as a sub-problem used to implicitly generate the set of all feasible columns in a column-generation solution algorithm. In the pr...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Vitale, Ignacio, Dondo, Rodolfo
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2020
Materias:
Ciencias Informáticas
Resource constrained shortest path
Label setting
Column generation
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/116727
http://49jaiio.sadio.org.ar/pdfs/siiio/SIIIO-01.pdf
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-116727
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Resource constrained shortest path
Label setting
Column generation
spellingShingle Ciencias Informáticas
Resource constrained shortest path
Label setting
Column generation
Vitale, Ignacio
Dondo, Rodolfo
A dynamic-pricing label-setting algorithm for solving the elementary resource constrained shortest path problem
topic_facet Ciencias Informáticas
Resource constrained shortest path
Label setting
Column generation
description The resource constrained elementary shortest-path problem is a problem used for solving vehicle-routing, production-scheduling and crew-scheduling applications. It occurs as a sub-problem used to implicitly generate the set of all feasible columns in a column-generation solution algorithm. In the problem there is a directed graph with a source node and a destination node, and each arc has a cost and a vector of weights specifying its requirements of resources. A minimum-cost source to destination directed path is sought such that the total consumption of resources does not exceed the resources vehicle-capacity. The problem is NP-hard in the strong sense. We propose a new label-setting heuristic algorithm based on the dynamic update of resources and prices vectors according the partial label-path and embed it into a column generation algorithm to solve some testing problems. Later we perform some numerical experiments in order to study its computational efficiency.
format Objeto de conferencia
Objeto de conferencia
author Vitale, Ignacio
Dondo, Rodolfo
author_facet Vitale, Ignacio
Dondo, Rodolfo
author_sort Vitale, Ignacio
title A dynamic-pricing label-setting algorithm for solving the elementary resource constrained shortest path problem
title_short A dynamic-pricing label-setting algorithm for solving the elementary resource constrained shortest path problem
title_full A dynamic-pricing label-setting algorithm for solving the elementary resource constrained shortest path problem
title_fullStr A dynamic-pricing label-setting algorithm for solving the elementary resource constrained shortest path problem
title_full_unstemmed A dynamic-pricing label-setting algorithm for solving the elementary resource constrained shortest path problem
title_sort dynamic-pricing label-setting algorithm for solving the elementary resource constrained shortest path problem
publishDate 2020
url http://sedici.unlp.edu.ar/handle/10915/116727
http://49jaiio.sadio.org.ar/pdfs/siiio/SIIIO-01.pdf
work_keys_str_mv AT vitaleignacio adynamicpricinglabelsettingalgorithmforsolvingtheelementaryresourceconstrainedshortestpathproblem
AT dondorodolfo adynamicpricinglabelsettingalgorithmforsolvingtheelementaryresourceconstrainedshortestpathproblem
AT vitaleignacio dynamicpricinglabelsettingalgorithmforsolvingtheelementaryresourceconstrainedshortestpathproblem
AT dondorodolfo dynamicpricinglabelsettingalgorithmforsolvingtheelementaryresourceconstrainedshortestpathproblem
bdutipo_str Repositorios
_version_ 1764820446391304195

Ejemplares similares