Title

Decomposition-Based Exact Algorithms For Risk-Constrained Traveling Salesman Problems With Discrete Random Arc Costs

Keywords

Benders decomposition; Conditional value at risk; Reliable routing; Traveling salesman problem

Abstract

Recently increasing attentions have been given to uncertainty handling in network optimization research. Along this trend, this paper discusses traveling salesman problem with discrete random arc costs while incorporating risk constraints. Minimizing expected total cost might not be enough because total costs of some realizations of the random arc costs might exceed the resource limit. To this respect, this paper presents a model of the traveling salesman problem that incorporates risk constraints based on Conditional Value at Risk to evaluate those worst-cost scenarios. Exact solution methods are developed and applied on the risk-constrained traveling salesman problem. Numerical experiments are conducted, and the results show the ability of the proposed methods in reducing the computational complexity.

Publication Date

9-23-2014

Publication Title

Optimization Letters

Volume

9

Issue

8

Number of Pages

1553-1568

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s11590-014-0798-7

Socpus ID

84947021282 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84947021282

This document is currently not available here.

Share

COinS