| 高文文,魏晨,胡志华.堆垛约束下基于偏序的路径优化时间窗松弛方法[J].,2019,59(4):393-399 |
| 堆垛约束下基于偏序的路径优化时间窗松弛方法 |
| Partial-order-based relaxation of time windows in routing optimization with stacking constraints |
| |
| DOI：10.7511/dllgxb201904010 |
| 中文关键词: 车辆路径优化问题 时间窗约束 偏序关系 分支定界算法 集装箱码头 |
| 英文关键词: vehicle routing problem time window constraints partial order relationship branch and bound algorithm container terminal |
| 基金项目:国家自然科学基金资助项目(7187113671471109)；上海市科学技术委员会重点项目(16040501800). |
|
| 摘要点击次数: 575 |
| 全文下载次数: 427 |
| 中文摘要: |
| 在求解车辆路径优化问题时，通常使用时间窗对任务之间的偏序关系进行建模，设计带时间窗约束的路径优化模型与算法，然而时间窗约束与偏序约束是不等价的．在集装箱码头堆垛作业背景下，针对时间窗约束的路径优化模型，提出将时间窗约束转化为偏序约束的松弛方法，并据此设计偏序约束的路径优化模型．在分支定界算法框架下，研究时间窗约束与偏序约束之间的关系，对两种模型的特征进行分析．采用Solomon数据集进行数值分析，验证两个模型在寻优能力与性能之间的差异．结果表明，偏序模型具有更好的优化性能，但是时间窗模型具有更好的计算时间性能，通过时间窗紧缩的特征分析发现基于时间窗分解设计偏序模型求解算法是新的研究方向． |
| 英文摘要: |
| In solving vehicle routing problems, time windows are often used to formulate the partial order relationships between tasks, and the routing optimization model and related algorithm with time window constraints are designed. However, time window constraint and partial order constraint are not equivalent. In the context of stacking operations in container terminals, a relaxation method is proposed to translate time window constraints into partial order constraints and a routing optimization model with partial order constraints is built based on the routing optimization model with time window constraints. Under the framework of branch and bound algorithm, the relationship between time window constraints and partial order constraints is studied and the features of two models are analyzed. Solomon datasets are used to do numerical analysis and the difference in the optimization ability of two models is examined. The results show that the partial-order-based model can be solved with better optimality, while the time-window-based model can be solved in a shorter time. Moreover, after analyzing the effects of narrowing the time windows, a new research direction is found to develop improved algorithms for partial-order-based model based on time-window-based decomposition method. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |