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

摘要： 良好的航线设计是船运公司降低运营成本，提高服务质量的关键。船舶运输中存在航行时间不确定，码头资源稀缺等特点，基于此将其航线问题抽象为考虑时间窗与随机旅行时间的多重流动旅行商问题。针对航行时间的随机性，设计了线性近似方法，提出了虚拟时间窗的概念，构建了初始模型与修正模型；给出了该问题的一个算例，验证了模型与算法的有效性和合理性。

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