伴随全球物流一体化的进程的加快和船舶大型化的迅猛发展,支线运输网络必将蓬勃发展。在支线船舶运输中,船舶的调配和航线的设计是影响航运企业效益的重要因素,也是节约社会物流成本的关键途径。然而,迄今为止,这类工作一般都是靠投资经营者的个人经验和主观判断力去完成,现有的为数不多的优化模型,在支线运输中港口数目达到几十个时,其实际应用性也十分有限。 本文在研究车辆调度问题(VRP)的基本理论和研究方法的基础上,根据船舶支线运输调度的实际情况,设计了支线船舶调度问题(FSRP)的混合整数规划模型。本文所研究设计的支线船舶调度问题模型与传统的VRP、VRPB、VRPPD以及VRPTW都有所不同。在支线船舶运输中,既有送货又有取货,且二者有时同时进行;不存在VRPB中关于送货优先的约束,也没有类似VRPPD中对于装卸顺序的约束,因为在喂给港所装上的货物都要送回枢纽港,船舶在出发和返回枢纽港时一般均为重载。传统的VRPTW中,时间窗的约束仅仅针对于顾客而言,配送中心不存在时间窗约束,但在FSRP模型中,由于配送中心是干线运输的挂靠港口,因此对枢纽港的时间窗也是有要求的。 由于支线船舶调度问题属于NP—难题,本文在遗传算法的基础上,结合启发式算法和免疫遗传算法的思想,设计了一个新的免疫遗传算法。文章的最后使用VB程序对所提出的算法进行了编程计算,通过试验数据的计算,并与文献中其他算法结果的比较,进一步证明了本文所提出的模型和算法的可行性和高效率性,对合理设计支线运输航线和调配船舶、节约支线船舶运营成本具有重要重要意义。