A new formulation for the Traveling Deliveryman Problem

Mostrar todas las versiones(3)

The Traveling Deliveryman Problem is a generalization of the Minimum Cost Hamiltonian Path Problem where the starting vertex of the path, i.e. a depot vertex, is fixed in advance and the cost associated with a Hamiltonian path equals the sum of the costs for the layers of paths (along the Hamiltonia...

Descripción completa

Detalles Bibliográficos
Autores principales: Méndez-Díaz, I., Zabala, P., Lucena, A.
Formato: Artículo publishedVersion
Publicado: 2008
Materias:
Branch-and-cut algorithms
Integer programming
Traveling deliveryman problem
Dynamic programming
Hamiltonians
Linearization
Meats
Particle size analysis
Branch-and-Bound
Computational results
Convex hulls
Cutting plane algorithms
Enumeration trees
Feasible solutions
Hamiltonian path problems
Hamiltonian paths
Integer programming formulations
Linear programming relaxations
Minimum costs
Valid inequalities
Linear programming
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0166218X_v156_n17_p3223_MendezDiaz
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v156_n17_p3223_MendezDiaz_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-paper_0166218X_v156_n17_p3223_MendezDiaz_oai
record_format dspace
spelling I28-R145-paper_0166218X_v156_n17_p3223_MendezDiaz_oai2024-08-16 Méndez-Díaz, I. Zabala, P. Lucena, A. 2008 The Traveling Deliveryman Problem is a generalization of the Minimum Cost Hamiltonian Path Problem where the starting vertex of the path, i.e. a depot vertex, is fixed in advance and the cost associated with a Hamiltonian path equals the sum of the costs for the layers of paths (along the Hamiltonian path) going from the depot vertex to each of the remaining vertices. In this paper, we propose a new Integer Programming formulation for the problem and computationally evaluate the strength of its Linear Programming relaxation. Computational results are also presented for a cutting plane algorithm that uses a number of valid inequalities associated with the proposed formulation. Some of these inequalities are shown to be facet defining for the convex hull of feasible solutions to that formulation. These inequalities proved very effective when used to reinforce Linear Programming relaxation bounds, at the nodes of a Branch and Bound enumeration tree. © 2008 Elsevier B.V. All rights reserved. Fil:Méndez-Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Zabala, P. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf http://hdl.handle.net/20.500.12110/paper_0166218X_v156_n17_p3223_MendezDiaz info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Discrete Appl Math 2008;156(17):3223-3237 Branch-and-cut algorithms Integer programming Traveling deliveryman problem Dynamic programming Hamiltonians Integer programming Linearization Meats Particle size analysis Branch-and-Bound Branch-and-cut algorithms Computational results Convex hulls Cutting plane algorithms Enumeration trees Feasible solutions Hamiltonian path problems Hamiltonian paths Integer programming formulations Linear programming relaxations Minimum costs Traveling deliveryman problem Valid inequalities Linear programming A new formulation for the Traveling Deliveryman Problem info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v156_n17_p3223_MendezDiaz_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
topic Branch-and-cut algorithms
Integer programming
Traveling deliveryman problem
Dynamic programming
Hamiltonians
Integer programming
Linearization
Meats
Particle size analysis
Branch-and-Bound
Branch-and-cut algorithms
Computational results
Convex hulls
Cutting plane algorithms
Enumeration trees
Feasible solutions
Hamiltonian path problems
Hamiltonian paths
Integer programming formulations
Linear programming relaxations
Minimum costs
Traveling deliveryman problem
Valid inequalities
Linear programming
spellingShingle Branch-and-cut algorithms
Integer programming
Traveling deliveryman problem
Dynamic programming
Hamiltonians
Integer programming
Linearization
Meats
Particle size analysis
Branch-and-Bound
Branch-and-cut algorithms
Computational results
Convex hulls
Cutting plane algorithms
Enumeration trees
Feasible solutions
Hamiltonian path problems
Hamiltonian paths
Integer programming formulations
Linear programming relaxations
Minimum costs
Traveling deliveryman problem
Valid inequalities
Linear programming
Méndez-Díaz, I.
Zabala, P.
Lucena, A.
A new formulation for the Traveling Deliveryman Problem
topic_facet Branch-and-cut algorithms
Integer programming
Traveling deliveryman problem
Dynamic programming
Hamiltonians
Integer programming
Linearization
Meats
Particle size analysis
Branch-and-Bound
Branch-and-cut algorithms
Computational results
Convex hulls
Cutting plane algorithms
Enumeration trees
Feasible solutions
Hamiltonian path problems
Hamiltonian paths
Integer programming formulations
Linear programming relaxations
Minimum costs
Traveling deliveryman problem
Valid inequalities
Linear programming
description The Traveling Deliveryman Problem is a generalization of the Minimum Cost Hamiltonian Path Problem where the starting vertex of the path, i.e. a depot vertex, is fixed in advance and the cost associated with a Hamiltonian path equals the sum of the costs for the layers of paths (along the Hamiltonian path) going from the depot vertex to each of the remaining vertices. In this paper, we propose a new Integer Programming formulation for the problem and computationally evaluate the strength of its Linear Programming relaxation. Computational results are also presented for a cutting plane algorithm that uses a number of valid inequalities associated with the proposed formulation. Some of these inequalities are shown to be facet defining for the convex hull of feasible solutions to that formulation. These inequalities proved very effective when used to reinforce Linear Programming relaxation bounds, at the nodes of a Branch and Bound enumeration tree. © 2008 Elsevier B.V. All rights reserved.
format Artículo
Artículo
publishedVersion
author Méndez-Díaz, I.
Zabala, P.
Lucena, A.
author_facet Méndez-Díaz, I.
Zabala, P.
Lucena, A.
author_sort Méndez-Díaz, I.
title A new formulation for the Traveling Deliveryman Problem
title_short A new formulation for the Traveling Deliveryman Problem
title_full A new formulation for the Traveling Deliveryman Problem
title_fullStr A new formulation for the Traveling Deliveryman Problem
title_full_unstemmed A new formulation for the Traveling Deliveryman Problem
title_sort new formulation for the traveling deliveryman problem
publishDate 2008
url http://hdl.handle.net/20.500.12110/paper_0166218X_v156_n17_p3223_MendezDiaz
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v156_n17_p3223_MendezDiaz_oai
work_keys_str_mv AT mendezdiazi anewformulationforthetravelingdeliverymanproblem
AT zabalap anewformulationforthetravelingdeliverymanproblem
AT lucenaa anewformulationforthetravelingdeliverymanproblem
AT mendezdiazi newformulationforthetravelingdeliverymanproblem
AT zabalap newformulationforthetravelingdeliverymanproblem
AT lucenaa newformulationforthetravelingdeliverymanproblem
_version_ 1809356811359223808

Ejemplares similares