1 September 2022 in IEEE Transactions on Neural Networks and Learning Systems
Recent studies in using deep learning (DL) to solve routing problems focus on construction heuristics, whose solutions are still far from optimality. Improvement heuristics have great potential to narrow this gap by iteratively refining a solution. However, classic improvement heuristics are all guided by handcrafted rules that may limit their performance. In this article, we propose a deep reinforcement learning framework to learn the improvement heuristics for routing problems. We design a self-attention-based deep architecture as the policy network to guide the selection of the next solution. We apply our method to two important routing problems, i.e., the traveling salesman problem (TSP) and the capacitated vehicle routing problem (CVRP). Experiments show that our method outperforms state-of-the-art DL-based approaches. The learned policies are more effective than the traditional handcrafted ones and can be further enhanced by simple diversifying strategies. Moreover, the policies generalize well to different problem sizes, initial solutions, and even real-world data set.
1 December 2003 in European Journal of Operational Research
1 January 2002 in SIAM Journal on Control and Optimization
This paper is concerned with mean-variance portfolio selection problems in continuous-time under the constraint that short-selling of stocks is prohibited. The problem is formulated as a stochastic optimal linear-quadratic (LQ) control problem. However, this LQ problem is not a conventional one in that the control (portfolio) is constrained to take nonnegative values due to the no-shorting restriction, and thereby the usual Riccati equation approach (involving a "completion of squares") does not apply directly. In addition, the corresponding Hamilton--Jacobi--Bellman (HJB) equation inherently has no smooth solution. To tackle these difficulties, a continuous function is constructed via two Riccati equations, and then it is shown that this function is a viscosity solution to the HJB equation. Solving these Riccati equations enables one to explicitly obtain the efficient frontier and efficient investment strategies for the original mean-variance problem. An example illustrating these results is also presented.
1 September 2011 in Transportation Research Part B: Methodological
1 March 1998 in Operations Research Letters
1 February 2002 in Mathematics of Operations Research
This paper concerns the continuous-time, mean-variance portfolio selection problem in a complete market with random interest rate, appreciation rates, and volatility coef.cients. The problem is tackled using the results of stochastic linear-quadratic (LQ) optimal control and backward stochastic differential equations (BSDEs), two theories that have been extensively studied and developed in recent years. Specifically, the mean-variance problem is formulated as a linearly constrained stochastic LQ control problem. Solvability of this LQ problem is reduced, in turn, to proving global solvability of a stochastic Riccati equation. The proof of existence and uniqueness of this Riccati equation, which is a fully nonlinear and singular BSDE with random coefficients, is interesting in its own right and relies heavily on the structural properties of the equation. Efficient investment strategies as well as the mean-variance efficient frontier are then analytically derived in terms of the solution of this equation. In particular, it is demonstrated that the efficient frontier in the mean-standard deviation diagram is still a straight line or, equivalently, risk-free investment is still possible, even when the interest rate is random. Finally, a version of the Mutual Fund Theorem is presented.