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

第49卷第3期 华中师范大学学报(自然科学版) Vol，49No．3 2015年6月 J()URNAI，OFCENTRAI。CHINA NORMAI。UNIVERSITY(Nat．Sci．) Jun．2015 文章编号：1000—1l90(20lj)03—0387—05 软时问窗与随机航行时问的不定期船舶航线规划 丁 一。，仲 颖，林国龙，温 馨 (上海海事大学科学研究院，上海201306) 摘要：为优化航线设计，降低船舶企业运营成本，在研究VRP(VehicleProblem)的基础 Routing 上·将其方法扩展应用到不定期船舶调度问题。船舶运输需要在路径优化时同时考虑不确定航行 时间及需求时间窗。用线性近似的方法来消除不确定航行时间的影响，通过惩罚函数的引入表示 需求时间窗，建立充分考虑时间因素的数学模型，以总成本最小为目标．运用扫描法和禁忌有哪些信誉好的足球投注网站算 SalesmanProb 法，将问题分为二个阶段，第一阶段．通过扫描法将VRP转化为TSP(Traveling lem)，然后用禁忌有哪些信誉好的足球投注网站算法解决TSP，通过算例证明了提出算法的有效性，为实际不定期船舶的航 线规划提供了参考． 关键词：时间窗；随机航行时间；航线规划；扫描法；禁忌有哪些信誉好的足球投注网站算法 中图分类号：U697．1 文献标识码：A 一般将船舶运输模式分为3类，分别为工业船 次行程服务于多个需求点，再回到配送中心的．本 运、不定期船运和班轮船运一1．不定期船运输是指 文是在研究VRP问题一。‘。的基础上，将其方法扩展 无固定航线、固定挂靠港口和班期的一种船舶营运 应用到不定期船舶调度问题，船舶运输需要在路径 方式，在整个水路运输中占有相当高的比重． 优化时同时考虑不确定航行时问及需求时间窗，这 对于带时间窗的VRP的研究，Archetti-2一等两个因素的引入都会使得原本就是NP—Hard的 提出了第一个求解SDVRPTW(VehicleRoutingTSP问题更加复杂，用线性近似的方法来消除不 Problemswith DeliveriesandTimeWin— Split 确定航行时间的影响‘8，通过惩罚函数的引入表 dows)的精确算法，他们运用禁忌有哪些信誉好的足球投注网站算法和新的示需求时间窗．运用扫描法一9。和禁忌有哪些信誉好的足球投注网站算法， 有效不等式对子问题分别求解，一种新的启发式算 将问题分为二个阶段，第一阶段，通过扫描法将 法则被用于寻找最优拆分点． VRP转化为TSP，然后用禁忌有哪些信誉好的足球投注网站算法口叩解 Problemwith 对于VRPST(VehicleRouting 决TSP． StochasticTravel Time)的研究，Zheng和I．iu。n运 1问题描述和符号表示 用一种混合智能算法求解车辆模糊旅行时间 问题． 假设从港口i到港口j的航行时间，服从参数 综上所述，国内外关于运输路径优化的问题， 为(‰，盯j)的正态分布并且满足以下假设： 重点在于研究车辆路径问题，但是在国际贸易中， 1)物流配送中心的位置为已知且唯一，设置配 海上运输担负着将近90％的海上货运量，船舶航 送中心为0； 线规划问题与车辆路径问题相比较，有其自己的特