原文传递
有先后顺序限制或时间窗口限制的线性往返问题研究
| 论文题名： | 有先后顺序限制或时间窗口限制的线性往返问题研究 |
| 关键词： | 序限制;时间窗口;线性;集装箱货场;服务时间;蚁群算法;直线上;证明;问题描述;实验设计;求解;节点;集装箱港口;访问时间;动态规划;泊位;拖车;排列;模型;搬运 |
| 摘要： | 在集装箱港口,泊位沿直线分布,到达的船只停泊在泊位处等待港口机械的服务。由于各种运输工具的载重量不同,所以到达港口的集装箱必须在集装箱货场堆放,以便按时装卸。在货场上,各集装箱货堆在货场上排列成网格状,前后左右留有拖车运行通道。由于外部集装箱到达时间的不确定性,所以集装箱无序的摆放在指定的货堆中。负责集装箱提取和摆放的卡吊在货堆内沿既定轨道来回直线移动,按照要求顺序进行提货。负责托运的拖车在通道内来回搬运集装箱,为了避免货场上交通拥挤,拖车在货堆内沿直线进行搬运。而对于港口泊位中的船只来说,当未到服务时间时,只能在泊水区等候命令,直到到达规定的服务时间时,才能入港接受服务。 有先后顺序限制的线性往返问题描述的是对于货场上集装箱,为了减少集装箱在船上的倒垛和搬运过程,所以在集装箱提取时,要按照一定的顺序对其进行提取。其模型可以描述为,对于排列在一条直线上的节点,存在着先后访问顺序的限制,目的是去寻找一条最优访问顺序,使所走过的路径最短。在本论文中,我们讨论了存在单一先后约束的情况和多个约束的情况。对于单一约束的有先后顺序限制的线性往返问题,我们提出了其拥有的优化性质,在此基础上给出了快速有效的求解算法。对于有多个约束的有先后顺序限制的线性往返问题,我们证明此类问题是多项式时间内可解的,而且我们证明了其具有动态规划的性质,可以利用动态规划进行求解。 有时间窗口限制的线性往返问题描述的是泊位上集装箱船服务的情况,其模型可以描述为,对于排列在一条直线上的节点,存在着访问时间的限制。每个节点存在着最早开始访问时间、最迟结束时间以及服务时间。对于有时间窗口限制的线性往返问题,我们首先证明它是NP-hard问题。在此基础上,我们建立了有时间窗口限制的线性往返问题的数学模型,并给出它的数据实验设计。在数据实验设计中,节点的服务时间窗口分为固定的服务时间窗口和随机的服务窗口。为了证明算法的有效,我们把其结果和CPLEX的标准结果进行对比。对于固定的时间窗口,我们提出一种启发式的排序算法进行求解,并且对于是否存在可行解,我们给出了数学证明;而对于可变时间窗口,我们利用蚁群算法进行求解,并且根据问题的具体特性,对蚁群算法进行了改进,提高算法的收敛速度。 |
| 作者： | 顾延德 |
| 专业： | 管理科学与工程 |
| 导师： | 石凤波 |
| 授予学位： | 硕士 |
| 授予学位单位： | 中山大学 |
| 学位年度： | 2009 |
| 正文语种： | 中文 |
检索历史
应用推荐
