软时间窗与随机航行时间的不定期船舶航线规划

丁一; 仲颖; 林国龙; 温馨

doi:10.19603/j.cnki.1000-1190.2015.03.011

华中师范大学学报（自然科学版） ›› 2015, Vol. 49 ›› Issue (03) : 387 -391. DOI: 10.19603/j.cnki.1000-1190.2015.03.011

软时间窗与随机航行时间的不定期船舶航线规划

丁一, 仲颖, 林国龙, 温馨

作者信息 +

Author information +

文章历史 +

摘要

为优化航线设计,降低船舶企业运营成本,在研究VRP(Vehicle Routing Problem)的基础上,将其方法扩展应用到不定期船舶调度问题,船舶运输需要在路径优化时同时考虑不确定航行时间及需求时间窗,用线性近似的方法来消除不确定航行时间的影响,通过惩罚函数的引入表示需求时间窗,建立充分考虑时间因素的数学模型,以总成本最小为目标.运用扫描法和禁忌搜索算法,将问题分为二个阶段,第一阶段,通过扫描法将VRP转化为TSP(Traveling Salesman Problem),然后用禁忌搜索算法解决TSP,通过算例证明了提出算法的有效性,为实际不定期船舶的航线规划提供了参考.