In this paper, we introduce the asymmetric probabilistic minimum-cost Hamiltonian cycle problem (APMCHCP) where arcs and vertices in the graph are possible to fail. APMCHCP is a generalization of traditional asymmetric minimum-cost Hamiltonian cycle problem, and it has applications in many emerging areas, such as post-disaster recovery, electronic circuit design, and security maintenance of wireless sensor networks. For each vertex, we define a chance-constraint to guarantee that the probability of arriving at the vertex must be greater than or equal to a given threshold. Four mixed-integer programming (MIP) formulations are proposed for modeling the problem, including two direct formulations and two recursive formulations. A combinatorial branch-and-bound (CBB) algorithm is proposed for solving the APMCHCP, where data preprocessing steps, feasibility rules, and approaches of finding upper and lower bounds are developed. In the numerical experiments, the CBB algorithm is compared with a commercial MIP solver (Gurobi 8.0) on a test-bed of two popular benchmark instance sets. The results show that the proposed CBB algorithm significantly outperforms Gurobi solver in terms of both the size of optimally solved instances and the computing time.
展开▼
