基于实际路网情境的配送车辆调度优化

在实际路网情境下结合车道数、车道宽度、路口信号灯设置等路网物理特性,构建了考虑综合交通阻抗的多车型车辆调度模型,提出了两阶段求解策略:第1阶段设计了改进A-star精确解算法用于计算客户时间距离矩阵;第2阶段针对实际路网的特征设计了混合模拟退火算法求解调度方案。以大连市某配送中心运营实例进行路网情境仿真试验,结果表明:改进A-star算法较改进Dijkstra算法具有更短的路径搜索时间;混合模拟退火算法求解结果较实际调度方案优化了13.1% 的综合成本;路网增流、区域拥堵和路段禁行三类路网情境均能对配送方案的车辆配置、路径选择、客户服务次序、作业时间和违约费用等5方面内容产生干扰,调度计划的制定需要详细考虑这些因素的变化。     

带时间窗取送货问题的混合算法

为解决带时间窗的取送货问题,建立了集合划分模型,设计列生成算法与启发式规则相结合的CGA混合算法进行求解。首先,放松约束构建主问题及受限主问题,运用单纯形法与分支定界进行求解;其次,建立时空网络以构建子问题,基于修正的Dijkstra's算法,设计包含算法A、B1、B2的求解算法;最后,通过启发式算法解决节点重复覆盖问题。为验证算法有效性,进一步构建了OPT近似最优解算法;并基于CGA提出三种求解策略C1、C2、C3,做单因素方差分析,采用算例分析算法的性能。实验结果表明,对于客户点数量小于30的小规模算例,CGA与OPT所得结果相近,但CGA求解效率更显著;针对客户点数量为600的大规模算例,CGA至多在20分钟内求得结果,可见本文算法的精度和效率较高。而针对不同类型及规模的客户点的单因素方差分析结果显示,C1、C2、C3在“平均行驶距离成本”、“平均车辆数”、“平均求解时间”三个维度上差异性显著,经营者可根据实际需求进行策略选择。     

基于两阶段混合动态规划算法的龙门吊路径优化

产业界已出现利用多台轨道式龙门吊同时作业以提升集装箱码头装船效率的情况,由于需要确定每台龙门吊的取箱作业集合以及增加了“避免碰撞”、“顺次移动”等现实约束,故其移动路径规划问题在模型建立与求解上比单台轨道式龙门吊更为复杂。本文针对两台轨道式龙门吊同时作业的情形,建立了龙门吊移动路径网络模型,并开发了基于贪婪算法与动态规划的两阶段混合算法,并通过仿真算例,借助与基于实际调度规则所得到的调度方案的对比,验证了模型及优化算法的有效性与实用性。     

考虑多阶段共用平行机特征的拖轮作业模式优化

在对拖轮调度问题进行分析的基础之上,将拖轮调度问题归结为一类具有多阶段共用平行机器特征的多处理器任务调度问题。建立了考虑靠泊与停泊两阶段、考虑切换时间的拖轮调度优化模型,并设计了启发式规则与模拟退火相结合的混合算法(HSA)求解该模型。通过运用所设计算法求解仿真算例,并将其结果与三种基于现行调度规则的调度方案进行比较,验证了模型与算法的高效性。基于此,对不同拖轮数量状态下的调度研究结果显示,拖轮总作业时间与平均单艘拖轮作业时间二者存在着一定的矛盾性;并指出采用拖轮适时返回停泊基地的作业模式,可有效地降低拖轮作业时间,进而提高有限拖轮资源的利用率,实现节能减排、绿色运输。     

考虑空重箱转换的港口集装箱甩挂运输问题研究

针对港口堆场与内陆腹地客户之间的空重集装箱运输问题,本文结合甩挂运输的特点将客户的进出港需求拆分为相互关联的空箱和重箱任务,实现单个决策期内运输系统中集装箱的状态转换与回收工作。状态转换受集装箱货物装卸时间影响,因此需要合理调度牵引车路线,以满足前置任务约束。针对此类问题的特点,本文建立了空重箱运输任务整合的整数规划模型,并设计了基于集群选择的改进蚁群算法进行求解。最后,通过不同规模的仿真算例与现有数学模型及优化算法对比结果可知,本文所提出的改进蚁群算法在此类问题的最优解搜索中具有良好的稳定性和求解效率。