关键词: 船运航线, 时间窗, 随机航行时间

Abstract: A good shipping routing planning is a key element for the shipping company to reduce its operation cost and improve its service quality. Considering there are two difficulties that uncertain travel time and scarcity of the resource in the docks, the shipping routing problem is abstracted to be a multiple Traveling Salesman Problem（TSP） with stochastic travel time and time window（m-TSPST） model. For the uncertain travel time, a linear approximate solution is designed, and the two-stage integer programing model and heuristic algorithm are built. At last, a numerical case is given to test the effectiveness of the model and algorithm.

Key words: shipping routing, time window, stochastic travel times