Optimization Online


A Cutting Plane Method for Risk-constrained Traveling Salesman Problem with Random Arc Costs

Zhouchun Huang(zhouchun.huang***at***knights.ucf.edu)
Qipeng Zheng(qipeng.zheng***at***ucf.edu)
Tao Zhang(taozhang***at***mail.shufe.edu.cn)
Vladimir Boginski(Vladimir.Boginski***at***ucf.edu)

Abstract: This paper considers the risk-constrained stochastic traveling salesman problem with random arc costs. In the context of stochastic arc costs, the deterministic traveling salesman problem's optimal solutions would be ineffective because the selected route might be exposed to a greater risk where the actual cost can exceed the resource limit in extreme scenarios. We present a stochastic model of the traveling salesman problem that incorporates risk management. Value at Risk and Conditional Value at Risk are respectively applied to measure and control the risk experiencing overly costly scenarios. We propose a novel cutting plane method to find the minimum-cost route in the stochastic environment while the risk level of the route is controlled by bounding the risk measures. Computational experiments are conducted to demonstrate the properties of the proposed models and the performance of the proposed cutting plan algorithm.

Keywords: Traveling Salesman Problem; Random; VaR; CVaR; Normal Distribution; Cutting Planes; Risk Constraints

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Applications -- OR and Management Sciences (Transportation )

Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 10/11/2015
Entry Accepted: 10/11/2015
Entry Last Modified: 10/11/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society