Solving the travelling salesman problem with Time Windows by Lagrangean Relaxation

R. Herrero; J. J. Ramos; D. Guimarans

Solving the travelling salesman problem with Time Windows by Lagrangean Relaxation

R. Herrero, J. J. Ramos, D. Guimarans

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

Abstract

This article presents a Lagrangean Relaxation-based methodology to solve the Travelling Salesman Problem with Time Windows. The Lagrangean function exploits the structure of the problem. The proposed method, which elaborates on the Subgradient Optimization, presents a simple heuristics aimed to improve algorithm's convergence on the optimal solution. Furthermore, if the optimal solution is not found in a reasonable number of iterations, this method is able to provide a feasible solution while guaranteeing a tight gap between the primal and the optimal cost.

Original language	English
Title of host publication	21st European Modeling and Simulation Symposium, EMSS 2009
Publisher	Curran Associates, Inc.
Number of pages	6
Publication status	Published - 2009
Externally published	Yes
Event	European Modeling and Simulation Symposium 2009 - Puerto de la Cruz, Spain Duration: 23 Sept 2009 → 25 Sept 2009 Conference number: 21st

Conference

Conference	European Modeling and Simulation Symposium 2009
Abbreviated title	EMSS 2009
Country/Territory	Spain
City	Puerto de la Cruz
Period	23/09/09 → 25/09/09

Keywords

Lagrangean Relaxation
Subgradient Optimization
Time Windows
Travelling Salesman Problem

Cite this

@inproceedings{dea5c2b4074b4f9ba7f4142813aaff4b,

title = "Solving the travelling salesman problem with Time Windows by Lagrangean Relaxation",

abstract = "This article presents a Lagrangean Relaxation-based methodology to solve the Travelling Salesman Problem with Time Windows. The Lagrangean function exploits the structure of the problem. The proposed method, which elaborates on the Subgradient Optimization, presents a simple heuristics aimed to improve algorithm's convergence on the optimal solution. Furthermore, if the optimal solution is not found in a reasonable number of iterations, this method is able to provide a feasible solution while guaranteeing a tight gap between the primal and the optimal cost.",

keywords = "Lagrangean Relaxation, Subgradient Optimization, Time Windows, Travelling Salesman Problem",

author = "R. Herrero and Ramos, {J. J.} and D. Guimarans",

year = "2009",

language = "English",

booktitle = "21st European Modeling and Simulation Symposium, EMSS 2009",

publisher = "Curran Associates, Inc.",

note = "European Modeling and Simulation Symposium 2009, EMSS 2009 ; Conference date: 23-09-2009 Through 25-09-2009",

}

TY - GEN

T1 - Solving the travelling salesman problem with Time Windows by Lagrangean Relaxation

AU - Herrero, R.

AU - Ramos, J. J.

AU - Guimarans, D.

N1 - Conference code: 21st

PY - 2009

Y1 - 2009

N2 - This article presents a Lagrangean Relaxation-based methodology to solve the Travelling Salesman Problem with Time Windows. The Lagrangean function exploits the structure of the problem. The proposed method, which elaborates on the Subgradient Optimization, presents a simple heuristics aimed to improve algorithm's convergence on the optimal solution. Furthermore, if the optimal solution is not found in a reasonable number of iterations, this method is able to provide a feasible solution while guaranteeing a tight gap between the primal and the optimal cost.

AB - This article presents a Lagrangean Relaxation-based methodology to solve the Travelling Salesman Problem with Time Windows. The Lagrangean function exploits the structure of the problem. The proposed method, which elaborates on the Subgradient Optimization, presents a simple heuristics aimed to improve algorithm's convergence on the optimal solution. Furthermore, if the optimal solution is not found in a reasonable number of iterations, this method is able to provide a feasible solution while guaranteeing a tight gap between the primal and the optimal cost.

KW - Lagrangean Relaxation

KW - Subgradient Optimization

KW - Time Windows

KW - Travelling Salesman Problem

UR - http://www.scopus.com/inward/record.url?scp=84874166349&partnerID=8YFLogxK

M3 - Conference Paper

AN - SCOPUS:84874166349

BT - 21st European Modeling and Simulation Symposium, EMSS 2009

PB - Curran Associates, Inc.

T2 - European Modeling and Simulation Symposium 2009

Y2 - 23 September 2009 through 25 September 2009

ER -

Solving the travelling salesman problem with Time Windows by Lagrangean Relaxation

Abstract

Conference

Keywords

Other files and links

Cite this