|
| 堆垛约束下基于偏序的路径优化时间窗松弛方法 |
| Partial-order-based relaxation of time windows in routing optimization with stacking constraints |
| 投稿时间：2019-01-26 修订日期：2019-03-05 |
| DOI： |
| 中文关键词: 车辆路径优化问题,时间窗约束,偏序关系,分支定界算法,集装箱码头 |
| 英文关键词: vehicle routing problem, time window constraints, partial order relationship, branch and bound algorithm, container terminal |
| 基金项目:国家自然科学基金面上项目(71871136)；国家自然科学基金面上项目(71471109)；上海市科学技术委员会重点项目(16040501800) |
|
| 摘要点击次数: 300 |
| 全文下载次数: 0 |
| 中文摘要: |
| 车辆路径优化问题中,通常使用时间窗对任务之间的偏序关系进行建模,设计带时间窗约束的路径优化模型与算法求解,然而时间窗约束与偏序关系约束是不等价的。在集装箱码头堆垛作业背景下,针对时间窗约束的路径优化模型,提出将时间窗约束转化为偏序关系约束的松弛方法,并据此设计偏序关系约束的路径优化模型。在分支定界算法框架下,研究时间窗与偏序约束之间的关系,对两种模型的特征进行分析。实验环节采用Solomon数据集进行数值分析,验证两个模型在寻优能力与性能之间的差异。研究发现,偏序模型具有更好的优化性能,但是时间窗模型具有更好的计算时间性能,通过时间窗紧缩的特征分析发现基于时间窗分解设计偏序模型求解算法是新的研究方向。 |
| 英文摘要: |
| In vehicle routing problems, time windows are often used to formulate the partial order relationships between tasks, to design the optimization model and related algorithm with time window constraints. However, time window constraint and partial order constraint are not equivalent. In the context of stacking operations in container terminals, this work proposes a relaxation method to translate time window constraints into partial order constraints and builds a routing optimization model with partial order constraints. Under the framework of branch and bound algorithm, this paper studies the relationship between time window constraints and partial order constraints and analyses the features of two models. Solomon datasets are used to do numerical analysis and examine the difference in the optimization ability of two models. As new results, the partial-order-based model can be solved with better optimality, while the time-window-based mode can be solved in a shorter time. Moreover, after analyzing the effects of narrowing the time windows, it is a new research direction to develop improved algorithms for partial-order-based model based on time-window-based decomposition method. |
|
View Fulltext
查看/发表评论 下载PDF阅读器 |
| 关闭 |
|
|
|